Bug 2273: Removed unbuilt third-party code. 42/12342/6
authorEd Warnicke <eaw@cisco.com>
Wed, 29 Oct 2014 19:20:56 +0000 (14:20 -0500)
committerEd Warnicke <eaw@cisco.com>
Thu, 13 Nov 2014 01:18:08 +0000 (01:18 +0000)
Change-Id: I0158a970b3ae65e6a0c49c93d96ab71928b25dd0
Signed-off-by: Ed Warnicke <eaw@cisco.com>
253 files changed:
pom.xml
third-party/commons/thirdparty/pom.xml [deleted file]
third-party/jersey-servlet/pom.xml [deleted file]
third-party/net.sf.jung2/pom.xml [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/StructurallyEquivalent.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/VertexPartition.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/BicomponentClusterer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/EdgeBetweennessClusterer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/VoltageClusterer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/WeakComponentClusterer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/EdgePredicateFilter.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/Filter.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/FilterUtils.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/VertexPredicateFilter.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/flows/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/EvolvingGraphGenerator.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/GraphGenerator.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/Lattice2DGenerator.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/BarabasiAlbertGenerator.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/EppsteinPowerLawGenerator.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/ErdosRenyiGenerator.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/KleinbergSmallWorldGenerator.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/MixedRandomGraphGenerator.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/AbstractRanker.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/BetweennessCentrality.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/KStepMarkov.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/Ranking.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/RelativeAuthorityRanker.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/WeightedNIPaths.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/AbstractLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/AggregateLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/BalloonLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/CircleLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/DAGLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/FRLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/FRLayout2.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/GraphElementAccessor.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/ISOMLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/KKLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/Layout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/LayoutDecorator.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/PolarPoint.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/RadialTreeLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/RadiusGraphElementAccessor.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/SpringLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/SpringLayout2.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/StaticLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/TreeLayout.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/util/RandomLocationTransformer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/util/Relaxer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/util/VisRunner.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/util/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/matrix/MatrixElementOperations.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/matrix/RealMatrixElementOperations.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/matrix/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/metrics/Metrics.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/metrics/StructuralHoles.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/metrics/TriadicCensus.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/metrics/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/AbstractIterativeScorer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/AbstractIterativeScorerWithPriors.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/BarycenterScorer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/BetweennessCentrality.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/ClosenessCentrality.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/DegreeScorer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/DistanceCentralityScorer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/EdgeScorer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/EigenvectorCentrality.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/HITS.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/HITSWithPriors.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/KStepMarkov.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/PageRank.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/PageRankWithPriors.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/VertexScorer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/VoltageScorer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/DelegateToEdgeTransformer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/ScoringUtils.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/UniformDegreeWeight.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/UniformInOut.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/VEPair.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/VertexScoreTransformer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/BFSDistanceLabeler.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/DijkstraDistance.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/DijkstraShortestPath.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/Distance.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/DistanceStatistics.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/MinimumSpanningForest.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/MinimumSpanningForest2.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/PrimMinimumSpanningTree.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/ShortestPath.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/ShortestPathUtils.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/UnweightedShortestPath.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/transformation/DirectionTransformer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/transformation/FoldingTransformer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/transformation/VertexPartitionCollapser.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/transformation/package.html [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/BasicMapEntry.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/ConstantMap.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/DiscreteDistribution.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/Indexer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/IterativeContext.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/IterativeProcess.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/KMeansClusterer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/MapBinaryHeap.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/MapSettableTransformer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/SelfLoopEdgePredicate.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/SettableTransformer.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/WeightedChoice.java [deleted file]
third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/package.html [deleted file]
third-party/openflowj/LICENSE [deleted file]
third-party/openflowj/Makefile [deleted file]
third-party/openflowj/README [deleted file]
third-party/openflowj/eclipse_codestyle.xml [deleted file]
third-party/openflowj/lib/commons-cli-1.2.jar [deleted file]
third-party/openflowj/lib/junit-4.8.1.jar [deleted file]
third-party/openflowj/pom.xml [deleted file]
third-party/openflowj/src/main/java/org/openflow/example/SelectListener.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/example/SelectLoop.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/example/SimpleController.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/example/cli/Option.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/example/cli/Options.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/example/cli/ParseException.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/example/cli/SimpleCLI.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/io/OFMessageAsyncStream.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/io/OFMessageInStream.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/io/OFMessageOutStream.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/Instantiable.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFBarrierReply.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFBarrierRequest.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFEchoReply.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFEchoRequest.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFError.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFFeaturesReply.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFFeaturesRequest.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFFlowMod.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFFlowRemoved.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFGetConfigReply.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFGetConfigRequest.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFHello.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFMatch.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFMatchBeanInfo.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFMessage.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFPacketIn.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFPacketOut.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFPhysicalPort.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFPort.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFPortMod.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFPortStatus.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFQueueConfigReply.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFQueueConfigRequest.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFSetConfig.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFStatisticsMessageBase.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFStatisticsReply.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFStatisticsRequest.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFSwitchConfig.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFType.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/OFVendor.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/ActionVendorOutputNextHop.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFAction.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionDataLayer.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionDataLayerDestination.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionDataLayerSource.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionEnqueue.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionNetworkLayerAddress.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionNetworkLayerDestination.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionNetworkLayerSource.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionNetworkTypeOfService.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionOutput.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionStripVirtualLan.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionTransportLayer.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionTransportLayerDestination.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionTransportLayerSource.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionType.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionVendor.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionVirtualLanIdentifier.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionVirtualLanPriorityCodePoint.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/factory/BasicFactory.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFActionFactory.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFActionFactoryAware.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFMessageFactory.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFMessageFactoryAware.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFQueuePropertyFactory.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFQueuePropertyFactoryAware.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFStatisticsFactory.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFStatisticsFactoryAware.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/queue/OFPacketQueue.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/queue/OFQueueProperty.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/queue/OFQueuePropertyMinRate.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/queue/OFQueuePropertyType.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFAggregateStatisticsReply.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFAggregateStatisticsRequest.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFDescriptionStatistics.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFFlowStatisticsReply.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFFlowStatisticsRequest.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFPortStatisticsReply.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFPortStatisticsRequest.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFQueueStatisticsReply.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFQueueStatisticsRequest.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFStatistics.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFStatisticsType.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFTableStatistics.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFVendorStatistics.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/util/HexString.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/util/LRULinkedHashMap.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/util/StringByteSerializer.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/util/U16.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/util/U32.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/util/U64.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/util/U8.java [deleted file]
third-party/openflowj/src/main/java/org/openflow/util/Unsigned.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/io/OFMessageAsyncStreamTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/BasicFactoryTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFActionTypeTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFBarrierReplyTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFBarrierRequestTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFErrorTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFFeaturesReplyTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFFlowRemovedTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFGetConfigReplyTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFGetConfigRequestTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFMatchTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFPortConfigTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFPortStatusTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFQueueConfigTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFSetConfigTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFStatisticsReplyTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFStatisticsRequestTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFStatisticsTypeTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFTypeTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/OFVendorTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/protocol/queue/OFQueuePropertyTypeTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/util/HexStringTest.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/util/OFTestCase.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/util/U16Test.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/util/U32Test.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/util/U64Test.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/util/U8Test.java [deleted file]
third-party/openflowj/src/test/java/org/openflow/util/UnsignedTest.java [deleted file]
third-party/org.apache.catalina.filters.CorsFilter/README [deleted file]
third-party/org.apache.catalina.filters.CorsFilter/pom.xml [deleted file]
third-party/org.apache.catalina.filters.CorsFilter/src/main/java/org/apache/catalina/filters/CorsFilter.java [deleted file]

diff --git a/pom.xml b/pom.xml
index d1e5494..bce3476 100644 (file)
--- a/pom.xml
+++ b/pom.xml
   <modules>
     <module>opendaylight/distribution/opendaylight</module>
 
-    <!-- third-parties uncomment them if you need snapshot version of it -->
-    <!-- <module>third-party/openflowj</module> -->
-    <!-- <module>third-party/net.sf.jung2</module> -->
-    <!-- <module>third-party/jersey-servlet</module> -->
-    <!-- <module>third-party/org.apache.catalina.filters.CorsFilter</module> -->
-
-    <module>third-party/commons/thirdparty</module>
-
     <!-- md-sal -->
     <module>opendaylight/md-sal</module>
     <!-- config -->
diff --git a/third-party/commons/thirdparty/pom.xml b/third-party/commons/thirdparty/pom.xml
deleted file mode 100644 (file)
index ad3c275..0000000
+++ /dev/null
@@ -1,230 +0,0 @@
-<?xml version="1.0" encoding="UTF-8"?>
-<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
-  <modelVersion>4.0.0</modelVersion>
-  <prerequisites>
-    <maven>3.0</maven>
-  </prerequisites>
-  <groupId>org.opendaylight.controller</groupId>
-  <artifactId>commons.thirdparty</artifactId>
-  <version>1.2.0-SNAPSHOT</version>
-  <packaging>pom</packaging>
-  <scm>
-    <connection>scm:git:ssh://git.opendaylight.org:29418/controller.git</connection>
-    <developerConnection>scm:git:ssh://git.opendaylight.org:29418/controller.git</developerConnection>
-    <url>https://wiki.opendaylight.org/view/OpenDaylight_Controller:Main</url>
-    <tag>HEAD</tag>
-  </scm>
-
-  <properties>
-    <sonar.host.url>https://sonar.opendaylight.org/</sonar.host.url>
-    <nexusproxy>http://nexus.opendaylight.org/content</nexusproxy>
-    <nexus.repository.release>opendaylight.release</nexus.repository.release>
-    <nexus.repository.snapshot>opendaylight.snapshot</nexus.repository.snapshot>
-    <sitedeploy>dav:http://nexus.opendaylight.org/content/sites/site</sitedeploy>
-    <siteplugin>3.2</siteplugin>
-    <projectinfo>2.6</projectinfo>
-    <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
-    <compiler.version>2.3.2</compiler.version>
-    <surefire.version>2.13</surefire.version>
-    <releaseplugin.version>2.3.2</releaseplugin.version>
-    <enforcer.version>1.3.1</enforcer.version>
-    <bundle.plugin.version>2.3.7</bundle.plugin.version>
-  </properties>
-
-  <pluginRepositories>
-    <pluginRepository>
-      <id>central2</id>
-      <name>central2</name>
-      <url>http://repo2.maven.org/maven2</url>
-    </pluginRepository>
-  </pluginRepositories>
-
-  <profiles>
-    <profile>
-      <id>fastreassembly</id>
-      <build>
-        <plugins>
-          <plugin>
-            <groupId>org.apache.maven.plugins</groupId>
-            <artifactId>maven-dependency-plugin</artifactId>
-            <version>2.4</version>
-            <executions>
-              <execution>
-                <id>copyfastreassembly</id>
-                <phase>install</phase>
-                <goals>
-                  <goal>copy</goal>
-                </goals>
-                <configuration>
-                  <artifactItems>
-                    <artifactItem>
-                      <groupId>${project.groupId}</groupId>
-                      <artifactId>${project.artifactId}</artifactId>
-                      <version>${project.version}</version>
-                      <destFileName>${project.groupId}.${project.artifactId}-${project.version}.jar</destFileName>
-                    </artifactItem>
-                  </artifactItems>
-                  <outputDirectory>${fastreassembly.directory}</outputDirectory>
-                </configuration>
-              </execution>
-            </executions>
-          </plugin>
-        </plugins>
-      </build>
-    </profile>
-  </profiles>
-
-  <build>
-    <plugins>
-      <plugin>
-        <groupId>com.googlecode.maven-java-formatter-plugin</groupId>
-        <artifactId>maven-java-formatter-plugin</artifactId>
-        <version>0.3.1</version>
-        <configuration>
-          <excludes>
-            <exclude>**/*</exclude>
-          </excludes>
-        </configuration>
-      </plugin>
-    </plugins>
-    <pluginManagement>
-      <plugins>
-        <plugin>
-          <groupId>org.apache.maven.plugins</groupId>
-          <artifactId>maven-release-plugin</artifactId>
-          <version>${releaseplugin.version}</version>
-        </plugin>
-        <plugin>
-          <groupId>org.apache.felix</groupId>
-          <artifactId>maven-bundle-plugin</artifactId>
-          <version>${bundle.plugin.version}</version>
-          <extensions>true</extensions>
-        </plugin>
-        <plugin>
-          <groupId>org.apache.maven.plugins</groupId>
-          <artifactId>maven-site-plugin</artifactId>
-          <version>${siteplugin}</version>
-          <configuration>
-            <reportPlugins>
-              <plugin>
-                <groupId>org.apache.maven.plugins</groupId>
-                <artifactId>maven-project-info-reports-plugin</artifactId>
-                <version>${projectinfo}</version>
-                <configuration>
-                  <dependencyDetailsEnabled>false</dependencyDetailsEnabled>
-                  <dependencyLocationsEnabled>false</dependencyLocationsEnabled>
-                </configuration>
-                <reports>
-                  <report>index</report>
-                  <report>project-team</report>
-                  <report>license</report>
-                  <report>mailing-list</report>
-                  <report>plugin-management</report>
-                  <report>cim</report>
-                  <report>issue-tracking</report>
-                  <report>scm</report>
-                  <report>summary</report>
-                </reports>
-              </plugin>
-              <plugin>
-                <groupId>org.apache.maven.plugins</groupId>
-                <artifactId>maven-checkstyle-plugin</artifactId>
-                <version>2.10</version>
-              </plugin>
-              <plugin>
-                <groupId>org.apache.maven.plugins</groupId>
-                <artifactId>maven-javadoc-plugin</artifactId>
-                <version>2.8.1</version>
-                <configuration>
-                  <doclet>org.jboss.apiviz.APIviz</doclet>
-                  <docletArtifact>
-                    <groupId>org.jboss.apiviz</groupId>
-                    <artifactId>apiviz</artifactId>
-                    <version>1.3.2.GA</version>
-                  </docletArtifact>
-                  <finalName>${project.artifactId}-${build.suffix}</finalName>
-                  <useStandardDocletOptions>true</useStandardDocletOptions>
-                  <charset>UTF-8</charset>
-                  <encoding>UTF-8</encoding>
-                  <docencoding>UTF-8</docencoding>
-                  <breakiterator>true</breakiterator>
-                  <version>true</version>
-                  <author>true</author>
-                  <keywords>true</keywords>
-                  <excludePackageNames>net.sf.jnetlib.*:cern.*:corejava</excludePackageNames>
-                </configuration>
-              </plugin>
-              <plugin>
-                <groupId>org.apache.maven.plugins</groupId>
-                <artifactId>maven-jxr-plugin</artifactId>
-                <version>2.3</version>
-                <configuration>
-                  <aggregate>true</aggregate>
-                  <linkJavadoc>true</linkJavadoc>
-                </configuration>
-              </plugin>
-            </reportPlugins>
-          </configuration>
-        </plugin>
-      </plugins>
-    </pluginManagement>
-  </build>
-
-  <repositories>
-    <repository>
-      <id>central2</id>
-      <name>central2</name>
-      <url>http://repo2.maven.org/maven2</url>
-      <snapshots>
-          <enabled>false</enabled>
-      </snapshots>
-      <releases>
-          <updatePolicy>never</updatePolicy>
-          <enabled>true</enabled>
-      </releases>
-    </repository>
-    <repository>
-      <id>central</id>
-      <name>central</name>
-      <url>http://repo1.maven.org/maven2</url>
-      <snapshots>
-           <enabled>false</enabled>
-      </snapshots>
-      <releases>
-          <updatePolicy>never</updatePolicy>
-          <enabled>true</enabled>
-      </releases>
-    </repository>
-    <!-- Third Packages hosted in local maven because not available in
-         other places -->
-    <repository>
-      <id>thirdparty</id>
-      <name>thirdparty</name>
-      <url>${nexusproxy}/repositories/thirdparty</url>
-      <snapshots>
-          <enabled>false</enabled>
-      </snapshots>
-      <releases>
-          <updatePolicy>never</updatePolicy>
-          <enabled>true</enabled>
-       </releases>
-    </repository>
-  </repositories>
-  <distributionManagement>
-    <!-- OpenDayLight Released artifact -->
-    <repository>
-      <id>opendaylight-release</id>
-      <url>${nexusproxy}/repositories/${nexus.repository.release}/</url>
-    </repository>
-    <!-- OpenDayLight Snapshot artifact -->
-    <snapshotRepository>
-      <id>opendaylight-snapshot</id>
-      <url>${nexusproxy}/repositories/${nexus.repository.snapshot}/</url>
-    </snapshotRepository>
-    <!-- Site deployment -->
-    <site>
-      <id>website</id>
-      <url>${sitedeploy}</url>
-    </site>
-  </distributionManagement>
-</project>
diff --git a/third-party/jersey-servlet/pom.xml b/third-party/jersey-servlet/pom.xml
deleted file mode 100644 (file)
index 27d503e..0000000
+++ /dev/null
@@ -1,90 +0,0 @@
-<?xml version="1.0" encoding="UTF-8"?>
-<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
-  <!-- Get some common settings for the project we are using it in -->
-  <parent>
-    <groupId>org.opendaylight.controller</groupId>
-    <artifactId>commons.thirdparty</artifactId>
-    <version>1.2.0-SNAPSHOT</version>
-    <relativePath>../commons/thirdparty</relativePath>
-  </parent>
-  <scm>
-    <connection>scm:git:ssh://git.opendaylight.org:29418/controller.git</connection>
-    <developerConnection>scm:git:ssh://git.opendaylight.org:29418/controller.git</developerConnection>
-    <url>https://wiki.opendaylight.org/view/OpenDaylight_Controller:Main</url>
-    <tag>HEAD</tag>
-  </scm>
-
-  <modelVersion>4.0.0</modelVersion>
-  <groupId>org.opendaylight.controller.thirdparty</groupId>
-  <artifactId>com.sun.jersey.jersey-servlet</artifactId>
-  <version>1.19.0-SNAPSHOT</version>
-  <packaging>bundle</packaging>
-  <build>
-    <plugins>
-      <plugin>
-        <groupId>org.apache.felix</groupId>
-        <artifactId>maven-bundle-plugin</artifactId>
-        <version>2.3.6</version>
-        <extensions>true</extensions>
-        <configuration>
-          <instructions>
-            <Embed-Dependency>*;scope=!provided;type=!pom;inline=false</Embed-Dependency>
-            <Embed-Transitive>false</Embed-Transitive>
-            <Export-Package>
-              com.sun.jersey.api.core.servlet,
-              com.sun.jersey.spi.container.servlet,
-              com.sun.jersey.spi.scanning.servlet,
-              com.sun.jersey.server.impl.container.servlet
-            </Export-Package>
-            <Import-Package>
-              com.sun.jersey.api.container,
-              com.sun.jersey.api.core,
-              com.sun.jersey.api.model,
-              com.sun.jersey.api.representation,
-              com.sun.jersey.api.uri,
-              com.sun.jersey.api.view,
-              com.sun.jersey.core.header,
-              com.sun.jersey.core.reflection,
-              com.sun.jersey.core.spi.component,
-              com.sun.jersey.core.spi.component.ioc,
-              com.sun.jersey.core.spi.scanning,
-              com.sun.jersey.core.util,
-              com.sun.jersey.server.impl,
-              com.sun.jersey.server.impl.application,
-              com.sun.jersey.server.impl.inject,
-              com.sun.jersey.server.impl.monitoring,
-              com.sun.jersey.server.probes,
-              com.sun.jersey.server.spi.component,
-              com.sun.jersey.spi,
-              com.sun.jersey.spi.container,
-              com.sun.jersey.spi.dispatch,
-              com.sun.jersey.spi.inject,
-              com.sun.jersey.spi.service,
-              com.sun.jersey.spi.template,
-              javax.naming,
-              javax.ws.rs,
-              javax.ws.rs.core,
-              javax.ws.rs.ext,
-              *;resolution:=optional
-            </Import-Package>
-          </instructions>
-          <manifestLocation>${project.basedir}/META-INF</manifestLocation>
-        </configuration>
-      </plugin>
-    </plugins>
-  </build>
-
-  <dependencies>
-    <dependency>
-      <groupId>com.sun.jersey</groupId>
-      <artifactId>jersey-servlet</artifactId>
-      <version>1.17</version>
-    </dependency>
-    <dependency>
-      <groupId>equinoxSDK381</groupId>
-      <artifactId>javax.servlet</artifactId>
-      <version>3.0.0.v201112011016</version>
-      <scope>provided</scope>
-    </dependency>
-  </dependencies>
-</project>
diff --git a/third-party/net.sf.jung2/pom.xml b/third-party/net.sf.jung2/pom.xml
deleted file mode 100644 (file)
index 63455dc..0000000
+++ /dev/null
@@ -1,80 +0,0 @@
-<?xml version="1.0" encoding="UTF-8"?>
-<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
-  <!-- Get some common settings for the project we are using it in -->
-  <parent>
-    <groupId>org.opendaylight.controller</groupId>
-    <artifactId>commons.thirdparty</artifactId>
-    <version>1.2.0-SNAPSHOT</version>
-    <relativePath>../commons/thirdparty</relativePath>
-  </parent>
-  <scm>
-    <connection>scm:git:ssh://git.opendaylight.org:29418/controller.git</connection>
-    <developerConnection>scm:git:ssh://git.opendaylight.org:29418/controller.git</developerConnection>
-    <url>https://wiki.opendaylight.org/view/OpenDaylight_Controller:Main</url>
-    <tag>HEAD</tag>
-  </scm>
-
-  <modelVersion>4.0.0</modelVersion>
-  <groupId>org.opendaylight.controller.thirdparty</groupId>
-  <artifactId>net.sf.jung2</artifactId>
-  <version>2.1.0-SNAPSHOT</version>
-  <packaging>bundle</packaging>
-  <build>
-    <plugins>
-      <plugin>
-        <groupId>org.apache.felix</groupId>
-        <artifactId>maven-bundle-plugin</artifactId>
-        <version>2.3.6</version>
-        <extensions>true</extensions>
-        <configuration>
-          <instructions>
-            <Embed-Dependency>*;scope=compile|runtime;type=!pom;inline=false</Embed-Dependency>
-            <Embed-Transitive>false</Embed-Transitive>
-            <Export-Package>
-              org.apache.commons*,
-              edu.uci.ics.jung.algorithms.blockmodel,
-              edu.uci.ics.jung.algorithms.cluster,
-              edu.uci.ics.jung.algorithms.filters,
-              edu.uci.ics.jung.algorithms.flows,
-              edu.uci.ics.jung.algorithms.generators,
-              edu.uci.ics.jung.algorithms.generators.random,
-              edu.uci.ics.jung.algorithms.layout,
-              edu.uci.ics.jung.algorithms.layout.util,
-              edu.uci.ics.jung.algorithms.metrics,
-              edu.uci.ics.jung.algorithms.scoring,
-              edu.uci.ics.jung.algorithms.scoring.util,
-              edu.uci.ics.jung.algorithms.shortestpath,
-              edu.uci.ics.jung.algorithms.transformation,
-              edu.uci.ics.jung.algorithms.util,
-              edu.uci.ics.jung.graph;-split-package:=merge-first,
-              edu.uci.ics.jung.graph.event,
-              edu.uci.ics.jung.graph.util;-split-package:=merge-first
-            </Export-Package>
-            <Import-Package>
-              !*
-            </Import-Package>
-          </instructions>
-          <manifestLocation>${project.basedir}/META-INF</manifestLocation>
-        </configuration>
-      </plugin>
-    </plugins>
-  </build>
-
-  <dependencies>
-    <dependency>
-      <groupId>net.sf.jung</groupId>
-      <artifactId>jung-api</artifactId>
-      <version>2.0.1</version>
-    </dependency>
-    <dependency>
-      <groupId>net.sf.jung</groupId>
-      <artifactId>jung-graph-impl</artifactId>
-      <version>2.0.1</version>
-    </dependency>
-    <dependency>
-      <groupId>net.sourceforge.collections</groupId>
-      <artifactId>collections-generic</artifactId>
-      <version>4.01</version>
-    </dependency>
-  </dependencies>
-</project>
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/StructurallyEquivalent.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/StructurallyEquivalent.java
deleted file mode 100644 (file)
index a9d4573..0000000
+++ /dev/null
@@ -1,178 +0,0 @@
-/*
- * Copyright (c) 2004, the JUNG Project and the Regents of the University 
- * of California
- * All rights reserved.
- * Created on Jan 28, 2004
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-package edu.uci.ics.jung.algorithms.blockmodel;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-import org.apache.commons.collections15.CollectionUtils;
-import org.apache.commons.collections15.Transformer;
-
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.util.Pair;
-
-/**
- * Identifies sets of structurally equivalent vertices in a graph. Vertices <i>
- * i</i> and <i>j</i> are structurally equivalent iff the set of <i>i</i>'s
- * neighbors is identical to the set of <i>j</i>'s neighbors, with the
- * exception of <i>i</i> and <i>j</i> themselves. This algorithm finds all
- * sets of equivalent vertices in O(V^2) time.
- * 
- * <p>You can extend this class to have a different definition of equivalence (by
- * overriding <code>isStructurallyEquivalent</code>), and may give it hints for
- * accelerating the process by overriding <code>canPossiblyCompare</code>. 
- * (For example, in a bipartite graph, <code>canPossiblyCompare</code> may 
- * return <code>false</code> for vertices in
- * different partitions. This function should be fast.)
- * 
- * @author Danyel Fisher
- */
-public class StructurallyEquivalent<V,E> implements Transformer<Graph<V,E>, VertexPartition<V,E>> 
-{
-       public VertexPartition<V,E> transform(Graph<V,E> g) 
-       {
-           Set<Pair<V>> vertex_pairs = getEquivalentPairs(g);
-           
-           Set<Set<V>> rv = new HashSet<Set<V>>();
-        Map<V, Set<V>> intermediate = new HashMap<V, Set<V>>();
-        for (Pair<V> p : vertex_pairs)
-        {
-            Set<V> res = intermediate.get(p.getFirst());
-            if (res == null)
-                res = intermediate.get(p.getSecond());
-            if (res == null)  // we haven't seen this one before
-                res = new HashSet<V>();
-            res.add(p.getFirst());
-            res.add(p.getSecond());
-            intermediate.put(p.getFirst(), res);
-            intermediate.put(p.getSecond(), res);
-        }
-        rv.addAll(intermediate.values());
-
-        // pick up the vertices which don't appear in intermediate; they are
-        // singletons (equivalence classes of size 1)
-        Collection<V> singletons = CollectionUtils.subtract(g.getVertices(),
-                intermediate.keySet());
-        for (V v : singletons)
-        {
-            Set<V> v_set = Collections.singleton(v);
-            intermediate.put(v, v_set);
-            rv.add(v_set);
-        }
-
-        return new VertexPartition<V, E>(g, intermediate, rv);
-       }
-
-       /**
-        * For each vertex pair v, v1 in G, checks whether v and v1 are fully
-        * equivalent: meaning that they connect to the exact same vertices. (Is
-        * this regular equivalence, or whathaveyou?)
-        * 
-        * Returns a Set of Pairs of vertices, where all the vertices in the inner
-        * Pairs are equivalent.
-        * 
-        * @param g
-        */
-       protected Set<Pair<V>> getEquivalentPairs(Graph<V,?> g) {
-
-               Set<Pair<V>> rv = new HashSet<Pair<V>>();
-               Set<V> alreadyEquivalent = new HashSet<V>();
-
-               List<V> l = new ArrayList<V>(g.getVertices());
-
-               for (V v1 : l)
-               {
-                       if (alreadyEquivalent.contains(v1))
-                               continue;
-
-                       for (Iterator<V> iterator = l.listIterator(l.indexOf(v1) + 1); iterator.hasNext();) {
-                           V v2 = iterator.next();
-
-                               if (alreadyEquivalent.contains(v2))
-                                       continue;
-
-                               if (!canPossiblyCompare(v1, v2))
-                                       continue;
-
-                               if (isStructurallyEquivalent(g, v1, v2)) {
-                                       Pair<V> p = new Pair<V>(v1, v2);
-                                       alreadyEquivalent.add(v2);
-                                       rv.add(p);
-                               }
-                       }
-               }
-               
-               return rv;
-       }
-
-       /**
-        * Checks whether a pair of vertices are structurally equivalent.
-        * Specifically, whether v1's predecessors are equal to v2's predecessors,
-        * and same for successors.
-        * 
-        * @param g the graph in which the structural equivalence comparison is to take place
-        * @param v1 the vertex to check for structural equivalence to v2
-        * @param v2 the vertex to check for structural equivalence to v1
-        */
-       protected boolean isStructurallyEquivalent(Graph<V,?> g, V v1, V v2) {
-               
-               if( g.degree(v1) != g.degree(v2)) {
-                       return false;
-               }
-
-               Set<V> n1 = new HashSet<V>(g.getPredecessors(v1));
-               n1.remove(v2);
-               n1.remove(v1);
-               Set<V> n2 = new HashSet<V>(g.getPredecessors(v2));
-               n2.remove(v1);
-               n2.remove(v2);
-
-               Set<V> o1 = new HashSet<V>(g.getSuccessors(v1));
-               Set<V> o2 = new HashSet<V>(g.getSuccessors(v2));
-               o1.remove(v1);
-               o1.remove(v2);
-               o2.remove(v1);
-               o2.remove(v2);
-
-               // this neglects self-loops and directed edges from 1 to other
-               boolean b = (n1.equals(n2) && o1.equals(o2));
-               if (!b)
-                       return b;
-               
-               // if there's a directed edge v1->v2 then there's a directed edge v2->v1
-               b &= ( g.isSuccessor(v1, v2) == g.isSuccessor(v2, v1));
-               
-               // self-loop check
-               b &= ( g.isSuccessor(v1, v1) == g.isSuccessor(v2, v2));
-
-               return b;
-
-       }
-
-       /**
-        * This is a space for optimizations. For example, for a bipartite graph,
-        * vertices from different partitions cannot possibly be compared.
-        * 
-        * @param v1
-        * @param v2
-        */
-       protected boolean canPossiblyCompare(V v1, V v2) {
-               return true;
-       }
-
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/VertexPartition.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/VertexPartition.java
deleted file mode 100644 (file)
index b5ec583..0000000
+++ /dev/null
@@ -1,131 +0,0 @@
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University 
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-/*
- * Created on Feb 3, 2004
- */
-package edu.uci.ics.jung.algorithms.blockmodel;
-
-import java.util.*;
-
-import edu.uci.ics.jung.graph.Graph;
-
-
-/**
- * Maintains information about a vertex partition of a graph.
- * This can be built from a map from vertices to vertex sets 
- * or from a collection of (disjoint) vertex sets,
- * such as those created by various clustering methods.
- */
-public class VertexPartition<V,E> 
-{
-       private Map<V,Set<V>> vertex_partition_map;
-       private Collection<Set<V>> vertex_sets;
-       private Graph<V,E> graph;
-       
-       /**
-        * Creates an instance based on the specified graph and mapping from vertices
-        * to vertex sets, and generates a set of partitions based on this mapping.
-        * @param g the graph over which the vertex partition is defined
-        * @param partition_map the mapping from vertices to vertex sets (partitions)
-        */
-       public VertexPartition(Graph<V,E> g, Map<V, Set<V>> partition_map) 
-       {
-               this.vertex_partition_map = Collections.unmodifiableMap(partition_map);
-               this.graph = g;
-       }
-
-       /**
-     * Creates an instance based on the specified graph, vertex-set mapping, 
-     * and set of disjoint vertex sets.  The vertex-set mapping and vertex 
-     * partitions must be consistent; that is, the mapping must reflect the 
-     * division of vertices into partitions, and each vertex must appear in 
-     * exactly one partition.
-     * @param g the graph over which the vertex partition is defined
-     * @param partition_map the mapping from vertices to vertex sets (partitions)
-        * @param vertex_sets the set of disjoint vertex sets 
-        */
-    public VertexPartition(Graph<V,E> g, Map<V, Set<V>> partition_map, 
-               Collection<Set<V>> vertex_sets) 
-    {
-        this.vertex_partition_map = Collections.unmodifiableMap(partition_map);
-        this.vertex_sets = vertex_sets;
-        this.graph = g;
-    }
-
-    /**
-     * Creates an instance based on the specified graph and set of disjoint vertex sets, 
-     * and generates a vertex-to-partition map based on these sets.
-     * @param g the graph over which the vertex partition is defined
-     * @param vertex_sets the set of disjoint vertex sets
-     */
-    public VertexPartition(Graph<V,E> g, Collection<Set<V>> vertex_sets)
-    {
-        this.vertex_sets = vertex_sets;
-        this.graph = g;
-    }
-       
-    /**
-     * Returns the graph on which the partition is defined.
-     * @return the graph on which the partition is defined
-     */
-       public Graph<V,E> getGraph() 
-       {
-               return graph;
-       }
-
-       /**
-        * Returns a map from each vertex in the input graph to its partition.
-        * This map is generated if it does not already exist.
-        * @return a map from each vertex in the input graph to a vertex set
-        */
-       public Map<V,Set<V>> getVertexToPartitionMap() 
-       {
-               if (vertex_partition_map == null)
-               {
-               this.vertex_partition_map = new HashMap<V, Set<V>>();
-               for (Set<V> set : this.vertex_sets)
-                   for (V v : set)
-                       this.vertex_partition_map.put(v, set);
-               }
-               return vertex_partition_map;
-       }
-       
-       /**
-        * Returns a collection of vertex sets, where each vertex in the 
-        * input graph is in exactly one set.
-        * This collection is generated based on the vertex-to-partition map 
-        * if it does not already exist.
-        * @return a collection of vertex sets such that each vertex in the 
-        * instance's graph is in exactly one set
-        */
-       public Collection<Set<V>> getVertexPartitions() 
-       {
-               if (vertex_sets == null)
-               {
-                       this.vertex_sets = new HashSet<Set<V>>();
-                       this.vertex_sets.addAll(vertex_partition_map.values());
-               }
-           return vertex_sets;
-       }
-
-       /**
-        * Returns the number of partitions.
-        */
-       public int numPartitions() 
-       {
-               return vertex_sets.size();
-       }
-       
-       @Override
-       public String toString() 
-       {
-               return "Partitions: " + vertex_partition_map;
-       }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/package.html b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/package.html
deleted file mode 100644 (file)
index d1cb06a..0000000
+++ /dev/null
@@ -1,33 +0,0 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
-<html>
-<head>
-<!--
-
-  @(#)package.html
-
- Copyright © 2003 The Regents of the University of California. All Rights Reserved. Permission to use, copy, modify, and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice, this paragraph and the following two paragraphs appear in all copies. This software program and documentation are copyrighted by The Regents of the University of California ("The University of California").
-
-THE SOFTWARE PROGRAM AND DOCUMENTATION ARE SUPPLIED "AS IS," WITHOUT ANY ACCOMPANYING SERVICES FROM THE UNIVERSITY OF CALFORNIA. FURTHERMORE, THE UNIVERSITY OF CALIFORNIA DOES NOT WARRANT THAT THE OPERATION OF THE PROGRAM WILL BE UNINTERRUPTED OR ERROR-FREE. THE END-USER UNDERSTANDS THAT THE PROGRAM WAS DEVELOPED FOR RESEARCH PURPOSES AND IS ADVISED NOT TO RELY EXCLUSIVELY ON THE PROGRAM FOR ANY REASON.
-
-IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
--->
-</head>
-<body>
-
-Support for establishing and maintaining graph element equivalence (such as in blockmodeling).
-<P/>
-In blockmodeling, groups of vertices are clustered together by similarity 
-(as if members of a "block" appearing on the diagonal of the graph's adjacency 
-matrix).
-<p/>
-This support currently includes:
-<ul>
-<li/><code>VertexPartition</code>: A class that maintains information on a 
-division of the vertices of a graph into disjoint sets.
-<li/><code>StructurallyEquivalent</code>: An algorithm that finds sets of vertices that are 
-structurally equivalent.
-</ul> 
-
-<p/>
-</body>
-</html>
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/BicomponentClusterer.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/BicomponentClusterer.java
deleted file mode 100644 (file)
index aa697c7..0000000
+++ /dev/null
@@ -1,162 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.cluster;
-
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.LinkedHashSet;
-import java.util.Map;
-import java.util.Set;
-import java.util.Stack;
-
-import org.apache.commons.collections15.Transformer;
-
-import edu.uci.ics.jung.graph.UndirectedGraph;
-
-/**
- * Finds all biconnected components (bicomponents) of an undirected graph.  
- * A graph is a biconnected component if 
- * at least 2 vertices must be removed in order to disconnect the graph.  (Graphs 
- * consisting of one vertex, or of two connected vertices, are also biconnected.)  Biconnected
- * components of three or more vertices have the property that every pair of vertices in the component
- * are connected by two or more vertex-disjoint paths.
- * <p>
- * Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges
- * @see "Depth first search and linear graph algorithms by R. E. Tarjan (1972), SIAM J. Comp."
- * 
- * @author Joshua O'Madadhain
- */
-public class BicomponentClusterer<V,E> implements Transformer<UndirectedGraph<V,E>, Set<Set<V>>> 
-{
-    protected Map<V,Number> dfs_num;
-    protected Map<V,Number> high;
-    protected Map<V,V> parents;
-    protected Stack<E> stack;
-    protected int converse_depth;
-
-    /**
-     * Constructs a new bicomponent finder
-     */
-    public BicomponentClusterer() {
-    }
-
-    /**
-    * Extracts the bicomponents from the graph.
-    * @param theGraph the graph whose bicomponents are to be extracted
-    * @return the <code>ClusterSet</code> of bicomponents
-    */
-    public Set<Set<V>> transform(UndirectedGraph<V,E> theGraph) 
-    {
-       Set<Set<V>> bicomponents = new LinkedHashSet<Set<V>>();
-
-        if (theGraph.getVertices().isEmpty())
-            return bicomponents;
-
-        // initialize DFS number for each vertex to 0
-        dfs_num = new HashMap<V,Number>();
-        for (V v : theGraph.getVertices())
-        {
-               dfs_num.put(v, 0);
-        }
-
-        for (V v : theGraph.getVertices())
-        {
-            if (dfs_num.get(v).intValue() == 0) // if we haven't hit this vertex yet...
-            {
-                high = new HashMap<V,Number>();
-                stack = new Stack<E>();
-                parents = new HashMap<V,V>();
-                converse_depth = theGraph.getVertexCount();
-                // find the biconnected components for this subgraph, starting from v
-                findBiconnectedComponents(theGraph, v, bicomponents);
-                
-                // if we only visited one vertex, this method won't have
-                // ID'd it as a biconnected component, so mark it as one
-                if (theGraph.getVertexCount() - converse_depth == 1)
-                {
-                    Set<V> s = new HashSet<V>();
-                    s.add(v);
-                    bicomponents.add(s);
-                }
-            }
-        }
-        
-        return bicomponents;
-    }
-
-    /**
-     * <p>Stores, in <code>bicomponents</code>, all the biconnected
-     * components that are reachable from <code>v</code>.</p>
-     * 
-     * <p>The algorithm basically proceeds as follows: do a depth-first
-     * traversal starting from <code>v</code>, marking each vertex with
-     * a value that indicates the order in which it was encountered (dfs_num), 
-     * and with
-     * a value that indicates the highest point in the DFS tree that is known
-     * to be reachable from this vertex using non-DFS edges (high).  (Since it
-     * is measured on non-DFS edges, "high" tells you how far back in the DFS
-     * tree you can reach by two distinct paths, hence biconnectivity.) 
-     * Each time a new vertex w is encountered, push the edge just traversed
-     * on a stack, and call this method recursively.  If w.high is no greater than
-     * v.dfs_num, then the contents of the stack down to (v,w) is a 
-     * biconnected component (and v is an articulation point, that is, a 
-     * component boundary).  In either case, set v.high to max(v.high, w.high), 
-     * and continue.  If w has already been encountered but is 
-     * not v's parent, set v.high max(v.high, w.dfs_num) and continue. 
-     * 
-     * <p>(In case anyone cares, the version of this algorithm on p. 224 of 
-     * Udi Manber's "Introduction to Algorithms: A Creative Approach" seems to be
-     * wrong: the stack should be initialized outside this method, 
-     * (v,w) should only be put on the stack if w hasn't been seen already,
-     * and there's no real benefit to putting v on the stack separately: just
-     * check for (v,w) on the stack rather than v.  Had I known this, I could
-     * have saved myself a few days.  JRTOM)</p>
-     * 
-     */
-    protected void findBiconnectedComponents(UndirectedGraph<V,E> g, V v, Set<Set<V>> bicomponents)
-    {
-        int v_dfs_num = converse_depth;
-        dfs_num.put(v, v_dfs_num);
-        converse_depth--;
-        high.put(v, v_dfs_num);
-
-        for (V w : g.getNeighbors(v))
-        {
-            int w_dfs_num = dfs_num.get(w).intValue();//get(w, dfs_num);
-            E vw = g.findEdge(v,w);
-            if (w_dfs_num == 0) // w hasn't yet been visited
-            {
-                parents.put(w, v); // v is w's parent in the DFS tree
-                stack.push(vw);
-                findBiconnectedComponents(g, w, bicomponents);
-                int w_high = high.get(w).intValue();//get(w, high);
-                if (w_high <= v_dfs_num)
-                {
-                    // v disconnects w from the rest of the graph,
-                    // i.e., v is an articulation point
-                    // thus, everything between the top of the stack and
-                    // v is part of a single biconnected component
-                    Set<V> bicomponent = new HashSet<V>();
-                    E e;
-                    do
-                    {
-                        e = stack.pop();
-                        bicomponent.addAll(g.getIncidentVertices(e));
-                    }
-                    while (e != vw);
-                    bicomponents.add(bicomponent);
-                }
-                high.put(v, Math.max(w_high, high.get(v).intValue()));
-            }
-            else if (w != parents.get(v)) // (v,w) is a back or a forward edge
-               high.put(v, Math.max(w_dfs_num, high.get(v).intValue()));
-        }
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/EdgeBetweennessClusterer.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/EdgeBetweennessClusterer.java
deleted file mode 100644 (file)
index 59e4605..0000000
+++ /dev/null
@@ -1,109 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.cluster;
-
-import java.util.ArrayList;
-import java.util.LinkedHashMap;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-import org.apache.commons.collections15.Transformer;
-
-import edu.uci.ics.jung.algorithms.scoring.BetweennessCentrality;
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.util.Pair;
-
-
-/**
- * An algorithm for computing clusters (community structure) in graphs based on edge betweenness.
- * The betweenness of an edge is defined as the extent to which that edge lies along 
- * shortest paths between all pairs of nodes.
- *
- * This algorithm works by iteratively following the 2 step process:
- * <ul>
- * <li> Compute edge betweenness for all edges in current graph
- * <li> Remove edge with highest betweenness
- * </ul>
- * <p>
- * Running time is: O(kmn) where k is the number of edges to remove, m is the total number of edges, and
- * n is the total number of vertices. For very sparse graphs the running time is closer to O(kn^2) and for
- * graphs with strong community structure, the complexity is even lower.
- * <p>
- * This algorithm is a slight modification of the algorithm discussed below in that the number of edges
- * to be removed is parameterized.
- * @author Scott White
- * @author Tom Nelson (converted to jung2)
- * @see "Community structure in social and biological networks by Michelle Girvan and Mark Newman"
- */
-public class EdgeBetweennessClusterer<V,E> implements Transformer<Graph<V,E>,Set<Set<V>>> {
-    private int mNumEdgesToRemove;
-    private Map<E, Pair<V>> edges_removed;
-
-   /**
-    * Constructs a new clusterer for the specified graph.
-    * @param numEdgesToRemove the number of edges to be progressively removed from the graph
-    */
-    public EdgeBetweennessClusterer(int numEdgesToRemove) {
-        mNumEdgesToRemove = numEdgesToRemove;
-        edges_removed = new LinkedHashMap<E, Pair<V>>();
-    }
-
-    /**
-    * Finds the set of clusters which have the strongest "community structure".
-    * The more edges removed the smaller and more cohesive the clusters.
-    * @param graph the graph
-    */
-    public Set<Set<V>> transform(Graph<V,E> graph) {
-                
-        if (mNumEdgesToRemove < 0 || mNumEdgesToRemove > graph.getEdgeCount()) {
-            throw new IllegalArgumentException("Invalid number of edges passed in.");
-        }
-        
-        edges_removed.clear();
-
-        for (int k=0;k<mNumEdgesToRemove;k++) {
-            BetweennessCentrality<V,E> bc = new BetweennessCentrality<V,E>(graph);
-            E to_remove = null;
-            double score = 0;
-            for (E e : graph.getEdges())
-                if (bc.getEdgeScore(e) > score)
-                {
-                    to_remove = e;
-                    score = bc.getEdgeScore(e);
-                }
-            edges_removed.put(to_remove, graph.getEndpoints(to_remove));
-            graph.removeEdge(to_remove);
-        }
-
-        WeakComponentClusterer<V,E> wcSearch = new WeakComponentClusterer<V,E>();
-        Set<Set<V>> clusterSet = wcSearch.transform(graph);
-
-        for (Map.Entry<E, Pair<V>> entry : edges_removed.entrySet())
-        {
-            Pair<V> endpoints = entry.getValue();
-            graph.addEdge(entry.getKey(), endpoints.getFirst(), endpoints.getSecond());
-        }
-        return clusterSet;
-    }
-
-    /**
-     * Retrieves the list of all edges that were removed 
-     * (assuming extract(...) was previously called).  
-     * The edges returned
-     * are stored in order in which they were removed.
-     * 
-     * @return the edges in the original graph
-     */
-    public List<E> getEdgesRemoved() 
-    {
-        return new ArrayList<E>(edges_removed.keySet());
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/VoltageClusterer.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/VoltageClusterer.java
deleted file mode 100644 (file)
index 859c063..0000000
+++ /dev/null
@@ -1,366 +0,0 @@
-/*
- * Copyright (c) 2004, the JUNG Project and the Regents of the University
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- *
- * Created on Aug 12, 2004
- */
-package edu.uci.ics.jung.algorithms.cluster;
-
-import edu.uci.ics.jung.algorithms.scoring.VoltageScorer;
-import edu.uci.ics.jung.algorithms.util.DiscreteDistribution;
-import edu.uci.ics.jung.algorithms.util.KMeansClusterer;
-import edu.uci.ics.jung.algorithms.util.KMeansClusterer.NotEnoughClustersException;
-import edu.uci.ics.jung.graph.Graph;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.LinkedList;
-import java.util.List;
-import java.util.Map;
-import java.util.Random;
-import java.util.Set;
-
-/**
- * <p>Clusters vertices of a <code>Graph</code> based on their ranks as
- * calculated by <code>VoltageScorer</code>.  This algorithm is based on,
- * but not identical with, the method described in the paper below.
- * The primary difference is that Wu and Huberman assume a priori that the clusters
- * are of approximately the same size, and therefore use a more complex
- * method than k-means (which is used here) for determining cluster
- * membership based on co-occurrence data.</p>
- *
- * <p>The algorithm proceeds as follows:
- * <ul>
- * <li/>first, generate a set of candidate clusters as follows:
- *      <ul>
- *      <li/>pick (widely separated) vertex pair, run VoltageScorer
- *      <li/>group the vertices in two clusters according to their voltages
- *      <li/>store resulting candidate clusters
- *      </ul>
- * <li/>second, generate k-1 clusters as follows:
- *      <ul>
- *      <li/>pick a vertex v as a cluster 'seed'
- *           <br>(Wu/Huberman: most frequent vertex in candidate clusters)
- *      <li/>calculate co-occurrence over all candidate clusters of v with each other
- *           vertex
- *      <li/>separate co-occurrence counts into high/low;
- *           high vertices constitute a cluster
- *      <li/>remove v's vertices from candidate clusters; continue
- *      </ul>
- * <li/>finally, remaining unassigned vertices are assigned to the kth ("garbage")
- * cluster.
- * </ul></p>
- *
- * <p><b>NOTE</b>: Depending on how the co-occurrence data splits the data into
- * clusters, the number of clusters returned by this algorithm may be less than the
- * number of clusters requested.  The number of clusters will never be more than
- * the number requested, however.</p>
- *
- * @author Joshua O'Madadhain
- * @see "'Finding communities in linear time: a physics approach', Fang Wu and Bernardo Huberman, http://www.hpl.hp.com/research/idl/papers/linear/"
- * @see VoltageScorer
- * @see KMeansClusterer
- */
-public class VoltageClusterer<V,E>
-{
-    protected int num_candidates;
-    protected KMeansClusterer<V> kmc;
-    protected Random rand;
-    protected Graph<V,E> g;
-
-    /**
-     * Creates an instance of a VoltageCluster with the specified parameters.
-     * These are mostly parameters that are passed directly to VoltageScorer
-     * and KMeansClusterer.
-     *
-     * @param num_candidates    the number of candidate clusters to create
-     */
-    public VoltageClusterer(Graph<V,E> g, int num_candidates)
-    {
-        if (num_candidates < 1)
-            throw new IllegalArgumentException("must generate >=1 candidates");
-
-        this.num_candidates = num_candidates;
-        this.kmc = new KMeansClusterer<V>();
-        rand = new Random();
-        this.g = g;
-    }
-
-    protected void setRandomSeed(int random_seed)
-    {
-        rand = new Random(random_seed);
-    }
-
-    /**
-     * Returns a community (cluster) centered around <code>v</code>.
-     * @param v the vertex whose community we wish to discover
-     */
-    public Collection<Set<V>> getCommunity(V v)
-    {
-        return cluster_internal(v, 2);
-    }
-
-    /**
-     * Clusters the vertices of <code>g</code> into
-     * <code>num_clusters</code> clusters, based on their connectivity.
-     * @param num_clusters  the number of clusters to identify
-     */
-    public Collection<Set<V>> cluster(int num_clusters)
-    {
-        return cluster_internal(null, num_clusters);
-    }
-
-    /**
-     * Does the work of <code>getCommunity</code> and <code>cluster</code>.
-     * @param origin the vertex around which clustering is to be done
-     * @param num_clusters the (maximum) number of clusters to find
-     */
-    protected Collection<Set<V>> cluster_internal(V origin, int num_clusters)
-    {
-        // generate candidate clusters
-        // repeat the following 'samples' times:
-        // * pick (widely separated) vertex pair, run VoltageScorer
-        // * use k-means to identify 2 communities in ranked graph
-        // * store resulting candidate communities
-        ArrayList<V> v_array = new ArrayList<V>(g.getVertices());
-
-        LinkedList<Set<V>> candidates = new LinkedList<Set<V>>();
-
-        for (int j = 0; j < num_candidates; j++)
-        {
-            V source;
-            if (origin == null)
-                source = v_array.get((int)(rand.nextDouble() * v_array.size()));
-            else
-                source = origin;
-            V target = null;
-            do
-            {
-                target = v_array.get((int)(rand.nextDouble() * v_array.size()));
-            }
-            while (source == target);
-            VoltageScorer<V,E> vs = new VoltageScorer<V,E>(g, source, target);
-            vs.evaluate();
-
-            Map<V, double[]> voltage_ranks = new HashMap<V, double[]>();
-            for (V v : g.getVertices())
-                voltage_ranks.put(v, new double[] {vs.getVertexScore(v)});
-
-//            addOneCandidateCluster(candidates, voltage_ranks);
-            addTwoCandidateClusters(candidates, voltage_ranks);
-        }
-
-        // repeat the following k-1 times:
-        // * pick a vertex v as a cluster seed
-        //   (Wu/Huberman: most frequent vertex in candidates)
-        // * calculate co-occurrence (in candidate clusters)
-        //   of this vertex with all others
-        // * use k-means to separate co-occurrence counts into high/low;
-        //   high vertices are a cluster
-        // * remove v's vertices from candidate clusters
-
-        Collection<Set<V>> clusters = new LinkedList<Set<V>>();
-        Set<V> remaining = new HashSet<V>(g.getVertices());
-
-        List<V> seed_candidates = getSeedCandidates(candidates);
-        int seed_index = 0;
-
-        for (int j = 0; j < (num_clusters - 1); j++)
-        {
-            if (remaining.isEmpty())
-                break;
-
-            V seed;
-            if (seed_index == 0 && origin != null)
-                seed = origin;
-            else
-            {
-                do { seed = seed_candidates.get(seed_index++); }
-                while (!remaining.contains(seed));
-            }
-
-            Map<V, double[]> occur_counts = getObjectCounts(candidates, seed);
-            if (occur_counts.size() < 2)
-                break;
-
-            // now that we have the counts, cluster them...
-            try
-            {
-                Collection<Map<V, double[]>> high_low = kmc.cluster(occur_counts, 2);
-                // ...get the cluster with the highest-valued centroid...
-                Iterator<Map<V, double[]>> h_iter = high_low.iterator();
-                Map<V, double[]> cluster1 = h_iter.next();
-                Map<V, double[]> cluster2 = h_iter.next();
-                double[] centroid1 = DiscreteDistribution.mean(cluster1.values());
-                double[] centroid2 = DiscreteDistribution.mean(cluster2.values());
-                Set<V> new_cluster;
-                if (centroid1[0] >= centroid2[0])
-                    new_cluster = cluster1.keySet();
-                else
-                    new_cluster = cluster2.keySet();
-
-                // ...remove the elements of new_cluster from each candidate...
-                for (Set<V> cluster : candidates)
-                    cluster.removeAll(new_cluster);
-                clusters.add(new_cluster);
-                remaining.removeAll(new_cluster);
-            }
-            catch (NotEnoughClustersException nece)
-            {
-                // all remaining vertices are in the same cluster
-                break;
-            }
-        }
-
-        // identify remaining vertices (if any) as a 'garbage' cluster
-        if (!remaining.isEmpty())
-            clusters.add(remaining);
-
-        return clusters;
-    }
-
-    /**
-     * Do k-means with three intervals and pick the
-     * smaller two clusters (presumed to be on the ends); this is closer to the Wu-Huberman method.
-     * @param candidates
-     * @param voltage_ranks
-     */
-    protected void addTwoCandidateClusters(LinkedList<Set<V>> candidates,
-            Map<V, double[]> voltage_ranks)
-    {
-        try
-        {
-            List<Map<V, double[]>> clusters = new ArrayList<Map<V, double[]>>(kmc.cluster(voltage_ranks, 3));
-            boolean b01 = clusters.get(0).size() > clusters.get(1).size();
-            boolean b02 = clusters.get(0).size() > clusters.get(2).size();
-            boolean b12 = clusters.get(1).size() > clusters.get(2).size();
-            if (b01 && b02)
-            {
-                candidates.add(clusters.get(1).keySet());
-                candidates.add(clusters.get(2).keySet());
-            }
-            else if (!b01 && b12)
-            {
-                candidates.add(clusters.get(0).keySet());
-                candidates.add(clusters.get(2).keySet());
-            }
-            else if (!b02 && !b12)
-            {
-                candidates.add(clusters.get(0).keySet());
-                candidates.add(clusters.get(1).keySet());
-            }
-        }
-        catch (NotEnoughClustersException e)
-        {
-            // no valid candidates, continue
-        }
-    }
-
-    /**
-     * alternative to addTwoCandidateClusters(): cluster vertices by voltages into 2 clusters.
-     * We only consider the smaller of the two clusters returned
-     * by k-means to be a 'true' cluster candidate; the other is a garbage cluster.
-     * @param candidates
-     * @param voltage_ranks
-     */
-    protected void addOneCandidateCluster(LinkedList<Set<V>> candidates,
-            Map<V, double[]> voltage_ranks)
-    {
-        try
-        {
-            List<Map<V, double[]>> clusters;
-            clusters = new ArrayList<Map<V, double[]>>(kmc.cluster(voltage_ranks, 2));
-            if (clusters.get(0).size() < clusters.get(1).size())
-                candidates.add(clusters.get(0).keySet());
-            else
-                candidates.add(clusters.get(1).keySet());
-        }
-        catch (NotEnoughClustersException e)
-        {
-            // no valid candidates, continue
-        }
-    }
-
-    /**
-     * Returns an array of cluster seeds, ranked in decreasing order
-     * of number of appearances in the specified collection of candidate
-     * clusters.
-     * @param candidates
-     */
-    protected List<V> getSeedCandidates(Collection<Set<V>> candidates)
-    {
-        final Map<V, double[]> occur_counts = getObjectCounts(candidates, null);
-
-        ArrayList<V> occurrences = new ArrayList<V>(occur_counts.keySet());
-        Collections.sort(occurrences, new MapValueArrayComparator(occur_counts));
-
-        System.out.println("occurrences: ");
-        for (int i = 0; i < occurrences.size(); i++)
-            System.out.println(occur_counts.get(occurrences.get(i))[0]);
-
-        return occurrences;
-    }
-
-    protected Map<V, double[]> getObjectCounts(Collection<Set<V>> candidates, V seed)
-    {
-        Map<V, double[]> occur_counts = new HashMap<V, double[]>();
-        for (V v : g.getVertices())
-            occur_counts.put(v, new double[]{0});
-
-        for (Set<V> candidate : candidates)
-        {
-            if (seed == null)
-                System.out.println(candidate.size());
-            if (seed == null || candidate.contains(seed))
-            {
-                for (V element : candidate)
-                {
-                    double[] count = occur_counts.get(element);
-                    count[0]++;
-                }
-            }
-        }
-
-        if (seed == null)
-        {
-            System.out.println("occur_counts size: " + occur_counts.size());
-            for (V v : occur_counts.keySet())
-                System.out.println(occur_counts.get(v)[0]);
-        }
-
-        return occur_counts;
-    }
-
-    protected class MapValueArrayComparator implements Comparator<V>
-    {
-        private Map<V, double[]> map;
-
-        protected MapValueArrayComparator(Map<V, double[]> map)
-        {
-            this.map = map;
-        }
-
-        public int compare(V o1, V o2)
-        {
-            double[] count0 = map.get(o1);
-            double[] count1 = map.get(o2);
-            if (count0[0] < count1[0])
-                return 1;
-            else if (count0[0] > count1[0])
-                return -1;
-            return 0;
-        }
-
-    }
-
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/WeakComponentClusterer.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/WeakComponentClusterer.java
deleted file mode 100644 (file)
index cb79a78..0000000
+++ /dev/null
@@ -1,73 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.cluster;
-
-import java.util.Collection;
-import java.util.HashSet;
-import java.util.Set;
-
-import org.apache.commons.collections15.Buffer;
-import org.apache.commons.collections15.Transformer;
-import org.apache.commons.collections15.buffer.UnboundedFifoBuffer;
-
-import edu.uci.ics.jung.graph.Graph;
-
-
-
-/**
- * Finds all weak components in a graph as sets of vertex sets.  A weak component is defined as
- * a maximal subgraph in which all pairs of vertices in the subgraph are reachable from one
- * another in the underlying undirected subgraph.
- * <p>This implementation identifies components as sets of vertex sets.  
- * To create the induced graphs from any or all of these vertex sets, 
- * see <code>algorithms.filters.FilterUtils</code>.
- * <p>
- * Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges.
- * @author Scott White
- */
-public class WeakComponentClusterer<V,E> implements Transformer<Graph<V,E>, Set<Set<V>>> 
-{
-       /**
-     * Extracts the weak components from a graph.
-     * @param graph the graph whose weak components are to be extracted
-     * @return the list of weak components
-     */
-    public Set<Set<V>> transform(Graph<V,E> graph) {
-
-        Set<Set<V>> clusterSet = new HashSet<Set<V>>();
-
-        HashSet<V> unvisitedVertices = new HashSet<V>(graph.getVertices());
-
-        while (!unvisitedVertices.isEmpty()) {
-               Set<V> cluster = new HashSet<V>();
-            V root = unvisitedVertices.iterator().next();
-            unvisitedVertices.remove(root);
-            cluster.add(root);
-
-            Buffer<V> queue = new UnboundedFifoBuffer<V>();
-            queue.add(root);
-
-            while (!queue.isEmpty()) {
-                V currentVertex = queue.remove();
-                Collection<V> neighbors = graph.getNeighbors(currentVertex);
-
-                for(V neighbor : neighbors) {
-                    if (unvisitedVertices.contains(neighbor)) {
-                        queue.add(neighbor);
-                        unvisitedVertices.remove(neighbor);
-                        cluster.add(neighbor);
-                    }
-                }
-            }
-            clusterSet.add(cluster);
-        }
-        return clusterSet;
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/package.html b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/package.html
deleted file mode 100644 (file)
index f8bdb22..0000000
+++ /dev/null
@@ -1,35 +0,0 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
-<html>
-<head>
-<!--
-
-  @(#)package.html
-
- Copyright © 2003 The Regents of the University of California. All Rights Reserved. Permission to use, copy, modify, and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice, this paragraph and the following two paragraphs appear in all copies. This software program and documentation are copyrighted by The Regents of the University of California ("The University of California").
-
-THE SOFTWARE PROGRAM AND DOCUMENTATION ARE SUPPLIED "AS IS," WITHOUT ANY ACCOMPANYING SERVICES FROM THE UNIVERSITY OF CALFORNIA. FURTHERMORE, THE UNIVERSITY OF CALIFORNIA DOES NOT WARRANT THAT THE OPERATION OF THE PROGRAM WILL BE UNINTERRUPTED OR ERROR-FREE. THE END-USER UNDERSTANDS THAT THE PROGRAM WAS DEVELOPED FOR RESEARCH PURPOSES AND IS ADVISED NOT TO RELY EXCLUSIVELY ON THE PROGRAM FOR ANY REASON.
-
-IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
--->
-</head>
-<body>
-
-Mechanisms for identifying clusters in graphs.  Where these clusters define disjoint sets of vertices, 
-they may be used to define a <code>VertexPartition</code> for more convenient manipulation of the vertex/set
-relationships.
-
-Current clustering algorithms include:
-<ul>
-<li/><code>BicomponentClusterer</code>: finds all subsets of vertices for which at least
-2 vertices must be removed in order to disconnect the induced subgraphs.
-<li/><code>EdgeBetweennessClusterer</code>: identifies vertex clusters by removing the edges of the highest
-'betweenness' scores (see the importance/scoring package).
-<li/><code>VoltageClusterer</code>: Clusters vertices based on their ranks as 
-calculated by <code>VoltageRanker</code>. 
-<li/><code>WeakComponentVertexClusterer</code>: Clusters vertices based on their membership in weakly 
-connected components of a graph.
-</ul>
-
-
-</body>
-</html>
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/EdgePredicateFilter.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/EdgePredicateFilter.java
deleted file mode 100644 (file)
index 5e3be06..0000000
+++ /dev/null
@@ -1,70 +0,0 @@
-/*
- * Created on May 19, 2008
- *
- * Copyright (c) 2008, the JUNG Project and the Regents of the University 
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-package edu.uci.ics.jung.algorithms.filters;
-
-import org.apache.commons.collections15.Predicate;
-
-import edu.uci.ics.jung.graph.Graph;
-
-/**
- * Transforms the input graph into one which contains only those edges 
- * that pass the specified <code>Predicate</code>.  The filtered graph
- * is a copy of the original graph (same type, uses the same vertex and
- * edge objects).  All vertices from the original graph
- * are copied into the new graph (even if they are not incident to any
- * edges in the new graph).
- * 
- * @author Joshua O'Madadhain
- */
-public class EdgePredicateFilter<V, E> implements Filter<V, E>
-{
-    protected Predicate<E> edge_pred;
-
-    /**
-     * Creates an instance based on the specified edge <code>Predicate</code>.
-     * @param edge_pred   the predicate that specifies which edges to add to the filtered graph
-     */
-    public EdgePredicateFilter(Predicate<E> edge_pred)
-    {
-        this.edge_pred = edge_pred;
-    }
-    
-    @SuppressWarnings("unchecked")
-    public Graph<V,E> transform(Graph<V,E> g)
-    {
-        Graph<V, E> filtered;
-        try
-        {
-            filtered = g.getClass().newInstance();
-        }
-        catch (InstantiationException e)
-        {
-            throw new RuntimeException("Unable to create copy of existing graph: ", e);
-        }
-        catch (IllegalAccessException e)
-        {
-            throw new RuntimeException("Unable to create copy of existing graph: ", e);
-        }
-
-        for (V v : g.getVertices())
-            filtered.addVertex(v);
-        
-        for (E e : g.getEdges())
-        {
-            if (edge_pred.evaluate(e))
-                filtered.addEdge(e, g.getIncidentVertices(e));
-        }
-        
-        return filtered;
-    }
-
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/Filter.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/Filter.java
deleted file mode 100644 (file)
index a62895c..0000000
+++ /dev/null
@@ -1,26 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.filters;
-
-import org.apache.commons.collections15.Transformer;
-
-import edu.uci.ics.jung.graph.Graph;
-
-
-
-/**
- * An interface for classes that return a subset of the input <code>Graph</code>
- * as a <code>Graph</code>.  The <code>Graph</code> returned may be either a
- * new graph or a view into an existing graph; the documentation for the filter
- * must specify which.
- * 
- * @author danyelf
- */
-public interface Filter<V,E> extends Transformer<Graph<V,E>, Graph<V,E>>{ }
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/FilterUtils.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/FilterUtils.java
deleted file mode 100644 (file)
index 4845c0f..0000000
+++ /dev/null
@@ -1,98 +0,0 @@
-/**
- * Copyright (c) 2008, the JUNG Project and the Regents of the University 
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- * Created on Jun 7, 2008
- * 
- */
-package edu.uci.ics.jung.algorithms.filters;
-
-import java.util.ArrayList;
-import java.util.Collection;
-
-import edu.uci.ics.jung.graph.Hypergraph;
-
-/**
- * Utility methods relating to filtering.
- */
-public class FilterUtils 
-{
-       /**
-        * Creates the induced subgraph from <code>graph</code> whose vertex set
-        * is equal to <code>vertices</code>.  The graph returned has 
-        * <code>vertices</code> as its vertex set, and includes all edges from
-        * <code>graph</code> which are incident only to elements of 
-        * <code>vertices</code>.
-        * 
-        * @param <V> the vertex type
-        * @param <E> the edge type
-        * @param vertices the subset of <code>graph</code>'s vertices around 
-        * which the subgraph is to be constructed
-        * @param graph the graph whose subgraph is to be constructed
-        * @return the subgraph induced by <code>vertices</code>
-        * @throws IllegalArgumentException if any vertex in 
-        * <code>vertices</code> is not in <code>graph</code>
-        */
-       @SuppressWarnings("unchecked")
-       public static <V,E,G extends Hypergraph<V,E>> G createInducedSubgraph(Collection<V> 
-               vertices, G graph)
-       {
-               G subgraph = null;
-               try 
-               {
-                       subgraph = (G)graph.getClass().newInstance();
-                       
-                       for (V v : vertices)
-                       {
-                               if (!graph.containsVertex(v))
-                                       throw new IllegalArgumentException("Vertex " + v + 
-                                               " is not an element of " + graph);
-                               subgraph.addVertex(v);
-                       }
-
-                       for (E e : graph.getEdges())
-                       {
-                               Collection<V> incident = graph.getIncidentVertices(e);
-                               if (vertices.containsAll(incident))
-                                       subgraph.addEdge(e, incident, graph.getEdgeType(e));
-                       }
-               } 
-        catch (InstantiationException e)
-        {
-            throw new RuntimeException("Unable to create copy of existing graph: ", e);
-        }
-        catch (IllegalAccessException e)
-        {
-            throw new RuntimeException("Unable to create copy of existing graph: ", e);
-        }
-               return subgraph;
-       }
-       
-       /**
-        * Creates the induced subgraphs of <code>graph</code> associated with each 
-        * element of <code>vertex_collections</code>.
-        * Note that these vertex collections need not be disjoint.
-        * @param <V> the vertex type
-        * @param <E> the edge type
-        * @param vertex_collections the collections of vertex collections to be
-        * used to induce the subgraphs
-        * @param graph the graph whose subgraphs are to be created
-        * @return the induced subgraphs of <code>graph</code> associated with each 
-        * element of <code>vertex_collections</code>
-        */
-       public static <V,E,G extends Hypergraph<V,E>> Collection<G> 
-               createAllInducedSubgraphs(Collection<? extends Collection<V>> 
-                       vertex_collections, G graph)
-       {
-               Collection<G> subgraphs = new ArrayList<G>();
-               
-               for (Collection<V> vertex_set : vertex_collections)
-                       subgraphs.add(createInducedSubgraph(vertex_set, graph));
-               
-               return subgraphs;
-       }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.java
deleted file mode 100644 (file)
index 62bcfc2..0000000
+++ /dev/null
@@ -1,142 +0,0 @@
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University 
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-/*
- * Created on Dec 26, 2001
- *
- */
-package edu.uci.ics.jung.algorithms.filters;
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Set;
-
-import edu.uci.ics.jung.algorithms.filters.Filter;
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.util.Pair;
-
-/**
- * A filter used to extract the k-neighborhood around one or more root node(s).
- * The k-neighborhood is defined as the subgraph induced by the set of 
- * vertices that are k or fewer hops (unweighted shortest-path distance)
- * away from the root node.
- * 
- * @author Danyel Fisher
- */
-public class KNeighborhoodFilter<V,E> implements Filter<V,E> {
-
-       /**
-        * The type of edge to follow for defining the neighborhood.
-        */
-       public static enum EdgeType { IN_OUT, IN, OUT }
-       private Set<V> rootNodes;
-       private int radiusK;
-       private EdgeType edgeType;
-       
-       /**
-        * Constructs a new instance of the filter.
-        * @param rootNodes the set of root nodes
-        * @param radiusK the neighborhood radius around the root set
-        * @param edgeType 0 for in/out edges, 1 for in-edges, 2  for out-edges
-        */
-       public KNeighborhoodFilter(Set<V> rootNodes, int radiusK, EdgeType edgeType) {
-               this.rootNodes = rootNodes;
-               this.radiusK = radiusK;
-               this.edgeType = edgeType;
-       }
-       
-       /**
-        * Constructs a new instance of the filter.
-        * @param rootNode the root node
-        * @param radiusK the neighborhood radius around the root set
-        * @param edgeType 0 for in/out edges, 1 for in-edges, 2  for out-edges
-        */
-       public KNeighborhoodFilter(V rootNode, int radiusK, EdgeType edgeType) {
-               this.rootNodes = new HashSet<V>();
-               this.rootNodes.add(rootNode);
-               this.radiusK = radiusK;
-               this.edgeType = edgeType;
-       }
-       
-       /**
-        * Constructs an unassembled graph containing the k-neighborhood around the root node(s).
-        */
-       @SuppressWarnings("unchecked")
-       public Graph<V,E> transform(Graph<V,E> graph) {
-               // generate a Set of Vertices we want
-               // add all to the UG
-               int currentDepth = 0;
-               List<V> currentVertices = new ArrayList<V>();
-               Set<V> visitedVertices = new HashSet<V>();
-               Set<E> visitedEdges = new HashSet<E>();
-               Set<V> acceptedVertices = new HashSet<V>();
-               //Copy, mark, and add all the root nodes to the new subgraph
-               for (V currentRoot : rootNodes) {
-
-                       visitedVertices.add(currentRoot);
-                       acceptedVertices.add(currentRoot);
-                       currentVertices.add(currentRoot);
-               }
-               ArrayList<V> newVertices = null;
-               //Use BFS to locate the neighborhood around the root nodes within distance k
-               while (currentDepth < radiusK) {
-                       newVertices = new ArrayList<V>();
-                       for (V currentVertex : currentVertices) {
-
-                               Collection<E> edges = null;
-                               switch (edgeType) {
-                                       case IN_OUT :
-                                               edges = graph.getIncidentEdges(currentVertex);
-                                               break;
-                                       case IN :
-                                               edges = graph.getInEdges(currentVertex);
-                                               break;
-                                       case OUT :
-                                               edges = graph.getOutEdges(currentVertex);
-                                               break;
-                               }
-                               for (E currentEdge : edges) {
-
-                                       V currentNeighbor =
-                                               graph.getOpposite(currentVertex, currentEdge);
-                                       if (!visitedEdges.contains(currentEdge)) {
-                                               visitedEdges.add(currentEdge);
-                                               if (!visitedVertices.contains(currentNeighbor)) {
-                                                       visitedVertices.add(currentNeighbor);
-                                                       acceptedVertices.add(currentNeighbor);
-                                                       newVertices.add(currentNeighbor);
-                                               }
-                                       }
-                               }
-                       }
-                       currentVertices = newVertices;
-                       currentDepth++;
-               }
-               Graph<V,E> ug = null;
-               try {
-                       ug = graph.getClass().newInstance();
-                       for(E edge : graph.getEdges()) {
-                               Pair<V> endpoints = graph.getEndpoints(edge);
-                               if(acceptedVertices.containsAll(endpoints)) {
-                                       ug.addEdge(edge, endpoints.getFirst(), endpoints.getSecond());
-                               }
-                       }
-               } 
-        catch (InstantiationException e)
-        {
-            throw new RuntimeException("Unable to create copy of existing graph: ", e);
-        }
-        catch (IllegalAccessException e)
-        {
-            throw new RuntimeException("Unable to create copy of existing graph: ", e);
-        }
-               return ug;
-       }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/VertexPredicateFilter.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/VertexPredicateFilter.java
deleted file mode 100644 (file)
index 4543b42..0000000
+++ /dev/null
@@ -1,75 +0,0 @@
-/*
- * Created on May 19, 2008
- *
- * Copyright (c) 2008, the JUNG Project and the Regents of the University 
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-package edu.uci.ics.jung.algorithms.filters;
-
-import java.util.Collection;
-
-import org.apache.commons.collections15.Predicate;
-
-import edu.uci.ics.jung.graph.Graph;
-
-/**
- * Transforms the input graph into one which contains only those vertices 
- * that pass the specified <code>Predicate</code>.  The filtered graph
- * is a copy of the original graph (same type, uses the same vertex and
- * edge objects).  Only those edges whose entire incident vertex collection
- * passes the predicate are copied into the new graph.
- * 
- * @author Joshua O'Madadhain
- */
-public class VertexPredicateFilter<V,E> implements Filter<V,E>
-{
-    protected Predicate<V> vertex_pred;
-
-    /**
-     * Creates an instance based on the specified vertex <code>Predicate</code>.
-     * @param vertex_pred   the predicate that specifies which vertices to add to the filtered graph
-     */
-    public VertexPredicateFilter(Predicate<V> vertex_pred)
-    {
-        this.vertex_pred = vertex_pred;
-    }
-    
-    @SuppressWarnings("unchecked")
-       public Graph<V,E> transform(Graph<V,E> g)
-    {
-        Graph<V, E> filtered;
-        try
-        {
-            filtered = g.getClass().newInstance();
-        }
-        catch (InstantiationException e)
-        {
-            throw new RuntimeException("Unable to create copy of existing graph: ", e);
-        }
-        catch (IllegalAccessException e)
-        {
-            throw new RuntimeException("Unable to create copy of existing graph: ", e);
-        }
-
-        for (V v : g.getVertices())
-            if (vertex_pred.evaluate(v))
-                filtered.addVertex(v);
-        
-        Collection<V> filtered_vertices = filtered.getVertices();
-        
-        for (E e : g.getEdges())
-        {
-            Collection<V> incident = g.getIncidentVertices(e);
-            if (filtered_vertices.containsAll(incident))
-                filtered.addEdge(e, incident);
-        }
-        
-        return filtered;
-    }
-
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/package.html b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/package.html
deleted file mode 100644 (file)
index 0f9a018..0000000
+++ /dev/null
@@ -1,31 +0,0 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
-<html>
-<head>
-<!--
-
-  @(#)package.html
-
- Copyright © 2008 The Regents of the University of California. All Rights Reserved. Permission to use, copy, modify, and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice, this paragraph and the following two paragraphs appear in all copies. This software program and documentation are copyrighted by The Regents of the University of California ("The University of California").
-
-THE SOFTWARE PROGRAM AND DOCUMENTATION ARE SUPPLIED "AS IS," WITHOUT ANY ACCOMPANYING SERVICES FROM THE UNIVERSITY OF CALFORNIA. FURTHERMORE, THE UNIVERSITY OF CALIFORNIA DOES NOT WARRANT THAT THE OPERATION OF THE PROGRAM WILL BE UNINTERRUPTED OR ERROR-FREE. THE END-USER UNDERSTANDS THAT THE PROGRAM WAS DEVELOPED FOR RESEARCH PURPOSES AND IS ADVISED NOT TO RELY EXCLUSIVELY ON THE PROGRAM FOR ANY REASON.
-
-IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 
--->
-</head>
-<body>
-
-Filtering mechanisms that produce subgraphs of an original graph. 
-Currently includes:
-<ul>
-<li/><code>Filter</code>: an interface for graph filters
-<li/><code>{Edge,Vertex}PredicateFilter</code>: graph filters that return the 
-induced subgraph according to the
-specified edge or vertex <code>Predicate</code>, respectively.
-<li/><code>KNeighborhoodFilter</code>: a filter that returns the subgraph 
-induced by vertices within (unweighted) distance k of a specified vertex.
-</ul>
-
-
-</body>
-</html>
-
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.java
deleted file mode 100644 (file)
index af9ee34..0000000
+++ /dev/null
@@ -1,314 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.flows;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-import org.apache.commons.collections15.Buffer;
-import org.apache.commons.collections15.Factory;
-import org.apache.commons.collections15.Transformer;
-import org.apache.commons.collections15.buffer.UnboundedFifoBuffer;
-
-import edu.uci.ics.jung.algorithms.util.IterativeProcess;
-import edu.uci.ics.jung.graph.DirectedGraph;
-import edu.uci.ics.jung.graph.util.EdgeType;
-
-
-/**
- * Implements the Edmonds-Karp maximum flow algorithm for solving the maximum flow problem. 
- * After the algorithm is executed,
- * the input {@code Map} is populated with a {@code Number} for each edge that indicates 
- * the flow along that edge.
- * <p>
- * An example of using this algorithm is as follows:
- * <pre>
- * EdmondsKarpMaxFlow ek = new EdmondsKarpMaxFlow(graph, source, sink, edge_capacities, edge_flows, 
- * edge_factory);
- * ek.evaluate(); // This instructs the class to compute the max flow
- * </pre>
- *
- * @see "Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein."
- * @see "Network Flows by Ahuja, Magnanti, and Orlin."
- * @see "Theoretical improvements in algorithmic efficiency for network flow problems by Edmonds and Karp, 1972."
- * @author Scott White, adapted to jung2 by Tom Nelson
- */
-public class EdmondsKarpMaxFlow<V,E> extends IterativeProcess {
-
-    private DirectedGraph<V,E> mFlowGraph;
-    private DirectedGraph<V,E> mOriginalGraph;
-    private V source;
-    private V target;
-    private int mMaxFlow;
-    private Set<V> mSourcePartitionNodes;
-    private Set<V> mSinkPartitionNodes;
-    private Set<E> mMinCutEdges;
-    
-    private Map<E,Number> residualCapacityMap = new HashMap<E,Number>();
-    private Map<V,V> parentMap = new HashMap<V,V>();
-    private Map<V,Number> parentCapacityMap = new HashMap<V,Number>();
-    private Transformer<E,Number> edgeCapacityTransformer;
-    private Map<E,Number> edgeFlowMap;
-    private Factory<E> edgeFactory;
-
-    /**
-     * Constructs a new instance of the algorithm solver for a given graph, source, and sink.
-     * Source and sink vertices must be elements of the specified graph, and must be 
-     * distinct.
-     * @param directedGraph the flow graph
-     * @param source the source vertex
-     * @param sink the sink vertex
-     * @param edgeCapacityTransformer the transformer that gets the capacity for each edge.
-     * @param edgeFlowMap the map where the solver will place the value of the flow for each edge
-     * @param edgeFactory used to create new edge instances for backEdges
-     */
-    @SuppressWarnings("unchecked")
-    public EdmondsKarpMaxFlow(DirectedGraph<V,E> directedGraph, V source, V sink, 
-               Transformer<E,Number> edgeCapacityTransformer, Map<E,Number> edgeFlowMap,
-               Factory<E> edgeFactory) {
-       
-       if(directedGraph.getVertices().contains(source) == false ||
-                       directedGraph.getVertices().contains(sink) == false) {
-            throw new IllegalArgumentException("source and sink vertices must be elements of the specified graph");
-       }
-        if (source.equals(sink)) {
-            throw new IllegalArgumentException("source and sink vertices must be distinct");
-        }
-        mOriginalGraph = directedGraph;
-
-        this.source = source;
-        this.target = sink;
-        this.edgeFlowMap = edgeFlowMap;
-        this.edgeCapacityTransformer = edgeCapacityTransformer;
-        this.edgeFactory = edgeFactory;
-        try {
-                       mFlowGraph = directedGraph.getClass().newInstance();
-                       for(E e : mOriginalGraph.getEdges()) {
-                               mFlowGraph.addEdge(e, mOriginalGraph.getSource(e), 
-                                               mOriginalGraph.getDest(e), EdgeType.DIRECTED);
-                       }
-                       for(V v : mOriginalGraph.getVertices()) {
-                               mFlowGraph.addVertex(v);
-                       }
-
-               } catch (InstantiationException e) {
-                       e.printStackTrace();
-               } catch (IllegalAccessException e) {
-                       e.printStackTrace();
-               }
-        mMaxFlow = 0;
-        mSinkPartitionNodes = new HashSet<V>();
-        mSourcePartitionNodes = new HashSet<V>();
-        mMinCutEdges = new HashSet<E>();
-    }
-
-    private void clearParentValues() {
-       parentMap.clear();
-       parentCapacityMap.clear();
-        parentCapacityMap.put(source, Integer.MAX_VALUE);
-        parentMap.put(source, source);
-    }
-
-    protected boolean hasAugmentingPath() {
-
-        mSinkPartitionNodes.clear();
-        mSourcePartitionNodes.clear();
-        mSinkPartitionNodes.addAll(mFlowGraph.getVertices());
-
-        Set<E> visitedEdgesMap = new HashSet<E>();
-        Buffer<V> queue = new UnboundedFifoBuffer<V>();
-        queue.add(source);
-
-        while (!queue.isEmpty()) {
-            V currentVertex = queue.remove();
-            mSinkPartitionNodes.remove(currentVertex);
-            mSourcePartitionNodes.add(currentVertex);
-            Number currentCapacity = parentCapacityMap.get(currentVertex);
-
-            Collection<E> neighboringEdges = mFlowGraph.getOutEdges(currentVertex);
-            
-            for (E neighboringEdge : neighboringEdges) {
-
-                V neighboringVertex = mFlowGraph.getDest(neighboringEdge);
-
-                Number residualCapacity = residualCapacityMap.get(neighboringEdge);
-                if (residualCapacity.intValue() <= 0 || visitedEdgesMap.contains(neighboringEdge))
-                    continue;
-
-                V neighborsParent = parentMap.get(neighboringVertex);
-                Number neighborCapacity = parentCapacityMap.get(neighboringVertex);
-                int newCapacity = Math.min(residualCapacity.intValue(),currentCapacity.intValue());
-
-                if ((neighborsParent == null) || newCapacity > neighborCapacity.intValue()) {
-                    parentMap.put(neighboringVertex, currentVertex);
-                    parentCapacityMap.put(neighboringVertex, new Integer(newCapacity));
-                    visitedEdgesMap.add(neighboringEdge);
-                    if (neighboringVertex != target) {
-                       queue.add(neighboringVertex);
-                    }
-                }
-            }
-        }
-
-        boolean hasAugmentingPath = false;
-        Number targetsParentCapacity = parentCapacityMap.get(target);
-        if (targetsParentCapacity != null && targetsParentCapacity.intValue() > 0) {
-            updateResidualCapacities();
-            hasAugmentingPath = true;
-        }
-        clearParentValues();
-        return hasAugmentingPath;
-    }
-
-     @Override
-    public void step() {
-        while (hasAugmentingPath()) {
-        }
-        computeMinCut();
-//        return 0;
-    }
-
-    private void computeMinCut() {
-
-        for (E e : mOriginalGraph.getEdges()) {
-
-               V source = mOriginalGraph.getSource(e);
-               V destination = mOriginalGraph.getDest(e);
-            if (mSinkPartitionNodes.contains(source) && mSinkPartitionNodes.contains(destination)) {
-                continue;
-            }
-            if (mSourcePartitionNodes.contains(source) && mSourcePartitionNodes.contains(destination)) {
-                continue;
-            }
-            if (mSinkPartitionNodes.contains(source) && mSourcePartitionNodes.contains(destination)) {
-                continue;
-            }
-            mMinCutEdges.add(e);
-        }
-    }
-
-    /**
-     * Returns the value of the maximum flow from the source to the sink.
-     */
-    public int getMaxFlow() {
-        return mMaxFlow;
-    }
-
-    /**
-     * Returns the nodes which share the same partition (as defined by the min-cut edges)
-     * as the sink node.
-     */
-    public Set<V> getNodesInSinkPartition() {
-        return mSinkPartitionNodes;
-    }
-
-    /**
-     * Returns the nodes which share the same partition (as defined by the min-cut edges)
-     * as the source node.
-     */
-    public Set<V> getNodesInSourcePartition() {
-        return mSourcePartitionNodes;
-    }
-
-    /**
-     * Returns the edges in the minimum cut.
-     */
-    public Set<E> getMinCutEdges() {
-        return mMinCutEdges;
-    }
-
-    /**
-     * Returns the graph for which the maximum flow is calculated.
-     */
-    public DirectedGraph<V,E> getFlowGraph() {
-        return mFlowGraph;
-    }
-
-    @Override
-    protected void initializeIterations() {
-        parentCapacityMap.put(source, Integer.MAX_VALUE);
-        parentMap.put(source, source);
-
-        List<E> edgeList = new ArrayList<E>(mFlowGraph.getEdges());
-
-        for (int eIdx=0;eIdx< edgeList.size();eIdx++) {
-            E edge = edgeList.get(eIdx);
-            Number capacity = edgeCapacityTransformer.transform(edge);
-
-            if (capacity == null) {
-                throw new IllegalArgumentException("Edge capacities must be provided in Transformer passed to constructor");
-            }
-            residualCapacityMap.put(edge, capacity);
-
-            V source = mFlowGraph.getSource(edge);
-            V destination = mFlowGraph.getDest(edge);
-
-            if(mFlowGraph.isPredecessor(source, destination) == false) {
-               E backEdge = edgeFactory.create();
-               mFlowGraph.addEdge(backEdge, destination, source, EdgeType.DIRECTED);
-                residualCapacityMap.put(backEdge, 0);
-            }
-        }
-    }
-    
-    @Override
-    protected void finalizeIterations() {
-
-        for (E currentEdge : mFlowGraph.getEdges()) {
-            Number capacity = edgeCapacityTransformer.transform(currentEdge);
-            
-            Number residualCapacity = residualCapacityMap.get(currentEdge);
-            if (capacity != null) {
-                Integer flowValue = new Integer(capacity.intValue()-residualCapacity.intValue());
-                this.edgeFlowMap.put(currentEdge, flowValue);
-            }
-        }
-
-        Set<E> backEdges = new HashSet<E>();
-        for (E currentEdge: mFlowGraph.getEdges()) {
-               
-            if (edgeCapacityTransformer.transform(currentEdge) == null) {
-                backEdges.add(currentEdge);
-            } else {
-                residualCapacityMap.remove(currentEdge);
-            }
-        }
-        for(E e : backEdges) {
-               mFlowGraph.removeEdge(e);
-        }
-    }
-
-    private void updateResidualCapacities() {
-
-        Number augmentingPathCapacity = parentCapacityMap.get(target);
-        mMaxFlow += augmentingPathCapacity.intValue();
-        V currentVertex = target;
-        V parentVertex = null;
-        while ((parentVertex = parentMap.get(currentVertex)) != currentVertex) {
-            E currentEdge = mFlowGraph.findEdge(parentVertex, currentVertex);
-
-            Number residualCapacity = residualCapacityMap.get(currentEdge);
-
-            residualCapacity = residualCapacity.intValue() - augmentingPathCapacity.intValue();
-            residualCapacityMap.put(currentEdge, residualCapacity);
-
-            E backEdge = mFlowGraph.findEdge(currentVertex, parentVertex);
-            residualCapacity = residualCapacityMap.get(backEdge);
-            residualCapacity = residualCapacity.intValue() + augmentingPathCapacity.intValue();
-            residualCapacityMap.put(backEdge, residualCapacity);
-            currentVertex = parentVertex;
-        }
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/flows/package.html b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/flows/package.html
deleted file mode 100644 (file)
index 1ec243d..0000000
+++ /dev/null
@@ -1,20 +0,0 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
-<html>
-<head>
-<!--
-
-  @(#)package.html
-
- Copyright © 2003 The Regents of the University of California. All Rights Reserved. Permission to use, copy, modify, and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice, this paragraph and the following two paragraphs appear in all copies. This software program and documentation are copyrighted by The Regents of the University of California ("The University of California").
-
-THE SOFTWARE PROGRAM AND DOCUMENTATION ARE SUPPLIED "AS IS," WITHOUT ANY ACCOMPANYING SERVICES FROM THE UNIVERSITY OF CALFORNIA. FURTHERMORE, THE UNIVERSITY OF CALIFORNIA DOES NOT WARRANT THAT THE OPERATION OF THE PROGRAM WILL BE UNINTERRUPTED OR ERROR-FREE. THE END-USER UNDERSTANDS THAT THE PROGRAM WAS DEVELOPED FOR RESEARCH PURPOSES AND IS ADVISED NOT TO RELY EXCLUSIVELY ON THE PROGRAM FOR ANY REASON.
-
-IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
--->
-</head>
-<body>
-
-Methods for calculating properties relating to network flows (such as max flow/min cut).
-
-</body>
-</html>
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/EvolvingGraphGenerator.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/EvolvingGraphGenerator.java
deleted file mode 100644 (file)
index d351f9b..0000000
+++ /dev/null
@@ -1,31 +0,0 @@
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University 
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-package edu.uci.ics.jung.algorithms.generators;
-
-
-
-/**
- * An interface for algorithms that generate graphs that evolve iteratively.
- * @author Scott White
- */
-public interface EvolvingGraphGenerator<V, E> extends GraphGenerator<V,E> {
-
-    /**
-     * Instructs the algorithm to evolve the graph N steps.
-     * @param numSteps number of steps to iterate from the current state
-     */
-    void evolveGraph(int numSteps);
-
-    /**
-     * Retrieves the total number of steps elapsed.
-     * @return number of elapsed steps
-     */
-    int numIterations();
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/GraphGenerator.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/GraphGenerator.java
deleted file mode 100644 (file)
index a329060..0000000
+++ /dev/null
@@ -1,20 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.generators;
-
-import org.apache.commons.collections15.Factory;
-
-import edu.uci.ics.jung.graph.Graph;
-
-/**
- * An interface for algorithms that generate graphs.
- * @author Scott White
- */
-public interface GraphGenerator<V, E> extends Factory<Graph<V,E>>{ }
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/Lattice2DGenerator.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/Lattice2DGenerator.java
deleted file mode 100644 (file)
index e84425c..0000000
+++ /dev/null
@@ -1,188 +0,0 @@
-/*
- * Copyright (c) 2009, the JUNG Project and the Regents of the University 
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-
-package edu.uci.ics.jung.algorithms.generators;
-
-import java.util.ArrayList;
-import java.util.List;
-
-import org.apache.commons.collections15.Factory;
-
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.util.EdgeType;
-
-/**
- * Simple generator of an m x n lattice where each vertex
- * is incident with each of its neighbors (to the left, right, up, and down).
- * May be toroidal, in which case the vertices on the edges are connected to
- * their counterparts on the opposite edges as well.
- * 
- * <p>If the graph factory supplied has a default edge type of {@code EdgeType.DIRECTED},
- * then edges will be created in both directions between adjacent vertices.
- * 
- * @author Joshua O'Madadhain
- */
-public class Lattice2DGenerator<V,E> implements GraphGenerator<V,E>
-{
-    protected int row_count;
-    protected int col_count;
-    protected boolean is_toroidal;
-    protected boolean is_directed;
-    protected Factory<? extends Graph<V, E>> graph_factory;
-    protected Factory<V> vertex_factory;
-    protected Factory<E> edge_factory;
-    private List<V> v_array;
-
-    /**
-     * Constructs a generator of square lattices of size {@code latticeSize} 
-     * with the specified parameters.
-     * 
-     * @param graph_factory used to create the {@code Graph} for the lattice
-     * @param vertex_factory used to create the lattice vertices
-     * @param edge_factory used to create the lattice edges
-     * @param latticeSize the number of rows and columns of the lattice
-     * @param isToroidal if true, the created lattice wraps from top to bottom and left to right
-     */
-    public Lattice2DGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory, 
-            Factory<E> edge_factory, int latticeSize, boolean isToroidal)
-    {
-        this(graph_factory, vertex_factory, edge_factory, latticeSize, latticeSize, isToroidal);
-    }
-
-    /**
-     * Creates a generator of {@code row_count} x {@code col_count} lattices 
-     * with the specified parameters.
-     * 
-     * @param graph_factory used to create the {@code Graph} for the lattice
-     * @param vertex_factory used to create the lattice vertices
-     * @param edge_factory used to create the lattice edges
-     * @param row_count the number of rows in the lattice
-     * @param col_count the number of columns in the lattice
-     * @param isToroidal if true, the created lattice wraps from top to bottom and left to right
-     */
-    public Lattice2DGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory, 
-            Factory<E> edge_factory, int row_count, int col_count, boolean isToroidal)
-    {
-        if (row_count < 2 || col_count < 2)
-        {
-            throw new IllegalArgumentException("Row and column counts must each be at least 2.");
-        }
-
-        this.row_count = row_count;
-        this.col_count = col_count;
-        this.is_toroidal = isToroidal;
-        this.graph_factory = graph_factory;
-        this.vertex_factory = vertex_factory;
-        this.edge_factory = edge_factory;
-        this.is_directed = (graph_factory.create().getDefaultEdgeType() == EdgeType.DIRECTED);
-    }
-    
-    /**
-     * @see edu.uci.ics.jung.algorithms.generators.GraphGenerator#create()
-     */
-    @SuppressWarnings("unchecked")
-    public Graph<V,E> create()
-    {
-        int vertex_count = row_count * col_count;
-        Graph<V,E> graph = graph_factory.create();
-        v_array = new ArrayList<V>(vertex_count);
-        for (int i = 0; i < vertex_count; i++)
-        {
-            V v = vertex_factory.create();
-            graph.addVertex(v);
-            v_array.add(i, v);
-        }
-
-        int start = is_toroidal ? 0 : 1;
-        int end_row = is_toroidal ? row_count : row_count - 1;
-        int end_col = is_toroidal ? col_count : col_count - 1;
-        
-        // fill in edges
-        // down
-        for (int i = 0; i < end_row; i++)
-            for (int j = 0; j < col_count; j++)
-                graph.addEdge(edge_factory.create(), getVertex(i,j), getVertex(i+1, j));
-        // right
-        for (int i = 0; i < row_count; i++)
-            for (int j = 0; j < end_col; j++)
-                graph.addEdge(edge_factory.create(), getVertex(i,j), getVertex(i, j+1));
-
-        // if the graph is directed, fill in the edges going the other direction...
-        if (graph.getDefaultEdgeType() == EdgeType.DIRECTED)
-        {
-            // up
-            for (int i = start; i < row_count; i++)
-                for (int j = 0; j < col_count; j++)
-                    graph.addEdge(edge_factory.create(), getVertex(i,j), getVertex(i-1, j));
-            // left
-            for (int i = 0; i < row_count; i++)
-                for (int j = start; j < col_count; j++)
-                    graph.addEdge(edge_factory.create(), getVertex(i,j), getVertex(i, j-1));
-        }
-        
-        return graph;
-    }
-
-    /**
-     * Returns the number of edges found in a lattice of this generator's specifications.
-     * (This is useful for subclasses that may modify the generated graphs to add more edges.)
-     */
-    public int getGridEdgeCount()
-    {
-        int boundary_adjustment = (is_toroidal ? 0 : 1);
-        int vertical_edge_count = col_count * (row_count - boundary_adjustment);
-        int horizontal_edge_count = row_count * (col_count - boundary_adjustment);
-        
-        return (vertical_edge_count + horizontal_edge_count) * (is_directed ? 2 : 1);
-    }
-    
-    protected int getIndex(int i, int j)
-    {
-        return ((mod(i, row_count)) * col_count) + (mod(j, col_count));
-    }
-
-    protected int mod(int i, int modulus) 
-    {
-        int i_mod = i % modulus;
-        return i_mod >= 0 ? i_mod : i_mod + modulus;
-    }
-    
-    /**
-     * Returns the vertex at position ({@code i mod row_count, j mod col_count}).
-     */
-    protected V getVertex(int i, int j)
-    {
-        return v_array.get(getIndex(i, j));
-    }
-    
-    /**
-     * Returns the {@code i}th vertex (counting row-wise).
-     */
-    protected V getVertex(int i)
-    {
-        return v_array.get(i);
-    }
-    
-    /**
-     * Returns the row in which vertex {@code i} is found.
-     */
-    protected int getRow(int i)
-    {
-        return i / row_count;
-    }
-    
-    /**
-     * Returns the column in which vertex {@code i} is found.
-     */
-    protected int getCol(int i)
-    {
-        return i % col_count;
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/package.html b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/package.html
deleted file mode 100644 (file)
index 441922d..0000000
+++ /dev/null
@@ -1,20 +0,0 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
-<html>
-<head>
-<!--
-
-  @(#)package.html
-
- Copyright © 2003 The Regents of the University of California. All Rights Reserved. Permission to use, copy, modify, and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice, this paragraph and the following two paragraphs appear in all copies. This software program and documentation are copyrighted by The Regents of the University of California ("The University of California").
-
-THE SOFTWARE PROGRAM AND DOCUMENTATION ARE SUPPLIED "AS IS," WITHOUT ANY ACCOMPANYING SERVICES FROM THE UNIVERSITY OF CALFORNIA. FURTHERMORE, THE UNIVERSITY OF CALIFORNIA DOES NOT WARRANT THAT THE OPERATION OF THE PROGRAM WILL BE UNINTERRUPTED OR ERROR-FREE. THE END-USER UNDERSTANDS THAT THE PROGRAM WAS DEVELOPED FOR RESEARCH PURPOSES AND IS ADVISED NOT TO RELY EXCLUSIVELY ON THE PROGRAM FOR ANY REASON.
-
-IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
--->
-</head>
-<body>
-
-Methods for generating new (often random) graphs with various properties.
-
-</body>
-</html>
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/BarabasiAlbertGenerator.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/BarabasiAlbertGenerator.java
deleted file mode 100644 (file)
index 77b419b..0000000
+++ /dev/null
@@ -1,227 +0,0 @@
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University 
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-package edu.uci.ics.jung.algorithms.generators.random;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Map;
-import java.util.Random;
-import java.util.Set;
-
-import org.apache.commons.collections15.Factory;
-
-import edu.uci.ics.jung.algorithms.generators.EvolvingGraphGenerator;
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.MultiGraph;
-import edu.uci.ics.jung.graph.util.EdgeType;
-import edu.uci.ics.jung.graph.util.Pair;
-
-
-/**
- * <p>Simple evolving scale-free random graph generator. At each time
- * step, a new vertex is created and is connected to existing vertices
- * according to the principle of "preferential attachment", whereby 
- * vertices with higher degree have a higher probability of being 
- * selected for attachment.</p>
- * 
- * <p>At a given timestep, the probability <code>p</code> of creating an edge
- * between an existing vertex <code>v</code> and the newly added vertex is
- * <pre>
- * p = (degree(v) + 1) / (|E| + |V|);
- * </pre>
- * 
- * <p>where <code>|E|</code> and <code>|V|</code> are, respectively, the number 
- * of edges and vertices currently in the network (counting neither the new
- * vertex nor the other edges that are being attached to it).</p>
- * 
- * <p>Note that the formula specified in the original paper
- * (cited below) was
- * <pre>
- * p = degree(v) / |E|
- * </pre>
- * </p>
- * 
- * <p>However, this would have meant that the probability of attachment for any existing
- * isolated vertex would be 0.  This version uses Lagrangian smoothing to give
- * each existing vertex a positive attachment probability.</p>
- * 
- * <p>The graph created may be either directed or undirected (controlled by a constructor
- * parameter); the default is undirected.  
- * If the graph is specified to be directed, then the edges added will be directed
- * from the newly added vertex u to the existing vertex v, with probability proportional to the 
- * indegree of v (number of edges directed towards v).  If the graph is specified to be undirected,
- * then the (undirected) edges added will connect u to v, with probability proportional to the 
- * degree of v.</p> 
- * 
- * <p>The <code>parallel</code> constructor parameter specifies whether parallel edges
- * may be created.</p>
- * 
- * @see "A.-L. Barabasi and R. Albert, Emergence of scaling in random networks, Science 286, 1999."
- * @author Scott White
- * @author Joshua O'Madadhain
- * @author Tom Nelson - adapted to jung2
- */
-public class BarabasiAlbertGenerator<V,E> implements EvolvingGraphGenerator<V,E> {
-    private Graph<V, E> mGraph = null;
-    private int mNumEdgesToAttachPerStep;
-    private int mElapsedTimeSteps;
-    private Random mRandom;
-    protected List<V> vertex_index;
-    protected int init_vertices;
-    protected Map<V,Integer> index_vertex;
-    protected Factory<Graph<V,E>> graphFactory;
-    protected Factory<V> vertexFactory;
-    protected Factory<E> edgeFactory;
-    
-    /**
-     * Constructs a new instance of the generator.
-     * @param init_vertices     number of unconnected 'seed' vertices that the graph should start with
-     * @param numEdgesToAttach the number of edges that should be attached from the
-     * new vertex to pre-existing vertices at each time step
-     * @param directed  specifies whether the graph and edges to be created should be directed or not
-     * @param parallel  specifies whether the algorithm permits parallel edges
-     * @param seed  random number seed
-     */
-    public BarabasiAlbertGenerator(Factory<Graph<V,E>> graphFactory,
-               Factory<V> vertexFactory, Factory<E> edgeFactory, 
-               int init_vertices, int numEdgesToAttach, 
-            int seed, Set<V> seedVertices)
-    {
-        assert init_vertices > 0 : "Number of initial unconnected 'seed' vertices " + 
-                    "must be positive";
-        assert numEdgesToAttach > 0 : "Number of edges to attach " +
-                    "at each time step must be positive";
-        
-        mNumEdgesToAttachPerStep = numEdgesToAttach;
-        mRandom = new Random(seed);
-        this.graphFactory = graphFactory;
-        this.vertexFactory = vertexFactory;
-        this.edgeFactory = edgeFactory;
-        this.init_vertices = init_vertices;
-        initialize(seedVertices);
-    }
-    
-
-    /**
-     * Constructs a new instance of the generator, whose output will be an undirected graph,
-     * and which will use the current time as a seed for the random number generation.
-     * @param init_vertices     number of vertices that the graph should start with
-     * @param numEdgesToAttach the number of edges that should be attached from the
-     * new vertex to pre-existing vertices at each time step
-     */
-    public BarabasiAlbertGenerator(Factory<Graph<V,E>> graphFactory, 
-               Factory<V> vertexFactory, Factory<E> edgeFactory,
-               int init_vertices, int numEdgesToAttach, Set<V> seedVertices) {
-        this(graphFactory, vertexFactory, edgeFactory, init_vertices, numEdgesToAttach, (int) System.currentTimeMillis(), seedVertices);
-    }
-    
-    private void initialize(Set<V> seedVertices) {
-       
-       mGraph = graphFactory.create();
-
-        vertex_index = new ArrayList<V>(2*init_vertices);
-        index_vertex = new HashMap<V, Integer>(2*init_vertices);
-        for (int i = 0; i < init_vertices; i++) {
-            V v = vertexFactory.create();
-            mGraph.addVertex(v);
-            vertex_index.add(v);
-            index_vertex.put(v, i);
-            seedVertices.add(v);
-        }
-            
-        mElapsedTimeSteps = 0;
-    }
-
-    private void createRandomEdge(Collection<V> preexistingNodes,
-               V newVertex, Set<Pair<V>> added_pairs) {
-        V attach_point;
-        boolean created_edge = false;
-        Pair<V> endpoints;
-        do {
-            attach_point = vertex_index.get(mRandom.nextInt(vertex_index.size()));
-            
-            endpoints = new Pair<V>(newVertex, attach_point);
-            
-            // if parallel edges are not allowed, skip attach_point if <newVertex, attach_point>
-            // already exists; note that because of the way edges are added, we only need to check
-            // the list of candidate edges for duplicates.
-            if (!(mGraph instanceof MultiGraph))
-            {
-               if (added_pairs.contains(endpoints))
-                       continue;
-               if (mGraph.getDefaultEdgeType() == EdgeType.UNDIRECTED && 
-                       added_pairs.contains(new Pair<V>(attach_point, newVertex)))
-                       continue;
-            }
-
-            double degree = mGraph.inDegree(attach_point);
-            
-            // subtract 1 from numVertices because we don't want to count newVertex
-            // (which has already been added to the graph, but not to vertex_index)
-            double attach_prob = (degree + 1) / (mGraph.getEdgeCount() + mGraph.getVertexCount() - 1);
-            if (attach_prob >= mRandom.nextDouble())
-                created_edge = true;
-        }
-        while (!created_edge);
-
-        added_pairs.add(endpoints);
-        
-        if (mGraph.getDefaultEdgeType() == EdgeType.UNDIRECTED) {
-               added_pairs.add(new Pair<V>(attach_point, newVertex));
-        }
-    }
-
-    public void evolveGraph(int numTimeSteps) {
-
-        for (int i = 0; i < numTimeSteps; i++) {
-            evolveGraph();
-            mElapsedTimeSteps++;
-        }
-    }
-
-    private void evolveGraph() {
-        Collection<V> preexistingNodes = mGraph.getVertices();
-        V newVertex = vertexFactory.create();
-
-        mGraph.addVertex(newVertex);
-
-        // generate and store the new edges; don't add them to the graph
-        // yet because we don't want to bias the degree calculations
-        // (all new edges in a timestep should be added in parallel)
-        Set<Pair<V>> added_pairs = new HashSet<Pair<V>>(mNumEdgesToAttachPerStep*3);
-        
-        for (int i = 0; i < mNumEdgesToAttachPerStep; i++) 
-               createRandomEdge(preexistingNodes, newVertex, added_pairs);
-        
-        for (Pair<V> pair : added_pairs)
-        {
-               V v1 = pair.getFirst();
-               V v2 = pair.getSecond();
-               if (mGraph.getDefaultEdgeType() != EdgeType.UNDIRECTED || 
-                               !mGraph.isNeighbor(v1, v2))
-                       mGraph.addEdge(edgeFactory.create(), pair);
-        }
-        // now that we're done attaching edges to this new vertex, 
-        // add it to the index
-        vertex_index.add(newVertex);
-        index_vertex.put(newVertex, new Integer(vertex_index.size() - 1));
-    }
-
-    public int numIterations() {
-        return mElapsedTimeSteps;
-    }
-
-    public Graph<V, E> create() {
-        return mGraph;
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/EppsteinPowerLawGenerator.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/EppsteinPowerLawGenerator.java
deleted file mode 100644 (file)
index e3bf04b..0000000
+++ /dev/null
@@ -1,128 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.generators.random;
-
-import java.util.ArrayList;
-import java.util.List;
-import java.util.Random;
-
-import org.apache.commons.collections15.Factory;
-
-import edu.uci.ics.jung.algorithms.generators.GraphGenerator;
-import edu.uci.ics.jung.graph.Graph;
-
-/**
- * Graph generator that generates undirected graphs with power-law degree distributions.
- * @author Scott White
- * @see "A Steady State Model for Graph Power Law by David Eppstein and Joseph Wang"
- */
-public class EppsteinPowerLawGenerator<V,E> implements GraphGenerator<V,E> {
-    private int mNumVertices;
-    private int mNumEdges;
-    private int mNumIterations;
-    private double mMaxDegree;
-    private Random mRandom;
-    private Factory<Graph<V,E>> graphFactory;
-    private Factory<V> vertexFactory;
-    private Factory<E> edgeFactory;
-
-    /**
-     * Creates an instance with the specified factories and specifications.
-     * @param graphFactory the factory to use to generate the graph
-     * @param vertexFactory the factory to use to create vertices
-     * @param edgeFactory the factory to use to create edges
-     * @param numVertices the number of vertices for the generated graph
-     * @param numEdges the number of edges the generated graph will have, should be Theta(numVertices)
-     * @param r the number of iterations to use; the larger the value the better the graph's degree
-     * distribution will approximate a power-law
-     */
-    public EppsteinPowerLawGenerator(Factory<Graph<V,E>> graphFactory,
-               Factory<V> vertexFactory, Factory<E> edgeFactory, 
-               int numVertices, int numEdges, int r) {
-       this.graphFactory = graphFactory;
-       this.vertexFactory = vertexFactory;
-       this.edgeFactory = edgeFactory;
-        mNumVertices = numVertices;
-        mNumEdges = numEdges;
-        mNumIterations = r;
-        mRandom = new Random();
-    }
-
-    protected Graph<V,E> initializeGraph() {
-        Graph<V,E> graph = null;
-        graph = graphFactory.create();
-        for(int i=0; i<mNumVertices; i++) {
-               graph.addVertex(vertexFactory.create());
-        }
-        List<V> vertices = new ArrayList<V>(graph.getVertices());
-        while (graph.getEdgeCount() < mNumEdges) {
-            V u = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
-            V v = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
-            if (!graph.isSuccessor(v,u)) {
-               graph.addEdge(edgeFactory.create(), u, v);
-            }
-        }
-
-        double maxDegree = 0;
-        for (V v : graph.getVertices()) {
-            maxDegree = Math.max(graph.degree(v),maxDegree);
-        }
-        mMaxDegree = maxDegree; //(maxDegree+1)*(maxDegree)/2;
-
-        return graph;
-    }
-
-    /**
-     * Generates a graph whose degree distribution approximates a power-law.
-     * @return the generated graph
-     */
-    public Graph<V,E> create() {
-        Graph<V,E> graph = initializeGraph();
-
-        List<V> vertices = new ArrayList<V>(graph.getVertices());
-        for (int rIdx = 0; rIdx < mNumIterations; rIdx++) {
-
-            V v = null;
-            int degree = 0;
-            do {
-                v = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
-                degree = graph.degree(v);
-
-            } while (degree == 0);
-
-            List<E> edges = new ArrayList<E>(graph.getIncidentEdges(v));
-            E randomExistingEdge = edges.get((int) (mRandom.nextDouble()*degree));
-
-            // FIXME: look at email thread on a more efficient RNG for arbitrary distributions
-            
-            V x = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
-            V y = null;
-            do {
-                y = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
-
-            } while (mRandom.nextDouble() > ((graph.degree(y)+1)/mMaxDegree));
-
-            if (!graph.isSuccessor(y,x) && x != y) {
-                graph.removeEdge(randomExistingEdge);
-                graph.addEdge(edgeFactory.create(), x, y);
-            }
-        }
-
-        return graph;
-    }
-
-    /**
-     * Sets the seed for the random number generator.
-     * @param seed input to the random number generator.
-     */
-    public void setSeed(long seed) {
-        mRandom.setSeed(seed);
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/ErdosRenyiGenerator.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/ErdosRenyiGenerator.java
deleted file mode 100644 (file)
index 3a33730..0000000
+++ /dev/null
@@ -1,100 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.generators.random;
-
-import java.util.ArrayList;
-import java.util.List;
-import java.util.Random;
-
-import org.apache.commons.collections15.Factory;
-
-import edu.uci.ics.jung.algorithms.generators.GraphGenerator;
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.UndirectedGraph;
-
-/**
- * Generates a random graph using the Erdos-Renyi binomial model
- * (each pair of vertices is connected with probability p).
- * 
- *  @author William Giordano, Scott White, Joshua O'Madadhain
- */
-public class ErdosRenyiGenerator<V,E> implements GraphGenerator<V,E> {
-    private int mNumVertices;
-    private double mEdgeConnectionProbability;
-    private Random mRandom;
-    Factory<UndirectedGraph<V,E>> graphFactory;
-    Factory<V> vertexFactory;
-    Factory<E> edgeFactory;
-
-    /**
-     *
-     * @param numVertices number of vertices graph should have
-     * @param p Connection's probability between 2 vertices
-     */
-       public ErdosRenyiGenerator(Factory<UndirectedGraph<V,E>> graphFactory,
-                       Factory<V> vertexFactory, Factory<E> edgeFactory,
-                       int numVertices,double p)
-    {
-        if (numVertices <= 0) {
-            throw new IllegalArgumentException("A positive # of vertices must be specified.");
-        }
-        mNumVertices = numVertices;
-        if (p < 0 || p > 1) {
-            throw new IllegalArgumentException("p must be between 0 and 1.");
-        }
-        this.graphFactory = graphFactory;
-        this.vertexFactory = vertexFactory;
-        this.edgeFactory = edgeFactory;
-        mEdgeConnectionProbability = p;
-        mRandom = new Random();
-       }
-
-    /**
-     * Returns a graph in which each pair of vertices is connected by 
-     * an undirected edge with the probability specified by the constructor.
-     */
-       public Graph<V,E> create() {
-        UndirectedGraph<V,E> g = graphFactory.create();
-        for(int i=0; i<mNumVertices; i++) {
-               g.addVertex(vertexFactory.create());
-        }
-        List<V> list = new ArrayList<V>(g.getVertices());
-
-               for (int i = 0; i < mNumVertices-1; i++) {
-            V v_i = list.get(i);
-                       for (int j = i+1; j < mNumVertices; j++) {
-                V v_j = list.get(j);
-                               if (mRandom.nextDouble() < mEdgeConnectionProbability) {
-                                       g.addEdge(edgeFactory.create(), v_i, v_j);
-                               }
-                       }
-               }
-        return g;
-    }
-
-    /**
-     * Sets the seed of the internal random number generator to {@code seed}.
-     * Enables consistent behavior.
-     */
-    public void setSeed(long seed) {
-        mRandom.setSeed(seed);
-    }
-}
-
-
-
-
-
-
-
-
-
-
-
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/KleinbergSmallWorldGenerator.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/KleinbergSmallWorldGenerator.java
deleted file mode 100644 (file)
index de01b69..0000000
+++ /dev/null
@@ -1,184 +0,0 @@
-
-package edu.uci.ics.jung.algorithms.generators.random;
-
-/*
-* Copyright (c) 2009, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-
-import java.util.HashMap;
-import java.util.Map;
-import java.util.Random;
-
-import org.apache.commons.collections15.Factory;
-
-import edu.uci.ics.jung.algorithms.generators.Lattice2DGenerator;
-import edu.uci.ics.jung.algorithms.util.WeightedChoice;
-import edu.uci.ics.jung.graph.Graph;
-
-/**
- * Graph generator that produces a random graph with small world properties. 
- * The underlying model is an mxn (optionally toroidal) lattice. Each node u 
- * has four local connections, one to each of its neighbors, and
- * in addition 1+ long range connections to some node v where v is chosen randomly according to
- * probability proportional to d^-alpha where d is the lattice distance between u and v and alpha
- * is the clustering exponent.
- * 
- * @see "Navigation in a small world J. Kleinberg, Nature 406(2000), 845."
- * @author Joshua O'Madadhain
- */
-public class KleinbergSmallWorldGenerator<V, E> extends Lattice2DGenerator<V, E> {
-    private double clustering_exponent;
-    private Random random;
-    private int num_connections = 1;
-    
-    /**
-     * Creates 
-     * @param graph_factory
-     * @param vertex_factory
-     * @param edge_factory
-     * @param latticeSize
-     * @param clusteringExponent
-     */
-    public KleinbergSmallWorldGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory, 
-            Factory<E> edge_factory, int latticeSize, double clusteringExponent) 
-    {
-        this(graph_factory, vertex_factory, edge_factory, latticeSize, latticeSize, clusteringExponent);
-    }
-
-    /**
-     * @param graph_factory
-     * @param vertex_factory
-     * @param edge_factory
-     * @param row_count
-     * @param col_count
-     * @param clusteringExponent
-     */
-    public KleinbergSmallWorldGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory, 
-            Factory<E> edge_factory, int row_count, int col_count, double clusteringExponent) 
-    {
-        super(graph_factory, vertex_factory, edge_factory, row_count, col_count, true);
-        clustering_exponent = clusteringExponent;
-        initialize();
-    }
-
-    /**
-     * @param graph_factory
-     * @param vertex_factory
-     * @param edge_factory
-     * @param row_count
-     * @param col_count
-     * @param clusteringExponent
-     * @param isToroidal
-     */
-    public KleinbergSmallWorldGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory, 
-            Factory<E> edge_factory, int row_count, int col_count, double clusteringExponent, 
-            boolean isToroidal) 
-    {
-        super(graph_factory, vertex_factory, edge_factory, row_count, col_count, isToroidal);
-        clustering_exponent = clusteringExponent;
-        initialize();
-    }
-
-    private void initialize()
-    {
-        this.random = new Random();
-    }
-    
-    /**
-     * Sets the {@code Random} instance used by this instance.  Useful for 
-     * unit testing.
-     */
-    public void setRandom(Random random)
-    {
-        this.random = random;
-    }
-    
-    /**
-     * Sets the seed of the internal random number generator.  May be used to provide repeatable
-     * experiments.
-     */
-    public void setRandomSeed(long seed) 
-    {
-        random.setSeed(seed);
-    }
-
-    /**
-     * Sets the number of new 'small-world' connections (outgoing edges) to be added to each vertex.
-     */
-    public void setConnectionCount(int num_connections)
-    {
-        if (num_connections <= 0)
-        {
-            throw new IllegalArgumentException("Number of new connections per vertex must be >= 1");
-        }
-        this.num_connections = num_connections;
-    }
-
-    /**
-     * Returns the number of new 'small-world' connections to be made to each vertex.
-     */
-    public int getConnectionCount()
-    {
-        return this.num_connections;
-    }
-    
-    /**
-     * Generates a random small world network according to the parameters given
-     * @return a random small world graph
-     */
-    @Override
-    public Graph<V,E> create() 
-    {
-        Graph<V, E> graph = super.create();
-        
-        // TODO: For toroidal graphs, we can make this more clever by pre-creating the WeightedChoice object
-        // and using the output as an offset to the current vertex location.
-        WeightedChoice<V> weighted_choice;
-        
-        // Add long range connections
-        for (int i = 0; i < graph.getVertexCount(); i++)
-        {
-            V source = getVertex(i);
-            int row = getRow(i);
-            int col = getCol(i);
-            int row_offset = row < row_count/2 ? -row_count : row_count;
-            int col_offset = col < col_count/2 ? -col_count : col_count;
-
-            Map<V, Float> vertex_weights = new HashMap<V, Float>();
-            for (int j = 0; j < row_count; j++)
-            {
-                for (int k = 0; k < col_count; k++)
-                {
-                    if (j == row && k == col)
-                        continue;
-                    int v_dist = Math.abs(j - row);
-                    int h_dist = Math.abs(k - col);
-                    if (is_toroidal)
-                    {
-                        v_dist = Math.min(v_dist, Math.abs(j - row+row_offset));
-                        h_dist = Math.min(h_dist, Math.abs(k - col+col_offset));
-                    }
-                    int distance = v_dist + h_dist;
-                    if (distance < 2)
-                        continue;
-                    else
-                        vertex_weights.put(getVertex(j,k), (float)Math.pow(distance, -clustering_exponent));
-                }
-            }
-
-            for (int j = 0; j < this.num_connections; j++) {
-                weighted_choice = new WeightedChoice<V>(vertex_weights, random);
-                V target = weighted_choice.nextItem();
-                graph.addEdge(edge_factory.create(), source, target);
-            }
-        }
-
-        return graph;
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/MixedRandomGraphGenerator.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/MixedRandomGraphGenerator.java
deleted file mode 100644 (file)
index a39a640..0000000
+++ /dev/null
@@ -1,88 +0,0 @@
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University of
- * California All rights reserved.
- * 
- * This software is open-source under the BSD license; see either "license.txt"
- * or http://jung.sourceforge.net/license.txt for a description.
- */
-/*
- * Created on Jul 2, 2003
- *  
- */
-package edu.uci.ics.jung.algorithms.generators.random;
-
-import java.util.Map;
-import java.util.Set;
-
-import org.apache.commons.collections15.Factory;
-
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.util.EdgeType;
-
-/**
- * 
- * Generates a mixed-mode random graph based on the output of <code>BarabasiAlbertGenerator</code>.
- * Primarily intended for providing a heterogeneous sample graph for visualization testing, etc.
- *  
- */
-public class MixedRandomGraphGenerator {
-
-       /**
-        * Equivalent to <code>generateMixedRandomGraph(edge_weight, num_vertices, true)</code>.
-        */
-       public static <V,E> Graph<V, E> generateMixedRandomGraph(
-                       Factory<Graph<V,E>> graphFactory,
-                       Factory<V> vertexFactory,
-               Factory<E> edgeFactory,
-               Map<E,Number> edge_weight, 
-                       int num_vertices, Set<V> seedVertices)
-       {
-               return generateMixedRandomGraph(graphFactory, vertexFactory, edgeFactory, 
-                               edge_weight, num_vertices, true, seedVertices);
-       }
-
-    /**
-     * Returns a random mixed-mode graph.  Starts with a randomly generated 
-     * Barabasi-Albert (preferential attachment) generator 
-     * (4 initial vertices, 3 edges added at each step, and num_vertices - 4 evolution steps).
-     * Then takes the resultant graph, replaces random undirected edges with directed
-     * edges, and assigns random weights to each edge.
-     */
-    public static <V,E> Graph<V,E> generateMixedRandomGraph(
-               Factory<Graph<V,E>> graphFactory,
-               Factory<V> vertexFactory,
-               Factory<E> edgeFactory,
-               Map<E,Number> edge_weights, 
-            int num_vertices, boolean parallel, Set<V> seedVertices)
-    {
-        int seed = (int)(Math.random() * 10000);
-        BarabasiAlbertGenerator<V,E> bag = 
-            new BarabasiAlbertGenerator<V,E>(graphFactory, vertexFactory, edgeFactory,
-                       4, 3, //false, parallel, 
-                       seed, seedVertices);
-        bag.evolveGraph(num_vertices - 4);
-        Graph<V, E> ug = bag.create();
-
-        // create a SparseMultigraph version of g
-        Graph<V, E> g = graphFactory.create();
-               //new SparseMultigraph<V, E>();
-        for(V v : ug.getVertices()) {
-               g.addVertex(v);
-        }
-        
-        // randomly replace some of the edges by directed edges to 
-        // get a mixed-mode graph, add random weights
-        
-        for(E e : ug.getEdges()) {
-            V v1 = ug.getEndpoints(e).getFirst();
-            V v2 = ug.getEndpoints(e).getSecond();
-
-            E me = edgeFactory.create();
-            g.addEdge(me, v1, v2, Math.random() < .5 ? EdgeType.DIRECTED : EdgeType.UNDIRECTED);
-            edge_weights.put(me, Math.random());
-        }
-        
-        return g;
-    }
-    
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/package.html b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/package.html
deleted file mode 100644 (file)
index 9f85614..0000000
+++ /dev/null
@@ -1,28 +0,0 @@
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
-<html>
-<head>
-<!--
-
-  @(#)package.html
-
- Copyright © 2003 The Regents of the University of California. All Rights Reserved. Permission to use, copy, modify, and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice, this paragraph and the following two paragraphs appear in all copies. This software program and documentation are copyrighted by The Regents of the University of California ("The University of California").
-
-THE SOFTWARE PROGRAM AND DOCUMENTATION ARE SUPPLIED "AS IS," WITHOUT ANY ACCOMPANYING SERVICES FROM THE UNIVERSITY OF CALFORNIA. FURTHERMORE, THE UNIVERSITY OF CALIFORNIA DOES NOT WARRANT THAT THE OPERATION OF THE PROGRAM WILL BE UNINTERRUPTED OR ERROR-FREE. THE END-USER UNDERSTANDS THAT THE PROGRAM WAS DEVELOPED FOR RESEARCH PURPOSES AND IS ADVISED NOT TO RELY EXCLUSIVELY ON THE PROGRAM FOR ANY REASON.
-
-IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATIONS TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
--->
-</head>
-<body>
-
-Methods for generating random graphs with various properties.  These include:
-<ul>
-<li/><code>BarabasiAlbertGenerator</code>: scale-free graphs using the preferential attachment heuristic.
-<li/><code>EppsteinPowerLawGenerator</code>: graphs whose degree distribution approximates a power law
-<li/><code>ErdosRenyiGenerator</code>: graphs for which edges are created with a specified probability
-<li/><code>MixedRandomGraphGenerator</code>: takes the output of <code>BarabasiAlbertGenerator</code> and
-perturbs it to generate a mixed-mode analog with both directed and undirected edges. 
-<li/>
-
-
-</body>
-</html>
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/AbstractRanker.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/AbstractRanker.java
deleted file mode 100644 (file)
index 6ea8bc8..0000000
+++ /dev/null
@@ -1,388 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.importance;
-
-import java.text.DecimalFormat;
-import java.text.Format;
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-
-import org.apache.commons.collections15.Factory;
-import org.apache.commons.collections15.map.LazyMap;
-
-import edu.uci.ics.jung.algorithms.util.IterativeProcess;
-import edu.uci.ics.jung.graph.Graph;
-
-/**
- * Abstract class for algorithms that rank nodes or edges by some "importance" metric. Provides a common set of
- * services such as:
- * <ul>
- *  <li> storing rank scores</li>
- *  <li> getters and setters for rank scores</li>
- *  <li> computing default edge weights</li>
- *  <li> normalizing default or user-provided edge transition weights </li>
- *  <li> normalizing rank scores</li>
- *  <li> automatic cleanup of decorations</li>
- *  <li> creation of Ranking list</li>
- * <li>print rankings in sorted order by rank</li>
- * </ul>
- * <p>
- * By default, all rank scores are removed from the vertices (or edges) being ranked.
- * @author Scott White
- */
-public abstract class AbstractRanker<V,E> extends IterativeProcess {
-    private Graph<V,E> mGraph;
-    private List<Ranking<?>> mRankings;
-    private boolean mRemoveRankScoresOnFinalize;
-    private boolean mRankNodes;
-    private boolean mRankEdges;
-    private boolean mNormalizeRankings;
-    protected Map<Object,Map<V, Number>> vertexRankScores = 
-       LazyMap.decorate(
-                       new HashMap<Object,Map<V,Number>>(),
-                       new Factory<Map<V,Number>>() {
-                                       public Map<V,Number> create() {
-                                               return new HashMap<V,Number>();
-                                       }});
-    protected Map<Object,Map<E, Number>> edgeRankScores = 
-       LazyMap.decorate(
-                       new HashMap<Object,Map<E,Number>>(),
-                       new Factory<Map<E,Number>>() {
-                                       public Map<E,Number> create() {
-                                               return new HashMap<E,Number>();
-                                       }});
-    private Map<E,Number> edgeWeights = new HashMap<E,Number>();
-
-    protected void initialize(Graph<V,E> graph, boolean isNodeRanker, 
-        boolean isEdgeRanker) {
-        if (!isNodeRanker && !isEdgeRanker)
-            throw new IllegalArgumentException("Must rank edges, vertices, or both");
-        mGraph = graph;
-        mRemoveRankScoresOnFinalize = true;
-        mNormalizeRankings = true;
-        mRankNodes = isNodeRanker;
-        mRankEdges = isEdgeRanker;
-    }
-    
-    /**
-        * @return all rankScores
-        */
-       public Map<Object,Map<V, Number>> getVertexRankScores() {
-               return vertexRankScores;
-       }
-
-       public Map<Object,Map<E, Number>> getEdgeRankScores() {
-               return edgeRankScores;
-       }
-
-    /**
-        * @return the rankScores
-        */
-       public Map<V, Number> getVertexRankScores(Object key) {
-               return vertexRankScores.get(key);
-       }
-
-       public Map<E, Number> getEdgeRankScores(Object key) {
-               return edgeRankScores.get(key);
-       }
-
-       protected Collection<V> getVertices() {
-        return mGraph.getVertices();
-    }
-
-       protected int getVertexCount() {
-        return mGraph.getVertexCount();
-    }
-
-    protected Graph<V,E> getGraph() {
-        return mGraph;
-    }
-
-    @Override
-    public void reset() {
-    }
-
-    /**
-     * Returns <code>true</code> if this ranker ranks nodes, and 
-     * <code>false</code> otherwise.
-     */
-    public boolean isRankingNodes() {
-        return mRankNodes;
-    }
-
-    /**
-     * Returns <code>true</code> if this ranker ranks edges, and 
-     * <code>false</code> otherwise.
-     */
-    public boolean isRankingEdges() {
-        return mRankEdges;
-    }
-    
-    /**
-     * Instructs the ranker whether or not it should remove the rank scores from the nodes (or edges) once the ranks
-     * have been computed.
-     * @param removeRankScoresOnFinalize <code>true</code> if the rank scores are to be removed, <code>false</code> otherwise
-     */
-    public void setRemoveRankScoresOnFinalize(boolean removeRankScoresOnFinalize) {
-        this.mRemoveRankScoresOnFinalize = removeRankScoresOnFinalize;
-    }
-
-    protected void onFinalize(Object e) {}
-    
-    /**
-     * The user datum key used to store the rank score.
-     * @return the key
-     */
-    abstract public Object getRankScoreKey();
-
-
-    @Override
-    protected void finalizeIterations() {
-        List<Ranking<?>> sortedRankings = new ArrayList<Ranking<?>>();
-
-        int id = 1;
-        if (mRankNodes) {
-            for (V currentVertex : getVertices()) {
-                Ranking<V> ranking = new Ranking<V>(id,getVertexRankScore(currentVertex),currentVertex);
-                sortedRankings.add(ranking);
-                if (mRemoveRankScoresOnFinalize) {
-                       this.vertexRankScores.get(getRankScoreKey()).remove(currentVertex);
-                }
-                id++;
-                onFinalize(currentVertex);
-            }
-        }
-        if (mRankEdges) {
-            for (E currentEdge : mGraph.getEdges()) {
-
-                Ranking<E> ranking = new Ranking<E>(id,getEdgeRankScore(currentEdge),currentEdge);
-                sortedRankings.add(ranking);
-                if (mRemoveRankScoresOnFinalize) {
-                       this.edgeRankScores.get(getRankScoreKey()).remove(currentEdge);
-                }
-                id++;
-                onFinalize(currentEdge);
-            }
-        }
-
-        mRankings = sortedRankings;
-        Collections.sort(mRankings);
-    }
-
-    /**
-     * Retrieves the list of ranking instances in descending sorted order by rank score
-     * If the algorithm is ranking edges, the instances will be of type <code>EdgeRanking</code>, otherwise
-     * if the algorithm is ranking nodes the instances will be of type <code>NodeRanking</code>
-     * @return  the list of rankings
-     */
-    public List<Ranking<?>> getRankings() {
-        return mRankings;
-    }
-
-    /**
-     * Return a list of the top k rank scores.
-     * @param topKRankings the value of k to use
-     * @return list of rank scores
-     */
-    public List<Double> getRankScores(int topKRankings) {
-        List<Double> scores = new ArrayList<Double>();
-        int count=1;
-        for (Ranking<?> currentRanking : getRankings()) {
-            if (count > topKRankings) {
-                return scores;
-            }
-            scores.add(currentRanking.rankScore);
-            count++;
-        }
-
-        return scores;
-    }
-
-    /**
-     * Given an edge or node, returns the corresponding rank score. This is a default
-     * implementation of getRankScore which assumes the decorations are of type MutableDouble.
-     * This method only returns legal values if <code>setRemoveRankScoresOnFinalize(false)</code> was called
-     * prior to <code>evaluate()</code>.
-     * @return  the rank score value
-     */
-    public double getVertexRankScore(V v) {
-        Number rankScore = vertexRankScores.get(getRankScoreKey()).get(v);
-        if (rankScore != null) {
-            return rankScore.doubleValue();
-        } else {
-            throw new RuntimeException("setRemoveRankScoresOnFinalize(false) must be called before evaluate().");
-        }
-    }
-    
-    public double getVertexRankScore(V v, Object key) {
-       return vertexRankScores.get(key).get(v).doubleValue();
-    }
-
-    public double getEdgeRankScore(E e) {
-        Number rankScore = edgeRankScores.get(getRankScoreKey()).get(e);
-        if (rankScore != null) {
-            return rankScore.doubleValue();
-        } else {
-            throw new RuntimeException("setRemoveRankScoresOnFinalize(false) must be called before evaluate().");
-        }
-    }
-    
-    public double getEdgeRankScore(E e, Object key) {
-       return edgeRankScores.get(key).get(e).doubleValue();
-    }
-
-    protected void setVertexRankScore(V v, double rankValue, Object key) {
-       vertexRankScores.get(key).put(v, rankValue);
-    }
-
-    protected void setEdgeRankScore(E e, double rankValue, Object key) {
-               edgeRankScores.get(key).put(e, rankValue);
-    }
-
-    protected void setVertexRankScore(V v, double rankValue) {
-       setVertexRankScore(v,rankValue, getRankScoreKey());
-    }
-
-    protected void setEdgeRankScore(E e, double rankValue) {
-       setEdgeRankScore(e, rankValue, getRankScoreKey());
-    }
-
-    protected void removeVertexRankScore(V v, Object key) {
-       vertexRankScores.get(key).remove(v);
-    }
-
-    protected void removeEdgeRankScore(E e, Object key) {
-       edgeRankScores.get(key).remove(e);
-    }
-
-    protected void removeVertexRankScore(V v) {
-       vertexRankScores.get(getRankScoreKey()).remove(v);
-    }
-
-    protected void removeEdgeRankScore(E e) {
-       edgeRankScores.get(getRankScoreKey()).remove(e);
-    }
-
-    protected double getEdgeWeight(E e) {
-       return edgeWeights.get(e).doubleValue();
-    }
-
-    protected void setEdgeWeight(E e, double weight) {
-       edgeWeights.put(e, weight);
-    }
-    
-    public void setEdgeWeights(Map<E,Number> edgeWeights) {
-       this.edgeWeights = edgeWeights;
-    }
-
-    /**
-        * @return the edgeWeights
-        */
-       public Map<E, Number> getEdgeWeights() {
-               return edgeWeights;
-       }
-
-       protected void assignDefaultEdgeTransitionWeights() {
-
-        for (V currentVertex : getVertices()) {
-
-            Collection<E> outgoingEdges = mGraph.getOutEdges(currentVertex);
-
-            double numOutEdges = outgoingEdges.size();
-            for (E currentEdge : outgoingEdges) {
-                setEdgeWeight(currentEdge,1.0/numOutEdges);
-            }
-        }
-    }
-
-    protected void normalizeEdgeTransitionWeights() {
-
-        for (V currentVertex : getVertices()) {
-
-               Collection<E> outgoingEdges = mGraph.getOutEdges(currentVertex);
-
-            double totalEdgeWeight = 0;
-            for (E currentEdge : outgoingEdges) {
-                totalEdgeWeight += getEdgeWeight(currentEdge);
-            }
-
-            for (E currentEdge : outgoingEdges) {
-                setEdgeWeight(currentEdge,getEdgeWeight(currentEdge)/totalEdgeWeight);
-            }
-        }
-    }
-
-    protected void normalizeRankings() {
-        if (!mNormalizeRankings) {
-            return;
-        }
-        double totalWeight = 0;
-
-        for (V currentVertex : getVertices()) {
-            totalWeight += getVertexRankScore(currentVertex);
-        }
-
-        for (V currentVertex : getVertices()) {
-            setVertexRankScore(currentVertex,getVertexRankScore(currentVertex)/totalWeight);
-        }
-    }
-
-    /**
-     * Print the rankings to standard out in descending order of rank score
-     * @param verbose if <code>true</code>, include information about the actual rank order as well as
-     * the original position of the vertex before it was ranked
-     * @param printScore if <code>true</code>, include the actual value of the rank score
-     */
-    public void printRankings(boolean verbose,boolean printScore) {
-            double total = 0;
-            Format formatter = new DecimalFormat("#0.#######");
-            int rank = 1;
-
-            for (Ranking<?> currentRanking : getRankings()) {
-                double rankScore = currentRanking.rankScore;
-                if (verbose) {
-                    System.out.print("Rank " + rank + ": ");
-                    if (printScore) {
-                        System.out.print(formatter.format(rankScore));
-                    }
-                    System.out.print("\tVertex Id: " + currentRanking.originalPos);
-                        System.out.print(" (" + currentRanking.getRanked() + ")");
-                    System.out.println();
-                } else {
-                    System.out.print(rank + "\t");
-                     if (printScore) {
-                        System.out.print(formatter.format(rankScore));
-                    }
-                    System.out.println("\t" + currentRanking.originalPos);
-
-                }
-                total += rankScore;
-                rank++;
-            }
-
-            if (verbose) {
-                System.out.println("Total: " + formatter.format(total));
-            }
-    }
-
-    /**
-     * Allows the user to specify whether or not s/he wants the rankings to be normalized.
-     * In some cases, this will have no effect since the algorithm doesn't allow normalization
-     * as an option
-     * @param normalizeRankings
-     */
-    public void setNormalizeRankings(boolean normalizeRankings) {
-        mNormalizeRankings = normalizeRankings;
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/BetweennessCentrality.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/BetweennessCentrality.java
deleted file mode 100644 (file)
index 25906f2..0000000
+++ /dev/null
@@ -1,190 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.importance;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-import java.util.Stack;
-
-import org.apache.commons.collections15.Buffer;
-import org.apache.commons.collections15.buffer.UnboundedFifoBuffer;
-
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.UndirectedGraph;
-
-/**
- * Computes betweenness centrality for each vertex and edge in the graph. The result is that each vertex
- * and edge has a UserData element of type MutableDouble whose key is 'centrality.BetweennessCentrality'.
- * Note: Many social network researchers like to normalize the betweenness values by dividing the values by
- * (n-1)(n-2)/2. The values given here are unnormalized.<p>
- *
- * A simple example of usage is:
- * <pre>
- * BetweennessCentrality ranker = new BetweennessCentrality(someGraph);
- * ranker.evaluate();
- * ranker.printRankings();
- * </pre>
- *
- * Running time is: O(n^2 + nm).
- * @see "Ulrik Brandes: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001."
- * @author Scott White
- * @author Tom Nelson converted to jung2
- */
-
-public class BetweennessCentrality<V,E> extends AbstractRanker<V,E> {
-
-    public static final String CENTRALITY = "centrality.BetweennessCentrality";
-
-    /**
-     * Constructor which initializes the algorithm
-     * @param g the graph whose nodes are to be analyzed
-     */
-    public BetweennessCentrality(Graph<V,E> g) {
-        initialize(g, true, true);
-    }
-
-    public BetweennessCentrality(Graph<V,E> g, boolean rankNodes) {
-        initialize(g, rankNodes, true);
-    }
-
-    public BetweennessCentrality(Graph<V,E> g, boolean rankNodes, boolean rankEdges)
-    {
-        initialize(g, rankNodes, rankEdges);
-    }
-    
-       protected void computeBetweenness(Graph<V,E> graph) {
-
-       Map<V,BetweennessData> decorator = new HashMap<V,BetweennessData>();
-       Map<V,Number> bcVertexDecorator = 
-               vertexRankScores.get(getRankScoreKey());
-       bcVertexDecorator.clear();
-       Map<E,Number> bcEdgeDecorator = 
-               edgeRankScores.get(getRankScoreKey());
-       bcEdgeDecorator.clear();
-        
-        Collection<V> vertices = graph.getVertices();
-        
-        for (V s : vertices) {
-
-            initializeData(graph,decorator);
-
-            decorator.get(s).numSPs = 1;
-            decorator.get(s).distance = 0;
-
-            Stack<V> stack = new Stack<V>();
-            Buffer<V> queue = new UnboundedFifoBuffer<V>();
-            queue.add(s);
-
-            while (!queue.isEmpty()) {
-                V v = queue.remove();
-                stack.push(v);
-
-                for(V w : getGraph().getSuccessors(v)) {
-
-                    if (decorator.get(w).distance < 0) {
-                        queue.add(w);
-                        decorator.get(w).distance = decorator.get(v).distance + 1;
-                    }
-
-                    if (decorator.get(w).distance == decorator.get(v).distance + 1) {
-                        decorator.get(w).numSPs += decorator.get(v).numSPs;
-                        decorator.get(w).predecessors.add(v);
-                    }
-                }
-            }
-            
-            while (!stack.isEmpty()) {
-                V w = stack.pop();
-
-                for (V v : decorator.get(w).predecessors) {
-
-                    double partialDependency = (decorator.get(v).numSPs / decorator.get(w).numSPs);
-                    partialDependency *= (1.0 + decorator.get(w).dependency);
-                    decorator.get(v).dependency +=  partialDependency;
-                    E currentEdge = getGraph().findEdge(v, w);
-                    double edgeValue = bcEdgeDecorator.get(currentEdge).doubleValue();
-                    edgeValue += partialDependency;
-                    bcEdgeDecorator.put(currentEdge, edgeValue);
-                }
-                if (w != s) {
-                       double bcValue = bcVertexDecorator.get(w).doubleValue();
-                       bcValue += decorator.get(w).dependency;
-                       bcVertexDecorator.put(w, bcValue);
-                }
-            }
-        }
-
-        if(graph instanceof UndirectedGraph) {
-            for (V v : vertices) { 
-               double bcValue = bcVertexDecorator.get(v).doubleValue();
-               bcValue /= 2.0;
-               bcVertexDecorator.put(v, bcValue);
-            }
-            for (E e : graph.getEdges()) {
-               double bcValue = bcEdgeDecorator.get(e).doubleValue();
-               bcValue /= 2.0;
-               bcEdgeDecorator.put(e, bcValue);
-            }
-        }
-
-        for (V vertex : vertices) {
-            decorator.remove(vertex);
-        }
-    }
-
-    private void initializeData(Graph<V,E> g, Map<V,BetweennessData> decorator) {
-        for (V vertex : g.getVertices()) {
-
-               Map<V,Number> bcVertexDecorator = vertexRankScores.get(getRankScoreKey());
-               if(bcVertexDecorator.containsKey(vertex) == false) {
-                       bcVertexDecorator.put(vertex, 0.0);
-               }
-            decorator.put(vertex, new BetweennessData());
-        }
-        for (E e : g.getEdges()) {
-
-               Map<E,Number> bcEdgeDecorator = edgeRankScores.get(getRankScoreKey());
-               if(bcEdgeDecorator.containsKey(e) == false) {
-                       bcEdgeDecorator.put(e, 0.0);
-               }
-        }
-    }
-    
-    /**
-     * the user datum key used to store the rank scores
-     * @return the key
-     */
-    @Override
-    public String getRankScoreKey() {
-        return CENTRALITY;
-    }
-
-    @Override
-    public void step() {
-        computeBetweenness(getGraph());
-    }
-
-    class BetweennessData {
-        double distance;
-        double numSPs;
-        List<V> predecessors;
-        double dependency;
-
-        BetweennessData() {
-            distance = -1;
-            numSPs = 0;
-            predecessors = new ArrayList<V>();
-            dependency = 0;
-        }
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/KStepMarkov.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/KStepMarkov.java
deleted file mode 100644 (file)
index 9ee4030..0000000
+++ /dev/null
@@ -1,135 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.importance;
-
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.Map;
-import java.util.Set;
-
-import edu.uci.ics.jung.graph.DirectedGraph;
-
-
-/**
- * Algorithm variant of <code>PageRankWithPriors</code> that computes the importance of a node based upon taking fixed-length random
- * walks out from the root set and then computing the stationary probability of being at each node. Specifically, it computes
- * the relative probability that the markov chain will spend at any particular node, given that it start in the root
- * set and ends after k steps.
- * <p>
- * A simple example of usage is:
- * <pre>
- * KStepMarkov ranker = new KStepMarkov(someGraph,rootSet,6,null);
- * ranker.evaluate();
- * ranker.printRankings();
- * </pre>
- * <p>
- *
- * @author Scott White
- * @author Tom Nelson - adapter to jung2
- * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
- */
-public class KStepMarkov<V,E> extends RelativeAuthorityRanker<V,E> {
-    public final static String RANK_SCORE = "jung.algorithms.importance.KStepMarkovExperimental.RankScore";
-    private final static String CURRENT_RANK = "jung.algorithms.importance.KStepMarkovExperimental.CurrentRank";
-    private int mNumSteps;
-    HashMap<V,Number> mPreviousRankingsMap;
-
-    /**
-     * Construct the algorihm instance and initializes the algorithm.
-     * @param graph the graph to be analyzed
-     * @param priors the set of root nodes
-     * @param k positive integer parameter which controls the relative tradeoff between a distribution "biased" towards
-     * R and the steady-state distribution which is independent of where the Markov-process started. Generally values
-     * between 4-8 are reasonable
-     * @param edgeWeights the weight for each edge 
-     */
-    public KStepMarkov(DirectedGraph<V,E> graph, Set<V> priors, int k, Map<E,Number> edgeWeights) {
-        super.initialize(graph,true,false);
-        mNumSteps = k;
-        setPriors(priors);
-        initializeRankings();
-        if (edgeWeights == null) {
-            assignDefaultEdgeTransitionWeights();
-        } else {
-            setEdgeWeights(edgeWeights);
-        }
-        normalizeEdgeTransitionWeights();
-    }
-
-    /**
-     * The user datum key used to store the rank scores.
-     * @return the key
-     */
-    @Override
-    public String getRankScoreKey() {
-        return RANK_SCORE;
-    }
-
-    protected void incrementRankScore(V v, double rankValue) {
-       double value = getVertexRankScore(v, RANK_SCORE);
-       value += rankValue;
-       setVertexRankScore(v, value, RANK_SCORE);
-    }
-
-    protected double getCurrentRankScore(V v) {
-       return getVertexRankScore(v, CURRENT_RANK);
-    }
-
-    protected void setCurrentRankScore(V v, double rankValue) {
-       setVertexRankScore(v, rankValue, CURRENT_RANK);
-    }
-
-    protected void initializeRankings() {
-         mPreviousRankingsMap = new HashMap<V,Number>();
-         for (V v : getVertices()) {
-            Set<V> priors = getPriors();
-            double numPriors = priors.size();
-
-            if (getPriors().contains(v)) {
-                setVertexRankScore(v, 1.0/ numPriors);
-                setCurrentRankScore(v, 1.0/ numPriors);
-                mPreviousRankingsMap.put(v,1.0/numPriors);
-            } else {
-                setVertexRankScore(v, 0);
-                setCurrentRankScore(v, 0);
-                mPreviousRankingsMap.put(v, 0);
-            }
-        }
-     }
-    @Override
-    public void step() {
-
-        for (int i=0;i<mNumSteps;i++) {
-            updateRankings();
-            for (V v : getVertices()) {
-                double currentRankScore = getCurrentRankScore(v);
-                incrementRankScore(v,currentRankScore);
-                mPreviousRankingsMap.put(v, currentRankScore);
-            }
-        }
-        normalizeRankings();
-    }
-
-    protected void updateRankings() {
-
-        for (V v : getVertices()) {
-
-            Collection<E> incomingEdges = getGraph().getInEdges(v);
-
-            double currentPageRankSum = 0;
-            for (E e : incomingEdges) {
-                double currentWeight = getEdgeWeight(e);
-                currentPageRankSum += 
-                       mPreviousRankingsMap.get(getGraph().getOpposite(v,e)).doubleValue()*currentWeight;
-            }
-            setCurrentRankScore(v,currentPageRankSum);
-        }
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/Ranking.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/Ranking.java
deleted file mode 100644 (file)
index b96e559..0000000
+++ /dev/null
@@ -1,77 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.importance;
-
-
-/**
- * Abstract data container for ranking objects. Stores common data relevant to both node and edge rankings, namely,
- * the original position of the instance in the list and the actual ranking score.
- * @author Scott White
- */
-public class Ranking<V> implements Comparable {
-    /**
-     * The original (0-indexed) position of the instance being ranked
-     */
-    public int originalPos;
-    /**
-     * The actual rank score (normally between 0 and 1)
-     */
-    public double rankScore;
-    
-    /**
-     * what is being ranked
-     */
-    private V ranked;
-
-    /**
-     * Constructor which allows values to be set on construction
-     * @param originalPos The original (0-indexed) position of the instance being ranked
-     * @param rankScore The actual rank score (normally between 0 and 1)
-     */
-    public Ranking(int originalPos, double rankScore, V ranked) {
-        this.originalPos = originalPos;
-        this.rankScore = rankScore;
-        this.ranked = ranked;
-    }
-
-    /**
-     * Compares two ranking based on the rank score.
-     * @param o The other ranking
-     * @return -1 if the other ranking is higher, 0 if they are equal, and 1 if this ranking is higher
-     */
-    public int compareTo(Object o) {
-
-        Ranking otherRanking = (Ranking) o;
-        return Double.compare(otherRanking.rankScore,rankScore);
-    }
-
-    /**
-     * Returns the rank score as a string.
-     * @return the stringified rank score
-     */
-    @Override
-    public String toString() {
-        return String.valueOf(rankScore);
-    }
-
-       /**
-        * @return the ranked
-        */
-       public V getRanked() {
-               return ranked;
-       }
-
-       /**
-        * @param ranked the ranked to set
-        */
-       public void setRanked(V ranked) {
-               this.ranked = ranked;
-       }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/RelativeAuthorityRanker.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/RelativeAuthorityRanker.java
deleted file mode 100644 (file)
index b40ba8d..0000000
+++ /dev/null
@@ -1,73 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.importance;
-
-import java.util.HashMap;
-import java.util.Map;
-import java.util.Set;
-
-
-/**
- * This class provides basic infrastructure for relative authority algorithms that compute the importance of nodes
- * relative to one or more root nodes. The services provided are:
- * <ul>
- * <li>The set of root nodes (priors) is stored and maintained</li>
- * <li>Getters and setters for the prior rank score are provided</li>
- * </ul>
- * 
- * @author Scott White
- */
-public abstract class RelativeAuthorityRanker<V,E> extends AbstractRanker<V,E> {
-    private Set<V> mPriors;
-    /**
-     * The default key used for the user datum key corresponding to prior rank scores.
-     */
-
-    protected Map<V,Number> priorRankScoreMap = new HashMap<V,Number>();
-    /**
-     * Cleans up all of the prior rank scores on finalize.
-     */
-    @Override
-    protected void finalizeIterations() {
-        super.finalizeIterations();
-        priorRankScoreMap.clear();
-    }
-
-    /**
-     * Retrieves the value of the prior rank score.
-     * @param v the root node (prior)
-     * @return the prior rank score
-     */
-    protected double getPriorRankScore(V v) {
-       return priorRankScoreMap.get(v).doubleValue();
-
-    }
-
-    /**
-     * Allows the user to specify a value to set for the prior rank score
-     * @param v the root node (prior)
-     * @param value the score to set to
-     */
-    public void setPriorRankScore(V v, double value) {
-       this.priorRankScoreMap.put(v, value);
-    }
-
-    /**
-     * Retrieves the set of priors.
-     * @return the set of root nodes (priors)
-     */
-    protected Set<V> getPriors() { return mPriors; }
-
-    /**
-     * Specifies which vertices are root nodes (priors).
-     * @param priors the root nodes
-     */
-    protected void setPriors(Set<V> priors) { mPriors = priors; }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/WeightedNIPaths.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/WeightedNIPaths.java
deleted file mode 100644 (file)
index bd715ce..0000000
+++ /dev/null
@@ -1,194 +0,0 @@
-/*
-* Copyright (c) 2003, the JUNG Project and the Regents of the University 
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-package edu.uci.ics.jung.algorithms.importance;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-import org.apache.commons.collections15.Factory;
-
-import edu.uci.ics.jung.graph.DirectedGraph;
-
-
-
-/**
- * This algorithm measures the importance of nodes based upon both the number and length of disjoint paths that lead
- * to a given node from each of the nodes in the root set. Specifically the formula for measuring the importance of a
- * node is given by: I(t|R) = sum_i=1_|P(r,t)|_{alpha^|p_i|} where alpha is the path decay coefficient, p_i is path i
- * and P(r,t) is a set of maximum-sized node-disjoint paths from r to t.
- * <p>
- * This algorithm uses heuristic breadth-first search to try and find the maximum-sized set of node-disjoint paths
- * between two nodes. As such, it is not guaranteed to give exact answers.
- * <p>
- * A simple example of usage is:
- * <pre>
- * WeightedNIPaths ranker = new WeightedNIPaths(someGraph,2.0,6,rootSet);
- * ranker.evaluate();
- * ranker.printRankings();
- * </pre>
- * 
- * @author Scott White
- * @see "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
- */
-public class WeightedNIPaths<V,E> extends AbstractRanker<V,E> {
-    public final static String WEIGHTED_NIPATHS_KEY = "jung.algorithms.importance.WEIGHTED_NIPATHS_KEY";
-    private double mAlpha;
-    private int mMaxDepth;
-    private Set<V> mPriors;
-    private Map<E,Number> pathIndices = new HashMap<E,Number>();
-    private Map<Object,V> roots = new HashMap<Object,V>();
-    private Map<V,Set<Number>> pathsSeenMap = new HashMap<V,Set<Number>>();
-    private Factory<V> vertexFactory;
-    private Factory<E> edgeFactory;
-
-    /**
-     * Constructs and initializes the algorithm.
-     * @param graph the graph whose nodes are being measured for their importance
-     * @param alpha the path decay coefficient (>= 1); 2 is recommended
-     * @param maxDepth the maximal depth to search out from the root set
-     * @param priors the root set (starting vertices)
-     */
-    public WeightedNIPaths(DirectedGraph<V,E> graph, Factory<V> vertexFactory,
-               Factory<E> edgeFactory, double alpha, int maxDepth, Set<V> priors) {
-        super.initialize(graph, true,false);
-        this.vertexFactory = vertexFactory;
-        this.edgeFactory = edgeFactory;
-        mAlpha = alpha;
-        mMaxDepth = maxDepth;
-        mPriors = priors;
-        for (V v : graph.getVertices()) {
-               super.setVertexRankScore(v, 0.0);
-        }
-    }
-
-    protected void incrementRankScore(V v, double rankValue) {
-        setVertexRankScore(v, getVertexRankScore(v) + rankValue);
-    }
-
-    protected void computeWeightedPathsFromSource(V root, int depth) {
-
-        int pathIdx = 1;
-
-        for (E e : getGraph().getOutEdges(root)) {
-            this.pathIndices.put(e, pathIdx);
-            this.roots.put(e, root);
-            newVertexEncountered(pathIdx, getGraph().getEndpoints(e).getSecond(), root);
-            pathIdx++;
-        }
-
-        List<E> edges = new ArrayList<E>();
-
-        V virtualNode = vertexFactory.create();
-        getGraph().addVertex(virtualNode);
-        E virtualSinkEdge = edgeFactory.create();
-
-        getGraph().addEdge(virtualSinkEdge, virtualNode, root);
-        edges.add(virtualSinkEdge);
-
-        int currentDepth = 0;
-        while (currentDepth <= depth) {
-
-            double currentWeight = Math.pow(mAlpha, -1.0 * currentDepth);
-            for (E currentEdge : edges) { 
-                incrementRankScore(getGraph().getEndpoints(currentEdge).getSecond(),//
-                               currentWeight);
-            }
-
-            if ((currentDepth == depth) || (edges.size() == 0)) break;
-
-            List<E> newEdges = new ArrayList<E>();
-
-            for (E currentSourceEdge : edges) { //Iterator sourceEdgeIt = edges.iterator(); sourceEdgeIt.hasNext();) {
-                Number sourcePathIndex = this.pathIndices.get(currentSourceEdge);
-
-                // from the currentSourceEdge, get its opposite end
-                // then iterate over the out edges of that opposite end
-                V newDestVertex = getGraph().getEndpoints(currentSourceEdge).getSecond();
-                Collection<E> outs = getGraph().getOutEdges(newDestVertex);
-                for (E currentDestEdge : outs) {
-                       V destEdgeRoot = this.roots.get(currentDestEdge);
-                       V destEdgeDest = getGraph().getEndpoints(currentDestEdge).getSecond();
-
-                    if (currentSourceEdge == virtualSinkEdge) {
-                        newEdges.add(currentDestEdge);
-                        continue;
-                    }
-                    if (destEdgeRoot == root) {
-                        continue;
-                    }
-                    if (destEdgeDest == getGraph().getEndpoints(currentSourceEdge).getFirst()) {//currentSourceEdge.getSource()) {
-                        continue;
-                    }
-                    Set<Number> pathsSeen = this.pathsSeenMap.get(destEdgeDest);
-
-                    if (pathsSeen == null) {
-                        newVertexEncountered(sourcePathIndex.intValue(), destEdgeDest, root);
-                    } else if (roots.get(destEdgeDest) != root) {
-                        roots.put(destEdgeDest,root);
-                        pathsSeen.clear();
-                        pathsSeen.add(sourcePathIndex);
-                    } else if (!pathsSeen.contains(sourcePathIndex)) {
-                        pathsSeen.add(sourcePathIndex);
-                    } else {
-                        continue;
-                    }
-
-                    this.pathIndices.put(currentDestEdge, sourcePathIndex);
-                    this.roots.put(currentDestEdge, root);
-                    newEdges.add(currentDestEdge);
-                }
-            }
-
-            edges = newEdges;
-            currentDepth++;
-        }
-
-        getGraph().removeVertex(virtualNode);
-    }
-
-    private void newVertexEncountered(int sourcePathIndex, V dest, V root) {
-        Set<Number> pathsSeen = new HashSet<Number>();
-        pathsSeen.add(sourcePathIndex);
-        this.pathsSeenMap.put(dest, pathsSeen);
-        roots.put(dest, root);
-    }
-
-    @Override
-    public void step() {
-        for (V v : mPriors) {
-            computeWeightedPathsFromSource(v, mMaxDepth);
-        }
-
-        normalizeRankings();
-//        return 0;
-    }
-    
-    /**
-     * Given a node, returns the corresponding rank score. This implementation of <code>getRankScore</code> assumes
-     * the decoration representing the rank score is of type <code>MutableDouble</code>.
-     * @return  the rank score for this node
-     */
-    @Override
-    public String getRankScoreKey() {
-        return WEIGHTED_NIPATHS_KEY;
-    }
-
-    @Override
-    protected void onFinalize(Object udc) {
-       pathIndices.remove(udc);
-       roots.remove(udc);
-       pathsSeenMap.remove(udc);
-    }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/AbstractLayout.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/AbstractLayout.java
deleted file mode 100644 (file)
index b59dcfa..0000000
+++ /dev/null
@@ -1,249 +0,0 @@
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University of
- * California All rights reserved.
- * 
- * This software is open-source under the BSD license; see either "license.txt"
- * or http://jung.sourceforge.net/license.txt for a description.
- * 
- * Created on Jul 7, 2003
- * 
- */
-package edu.uci.ics.jung.algorithms.layout;
-
-import java.awt.Dimension;
-import java.awt.geom.Point2D;
-import java.util.ConcurrentModificationException;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Map;
-import java.util.Set;
-
-import org.apache.commons.collections15.Transformer;
-import org.apache.commons.collections15.functors.ChainedTransformer;
-import org.apache.commons.collections15.functors.CloneTransformer;
-import org.apache.commons.collections15.map.LazyMap;
-
-import edu.uci.ics.jung.graph.Graph;
-
-/**
- * Abstract class for implementations of {@code Layout}.  It handles some of the
- * basic functions: storing coordinates, maintaining the dimensions, initializing
- * the locations, maintaining locked vertices.
- * 
- * @author Danyel Fisher, Scott White
- * @author Tom Nelson - converted to jung2
- * @param <V> the vertex type
- * @param <E> the edge type
- */
-abstract public class AbstractLayout<V, E> implements Layout<V,E> {
-
-    /**
-     * a set of vertices that should not move in relation to the
-     * other vertices
-     */
-       private Set<V> dontmove = new HashSet<V>();
-
-       protected Dimension size;
-       protected Graph<V, E> graph;
-       protected boolean initialized;
-    
-    protected Map<V, Point2D> locations = 
-       LazyMap.decorate(new HashMap<V, Point2D>(),
-                       new Transformer<V,Point2D>() {
-                                       public Point2D transform(V arg0) {
-                                               return new Point2D.Double();
-                                       }});
-
-
-       /**
-        * Creates an instance which does not initialize the vertex locations.
-        * 
-        * @param graph the graph for which the layout algorithm is to be created.
-        */
-       protected AbstractLayout(Graph<V, E> graph) {
-           if (graph == null) 
-           {
-               throw new IllegalArgumentException("Graph must be non-null");
-           }
-               this.graph = graph;
-       }
-       
-    @SuppressWarnings("unchecked")
-    protected AbstractLayout(Graph<V,E> graph, Transformer<V,Point2D> initializer) {
-               this.graph = graph;
-               Transformer<V, ? extends Object> chain = 
-                       ChainedTransformer.getInstance(initializer, CloneTransformer.getInstance());
-               this.locations = LazyMap.decorate(new HashMap<V,Point2D>(), (Transformer<V,Point2D>)chain);
-               initialized = true;
-       }
-       
-       protected AbstractLayout(Graph<V,E> graph, Dimension size) {
-               this.graph = graph;
-               this.size = size;
-       }
-       
-       @SuppressWarnings("unchecked")
-    protected AbstractLayout(Graph<V,E> graph, Transformer<V,Point2D> initializer, Dimension size) {
-               this.graph = graph;
-               Transformer<V, ? extends Object> chain = 
-                       ChainedTransformer.getInstance(initializer, CloneTransformer.getInstance());
-               this.locations = LazyMap.decorate(new HashMap<V,Point2D>(), (Transformer<V,Point2D>)chain);
-               this.size = size;
-       }
-    
-    public void setGraph(Graph<V,E> graph) {
-        this.graph = graph;
-        if(size != null && graph != null) {
-               initialize();
-        }
-    }
-    
-       /**
-        * When a visualization is resized, it presumably wants to fix the
-        * locations of the vertices and possibly to reinitialize its data. The
-        * current method calls <tt>initializeLocations</tt> followed by <tt>initialize_local</tt>.
-        */
-       public void setSize(Dimension size) {
-               
-               if(size != null && graph != null) {
-                       
-                       Dimension oldSize = this.size;
-                       this.size = size;
-                       initialize();
-                       
-                       if(oldSize != null) {
-                               adjustLocations(oldSize, size);
-                       }
-               }
-       }
-       
-       private void adjustLocations(Dimension oldSize, Dimension size) {
-
-               int xOffset = (size.width - oldSize.width) / 2;
-               int yOffset = (size.height - oldSize.height) / 2;
-
-               // now, move each vertex to be at the new screen center
-               while(true) {
-                   try {
-                for(V v : getGraph().getVertices()) {
-                           offsetVertex(v, xOffset, yOffset);
-                       }
-                       break;
-                   } catch(ConcurrentModificationException cme) {
-                   }
-               }
-       }
-    
-    public boolean isLocked(V v) {
-        return dontmove.contains(v);
-    }
-    
-    @SuppressWarnings("unchecked")
-    public void setInitializer(Transformer<V,Point2D> initializer) {
-       if(this.equals(initializer)) {
-               throw new IllegalArgumentException("Layout cannot be initialized with itself");
-       }
-               Transformer<V, ? extends Object> chain = 
-                       ChainedTransformer.getInstance(initializer, CloneTransformer.getInstance());
-       this.locations = LazyMap.decorate(new HashMap<V,Point2D>(), (Transformer<V, Point2D>)chain);
-       initialized = true;
-    }
-    
-       /**
-        * Returns the current size of the visualization space, accoring to the
-        * last call to resize().
-        * 
-        * @return the current size of the screen
-        */
-       public Dimension getSize() {
-               return size;
-       }
-
-       /**
-        * Returns the Coordinates object that stores the vertex' x and y location.
-        * 
-        * @param v
-        *            A Vertex that is a part of the Graph being visualized.
-        * @return A Coordinates object with x and y locations.
-        */
-       private Point2D getCoordinates(V v) {
-        return locations.get(v);
-       }
-       
-       public Point2D transform(V v) {
-               return getCoordinates(v);
-       }
-       
-       /**
-        * Returns the x coordinate of the vertex from the Coordinates object.
-        * in most cases you will be better off calling transform(v).
-        */
-       public double getX(V v) {
-        assert getCoordinates(v) != null : "Cannot getX for an unmapped vertex "+v;
-        return getCoordinates(v).getX();
-       }
-
-       /**
-        * Returns the y coordinate of the vertex from the Coordinates object.
-        * In most cases you will be better off calling transform(v).
-        */
-       public double getY(V v) {
-        assert getCoordinates(v) != null : "Cannot getY for an unmapped vertex "+v;
-        return getCoordinates(v).getY();
-       }
-       
-       /**
-        * @param v
-        * @param xOffset
-        * @param yOffset
-        */
-       protected void offsetVertex(V v, double xOffset, double yOffset) {
-               Point2D c = getCoordinates(v);
-        c.setLocation(c.getX()+xOffset, c.getY()+yOffset);
-               setLocation(v, c);
-       }
-
-       /**
-        * Accessor for the graph that represets all vertices.
-        * 
-        * @return the graph that contains all vertices.
-        */
-       public Graph<V, E> getGraph() {
-           return graph;
-       }
-       
-       /**
-        * Forcibly moves a vertex to the (x,y) location by setting its x and y
-        * locations to the inputted location. Does not add the vertex to the
-        * "dontmove" list, and (in the default implementation) does not make any
-        * adjustments to the rest of the graph.
-        */
-       public void setLocation(V picked, double x, double y) {
-               Point2D coord = getCoordinates(picked);
-               coord.setLocation(x, y);
-       }
-
-       public void setLocation(V picked, Point2D p) {
-               Point2D coord = getCoordinates(picked);
-               coord.setLocation(p);
-       }
-
-       /**
-        * Locks {@code v} in place if {@code state} is {@code true}, otherwise unlocks it.
-        */
-       public void lock(V v, boolean state) {
-               if(state == true) 
-                   dontmove.add(v);
-               else 
-                   dontmove.remove(v);
-       }
-       
-       /**
-        * Locks all vertices in place if {@code lock} is {@code true}, otherwise unlocks all vertices.
-        */
-       public void lock(boolean lock) {
-               for(V v : graph.getVertices()) {
-                       lock(v, lock);
-               }
-       }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/AggregateLayout.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/AggregateLayout.java
deleted file mode 100644 (file)
index 3805837..0000000
+++ /dev/null
@@ -1,291 +0,0 @@
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University of
- * California All rights reserved.
- * 
- * This software is open-source under the BSD license; see either "license.txt"
- * or http://jung.sourceforge.net/license.txt for a description.
- * 
- * 
- * 
- */
-package edu.uci.ics.jung.algorithms.layout;
-
-import java.awt.Dimension;
-import java.awt.geom.AffineTransform;
-import java.awt.geom.Point2D;
-import java.util.HashMap;
-import java.util.Map;
-
-import org.apache.commons.collections15.Transformer;
-
-import edu.uci.ics.jung.algorithms.util.IterativeContext;
-import edu.uci.ics.jung.graph.Graph;
-
-/**
- * A {@code Layout} implementation that combines 
- * multiple other layouts so that they may be manipulated
- * as one layout. The relaxer thread will step each layout
- * in sequence.
- * 
- * @author Tom Nelson - tomnelson@dev.java.net
- *
- * @param <V> the vertex type
- * @param <E> the edge type
- */
-public class AggregateLayout<V, E> implements Layout<V,E>, IterativeContext {
-
-       protected Layout<V,E> delegate;
-       protected Map<Layout<V,E>,Point2D> layouts = new HashMap<Layout<V,E>,Point2D>();
-
-       /**
-        * Creates an instance backed by the specified {@code delegate}.
-        * @param delegate
-        */
-       public AggregateLayout(Layout<V, E> delegate) {
-               this.delegate = delegate;
-       }
-
-       /**
-        * @return the delegate
-        */
-       public Layout<V, E> getDelegate() {
-               return delegate;
-       }
-
-       /**
-        * @param delegate the delegate to set
-        */
-       public void setDelegate(Layout<V, E> delegate) {
-               this.delegate = delegate;
-       }
-
-       /**
-        * adds the passed layout as a sublayout, also specifying
-        * the center of where this sublayout should appear
-        * @param layout
-        * @param center
-        */
-       public void put(Layout<V,E> layout, Point2D center) {
-               layouts.put(layout,center);
-       }
-       
-       /**
-        * Returns the center of the passed layout.
-        * @param layout
-        * @return the center of the passed layout
-        */
-       public Point2D get(Layout<V,E> layout) {
-               return layouts.get(layout);
-       }
-       
-       /**
-        * Removes {@code layout} from this instance.
-        */
-       public void remove(Layout<V,E> layout) {
-               layouts.remove(layout);
-       }
-       
-       /**
-        * Removes all layouts from this instance.
-        */
-       public void removeAll() {
-               layouts.clear();
-       }
-       
-       /**
-        * Returns the graph for which this layout is defined.
-        * @return the graph for which this layout is defined
-        * @see edu.uci.ics.jung.algorithms.layout.Layout#getGraph()
-        */
-       public Graph<V, E> getGraph() {
-               return delegate.getGraph();
-       }
-
-       /**
-        * Returns the size of the underlying layout.
-        * @return the size of the underlying layout
-        * @see edu.uci.ics.jung.algorithms.layout.Layout#getSize()
-        */
-       public Dimension getSize() {
-               return delegate.getSize();
-       }
-
-       /**
-        * 
-        * @see edu.uci.ics.jung.algorithms.layout.Layout#initialize()
-        */
-       public void initialize() {
-               delegate.initialize();
-               for(Layout<V,E> layout : layouts.keySet()) {
-                       layout.initialize();
-               }
-       }
-
-       /**
-        * Override to test if the passed vertex is locked in
-        * any of the layouts.
-        * @param v
-        * @return true if v is locked in any of the layouts, and false otherwise
-        * @see edu.uci.ics.jung.algorithms.layout.Layout#isLocked(java.lang.Object)
-        */
-       public boolean isLocked(V v) {
-               boolean locked = false;
-               for(Layout<V,E> layout : layouts.keySet()) {
-                       locked |= layout.isLocked(v);
-               }
-               locked |= delegate.isLocked(v);
-               return locked;
-       }
-
-       /**
-        * override to lock or unlock this vertex in any layout with
-        * a subgraph containing it
-        * @param v
-        * @param state
-        * @see edu.uci.ics.jung.algorithms.layout.Layout#lock(java.lang.Object, boolean)
-        */
-       public void lock(V v, boolean state) {
-               for(Layout<V,E> layout : layouts.keySet()) {
-                       if(layout.getGraph().getVertices().contains(v)) {
-                               layout.lock(v, state);
-                       }
-               }
-               delegate.lock(v, state);
-       }
-
-       /**
-        * 
-        * @see edu.uci.ics.jung.algorithms.layout.Layout#reset()
-        */
-       public void reset() {
-               for(Layout<V,E> layout : layouts.keySet()) {
-                       layout.reset();
-               }
-               delegate.reset();
-       }
-
-       /**
-        * @param graph
-        * @see edu.uci.ics.jung.algorithms.layout.Layout#setGraph(edu.uci.ics.jung.graph.Graph)
-        */
-       public void setGraph(Graph<V, E> graph) {
-               delegate.setGraph(graph);
-       }
-
-       /**
-        * @param initializer
-        * @see edu.uci.ics.jung.algorithms.layout.Layout#setInitializer(org.apache.commons.collections15.Transformer)
-        */
-       public void setInitializer(Transformer<V, Point2D> initializer) {
-               delegate.setInitializer(initializer);
-       }
-
-       /**
-        * @param v
-        * @param location
-        * @see edu.uci.ics.jung.algorithms.layout.Layout#setLocation(java.lang.Object, java.awt.geom.Point2D)
-        */
-       public void setLocation(V v, Point2D location) {
-               boolean wasInSublayout = false;
-               for(Layout<V,E> layout : layouts.keySet()) {
-                       if(layout.getGraph().getVertices().contains(v)) {
-                               Point2D center = layouts.get(layout);
-                               // transform by the layout itself, but offset to the
-                               // center of the sublayout
-                               Dimension d = layout.getSize();
-
-                               AffineTransform at = 
-                                       AffineTransform.getTranslateInstance(-center.getX()+d.width/2,-center.getY()+d.height/2);
-                               Point2D localLocation = at.transform(location, null);
-                               layout.setLocation(v, localLocation);
-                               wasInSublayout = true;
-                       }
-               }
-               if(wasInSublayout == false && getGraph().getVertices().contains(v)) {
-                       delegate.setLocation(v, location);
-               }
-       }
-
-       /**
-        * @param d
-        * @see edu.uci.ics.jung.algorithms.layout.Layout#setSize(java.awt.Dimension)
-        */
-       public void setSize(Dimension d) {
-               delegate.setSize(d);
-       }
-       
-       /**
-        * Returns a map from each {@code Layout} instance to its center point.
-        */
-       public Map<Layout<V,E>,Point2D> getLayouts() {
-               return layouts;
-       }
-
-       /**
-        * Returns the location of the vertex.  The location is specified first
-        * by the sublayouts, and then by the base layout if no sublayouts operate
-        * on this vertex.
-        * @return the location of the vertex
-        * @see org.apache.commons.collections15.Transformer#transform(java.lang.Object)
-        */
-       public Point2D transform(V v) {
-               boolean wasInSublayout = false;
-               for(Layout<V,E> layout : layouts.keySet()) {
-                       if(layout.getGraph().getVertices().contains(v)) {
-                               wasInSublayout = true;
-                               Point2D center = layouts.get(layout);
-                               // transform by the layout itself, but offset to the
-                               // center of the sublayout
-                               Dimension d = layout.getSize();
-                               AffineTransform at = 
-                                       AffineTransform.getTranslateInstance(center.getX()-d.width/2,
-                                                       center.getY()-d.height/2);
-                               return at.transform(layout.transform(v),null);
-                       }
-               }
-               if(wasInSublayout == false) {
-                       return delegate.transform(v);
-               }
-               return null;
-       
-       }
-
-       /**
-        * Check all sublayouts.keySet() and the delegate layout, returning
-        * done == true iff all are done.
-        */
-       public boolean done() {
-               boolean done = true;
-               for(Layout<V,E> layout : layouts.keySet()) {
-                       if(layout instanceof IterativeContext) {
-                               done &= ((IterativeContext)layout).done();
-                       }
-               }
-               if(delegate instanceof IterativeContext) {
-                       done &= ((IterativeContext)delegate).done();
-               }
-               return done;
-       }
-
-       /**
-        * call step on any sublayout that is also an IterativeContext
-        * and is not done
-        */
-       public void step() {
-               for(Layout<V,E> layout : layouts.keySet()) {
-                       if(layout instanceof IterativeContext) {
-                               IterativeContext context = (IterativeContext)layout;
-                               if(context.done() == false) {
-                                       context.step();
-                               }
-                       }
-               }
-               if(delegate instanceof IterativeContext) {
-                       IterativeContext context = (IterativeContext)delegate;
-                       if(context.done() == false) {
-                               context.step();
-                       }
-               }
-       }
-       
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/BalloonLayout.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/BalloonLayout.java
deleted file mode 100644 (file)
index 1d9f384..0000000
+++ /dev/null
@@ -1,143 +0,0 @@
-/*
- * Copyright (c) 2005, the JUNG Project and the Regents of the University of
- * California All rights reserved.
- *
- * This software is open-source under the BSD license; see either "license.txt"
- * or http://jung.sourceforge.net/license.txt for a description.
- *
- * Created on Jul 9, 2005
- */
-
-package edu.uci.ics.jung.algorithms.layout;
-import java.awt.Dimension;
-import java.awt.geom.Point2D;
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-
-import org.apache.commons.collections15.Transformer;
-import org.apache.commons.collections15.map.LazyMap;
-
-import edu.uci.ics.jung.graph.Forest;
-import edu.uci.ics.jung.graph.util.TreeUtils;
-
-/**
- * A {@code Layout} implementation that assigns positions to {@code Tree} or 
- * {@code Forest} vertices using associations with nested circles ("balloons").  
- * A balloon is nested inside another balloon if the first balloon's subtree
- * is a subtree of the second balloon's subtree.
- * 
- * @author Tom Nelson 
- *  
- */
-public class BalloonLayout<V,E> extends TreeLayout<V,E> {
-
-    protected Map<V,PolarPoint> polarLocations =
-       LazyMap.decorate(new HashMap<V, PolarPoint>(),
-                       new Transformer<V,PolarPoint>() {
-                                       public PolarPoint transform(V arg0) {
-                                               return new PolarPoint();
-                                       }});
-    
-    protected Map<V,Double> radii = new HashMap<V,Double>();
-    
-    /**
-     * Creates an instance based on the input forest.
-     */
-    public BalloonLayout(Forest<V,E> g) 
-    {
-        super(g);
-    }
-    
-    protected void setRootPolars() 
-    {
-        List<V> roots = TreeUtils.getRoots(graph);
-        if(roots.size() == 1) {
-               // its a Tree
-               V root = roots.get(0);
-               setRootPolar(root);
-            setPolars(new ArrayList<V>(graph.getChildren(root)),
-                    getCenter(), getSize().width/2);
-       } else if (roots.size() > 1) {
-               // its a Forest
-               setPolars(roots, getCenter(), getSize().width/2);
-       }
-    }
-    
-    protected void setRootPolar(V root) {
-       PolarPoint pp = new PolarPoint(0,0);
-       Point2D p = getCenter();
-       polarLocations.put(root, pp);
-       locations.put(root, p);
-    }
-    
-
-    protected void setPolars(List<V> kids, Point2D parentLocation, double parentRadius) {
-
-       int childCount = kids.size();
-       if(childCount == 0) return;
-       // handle the 1-child case with 0 limit on angle.
-       double angle = Math.max(0, Math.PI / 2 * (1 - 2.0/childCount));
-       double childRadius = parentRadius*Math.cos(angle) / (1 + Math.cos(angle));
-       double radius = parentRadius - childRadius;
-
-       double rand = Math.random();
-
-       for(int i=0; i< childCount; i++) {
-               V child = kids.get(i);
-               double theta = i* 2*Math.PI/childCount + rand;
-               radii.put(child, childRadius);
-               
-               PolarPoint pp = new PolarPoint(theta, radius);
-               polarLocations.put(child, pp);
-               
-               Point2D p = PolarPoint.polarToCartesian(pp);
-               p.setLocation(p.getX()+parentLocation.getX(), p.getY()+parentLocation.getY());
-               locations.put(child, p);
-               setPolars(new ArrayList<V>(graph.getChildren(child)), p, childRadius);
-       }
-    }
-
-    @Override
-    public void setSize(Dimension size) {
-       this.size = size;
-       setRootPolars();
-    }
-
-       /**
-        * Returns the coordinates of {@code v}'s parent, or the
-        * center of this layout's area if it's a root.
-        */
-       public Point2D getCenter(V v) {
-               V parent = graph.getParent(v);
-               if(parent == null) {
-                       return getCenter();
-               }
-               return locations.get(parent);
-       }
-
-       @Override
-    public void setLocation(V v, Point2D location) {
-               Point2D c = getCenter(v);
-               Point2D pv = new Point2D.Double(location.getX()-c.getX(),location.getY()-c.getY());
-               PolarPoint newLocation = PolarPoint.cartesianToPolar(pv);
-               polarLocations.get(v).setLocation(newLocation);
-               
-               Point2D center = getCenter(v);
-               pv.setLocation(pv.getX()+center.getX(), pv.getY()+center.getY());
-               locations.put(v, pv);
-       }
-
-       @Override
-    public Point2D transform(V v) {
-               return locations.get(v);
-       }
-
-       /**
-        * @return the radii
-        */
-       public Map<V, Double> getRadii() {
-               return radii;
-       }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/CircleLayout.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/CircleLayout.java
deleted file mode 100644 (file)
index 8cafb77..0000000
+++ /dev/null
@@ -1,150 +0,0 @@
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University 
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- */
-/*
- * Created on Dec 4, 2003
- */
-package edu.uci.ics.jung.algorithms.layout;
-
-import java.awt.Dimension;
-import java.awt.geom.Point2D;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-
-import org.apache.commons.collections15.Factory;
-import org.apache.commons.collections15.map.LazyMap;
-
-import edu.uci.ics.jung.graph.Graph;
-
-
-
-/**
- * A {@code Layout} implementation that positions vertices equally spaced on a regular circle.
- *
- * @author Masanori Harada
- */
-public class CircleLayout<V, E> extends AbstractLayout<V,E> {
-
-       private double radius;
-       private List<V> vertex_ordered_list;
-       
-       Map<V, CircleVertexData> circleVertexDataMap =
-                       LazyMap.decorate(new HashMap<V,CircleVertexData>(), 
-                       new Factory<CircleVertexData>() {
-                               public CircleVertexData create() {
-                                       return new CircleVertexData();
-                               }});    
-
-       /**
-        * Creates an instance for the specified graph.
-        */
-       public CircleLayout(Graph<V,E> g) {
-               super(g);
-       }
-
-       /**
-        * Returns the radius of the circle.
-        */
-       public double getRadius() {
-               return radius;
-       }
-
-       /**
-        * Sets the radius of the circle.  Must be called before
-        * {@code initialize()} is called.
-        */
-       public void setRadius(double radius) {
-               this.radius = radius;
-       }
-
-       /**
-        * Sets the order of the vertices in the layout according to the ordering
-        * specified by {@code comparator}.
-        */
-       public void setVertexOrder(Comparator<V> comparator)
-       {
-           if (vertex_ordered_list == null)
-               vertex_ordered_list = new ArrayList<V>(getGraph().getVertices());
-           Collections.sort(vertex_ordered_list, comparator);
-       }
-
-    /**
-     * Sets the order of the vertices in the layout according to the ordering
-     * of {@code vertex_list}.
-     */
-       public void setVertexOrder(List<V> vertex_list)
-       {
-           if (!vertex_list.containsAll(getGraph().getVertices())) 
-               throw new IllegalArgumentException("Supplied list must include " +
-                               "all vertices of the graph");
-           this.vertex_ordered_list = vertex_list;
-       }
-       
-       public void reset() {
-               initialize();
-       }
-
-       public void initialize() 
-       {
-               Dimension d = getSize();
-               
-               if (d != null) 
-               {
-                   if (vertex_ordered_list == null) 
-                       setVertexOrder(new ArrayList<V>(getGraph().getVertices()));
-
-                       double height = d.getHeight();
-                       double width = d.getWidth();
-
-                       if (radius <= 0) {
-                               radius = 0.45 * (height < width ? height : width);
-                       }
-
-                       int i = 0;
-                       for (V v : vertex_ordered_list)
-                       {
-                               Point2D coord = transform(v);
-
-                               double angle = (2 * Math.PI * i) / vertex_ordered_list.size();
-
-                               coord.setLocation(Math.cos(angle) * radius + width / 2,
-                                               Math.sin(angle) * radius + height / 2);
-
-                               CircleVertexData data = getCircleData(v);
-                               data.setAngle(angle);
-                               i++;
-                       }
-               }
-       }
-
-       protected CircleVertexData getCircleData(V v) {
-               return circleVertexDataMap.get(v);
-       }
-
-       protected static class CircleVertexData {
-               private double angle;
-
-               protected double getAngle() {
-                       return angle;
-               }
-
-               protected void setAngle(double angle) {
-                       this.angle = angle;
-               }
-
-               @Override
-               public String toString() {
-                       return "CircleVertexData: angle=" + angle;
-               }
-       }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/DAGLayout.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/DAGLayout.java
deleted file mode 100644 (file)
index 97d3ee6..0000000
+++ /dev/null
@@ -1,347 +0,0 @@
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- *
- * Created on Dec 4, 2003
- */
-package edu.uci.ics.jung.algorithms.layout;
-
-import java.awt.Dimension;
-import java.awt.geom.Point2D;
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.Map;
-
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.util.Pair;
-
-/**
- * An implementation of {@code Layout} suitable for tree-like directed
- * acyclic graphs. Parts of it will probably not terminate if the graph is
- * cyclic! The layout will result in directed edges pointing generally upwards.
- * Any vertices with no successors are considered to be level 0, and tend
- * towards the top of the layout. Any vertex has a level one greater than the
- * maximum level of all its successors.
- *
- *
- * @author John Yesberg
- */
-public class DAGLayout<V, E> extends SpringLayout<V,E> {
-
-    /**
-     * Each vertex has a minimumLevel. Any vertex with no successors has
-     * minimumLevel of zero. The minimumLevel of any vertex must be strictly
-     * greater than the minimumLevel of its parents. (Vertex A is a parent of
-     * Vertex B iff there is an edge from B to A.) Typically, a vertex will
-     * have a minimumLevel which is one greater than the minimumLevel of its
-     * parent's. However, if the vertex has two parents, its minimumLevel will
-     * be one greater than the maximum of the parents'. We need to calculate
-     * the minimumLevel for each vertex. When we layout the graph, vertices
-     * cannot be drawn any higher than the minimumLevel. The graphHeight of a
-     * graph is the greatest minimumLevel that is used. We will modify the
-     * SpringLayout calculations so that nodes cannot move above their assigned
-     * minimumLevel.
-     */
-       private Map<V,Number> minLevels = new HashMap<V,Number>();
-       // Simpler than the "pair" technique.
-       static int graphHeight;
-       static int numRoots;
-       final double SPACEFACTOR = 1.3;
-       // How much space do we allow for additional floating at the bottom.
-       final double LEVELATTRACTIONRATE = 0.8;
-
-       /**
-        * A bunch of parameters to help work out when to stop quivering.
-        *
-        * If the MeanSquareVel(ocity) ever gets below the MSV_THRESHOLD, then we
-        * will start a final cool-down phase of COOL_DOWN_INCREMENT increments. If
-        * the MeanSquareVel ever exceeds the threshold, we will exit the cool down
-        * phase, and continue looking for another opportunity.
-        */
-       final double MSV_THRESHOLD = 10.0;
-       double meanSquareVel;
-       boolean stoppingIncrements = false;
-       int incrementsLeft;
-       final int COOL_DOWN_INCREMENTS = 200;
-
-       /**
-        * Creates an instance for the specified graph.
-        */
-       public DAGLayout(Graph<V,E> g) {
-               super(g);
-       }
-
-       /**
-        * setRoot calculates the level of each vertex in the graph. Level 0 is
-        * allocated to any vertex with no successors. Level n+1 is allocated to
-        * any vertex whose successors' maximum level is n.
-        */
-       public void setRoot(Graph<V,E> g) {
-               numRoots = 0;
-               for(V v : g.getVertices()) {
-                       Collection<V> successors = getGraph().getSuccessors(v);
-                       if (successors.size() == 0) {
-                               setRoot(v);
-                               numRoots++;
-                       }
-               }
-       }
-
-       /**
-        * Set vertex v to be level 0.
-        */
-       public void setRoot(V v) {
-               minLevels.put(v, new Integer(0));
-               // set all the levels.
-               propagateMinimumLevel(v);
-       }
-
-       /**
-        * A recursive method for allocating the level for each vertex. Ensures
-        * that all predecessors of v have a level which is at least one greater
-        * than the level of v.
-        *
-        * @param v
-        */
-       public void propagateMinimumLevel(V v) {
-               int level = minLevels.get(v).intValue();
-               for(V child : getGraph().getPredecessors(v)) {
-                       int oldLevel, newLevel;
-                       Number o = minLevels.get(child);
-                       if (o != null)
-                               oldLevel = o.intValue();
-                       else
-                               oldLevel = 0;
-                       newLevel = Math.max(oldLevel, level + 1);
-                       minLevels.put(child, new Integer(newLevel));
-
-                       if (newLevel > graphHeight)
-                               graphHeight = newLevel;
-                       propagateMinimumLevel(child);
-               }
-       }
-
-       /**
-        * Sets random locations for a vertex within the dimensions of the space.
-        * This overrides the method in AbstractLayout
-        *
-        * @param coord
-        * @param d
-        */
-       private void initializeLocation(
-               V v,
-               Point2D coord,
-               Dimension d) {
-
-               int level = minLevels.get(v).intValue();
-               int minY = (int) (level * d.getHeight() / (graphHeight * SPACEFACTOR));
-               double x = Math.random() * d.getWidth();
-               double y = Math.random() * (d.getHeight() - minY) + minY;
-               coord.setLocation(x,y);
-       }
-
-       @Override
-       public void setSize(Dimension size) {
-               super.setSize(size);
-               for(V v : getGraph().getVertices()) {
-                       initializeLocation(v,transform(v),getSize());
-               }
-       }
-
-       /**
-        * Had to override this one as well, to ensure that setRoot() is called.
-        */
-       @Override
-       public void initialize() {
-               super.initialize();
-               setRoot(getGraph());
-       }
-
-       /**
-        * Override the moveNodes() method from SpringLayout. The only change we
-        * need to make is to make sure that nodes don't float higher than the minY
-        * coordinate, as calculated by their minimumLevel.
-        */
-       @Override
-       protected void moveNodes() {
-               // Dimension d = currentSize;
-               double oldMSV = meanSquareVel;
-               meanSquareVel = 0;
-
-               synchronized (getSize()) {
-
-                       for(V v : getGraph().getVertices()) {
-                               if (isLocked(v))
-                                       continue;
-                               SpringLayout.SpringVertexData vd = springVertexData.get(v);
-                               Point2D xyd = transform(v);
-
-                               int width = getSize().width;
-                               int height = getSize().height;
-
-                               // (JY addition: three lines are new)
-                               int level =
-                                       minLevels.get(v).intValue();
-                               int minY = (int) (level * height / (graphHeight * SPACEFACTOR));
-                               int maxY =
-                                       level == 0
-                                               ? (int) (height / (graphHeight * SPACEFACTOR * 2))
-                                               : height;
-
-                               // JY added 2* - double the sideways repulsion.
-                               vd.dx += 2 * vd.repulsiondx + vd.edgedx;
-                               vd.dy += vd.repulsiondy + vd.edgedy;
-
-                               // JY Addition: Attract the vertex towards it's minimumLevel
-                               // height.
-                               double delta = xyd.getY() - minY;
-                               vd.dy -= delta * LEVELATTRACTIONRATE;
-                               if (level == 0)
-                                       vd.dy -= delta * LEVELATTRACTIONRATE;
-                               // twice as much at the top.
-
-                               // JY addition:
-                               meanSquareVel += (vd.dx * vd.dx + vd.dy * vd.dy);
-
-                               // keeps nodes from moving any faster than 5 per time unit
-                               xyd.setLocation(xyd.getX()+Math.max(-5, Math.min(5, vd.dx)) , xyd.getY()+Math.max(-5, Math.min(5, vd.dy)) );
-
-                               if (xyd.getX() < 0) {
-                                       xyd.setLocation(0, xyd.getY());
-                               } else if (xyd.getX() > width) {
-                                       xyd.setLocation(width, xyd.getY());
-                               }
-
-                               // (JY addition: These two lines replaced 0 with minY)
-                               if (xyd.getY() < minY) {
-                                       xyd.setLocation(xyd.getX(), minY);
-                                       // (JY addition: replace height with maxY)
-                               } else if (xyd.getY() > maxY) {
-                                       xyd.setLocation(xyd.getX(), maxY);
-                               }
-
-                               // (JY addition: if there's only one root, anchor it in the
-                               // middle-top of the screen)
-                               if (numRoots == 1 && level == 0) {
-                                       xyd.setLocation(width/2, xyd.getY());
-                               }
-                       }
-               }
-               //System.out.println("MeanSquareAccel="+meanSquareVel);
-               if (!stoppingIncrements
-                       && Math.abs(meanSquareVel - oldMSV) < MSV_THRESHOLD) {
-                       stoppingIncrements = true;
-                       incrementsLeft = COOL_DOWN_INCREMENTS;
-               } else if (
-                       stoppingIncrements
-                               && Math.abs(meanSquareVel - oldMSV) <= MSV_THRESHOLD) {
-                       incrementsLeft--;
-                       if (incrementsLeft <= 0)
-                               incrementsLeft = 0;
-               }
-       }
-
-       /**
-        * Override incrementsAreDone so that we can eventually stop.
-        */
-       @Override
-       public boolean done() {
-               if (stoppingIncrements && incrementsLeft == 0)
-                       return true;
-               else
-                       return false;
-       }
-
-       /**
-        * Override forceMove so that if someone moves a node, we can re-layout
-        * everything.
-        */
-       @Override
-       public void setLocation(V picked, double x, double y) {
-               Point2D coord = transform(picked);
-               coord.setLocation(x,y);
-               stoppingIncrements = false;
-       }
-
-       /**
-        * Override forceMove so that if someone moves a node, we can re-layout
-        * everything.
-        */
-       @Override
-       public void setLocation(V picked, Point2D p) {
-               Point2D coord = transform(picked);
-               coord.setLocation(p);
-               stoppingIncrements = false;
-       }
-
-       /**
-        * Overridden relaxEdges. This one reduces the effect of edges between
-        * greatly different levels.
-        *
-        */
-       @Override
-       protected void relaxEdges() {
-               for(E e : getGraph().getEdges()) {
-                   Pair<V> endpoints = getGraph().getEndpoints(e);
-                       V v1 = endpoints.getFirst();
-                       V v2 = endpoints.getSecond();
-
-                       Point2D p1 = transform(v1);
-                       Point2D p2 = transform(v2);
-                       double vx = p1.getX() - p2.getX();
-                       double vy = p1.getY() - p2.getY();
-                       double len = Math.sqrt(vx * vx + vy * vy);
-
-                       // JY addition.
-                       int level1 =
-                               minLevels.get(v1).intValue();
-                       int level2 =
-                               minLevels.get(v2).intValue();
-
-                       // desiredLen *= Math.pow( 1.1, (v1.degree() + v2.degree()) );
-//          double desiredLen = getLength(e);
-                       double desiredLen = lengthFunction.transform(e);
-
-                       // round from zero, if needed [zero would be Bad.].
-                       len = (len == 0) ? .0001 : len;
-
-                       // force factor: optimal length minus actual length,
-                       // is made smaller as the current actual length gets larger.
-                       // why?
-
-                       // System.out.println("Desired : " + getLength( e ));
-                       double f = force_multiplier * (desiredLen - len) / len;
-
-                       f = f * Math.pow(stretch / 100.0,
-                                       (getGraph().degree(v1) + getGraph().degree(v2) -2));
-
-                       // JY addition. If this is an edge which stretches a long way,
-                       // don't be so concerned about it.
-                       if (level1 != level2)
-                               f = f / Math.pow(Math.abs(level2 - level1), 1.5);
-
-                       // f= Math.min( 0, f );
-
-                       // the actual movement distance 'dx' is the force multiplied by the
-                       // distance to go.
-                       double dx = f * vx;
-                       double dy = f * vy;
-                       SpringVertexData v1D, v2D;
-                       v1D = springVertexData.get(v1);
-                       v2D = springVertexData.get(v2);
-
-//                     SpringEdgeData<E> sed = getSpringEdgeData(e);
-//                     sed.f = f;
-
-                       v1D.edgedx += dx;
-                       v1D.edgedy += dy;
-                       v2D.edgedx += -dx;
-                       v2D.edgedy += -dy;
-               }
-       }
-}
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/FRLayout.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/FRLayout.java
deleted file mode 100644 (file)
index c8a2a24..0000000
+++ /dev/null
@@ -1,333 +0,0 @@
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University of
- * California All rights reserved.
- *
- * This software is open-source under the BSD license; see either "license.txt"
- * or http://jung.sourceforge.net/license.txt for a description.
- */
-package edu.uci.ics.jung.algorithms.layout;
-
-import edu.uci.ics.jung.algorithms.layout.util.RandomLocationTransformer;
-import edu.uci.ics.jung.algorithms.util.IterativeContext;
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.util.Pair;
-
-import org.apache.commons.collections15.Factory;
-import org.apache.commons.collections15.map.LazyMap;
-
-import java.awt.Dimension;
-import java.awt.geom.Point2D;
-import java.util.ConcurrentModificationException;
-import java.util.HashMap;
-import java.util.Map;
-
-/**
- * Implements the Fruchterman-Reingold force-directed algorithm for node layout.
- * 
- * <p>Behavior is determined by the following settable parameters:
- * <ul>
- * <li/>attraction multiplier: how much edges try to keep their vertices together
- * <li/>repulsion multiplier: how much vertices try to push each other apart
- * <li/>maximum iterations: how many iterations this algorithm will use before stopping
- * </ul>
- * Each of the first two defaults to 0.75; the maximum number of iterations defaults to 700.
- *
- * @see "Fruchterman and Reingold, 'Graph Drawing by Force-directed Placement'"
- * @see "http://i11www.ilkd.uni-karlsruhe.de/teaching/SS_04/visualisierung/papers/fruchterman91graph.pdf"
- * @author Scott White, Yan-Biao Boey, Danyel Fisher
- */
-public class FRLayout<V, E> extends AbstractLayout<V, E> implements IterativeContext {
-
-    private double forceConstant;
-
-    private double temperature;
-
-    private int currentIteration;
-
-    private int mMaxIterations = 700;
-
-    private Map<V, FRVertexData> frVertexData =
-       LazyMap.decorate(new HashMap<V,FRVertexData>(), new Factory<FRVertexData>() {
-               public FRVertexData create() {
-                       return new FRVertexData();
-               }});
-
-    private double attraction_multiplier = 0.75;
-
-    private double attraction_constant;
-
-    private double repulsion_multiplier = 0.75;
-
-    private double repulsion_constant;
-
-    private double max_dimension;
-
-    /**
-     * Creates an instance for the specified graph.
-     */
-    public FRLayout(Graph<V, E> g) {
-        super(g);
-    }
-
-    /**
-     * Creates an instance of size {@code d} for the specified graph.
-     */
-    public FRLayout(Graph<V, E> g, Dimension d) {
-        super(g, new RandomLocationTransformer<V>(d), d);
-        initialize();
-        max_dimension = Math.max(d.height, d.width);
-    }
-
-       @Override
-       public void setSize(Dimension size) {
-               if(initialized == false) {
-                       setInitializer(new RandomLocationTransformer<V>(size));
-               }
-               super.setSize(size);
-        max_dimension = Math.max(size.height, size.width);
-       }
-
-       /**
-        * Sets the attraction multiplier.
-        */
-       public void setAttractionMultiplier(double attraction) {
-        this.attraction_multiplier = attraction;
-    }
-
-       /**
-        * Sets the repulsion multiplier.
-        */
-    public void setRepulsionMultiplier(double repulsion) {
-        this.repulsion_multiplier = repulsion;
-    }
-
-       public void reset() {
-               doInit();
-       }
-
-    public void initialize() {
-       doInit();
-    }
-
-    private void doInit() {
-       Graph<V,E> graph = getGraph();
-       Dimension d = getSize();
-       if(graph != null && d != null) {
-               currentIteration = 0;
-               temperature = d.getWidth() / 10;
-
-               forceConstant =
-                       Math
-                       .sqrt(d.getHeight()
-                                       * d.getWidth()
-                                       / graph.getVertexCount());
-
-               attraction_constant = attraction_multiplier * forceConstant;
-               repulsion_constant = repulsion_multiplier * forceConstant;
-       }
-    }
-
-    private double EPSILON = 0.000001D;
-
-    /**
-     * Moves the iteration forward one notch, calculation attraction and
-     * repulsion between vertices and edges and cooling the temperature.
-     */
-    public synchronized void step() {
-        currentIteration++;
-
-        /**
-         * Calculate repulsion
-         */
-        while(true) {
-
-            try {
-                for(V v1 : getGraph().getVertices()) {
-                    calcRepulsion(v1);
-                }
-                break;
-            } catch(ConcurrentModificationException cme) {}
-        }
-
-        /**
-         * Calculate attraction
-         */
-        while(true) {
-            try {
-                for(E e : getGraph().getEdges()) {
-
-                    calcAttraction(e);
-                }
-                break;
-            } catch(ConcurrentModificationException cme) {}
-        }
-
-
-        while(true) {
-            try {
-                for(V v : getGraph().getVertices()) {
-                    if (isLocked(v)) continue;
-                    calcPositions(v);
-                }
-                break;
-            } catch(ConcurrentModificationException cme) {}
-        }
-        cool();
-    }
-
-    protected synchronized void calcPositions(V v) {
-        FRVertexData fvd = getFRData(v);
-        if(fvd == null) return;
-        Point2D xyd = transform(v);
-        double deltaLength = Math.max(EPSILON, fvd.norm());
-
-        double newXDisp = fvd.getX() / deltaLength
-                * Math.min(deltaLength, temperature);
-
-        if (Double.isNaN(newXDisp)) {
-               throw new IllegalArgumentException(
-                "Unexpected mathematical result in FRLayout:calcPositions [xdisp]"); }
-
-        double newYDisp = fvd.getY() / deltaLength
-                * Math.min(deltaLength, temperature);
-        xyd.setLocation(xyd.getX()+newXDisp, xyd.getY()+newYDisp);
-
-        double borderWidth = getSize().getWidth() / 50.0;
-        double newXPos = xyd.getX();
-        if (newXPos < borderWidth) {
-            newXPos = borderWidth + Math.random() * borderWidth * 2.0;
-        } else if (newXPos > (getSize().getWidth() - borderWidth)) {
-            newXPos = getSize().getWidth() - borderWidth - Math.random()
-                    * borderWidth * 2.0;
-        }
-
-        double newYPos = xyd.getY();
-        if (newYPos < borderWidth) {
-            newYPos = borderWidth + Math.random() * borderWidth * 2.0;
-        } else if (newYPos > (getSize().getHeight() - borderWidth)) {
-            newYPos = getSize().getHeight() - borderWidth
-                    - Math.random() * borderWidth * 2.0;
-        }
-
-        xyd.setLocation(newXPos, newYPos);
-    }
-
-    protected void calcAttraction(E e) {
-       Pair<V> endpoints = getGraph().getEndpoints(e);
-        V v1 = endpoints.getFirst();
-        V v2 = endpoints.getSecond();
-        boolean v1_locked = isLocked(v1);
-        boolean v2_locked = isLocked(v2);
-
-        if(v1_locked && v2_locked) {
-               // both locked, do nothing
-               return;
-        }
-        Point2D p1 = transform(v1);
-        Point2D p2 = transform(v2);
-        if(p1 == null || p2 == null) return;
-        double xDelta = p1.getX() - p2.getX();
-        double yDelta = p1.getY() - p2.getY();
-
-        double deltaLength = Math.max(EPSILON, Math.sqrt((xDelta * xDelta)
-                + (yDelta * yDelta)));
-
-        double force = (deltaLength * deltaLength) / attraction_constant;
-
-        if (Double.isNaN(force)) { throw new IllegalArgumentException(
-                "Unexpected mathematical result in FRLayout:calcPositions [force]"); }
-
-        double dx = (xDelta / deltaLength) * force;
-        double dy = (yDelta / deltaLength) * force;
-        if(v1_locked == false) {
-               FRVertexData fvd1 = getFRData(v1);
-               fvd1.offset(-dx, -dy);
-        }
-        if(v2_locked == false) {
-               FRVertexData fvd2 = getFRData(v2);
-               fvd2.offset(dx, dy);
-        }
-    }
-
-    protected void calcRepulsion(V v1) {
-        FRVertexData fvd1 = getFRData(v1);
-        if(fvd1 == null)
-            return;
-        fvd1.setLocation(0, 0);
-
-        try {
-            for(V v2 : getGraph().getVertices()) {
-
-//                if (isLocked(v2)) continue;
-                if (v1 != v2) {
-                    Point2D p1 = transform(v1);
-                    Point2D p2 = transform(v2);
-                    if(p1 == null || p2 == null) continue;
-                    double xDelta = p1.getX() - p2.getX();
-                    double yDelta = p1.getY() - p2.getY();
-
-                    double deltaLength = Math.max(EPSILON, Math
-                            .sqrt((xDelta * xDelta) + (yDelta * yDelta)));
-
-                    double force = (repulsion_constant * repulsion_constant) / deltaLength;
-
-                    if (Double.isNaN(force)) { throw new RuntimeException(
-                    "Unexpected mathematical result in FRLayout:calcPositions [repulsion]"); }
-
-                    fvd1.offset((xDelta / deltaLength) * force,
-                            (yDelta / deltaLength) * force);
-                }
-            }
-        } catch(ConcurrentModificationException cme) {
-            calcRepulsion(v1);
-        }
-    }
-
-    private void cool() {
-        temperature *= (1.0 - currentIteration / (double) mMaxIterations);
-    }
-
-    /**
-     * Sets the maximum number of iterations.
-     */
-    public void setMaxIterations(int maxIterations) {
-        mMaxIterations = maxIterations;
-    }
-
-    protected FRVertexData getFRData(V v) {
-        return frVertexData.get(v);
-    }
-
-    /**
-     * This one is an incremental visualization.
-     */
-    public boolean isIncremental() {
-        return true;
-    }
-
-    /**
-     * Returns true once the current iteration has passed the maximum count,
-     * <tt>MAX_ITERATIONS</tt>.
-     */
-    public boolean done() {
-        if (currentIteration > mMaxIterations || temperature < 1.0/max_dimension)
-        {
-            return true;
-        }
-        return false;
-    }
-
-    protected static class FRVertexData extends Point2D.Double
-    {
-        protected void offset(double x, double y)
-        {
-            this.x += x;
-            this.y += y;
-        }
-
-        protected double norm()
-        {
-            return Math.sqrt(x*x + y*y);
-        }
-     }
-}
\ No newline at end of file
diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/FRLayout2.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/FRLayout2.java
deleted file mode 100644 (file)
index 0f5b05e..0000000
+++ /dev/null
@@ -1,331 +0,0 @@
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University of
- * California All rights reserved.
- * 
- * This software is open-source under the BSD license; see either "license.txt"
- * or http://jung.sourceforge.net/license.txt for a description.
- */
-package edu.uci.ics.jung.algorithms.layout;
-
-import java.awt.Dimension;
-import java.awt.geom.Point2D;
-import java.awt.geom.Rectangle2D;
-import java.util.ConcurrentModificationException;
-import java.util.HashMap;
-import java.util.Map;
-
-import org.apache.commons.collections15.Factory;
-import org.apache.commons.collections15.map.LazyMap;
-
-import edu.uci.ics.jung.algorithms.layout.util.RandomLocationTransformer;
-import edu.uci.ics.jung.algorithms.util.IterativeContext;
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.util.Pair;
-
-/**
- * Implements the Fruchterman-Reingold force-directed algorithm for node layout.
- * This is an experimental attempt at optimizing {@code FRLayout}; if it is successful
- * it will be folded back into {@code FRLayout} (and this class will disappear).
- * 
- * <p>Behavior is determined by the following settable parameters:
- * <ul>
- * <li/>attraction multiplier: how much edges try to keep their vertices together
- * <li/>repulsion multiplier: how much vertices try to push each other apart
- * <li/>maximum iterations: how many iterations this algorithm will use before stopping
- * </ul>
- * Each of the first two defaults to 0.75; the maximum number of iterations defaults to 700.
-
- * 
- * @see "Fruchterman and Reingold, 'Graph Drawing by Force-directed Placement'"
- * @see http://i11www.ilkd.uni-karlsruhe.de/teaching/SS_04/visualisierung/papers/fruchterman91graph.pdf
- * 
- * @author Tom Nelson
- * @author Scott White, Yan-Biao Boey, Danyel Fisher
- */
-public class FRLayout2<V, E> extends AbstractLayout<V, E> implements IterativeContext {
-
-    private double forceConstant;
-
-    private double temperature;
-
-    private int currentIteration;
-
-    private int maxIterations = 700;
-    
-    private Map<V, Point2D> frVertexData = 
-       LazyMap.decorate(new HashMap<V,Point2D>(), new Factory<Point2D>() {
-               public Point2D create() {
-                       return new Point2D.Double();
-               }});
-
-    private double attraction_multiplier = 0.75;
-    
-    private double attraction_constant;
-    
-    private double repulsion_multiplier = 0.75;
-    
-    private double repulsion_constant;
-    
-    private double max_dimension;
-    
-    private Rectangle2D innerBounds = new Rectangle2D.Double();
-    
-    private boolean checked = false;
-    
-    /**
-     * Creates an instance for the specified graph.
-     */
-    public FRLayout2(Graph<V, E> g) {
-        super(g);
-    }
-    
-    /**
-     * Creates an instance of size {@code d} for the specified graph.
-     */
-    public FRLayout2(Graph<V, E> g, Dimension d) {
-        super(g, new RandomLocationTransformer<V>(d), d);
-        max_dimension = Math.max(d.height, d.width);
-        initialize();
-    }
-    
-       @Override
-       public void setSize(Dimension size) {
-               if(initialized == false) 
-                       setInitializer(new RandomLocationTransformer<V>(size));
-               super.setSize(size);
-               double t = size.width/50.0;
-               innerBounds.setFrameFromDiagonal(t,t,size.width-t,size.height-t);
-        max_dimension = Math.max(size.height, size.width);
-       }
-
-    /**
-     * Sets the attraction multiplier.
-     */
-       public void setAttractionMultiplier(double attraction) {
-        this.attraction_multiplier = attraction;
-    }
-    
-    /**
-     * Sets the repulsion multiplier.
-     */
-    public void setRepulsionMultiplier(double repulsion) {
-        this.repulsion_multiplier = repulsion;
-    }
-    
-       public void reset() {
-               doInit();
-       }
-    
-    public void initialize() {
-       doInit();
-    }
-
-    private void doInit() {
-       Graph<V,E> graph = getGraph();
-       Dimension d = getSize();
-       if(graph != null && d != null) {
-               currentIteration = 0;
-               temperature = d.getWidth() / 10;
-
-               forceConstant = 
-                       Math
-                       .sqrt(d.getHeight()
-                                       * d.getWidth()
-                                       / graph.getVertexCount());
-
-               attraction_constant = attraction_multiplier * forceConstant;
-               repulsion_constant = repulsion_multiplier * forceConstant;
-       }
-    }
-
-    private double EPSILON = 0.000001D;
-
-    /**
-     * Moves the iteration forward one notch, calculation attraction and
-     * repulsion between vertices and edges and cooling the temperature.
-     */
-    public synchronized void step() {
-        currentIteration++;
-
-        /**
-         * Calculate repulsion
-         */
-        while(true) {
-            
-            try {
-                for(V v1 : getGraph().getVertices()) {
-                    calcRepulsion(v1);
-                }
-                break;
-            } catch(ConcurrentModificationException cme) {}
-        }
-
-        /**
-         * Calculate attraction
-         */
-        while(true) {
-            try {
-                for(E e : getGraph().getEdges()) {
-                    calcAttraction(e);
-                }
-                break;
-            } catch(ConcurrentModificationException cme) {}
-        }
-
-
-        while(true) {
-            try {    
-                for(V v : getGraph().getVertices()) {
-                    if (isLocked(v)) continue;
-                    calcPositions(v);
-                }
-                break;
-            } catch(ConcurrentModificationException cme) {}
-        }
-        cool();
-    }
-
-    protected synchronized void calcPositions(V v) {
-        Point2D fvd = this.frVertexData.get(v);
-        if(fvd == null) return;
-        Point2D xyd = transform(v);
-        double deltaLength = Math.max(EPSILON, 
-                       Math.sqrt(fvd.getX()*fvd.getX()+fvd.getY()*fvd.getY()));
-
-        double newXDisp = fvd.getX() / deltaLength
-                * Math.min(deltaLength, temperature);
-
-        assert Double.isNaN(newXDisp) == false : "Unexpected mathematical result in FRLayout:calcPositions [xdisp]";
-
-        double newYDisp = fvd.getY() / deltaLength
-                * Math.min(deltaLength, temperature);
-        double newX = xyd.getX()+Math.max(-5, Math.min(5,newXDisp));
-        double newY = xyd.getY()+Math.max(-5, Math.min(5,newYDisp));
-        
-        newX = Math.max(innerBounds.getMinX(), Math.min(newX, innerBounds.getMaxX()));
-        newY = Math.max(innerBounds.getMinY(), Math.min(newY, innerBounds.getMaxY()));
-        
-        xyd.setLocation(newX, newY);
-
-    }
-
-    protected void calcAttraction(E e) {
-       Pair<V> endpoints = getGraph().getEndpoints(e);
-        V v1 = endpoints.getFirst();
-        V v2 = endpoints.getSecond();
-        boolean v1_locked = isLocked(v1);
-        boolean v2_locked = isLocked(v2);
-        
-        if(v1_locked && v2_locked) {
-               // both locked, do nothing
-               return;
-        }
-        Point2D p1 = transform(v1);
-        Point2D p2 = transform(v2);
-        if(p1 == null || p2 == null) return;
-        double xDelta = p1.getX() - p2.getX();
-        double yDelta = p1.getY() - p2.getY();
-
-        double deltaLength = Math.max(EPSILON, p1.distance(p2));
-
-        double force = deltaLength  / attraction_constant;
-
-        assert Double.isNaN(force) == false : "Unexpected mathematical result in FRLayout:calcPositions [force]";
-
-        double dx = xDelta * force;
-        double dy = yDelta * force;
-        Point2D fvd1 = frVertexData.get(v1);
-        Point2D fvd2 = frVertexData.get(v2);
-        if(v2_locked) {
-               // double the offset for v1, as v2 will not be moving in
-               // the opposite direction
-               fvd1.setLocation(fvd1.getX()-2*dx, fvd1.getY()-2*dy);
-        } else {
-        fvd1.setLocation(fvd1.getX()-dx, fvd1.getY()-dy);
-        }
-        if(v1_locked) {
-               // double the offset for v2, as v1 will not be moving in
-               // the opposite direction
-               fvd2.setLocation(fvd2.getX()+2*dx, fvd2.getY()+2*dy);
-        } else {
-        fvd2.setLocation(fvd2.getX()+dx, fvd2.getY()+dy);
-    }
-    }
-
-    protected void calcRepulsion(V v1) {
-        Point2D fvd1 = frVertexData.get(v1);
-        if(fvd1 == null) return;
-        fvd1.setLocation(0, 0);
-        boolean v1_locked = isLocked(v1);
-
-        try {
-            for(V v2 : getGraph().getVertices()) {
-
-   &nb