From e1c04c5af263a9604a765f1ab98be51dfc51d8cb Mon Sep 17 00:00:00 2001 From: Ed Warnicke Date: Wed, 29 Oct 2014 14:20:56 -0500 Subject: [PATCH] Bug 2273: Removed unbuilt third-party code. Change-Id: I0158a970b3ae65e6a0c49c93d96ab71928b25dd0 Signed-off-by: Ed Warnicke --- pom.xml | 8 - third-party/commons/thirdparty/pom.xml | 230 ---- third-party/jersey-servlet/pom.xml | 90 -- third-party/net.sf.jung2/pom.xml | 80 -- .../blockmodel/StructurallyEquivalent.java | 178 --- .../blockmodel/VertexPartition.java | 131 -- .../jung/algorithms/blockmodel/package.html | 33 - .../cluster/BicomponentClusterer.java | 162 --- .../cluster/EdgeBetweennessClusterer.java | 109 -- .../algorithms/cluster/VoltageClusterer.java | 366 ------ .../cluster/WeakComponentClusterer.java | 73 -- .../ics/jung/algorithms/cluster/package.html | 35 - .../filters/EdgePredicateFilter.java | 70 - .../ics/jung/algorithms/filters/Filter.java | 26 - .../jung/algorithms/filters/FilterUtils.java | 98 -- .../filters/KNeighborhoodFilter.java | 142 -- .../filters/VertexPredicateFilter.java | 75 -- .../ics/jung/algorithms/filters/package.html | 31 - .../algorithms/flows/EdmondsKarpMaxFlow.java | 314 ----- .../ics/jung/algorithms/flows/package.html | 20 - .../generators/EvolvingGraphGenerator.java | 31 - .../algorithms/generators/GraphGenerator.java | 20 - .../generators/Lattice2DGenerator.java | 188 --- .../jung/algorithms/generators/package.html | 20 - .../random/BarabasiAlbertGenerator.java | 227 ---- .../random/EppsteinPowerLawGenerator.java | 128 -- .../random/ErdosRenyiGenerator.java | 100 -- .../random/KleinbergSmallWorldGenerator.java | 184 --- .../random/MixedRandomGraphGenerator.java | 88 -- .../algorithms/generators/random/package.html | 28 - .../algorithms/importance/AbstractRanker.java | 388 ------ .../importance/BetweennessCentrality.java | 190 --- .../algorithms/importance/KStepMarkov.java | 135 -- .../jung/algorithms/importance/Ranking.java | 77 -- .../importance/RelativeAuthorityRanker.java | 73 -- .../importance/WeightedNIPaths.java | 194 --- .../algorithms/layout/AbstractLayout.java | 249 ---- .../algorithms/layout/AggregateLayout.java | 291 ---- .../jung/algorithms/layout/BalloonLayout.java | 143 -- .../jung/algorithms/layout/CircleLayout.java | 150 --- .../ics/jung/algorithms/layout/DAGLayout.java | 347 ----- .../ics/jung/algorithms/layout/FRLayout.java | 333 ----- .../ics/jung/algorithms/layout/FRLayout2.java | 331 ----- .../layout/GraphElementAccessor.java | 45 - .../jung/algorithms/layout/ISOMLayout.java | 231 ---- .../ics/jung/algorithms/layout/KKLayout.java | 433 ------ .../ics/jung/algorithms/layout/Layout.java | 93 -- .../algorithms/layout/LayoutDecorator.java | 149 --- .../jung/algorithms/layout/PolarPoint.java | 103 -- .../algorithms/layout/RadialTreeLayout.java | 125 -- .../layout/RadiusGraphElementAccessor.java | 180 --- .../jung/algorithms/layout/SpringLayout.java | 336 ----- .../jung/algorithms/layout/SpringLayout2.java | 139 -- .../jung/algorithms/layout/StaticLayout.java | 69 - .../jung/algorithms/layout/TreeLayout.java | 252 ---- .../ics/jung/algorithms/layout/package.html | 40 - .../util/RandomLocationTransformer.java | 59 - .../jung/algorithms/layout/util/Relaxer.java | 43 - .../algorithms/layout/util/VisRunner.java | 145 -- .../jung/algorithms/layout/util/package.html | 21 - .../matrix/MatrixElementOperations.java | 73 -- .../matrix/RealMatrixElementOperations.java | 68 - .../ics/jung/algorithms/matrix/package.html | 20 - .../ics/jung/algorithms/metrics/Metrics.java | 70 - .../algorithms/metrics/StructuralHoles.java | 310 ----- .../algorithms/metrics/TriadicCensus.java | 196 --- .../ics/jung/algorithms/metrics/package.html | 27 - .../edu/uci/ics/jung/algorithms/package.html | 61 - .../scoring/AbstractIterativeScorer.java | 368 ------ .../AbstractIterativeScorerWithPriors.java | 117 -- .../algorithms/scoring/BarycenterScorer.java | 55 - .../scoring/BetweennessCentrality.java | 351 ----- .../scoring/ClosenessCentrality.java | 55 - .../jung/algorithms/scoring/DegreeScorer.java | 45 - .../scoring/DistanceCentralityScorer.java | 249 ---- .../jung/algorithms/scoring/EdgeScorer.java | 28 - .../scoring/EigenvectorCentrality.java | 52 - .../uci/ics/jung/algorithms/scoring/HITS.java | 145 -- .../algorithms/scoring/HITSWithPriors.java | 200 --- .../jung/algorithms/scoring/KStepMarkov.java | 156 --- .../ics/jung/algorithms/scoring/PageRank.java | 70 - .../scoring/PageRankWithPriors.java | 142 -- .../jung/algorithms/scoring/VertexScorer.java | 28 - .../algorithms/scoring/VoltageScorer.java | 250 ---- .../ics/jung/algorithms/scoring/package.html | 43 - .../util/DelegateToEdgeTransformer.java | 48 - .../algorithms/scoring/util/ScoringUtils.java | 72 - .../scoring/util/UniformDegreeWeight.java | 58 - .../algorithms/scoring/util/UniformInOut.java | 57 - .../jung/algorithms/scoring/util/VEPair.java | 56 - .../scoring/util/VertexScoreTransformer.java | 44 - .../jung/algorithms/scoring/util/package.html | 35 - .../shortestpath/BFSDistanceLabeler.java | 169 --- .../shortestpath/DijkstraDistance.java | 582 -------- .../shortestpath/DijkstraShortestPath.java | 314 ----- .../algorithms/shortestpath/Distance.java | 41 - .../shortestpath/DistanceStatistics.java | 136 -- .../shortestpath/MinimumSpanningForest.java | 165 --- .../shortestpath/MinimumSpanningForest2.java | 104 -- .../shortestpath/PrimMinimumSpanningTree.java | 116 -- .../algorithms/shortestpath/ShortestPath.java | 29 - .../shortestpath/ShortestPathUtils.java | 54 - .../shortestpath/UnweightedShortestPath.java | 151 --- .../jung/algorithms/shortestpath/package.html | 31 - .../transformation/DirectionTransformer.java | 121 -- .../transformation/FoldingTransformer.java | 325 ----- .../VertexPartitionCollapser.java | 103 -- .../algorithms/transformation/package.html | 29 - .../jung/algorithms/util/BasicMapEntry.java | 80 -- .../ics/jung/algorithms/util/ConstantMap.java | 93 -- .../algorithms/util/DiscreteDistribution.java | 205 --- .../uci/ics/jung/algorithms/util/Indexer.java | 56 - .../algorithms/util/IterativeContext.java | 28 - .../algorithms/util/IterativeProcess.java | 174 --- .../jung/algorithms/util/KMeansClusterer.java | 253 ---- .../jung/algorithms/util/MapBinaryHeap.java | 389 ------ .../util/MapSettableTransformer.java | 44 - .../util/SelfLoopEdgePredicate.java | 23 - .../algorithms/util/SettableTransformer.java | 31 - .../jung/algorithms/util/WeightedChoice.java | 193 --- .../uci/ics/jung/algorithms/util/package.html | 32 - third-party/openflowj/LICENSE | 29 - third-party/openflowj/Makefile | 19 - third-party/openflowj/README | 16 - third-party/openflowj/eclipse_codestyle.xml | 269 ---- third-party/openflowj/lib/commons-cli-1.2.jar | Bin 41123 -> 0 bytes third-party/openflowj/lib/junit-4.8.1.jar | Bin 237047 -> 0 bytes third-party/openflowj/pom.xml | 140 -- .../org/openflow/example/SelectListener.java | 21 - .../java/org/openflow/example/SelectLoop.java | 156 --- .../openflow/example/SimpleController.java | 321 ----- .../java/org/openflow/example/cli/Option.java | 40 - .../org/openflow/example/cli/Options.java | 69 - .../openflow/example/cli/ParseException.java | 14 - .../org/openflow/example/cli/SimpleCLI.java | 132 -- .../org/openflow/io/OFMessageAsyncStream.java | 121 -- .../org/openflow/io/OFMessageInStream.java | 51 - .../org/openflow/io/OFMessageOutStream.java | 41 - .../org/openflow/protocol/Instantiable.java | 14 - .../org/openflow/protocol/OFBarrierReply.java | 15 - .../openflow/protocol/OFBarrierRequest.java | 15 - .../org/openflow/protocol/OFEchoReply.java | 19 - .../org/openflow/protocol/OFEchoRequest.java | 54 - .../java/org/openflow/protocol/OFError.java | 258 ---- .../openflow/protocol/OFFeaturesReply.java | 238 ---- .../openflow/protocol/OFFeaturesRequest.java | 19 - .../java/org/openflow/protocol/OFFlowMod.java | 371 ------ .../org/openflow/protocol/OFFlowRemoved.java | 273 ---- .../openflow/protocol/OFGetConfigReply.java | 12 - .../openflow/protocol/OFGetConfigRequest.java | 15 - .../java/org/openflow/protocol/OFHello.java | 22 - .../java/org/openflow/protocol/OFMatch.java | 1047 --------------- .../openflow/protocol/OFMatchBeanInfo.java | 90 -- .../java/org/openflow/protocol/OFMessage.java | 197 --- .../org/openflow/protocol/OFPacketIn.java | 187 --- .../org/openflow/protocol/OFPacketOut.java | 223 ---- .../org/openflow/protocol/OFPhysicalPort.java | 365 ------ .../java/org/openflow/protocol/OFPort.java | 26 - .../java/org/openflow/protocol/OFPortMod.java | 165 --- .../org/openflow/protocol/OFPortStatus.java | 109 -- .../openflow/protocol/OFQueueConfigReply.java | 150 --- .../protocol/OFQueueConfigRequest.java | 84 -- .../org/openflow/protocol/OFSetConfig.java | 12 - .../protocol/OFStatisticsMessageBase.java | 140 -- .../openflow/protocol/OFStatisticsReply.java | 29 - .../protocol/OFStatisticsRequest.java | 15 - .../org/openflow/protocol/OFSwitchConfig.java | 100 -- .../java/org/openflow/protocol/OFType.java | 232 ---- .../java/org/openflow/protocol/OFVendor.java | 100 -- .../action/ActionVendorOutputNextHop.java | 193 --- .../openflow/protocol/action/OFAction.java | 157 --- .../protocol/action/OFActionDataLayer.java | 77 -- .../action/OFActionDataLayerDestination.java | 13 - .../action/OFActionDataLayerSource.java | 13 - .../protocol/action/OFActionEnqueue.java | 100 -- .../action/OFActionNetworkLayerAddress.java | 68 - .../OFActionNetworkLayerDestination.java | 13 - .../action/OFActionNetworkLayerSource.java | 13 - .../action/OFActionNetworkTypeOfService.java | 77 -- .../protocol/action/OFActionOutput.java | 119 -- .../action/OFActionStripVirtualLan.java | 35 - .../action/OFActionTransportLayer.java | 70 - .../OFActionTransportLayerDestination.java | 13 - .../action/OFActionTransportLayerSource.java | 13 - .../protocol/action/OFActionType.java | 187 --- .../protocol/action/OFActionVendor.java | 87 -- .../action/OFActionVirtualLanIdentifier.java | 75 -- .../OFActionVirtualLanPriorityCodePoint.java | 77 -- .../protocol/factory/BasicFactory.java | 241 ---- .../protocol/factory/OFActionFactory.java | 44 - .../factory/OFActionFactoryAware.java | 14 - .../protocol/factory/OFMessageFactory.java | 47 - .../factory/OFMessageFactoryAware.java | 18 - .../factory/OFQueuePropertyFactory.java | 44 - .../factory/OFQueuePropertyFactoryAware.java | 14 - .../protocol/factory/OFStatisticsFactory.java | 55 - .../factory/OFStatisticsFactoryAware.java | 14 - .../protocol/queue/OFPacketQueue.java | 153 --- .../protocol/queue/OFQueueProperty.java | 100 -- .../queue/OFQueuePropertyMinRate.java | 87 -- .../protocol/queue/OFQueuePropertyType.java | 143 -- .../OFAggregateStatisticsReply.java | 110 -- .../OFAggregateStatisticsRequest.java | 118 -- .../statistics/OFDescriptionStatistics.java | 202 --- .../statistics/OFFlowStatisticsReply.java | 324 ----- .../statistics/OFFlowStatisticsRequest.java | 119 -- .../statistics/OFPortStatisticsReply.java | 332 ----- .../statistics/OFPortStatisticsRequest.java | 70 - .../statistics/OFQueueStatisticsReply.java | 155 --- .../statistics/OFQueueStatisticsRequest.java | 89 -- .../protocol/statistics/OFStatistics.java | 28 - .../protocol/statistics/OFStatisticsType.java | 300 ----- .../statistics/OFTableStatistics.java | 207 --- .../statistics/OFVendorStatistics.java | 83 -- .../java/org/openflow/util/HexString.java | 65 - .../org/openflow/util/LRULinkedHashMap.java | 25 - .../openflow/util/StringByteSerializer.java | 40 - .../src/main/java/org/openflow/util/U16.java | 11 - .../src/main/java/org/openflow/util/U32.java | 11 - .../src/main/java/org/openflow/util/U64.java | 13 - .../src/main/java/org/openflow/util/U8.java | 11 - .../main/java/org/openflow/util/Unsigned.java | 195 --- .../openflow/io/OFMessageAsyncStreamTest.java | 48 - .../openflow/protocol/BasicFactoryTest.java | 31 - .../openflow/protocol/OFActionTypeTest.java | 20 - .../openflow/protocol/OFBarrierReplyTest.java | 20 - .../protocol/OFBarrierRequestTest.java | 20 - .../org/openflow/protocol/OFErrorTest.java | 71 - .../protocol/OFFeaturesReplyTest.java | 47 - .../openflow/protocol/OFFlowRemovedTest.java | 27 - .../protocol/OFGetConfigReplyTest.java | 22 - .../protocol/OFGetConfigRequestTest.java | 20 - .../org/openflow/protocol/OFMatchTest.java | 102 -- .../openflow/protocol/OFPortConfigTest.java | 23 - .../openflow/protocol/OFPortStatusTest.java | 28 - .../openflow/protocol/OFQueueConfigTest.java | 84 -- .../openflow/protocol/OFSetConfigTest.java | 22 - .../protocol/OFStatisticsReplyTest.java | 58 - .../protocol/OFStatisticsRequestTest.java | 59 - .../protocol/OFStatisticsTypeTest.java | 20 - .../org/openflow/protocol/OFTypeTest.java | 22 - .../org/openflow/protocol/OFVendorTest.java | 20 - .../queue/OFQueuePropertyTypeTest.java | 17 - .../java/org/openflow/util/HexStringTest.java | 27 - .../java/org/openflow/util/OFTestCase.java | 19 - .../test/java/org/openflow/util/U16Test.java | 16 - .../test/java/org/openflow/util/U32Test.java | 15 - .../test/java/org/openflow/util/U64Test.java | 17 - .../test/java/org/openflow/util/U8Test.java | 15 - .../java/org/openflow/util/UnsignedTest.java | 66 - .../README | 12 - .../pom.xml | 72 - .../apache/catalina/filters/CorsFilter.java | 1166 ----------------- 253 files changed, 29392 deletions(-) delete mode 100644 third-party/commons/thirdparty/pom.xml delete mode 100644 third-party/jersey-servlet/pom.xml delete mode 100644 third-party/net.sf.jung2/pom.xml delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/StructurallyEquivalent.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/VertexPartition.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/BicomponentClusterer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/EdgeBetweennessClusterer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/VoltageClusterer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/WeakComponentClusterer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/EdgePredicateFilter.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/Filter.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/FilterUtils.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/VertexPredicateFilter.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/flows/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/EvolvingGraphGenerator.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/GraphGenerator.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/Lattice2DGenerator.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/BarabasiAlbertGenerator.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/EppsteinPowerLawGenerator.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/ErdosRenyiGenerator.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/KleinbergSmallWorldGenerator.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/MixedRandomGraphGenerator.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/AbstractRanker.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/BetweennessCentrality.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/KStepMarkov.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/Ranking.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/RelativeAuthorityRanker.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/importance/WeightedNIPaths.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/AbstractLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/AggregateLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/BalloonLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/CircleLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/DAGLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/FRLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/FRLayout2.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/GraphElementAccessor.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/ISOMLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/KKLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/Layout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/LayoutDecorator.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/PolarPoint.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/RadialTreeLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/RadiusGraphElementAccessor.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/SpringLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/SpringLayout2.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/StaticLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/TreeLayout.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/util/RandomLocationTransformer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/util/Relaxer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/util/VisRunner.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/util/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/matrix/MatrixElementOperations.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/matrix/RealMatrixElementOperations.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/matrix/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/metrics/Metrics.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/metrics/StructuralHoles.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/metrics/TriadicCensus.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/metrics/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/AbstractIterativeScorer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/AbstractIterativeScorerWithPriors.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/BarycenterScorer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/BetweennessCentrality.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/ClosenessCentrality.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/DegreeScorer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/DistanceCentralityScorer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/EdgeScorer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/EigenvectorCentrality.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/HITS.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/HITSWithPriors.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/KStepMarkov.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/PageRank.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/PageRankWithPriors.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/VertexScorer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/VoltageScorer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/DelegateToEdgeTransformer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/ScoringUtils.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/UniformDegreeWeight.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/UniformInOut.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/VEPair.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/VertexScoreTransformer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/scoring/util/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/BFSDistanceLabeler.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/DijkstraDistance.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/DijkstraShortestPath.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/Distance.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/DistanceStatistics.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/MinimumSpanningForest.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/MinimumSpanningForest2.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/PrimMinimumSpanningTree.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/ShortestPath.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/ShortestPathUtils.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/UnweightedShortestPath.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/shortestpath/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/transformation/DirectionTransformer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/transformation/FoldingTransformer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/transformation/VertexPartitionCollapser.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/transformation/package.html delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/BasicMapEntry.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/ConstantMap.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/DiscreteDistribution.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/Indexer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/IterativeContext.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/IterativeProcess.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/KMeansClusterer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/MapBinaryHeap.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/MapSettableTransformer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/SelfLoopEdgePredicate.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/SettableTransformer.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/WeightedChoice.java delete mode 100644 third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/util/package.html delete mode 100644 third-party/openflowj/LICENSE delete mode 100644 third-party/openflowj/Makefile delete mode 100644 third-party/openflowj/README delete mode 100644 third-party/openflowj/eclipse_codestyle.xml delete mode 100644 third-party/openflowj/lib/commons-cli-1.2.jar delete mode 100644 third-party/openflowj/lib/junit-4.8.1.jar delete mode 100644 third-party/openflowj/pom.xml delete mode 100644 third-party/openflowj/src/main/java/org/openflow/example/SelectListener.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/example/SelectLoop.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/example/SimpleController.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/example/cli/Option.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/example/cli/Options.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/example/cli/ParseException.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/example/cli/SimpleCLI.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/io/OFMessageAsyncStream.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/io/OFMessageInStream.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/io/OFMessageOutStream.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/Instantiable.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFBarrierReply.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFBarrierRequest.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFEchoReply.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFEchoRequest.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFError.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFFeaturesReply.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFFeaturesRequest.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFFlowMod.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFFlowRemoved.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFGetConfigReply.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFGetConfigRequest.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFHello.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFMatch.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFMatchBeanInfo.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFMessage.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFPacketIn.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFPacketOut.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFPhysicalPort.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFPort.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFPortMod.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFPortStatus.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFQueueConfigReply.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFQueueConfigRequest.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFSetConfig.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFStatisticsMessageBase.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFStatisticsReply.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFStatisticsRequest.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFSwitchConfig.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFType.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/OFVendor.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/ActionVendorOutputNextHop.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFAction.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionDataLayer.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionDataLayerDestination.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionDataLayerSource.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionEnqueue.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionNetworkLayerAddress.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionNetworkLayerDestination.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionNetworkLayerSource.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionNetworkTypeOfService.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionOutput.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionStripVirtualLan.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionTransportLayer.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionTransportLayerDestination.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionTransportLayerSource.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionType.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionVendor.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionVirtualLanIdentifier.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/action/OFActionVirtualLanPriorityCodePoint.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/factory/BasicFactory.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFActionFactory.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFActionFactoryAware.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFMessageFactory.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFMessageFactoryAware.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFQueuePropertyFactory.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFQueuePropertyFactoryAware.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFStatisticsFactory.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/factory/OFStatisticsFactoryAware.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/queue/OFPacketQueue.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/queue/OFQueueProperty.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/queue/OFQueuePropertyMinRate.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/queue/OFQueuePropertyType.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFAggregateStatisticsReply.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFAggregateStatisticsRequest.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFDescriptionStatistics.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFFlowStatisticsReply.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFFlowStatisticsRequest.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFPortStatisticsReply.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFPortStatisticsRequest.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFQueueStatisticsReply.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFQueueStatisticsRequest.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFStatistics.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFStatisticsType.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFTableStatistics.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/protocol/statistics/OFVendorStatistics.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/util/HexString.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/util/LRULinkedHashMap.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/util/StringByteSerializer.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/util/U16.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/util/U32.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/util/U64.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/util/U8.java delete mode 100644 third-party/openflowj/src/main/java/org/openflow/util/Unsigned.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/io/OFMessageAsyncStreamTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/BasicFactoryTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFActionTypeTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFBarrierReplyTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFBarrierRequestTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFErrorTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFFeaturesReplyTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFFlowRemovedTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFGetConfigReplyTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFGetConfigRequestTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFMatchTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFPortConfigTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFPortStatusTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFQueueConfigTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFSetConfigTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFStatisticsReplyTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFStatisticsRequestTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFStatisticsTypeTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFTypeTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/OFVendorTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/protocol/queue/OFQueuePropertyTypeTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/util/HexStringTest.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/util/OFTestCase.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/util/U16Test.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/util/U32Test.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/util/U64Test.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/util/U8Test.java delete mode 100644 third-party/openflowj/src/test/java/org/openflow/util/UnsignedTest.java delete mode 100644 third-party/org.apache.catalina.filters.CorsFilter/README delete mode 100644 third-party/org.apache.catalina.filters.CorsFilter/pom.xml delete mode 100644 third-party/org.apache.catalina.filters.CorsFilter/src/main/java/org/apache/catalina/filters/CorsFilter.java diff --git a/pom.xml b/pom.xml index d1e5494b44..bce34763b3 100644 --- a/pom.xml +++ b/pom.xml @@ -16,14 +16,6 @@ opendaylight/distribution/opendaylight - - - - - - - third-party/commons/thirdparty - opendaylight/md-sal diff --git a/third-party/commons/thirdparty/pom.xml b/third-party/commons/thirdparty/pom.xml deleted file mode 100644 index ad3c27523e..0000000000 --- a/third-party/commons/thirdparty/pom.xml +++ /dev/null @@ -1,230 +0,0 @@ - - - 4.0.0 - - 3.0 - - org.opendaylight.controller - commons.thirdparty - 1.2.0-SNAPSHOT - pom - - scm:git:ssh://git.opendaylight.org:29418/controller.git - scm:git:ssh://git.opendaylight.org:29418/controller.git - https://wiki.opendaylight.org/view/OpenDaylight_Controller:Main - HEAD - - - - https://sonar.opendaylight.org/ - http://nexus.opendaylight.org/content - opendaylight.release - opendaylight.snapshot - dav:http://nexus.opendaylight.org/content/sites/site - 3.2 - 2.6 - UTF-8 - 2.3.2 - 2.13 - 2.3.2 - 1.3.1 - 2.3.7 - - - - - central2 - central2 - http://repo2.maven.org/maven2 - - - - - - fastreassembly - - - - org.apache.maven.plugins - maven-dependency-plugin - 2.4 - - - copyfastreassembly - install - - copy - - - - - ${project.groupId} - ${project.artifactId} - ${project.version} - ${project.groupId}.${project.artifactId}-${project.version}.jar - - - ${fastreassembly.directory} - - - - - - - - - - - - - com.googlecode.maven-java-formatter-plugin - maven-java-formatter-plugin - 0.3.1 - - - **/* - - - - - - - - org.apache.maven.plugins - maven-release-plugin - ${releaseplugin.version} - - - org.apache.felix - maven-bundle-plugin - ${bundle.plugin.version} - true - - - org.apache.maven.plugins - maven-site-plugin - ${siteplugin} - - - - org.apache.maven.plugins - maven-project-info-reports-plugin - ${projectinfo} - - false - false - - - index - project-team - license - mailing-list - plugin-management - cim - issue-tracking - scm - summary - - - - org.apache.maven.plugins - maven-checkstyle-plugin - 2.10 - - - org.apache.maven.plugins - maven-javadoc-plugin - 2.8.1 - - org.jboss.apiviz.APIviz - - org.jboss.apiviz - apiviz - 1.3.2.GA - - ${project.artifactId}-${build.suffix} - true - UTF-8 - UTF-8 - UTF-8 - true - true - true - true - net.sf.jnetlib.*:cern.*:corejava - - - - org.apache.maven.plugins - maven-jxr-plugin - 2.3 - - true - true - - - - - - - - - - - - central2 - central2 - http://repo2.maven.org/maven2 - - false - - - never - true - - - - central - central - http://repo1.maven.org/maven2 - - false - - - never - true - - - - - thirdparty - thirdparty - ${nexusproxy}/repositories/thirdparty - - false - - - never - true - - - - - - - opendaylight-release - ${nexusproxy}/repositories/${nexus.repository.release}/ - - - - opendaylight-snapshot - ${nexusproxy}/repositories/${nexus.repository.snapshot}/ - - - - website - ${sitedeploy} - - - diff --git a/third-party/jersey-servlet/pom.xml b/third-party/jersey-servlet/pom.xml deleted file mode 100644 index 27d503e898..0000000000 --- a/third-party/jersey-servlet/pom.xml +++ /dev/null @@ -1,90 +0,0 @@ - - - - - org.opendaylight.controller - commons.thirdparty - 1.2.0-SNAPSHOT - ../commons/thirdparty - - - scm:git:ssh://git.opendaylight.org:29418/controller.git - scm:git:ssh://git.opendaylight.org:29418/controller.git - https://wiki.opendaylight.org/view/OpenDaylight_Controller:Main - HEAD - - - 4.0.0 - org.opendaylight.controller.thirdparty - com.sun.jersey.jersey-servlet - 1.19.0-SNAPSHOT - bundle - - - - org.apache.felix - maven-bundle-plugin - 2.3.6 - true - - - *;scope=!provided;type=!pom;inline=false - false - - 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 - - - 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 - - - ${project.basedir}/META-INF - - - - - - - - com.sun.jersey - jersey-servlet - 1.17 - - - equinoxSDK381 - javax.servlet - 3.0.0.v201112011016 - provided - - - diff --git a/third-party/net.sf.jung2/pom.xml b/third-party/net.sf.jung2/pom.xml deleted file mode 100644 index 63455dc8be..0000000000 --- a/third-party/net.sf.jung2/pom.xml +++ /dev/null @@ -1,80 +0,0 @@ - - - - - org.opendaylight.controller - commons.thirdparty - 1.2.0-SNAPSHOT - ../commons/thirdparty - - - scm:git:ssh://git.opendaylight.org:29418/controller.git - scm:git:ssh://git.opendaylight.org:29418/controller.git - https://wiki.opendaylight.org/view/OpenDaylight_Controller:Main - HEAD - - - 4.0.0 - org.opendaylight.controller.thirdparty - net.sf.jung2 - 2.1.0-SNAPSHOT - bundle - - - - org.apache.felix - maven-bundle-plugin - 2.3.6 - true - - - *;scope=compile|runtime;type=!pom;inline=false - false - - 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 - - - !* - - - ${project.basedir}/META-INF - - - - - - - - net.sf.jung - jung-api - 2.0.1 - - - net.sf.jung - jung-graph-impl - 2.0.1 - - - net.sourceforge.collections - collections-generic - 4.01 - - - 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 index a9d457345e..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/StructurallyEquivalent.java +++ /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 and j are structurally equivalent iff the set of i's - * neighbors is identical to the set of j's neighbors, with the - * exception of i and j themselves. This algorithm finds all - * sets of equivalent vertices in O(V^2) time. - * - *

You can extend this class to have a different definition of equivalence (by - * overriding isStructurallyEquivalent), and may give it hints for - * accelerating the process by overriding canPossiblyCompare. - * (For example, in a bipartite graph, canPossiblyCompare may - * return false for vertices in - * different partitions. This function should be fast.) - * - * @author Danyel Fisher - */ -public class StructurallyEquivalent implements Transformer, VertexPartition> -{ - public VertexPartition transform(Graph g) - { - Set> vertex_pairs = getEquivalentPairs(g); - - Set> rv = new HashSet>(); - Map> intermediate = new HashMap>(); - for (Pair p : vertex_pairs) - { - Set 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(); - 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 singletons = CollectionUtils.subtract(g.getVertices(), - intermediate.keySet()); - for (V v : singletons) - { - Set v_set = Collections.singleton(v); - intermediate.put(v, v_set); - rv.add(v_set); - } - - return new VertexPartition(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> getEquivalentPairs(Graph g) { - - Set> rv = new HashSet>(); - Set alreadyEquivalent = new HashSet(); - - List l = new ArrayList(g.getVertices()); - - for (V v1 : l) - { - if (alreadyEquivalent.contains(v1)) - continue; - - for (Iterator 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 p = new Pair(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 g, V v1, V v2) { - - if( g.degree(v1) != g.degree(v2)) { - return false; - } - - Set n1 = new HashSet(g.getPredecessors(v1)); - n1.remove(v2); - n1.remove(v1); - Set n2 = new HashSet(g.getPredecessors(v2)); - n2.remove(v1); - n2.remove(v2); - - Set o1 = new HashSet(g.getSuccessors(v1)); - Set o2 = new HashSet(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 index b5ec5831ba..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/VertexPartition.java +++ /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 -{ - private Map> vertex_partition_map; - private Collection> vertex_sets; - private Graph 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 g, Map> 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 g, Map> partition_map, - Collection> 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 g, Collection> 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 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> getVertexToPartitionMap() - { - if (vertex_partition_map == null) - { - this.vertex_partition_map = new HashMap>(); - for (Set 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> getVertexPartitions() - { - if (vertex_sets == null) - { - this.vertex_sets = new HashSet>(); - 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 index d1cb06acae..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/blockmodel/package.html +++ /dev/null @@ -1,33 +0,0 @@ - - - - - - - -Support for establishing and maintaining graph element equivalence (such as in blockmodeling). -

-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). -

-This support currently includes: -

    -
  • VertexPartition: A class that maintains information on a -division of the vertices of a graph into disjoint sets. -
  • StructurallyEquivalent: An algorithm that finds sets of vertices that are -structurally equivalent. -
- -

- - 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 index aa697c7dbb..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/BicomponentClusterer.java +++ /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. - *

- * 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 implements Transformer, Set>> -{ - protected Map dfs_num; - protected Map high; - protected Map parents; - protected Stack 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 ClusterSet of bicomponents - */ - public Set> transform(UndirectedGraph theGraph) - { - Set> bicomponents = new LinkedHashSet>(); - - if (theGraph.getVertices().isEmpty()) - return bicomponents; - - // initialize DFS number for each vertex to 0 - dfs_num = new HashMap(); - 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(); - stack = new Stack(); - parents = new HashMap(); - 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 s = new HashSet(); - s.add(v); - bicomponents.add(s); - } - } - } - - return bicomponents; - } - - /** - *

Stores, in bicomponents, all the biconnected - * components that are reachable from v.

- * - *

The algorithm basically proceeds as follows: do a depth-first - * traversal starting from v, 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. - * - *

(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)

- * - */ - protected void findBiconnectedComponents(UndirectedGraph g, V v, Set> 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 bicomponent = new HashSet(); - 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 index 59e4605e35..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/EdgeBetweennessClusterer.java +++ /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: - *
    - *
  • Compute edge betweenness for all edges in current graph - *
  • Remove edge with highest betweenness - *
- *

- * 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. - *

- * 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 implements Transformer,Set>> { - private int mNumEdgesToRemove; - private Map> 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>(); - } - - /** - * 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> transform(Graph graph) { - - if (mNumEdgesToRemove < 0 || mNumEdgesToRemove > graph.getEdgeCount()) { - throw new IllegalArgumentException("Invalid number of edges passed in."); - } - - edges_removed.clear(); - - for (int k=0;k bc = new BetweennessCentrality(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 wcSearch = new WeakComponentClusterer(); - Set> clusterSet = wcSearch.transform(graph); - - for (Map.Entry> entry : edges_removed.entrySet()) - { - Pair 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 getEdgesRemoved() - { - return new ArrayList(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 index 859c06307c..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/VoltageClusterer.java +++ /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; - -/** - *

Clusters vertices of a Graph based on their ranks as - * calculated by VoltageScorer. 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.

- * - *

The algorithm proceeds as follows: - *

    - *
  • first, generate a set of candidate clusters as follows: - *
      - *
    • pick (widely separated) vertex pair, run VoltageScorer - *
    • group the vertices in two clusters according to their voltages - *
    • store resulting candidate clusters - *
    - *
  • second, generate k-1 clusters as follows: - *
      - *
    • pick a vertex v as a cluster 'seed' - *
      (Wu/Huberman: most frequent vertex in candidate clusters) - *
    • calculate co-occurrence over all candidate clusters of v with each other - * vertex - *
    • separate co-occurrence counts into high/low; - * high vertices constitute a cluster - *
    • remove v's vertices from candidate clusters; continue - *
    - *
  • finally, remaining unassigned vertices are assigned to the kth ("garbage") - * cluster. - *

- * - *

NOTE: 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.

- * - * @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 -{ - protected int num_candidates; - protected KMeansClusterer kmc; - protected Random rand; - protected Graph 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 g, int num_candidates) - { - if (num_candidates < 1) - throw new IllegalArgumentException("must generate >=1 candidates"); - - this.num_candidates = num_candidates; - this.kmc = new KMeansClusterer(); - rand = new Random(); - this.g = g; - } - - protected void setRandomSeed(int random_seed) - { - rand = new Random(random_seed); - } - - /** - * Returns a community (cluster) centered around v. - * @param v the vertex whose community we wish to discover - */ - public Collection> getCommunity(V v) - { - return cluster_internal(v, 2); - } - - /** - * Clusters the vertices of g into - * num_clusters clusters, based on their connectivity. - * @param num_clusters the number of clusters to identify - */ - public Collection> cluster(int num_clusters) - { - return cluster_internal(null, num_clusters); - } - - /** - * Does the work of getCommunity and cluster. - * @param origin the vertex around which clustering is to be done - * @param num_clusters the (maximum) number of clusters to find - */ - protected Collection> 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_array = new ArrayList(g.getVertices()); - - LinkedList> candidates = new LinkedList>(); - - 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 vs = new VoltageScorer(g, source, target); - vs.evaluate(); - - Map voltage_ranks = new HashMap(); - 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> clusters = new LinkedList>(); - Set remaining = new HashSet(g.getVertices()); - - List 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 occur_counts = getObjectCounts(candidates, seed); - if (occur_counts.size() < 2) - break; - - // now that we have the counts, cluster them... - try - { - Collection> high_low = kmc.cluster(occur_counts, 2); - // ...get the cluster with the highest-valued centroid... - Iterator> h_iter = high_low.iterator(); - Map cluster1 = h_iter.next(); - Map cluster2 = h_iter.next(); - double[] centroid1 = DiscreteDistribution.mean(cluster1.values()); - double[] centroid2 = DiscreteDistribution.mean(cluster2.values()); - Set 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 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> candidates, - Map voltage_ranks) - { - try - { - List> clusters = new ArrayList>(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> candidates, - Map voltage_ranks) - { - try - { - List> clusters; - clusters = new ArrayList>(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 getSeedCandidates(Collection> candidates) - { - final Map occur_counts = getObjectCounts(candidates, null); - - ArrayList occurrences = new ArrayList(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 getObjectCounts(Collection> candidates, V seed) - { - Map occur_counts = new HashMap(); - for (V v : g.getVertices()) - occur_counts.put(v, new double[]{0}); - - for (Set 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 - { - private Map map; - - protected MapValueArrayComparator(Map 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 index cb79a78448..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/WeakComponentClusterer.java +++ /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. - *

This implementation identifies components as sets of vertex sets. - * To create the induced graphs from any or all of these vertex sets, - * see algorithms.filters.FilterUtils. - *

- * 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 implements Transformer, Set>> -{ - /** - * 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> transform(Graph graph) { - - Set> clusterSet = new HashSet>(); - - HashSet unvisitedVertices = new HashSet(graph.getVertices()); - - while (!unvisitedVertices.isEmpty()) { - Set cluster = new HashSet(); - V root = unvisitedVertices.iterator().next(); - unvisitedVertices.remove(root); - cluster.add(root); - - Buffer queue = new UnboundedFifoBuffer(); - queue.add(root); - - while (!queue.isEmpty()) { - V currentVertex = queue.remove(); - Collection 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 index f8bdb2279a..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/cluster/package.html +++ /dev/null @@ -1,35 +0,0 @@ - - - - - - - -Mechanisms for identifying clusters in graphs. Where these clusters define disjoint sets of vertices, -they may be used to define a VertexPartition for more convenient manipulation of the vertex/set -relationships. - -Current clustering algorithms include: -

    -
  • BicomponentClusterer: finds all subsets of vertices for which at least -2 vertices must be removed in order to disconnect the induced subgraphs. -
  • EdgeBetweennessClusterer: identifies vertex clusters by removing the edges of the highest -'betweenness' scores (see the importance/scoring package). -
  • VoltageClusterer: Clusters vertices based on their ranks as -calculated by VoltageRanker. -
  • WeakComponentVertexClusterer: Clusters vertices based on their membership in weakly -connected components of a graph. -
- - - - 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 index 5e3be06d18..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/EdgePredicateFilter.java +++ /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 Predicate. 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 implements Filter -{ - protected Predicate edge_pred; - - /** - * Creates an instance based on the specified edge Predicate. - * @param edge_pred the predicate that specifies which edges to add to the filtered graph - */ - public EdgePredicateFilter(Predicate edge_pred) - { - this.edge_pred = edge_pred; - } - - @SuppressWarnings("unchecked") - public Graph transform(Graph g) - { - Graph 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 index a62895cc43..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/Filter.java +++ /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 Graph - * as a Graph. The Graph 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 extends Transformer, Graph>{ } 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 index 4845c0f37b..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/FilterUtils.java +++ /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 graph whose vertex set - * is equal to vertices. The graph returned has - * vertices as its vertex set, and includes all edges from - * graph which are incident only to elements of - * vertices. - * - * @param the vertex type - * @param the edge type - * @param vertices the subset of graph'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 vertices - * @throws IllegalArgumentException if any vertex in - * vertices is not in graph - */ - @SuppressWarnings("unchecked") - public static > G createInducedSubgraph(Collection - 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 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 graph associated with each - * element of vertex_collections. - * Note that these vertex collections need not be disjoint. - * @param the vertex type - * @param 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 graph associated with each - * element of vertex_collections - */ - public static > Collection - createAllInducedSubgraphs(Collection> - vertex_collections, G graph) - { - Collection subgraphs = new ArrayList(); - - for (Collection 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 index 62bcfc29b5..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/KNeighborhoodFilter.java +++ /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 implements Filter { - - /** - * The type of edge to follow for defining the neighborhood. - */ - public static enum EdgeType { IN_OUT, IN, OUT } - private Set 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 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(); - 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 transform(Graph graph) { - // generate a Set of Vertices we want - // add all to the UG - int currentDepth = 0; - List currentVertices = new ArrayList(); - Set visitedVertices = new HashSet(); - Set visitedEdges = new HashSet(); - Set acceptedVertices = new HashSet(); - //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 newVertices = null; - //Use BFS to locate the neighborhood around the root nodes within distance k - while (currentDepth < radiusK) { - newVertices = new ArrayList(); - for (V currentVertex : currentVertices) { - - Collection 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 ug = null; - try { - ug = graph.getClass().newInstance(); - for(E edge : graph.getEdges()) { - Pair 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 index 4543b424dc..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/VertexPredicateFilter.java +++ /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 Predicate. 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 implements Filter -{ - protected Predicate vertex_pred; - - /** - * Creates an instance based on the specified vertex Predicate. - * @param vertex_pred the predicate that specifies which vertices to add to the filtered graph - */ - public VertexPredicateFilter(Predicate vertex_pred) - { - this.vertex_pred = vertex_pred; - } - - @SuppressWarnings("unchecked") - public Graph transform(Graph g) - { - Graph 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 filtered_vertices = filtered.getVertices(); - - for (E e : g.getEdges()) - { - Collection 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 index 0f9a018f88..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/filters/package.html +++ /dev/null @@ -1,31 +0,0 @@ - - - - - - - -Filtering mechanisms that produce subgraphs of an original graph. -Currently includes: -
    -
  • Filter: an interface for graph filters -
  • {Edge,Vertex}PredicateFilter: graph filters that return the -induced subgraph according to the -specified edge or vertex Predicate, respectively. -
  • KNeighborhoodFilter: a filter that returns the subgraph -induced by vertices within (unweighted) distance k of a specified vertex. -
- - - - - 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 index af9ee34c4c..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/flows/EdmondsKarpMaxFlow.java +++ /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. - *

- * An example of using this algorithm is as follows: - * 

- * EdmondsKarpMaxFlow ek = new EdmondsKarpMaxFlow(graph, source, sink, edge_capacities, edge_flows, 
- * edge_factory);
- * ek.evaluate(); // This instructs the class to compute the max flow
- *
- * - * @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 extends IterativeProcess { - - private DirectedGraph mFlowGraph; - private DirectedGraph mOriginalGraph; - private V source; - private V target; - private int mMaxFlow; - private Set mSourcePartitionNodes; - private Set mSinkPartitionNodes; - private Set mMinCutEdges; - - private Map residualCapacityMap = new HashMap(); - private Map parentMap = new HashMap(); - private Map parentCapacityMap = new HashMap(); - private Transformer edgeCapacityTransformer; - private Map edgeFlowMap; - private Factory 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 directedGraph, V source, V sink, - Transformer edgeCapacityTransformer, Map edgeFlowMap, - Factory 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(); - mSourcePartitionNodes = new HashSet(); - mMinCutEdges = new HashSet(); - } - - 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 visitedEdgesMap = new HashSet(); - Buffer queue = new UnboundedFifoBuffer(); - queue.add(source); - - while (!queue.isEmpty()) { - V currentVertex = queue.remove(); - mSinkPartitionNodes.remove(currentVertex); - mSourcePartitionNodes.add(currentVertex); - Number currentCapacity = parentCapacityMap.get(currentVertex); - - Collection 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 getNodesInSinkPartition() { - return mSinkPartitionNodes; - } - - /** - * Returns the nodes which share the same partition (as defined by the min-cut edges) - * as the source node. - */ - public Set getNodesInSourcePartition() { - return mSourcePartitionNodes; - } - - /** - * Returns the edges in the minimum cut. - */ - public Set getMinCutEdges() { - return mMinCutEdges; - } - - /** - * Returns the graph for which the maximum flow is calculated. - */ - public DirectedGraph getFlowGraph() { - return mFlowGraph; - } - - @Override - protected void initializeIterations() { - parentCapacityMap.put(source, Integer.MAX_VALUE); - parentMap.put(source, source); - - List edgeList = new ArrayList(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 backEdges = new HashSet(); - 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 index 1ec243d845..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/flows/package.html +++ /dev/null @@ -1,20 +0,0 @@ - - - - - - - -Methods for calculating properties relating to network flows (such as max flow/min cut). - - - 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 index d351f9b1ca..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/EvolvingGraphGenerator.java +++ /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 extends GraphGenerator { - - /** - * 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 index a32906095f..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/GraphGenerator.java +++ /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 extends Factory>{ } 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 index e84425cebb..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/Lattice2DGenerator.java +++ /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. - * - *

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 implements GraphGenerator -{ - protected int row_count; - protected int col_count; - protected boolean is_toroidal; - protected boolean is_directed; - protected Factory> graph_factory; - protected Factory vertex_factory; - protected Factory edge_factory; - private List 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> graph_factory, Factory vertex_factory, - Factory 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> graph_factory, Factory vertex_factory, - Factory 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 create() - { - int vertex_count = row_count * col_count; - Graph graph = graph_factory.create(); - v_array = new ArrayList(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 index 441922dca5..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/package.html +++ /dev/null @@ -1,20 +0,0 @@ - - - - - - - -Methods for generating new (often random) graphs with various properties. - - - 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 index 77b419b4a4..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/BarabasiAlbertGenerator.java +++ /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; - - -/** - *

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.

- * - *

At a given timestep, the probability p of creating an edge - * between an existing vertex v and the newly added vertex is - * 

- * p = (degree(v) + 1) / (|E| + |V|);
- *
- * - *

where |E| and |V| 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).

- * - *

Note that the formula specified in the original paper - * (cited below) was - * 

- * p = degree(v) / |E|
- *
- *

- * - *

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.

- * - *

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.

- * - *

The parallel constructor parameter specifies whether parallel edges - * may be created.

- * - * @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 implements EvolvingGraphGenerator { - private Graph mGraph = null; - private int mNumEdgesToAttachPerStep; - private int mElapsedTimeSteps; - private Random mRandom; - protected List vertex_index; - protected int init_vertices; - protected Map index_vertex; - protected Factory> graphFactory; - protected Factory vertexFactory; - protected Factory 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> graphFactory, - Factory vertexFactory, Factory edgeFactory, - int init_vertices, int numEdgesToAttach, - int seed, Set 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> graphFactory, - Factory vertexFactory, Factory edgeFactory, - int init_vertices, int numEdgesToAttach, Set seedVertices) { - this(graphFactory, vertexFactory, edgeFactory, init_vertices, numEdgesToAttach, (int) System.currentTimeMillis(), seedVertices); - } - - private void initialize(Set seedVertices) { - - mGraph = graphFactory.create(); - - vertex_index = new ArrayList(2*init_vertices); - index_vertex = new HashMap(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 preexistingNodes, - V newVertex, Set> added_pairs) { - V attach_point; - boolean created_edge = false; - Pair endpoints; - do { - attach_point = vertex_index.get(mRandom.nextInt(vertex_index.size())); - - endpoints = new Pair(newVertex, attach_point); - - // if parallel edges are not allowed, skip attach_point if - // 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(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(attach_point, newVertex)); - } - } - - public void evolveGraph(int numTimeSteps) { - - for (int i = 0; i < numTimeSteps; i++) { - evolveGraph(); - mElapsedTimeSteps++; - } - } - - private void evolveGraph() { - Collection 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> added_pairs = new HashSet>(mNumEdgesToAttachPerStep*3); - - for (int i = 0; i < mNumEdgesToAttachPerStep; i++) - createRandomEdge(preexistingNodes, newVertex, added_pairs); - - for (Pair 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 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 index e3bf04b68d..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/EppsteinPowerLawGenerator.java +++ /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 implements GraphGenerator { - private int mNumVertices; - private int mNumEdges; - private int mNumIterations; - private double mMaxDegree; - private Random mRandom; - private Factory> graphFactory; - private Factory vertexFactory; - private Factory 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> graphFactory, - Factory vertexFactory, Factory 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 initializeGraph() { - Graph graph = null; - graph = graphFactory.create(); - for(int i=0; i vertices = new ArrayList(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 create() { - Graph graph = initializeGraph(); - - List vertices = new ArrayList(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 edges = new ArrayList(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 index 3a33730802..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/ErdosRenyiGenerator.java +++ /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 implements GraphGenerator { - private int mNumVertices; - private double mEdgeConnectionProbability; - private Random mRandom; - Factory> graphFactory; - Factory vertexFactory; - Factory edgeFactory; - - /** - * - * @param numVertices number of vertices graph should have - * @param p Connection's probability between 2 vertices - */ - public ErdosRenyiGenerator(Factory> graphFactory, - Factory vertexFactory, Factory 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 create() { - UndirectedGraph g = graphFactory.create(); - for(int i=0; i list = new ArrayList(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 index de01b69b5a..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/KleinbergSmallWorldGenerator.java +++ /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 extends Lattice2DGenerator { - 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> graph_factory, Factory vertex_factory, - Factory 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> graph_factory, Factory vertex_factory, - Factory 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> graph_factory, Factory vertex_factory, - Factory 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 create() - { - Graph 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 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 vertex_weights = new HashMap(); - 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(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 index a39a6404bd..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/MixedRandomGraphGenerator.java +++ /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 BarabasiAlbertGenerator. - * Primarily intended for providing a heterogeneous sample graph for visualization testing, etc. - * - */ -public class MixedRandomGraphGenerator { - - /** - * Equivalent to generateMixedRandomGraph(edge_weight, num_vertices, true). - */ - public static Graph generateMixedRandomGraph( - Factory> graphFactory, - Factory vertexFactory, - Factory edgeFactory, - Map edge_weight, - int num_vertices, Set 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 Graph generateMixedRandomGraph( - Factory> graphFactory, - Factory vertexFactory, - Factory edgeFactory, - Map edge_weights, - int num_vertices, boolean parallel, Set seedVertices) - { - int seed = (int)(Math.random() * 10000); - BarabasiAlbertGenerator bag = - new BarabasiAlbertGenerator(graphFactory, vertexFactory, edgeFactory, - 4, 3, //false, parallel, - seed, seedVertices); - bag.evolveGraph(num_vertices - 4); - Graph ug = bag.create(); - - // create a SparseMultigraph version of g - Graph g = graphFactory.create(); - //new SparseMultigraph(); - 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 index 9f85614a82..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/package.html +++ /dev/null @@ -1,28 +0,0 @@ - - - - - - - -Methods for generating random graphs with various properties. These include: -