You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2012/03/02 22:57:44 UTC
svn commit: r1296490 - in /commons/sandbox/graph/trunk/src:
benchmarks/java/org/apache/commons/graph/scc/
main/java/org/apache/commons/graph/scc/
test/java/org/apache/commons/graph/scc/
Author: tn
Date: Fri Mar 2 21:57:44 2012
New Revision: 1296490
URL: http://svn.apache.org/viewvc?rev=1296490&view=rev
Log:
greatly improved speed of Kosarajus algorithm, added more unit tests, SCC benchmark and javadoc with runtime complexity information and algorithm recommendation
Added:
commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/
commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java (with props)
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithmSelector.java
commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java
Added: commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java?rev=1296490&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java (added)
+++ commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java Fri Mar 2 21:57:44 2012
@@ -0,0 +1,102 @@
+package org.apache.commons.graph.scc;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+import static java.lang.String.format;
+import static java.lang.String.valueOf;
+import static org.apache.commons.graph.CommonsGraph.findStronglyConnectedComponent;
+import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph;
+import static org.junit.Assert.assertTrue;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Random;
+import java.util.Set;
+
+import org.apache.commons.graph.GraphException;
+import org.apache.commons.graph.builder.AbstractGraphConnection;
+import org.apache.commons.graph.model.BaseLabeledEdge;
+import org.apache.commons.graph.model.BaseLabeledVertex;
+import org.apache.commons.graph.model.DirectedMutableGraph;
+import org.junit.BeforeClass;
+import org.junit.Rule;
+import org.junit.Test;
+
+import com.carrotsearch.junitbenchmarks.BenchmarkRule;
+import com.carrotsearch.junitbenchmarks.annotation.AxisRange;
+import com.carrotsearch.junitbenchmarks.annotation.BenchmarkMethodChart;
+
+@AxisRange( min = 0, max = 2 )
+@BenchmarkMethodChart( filePrefix = "strongly-connected-components" )
+public final class SCCAlgorithmBenchmarkTestCase
+{
+ private static final int NODES = 5000;
+ private static final int EDGES = 5000;
+
+ @Rule
+ public BenchmarkRule benchmarkRun = new BenchmarkRule();
+
+ private static DirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> graph;
+
+ @BeforeClass
+ public static void setUp()
+ {
+ graph = newDirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
+ public void connect()
+ {
+ List<BaseLabeledVertex> vertices = new ArrayList<BaseLabeledVertex>();
+ for ( int i = 0; i < NODES; i++ )
+ {
+ BaseLabeledVertex v = new BaseLabeledVertex( valueOf( i ) );
+ addVertex( v );
+ vertices.add( v );
+ }
+
+ Random r = new Random();
+ for ( int i = 0; i < EDGES; i++ ) {
+ int v1 = r.nextInt(NODES);
+ int v2 = r.nextInt(NODES);
+
+ try {
+ addEdge( new BaseLabeledEdge( format( "%s -> %s", v1, v2 ) ) ).from( vertices.get( v1 ) ).to( vertices.get( v2 ) );
+ } catch (GraphException e) {
+ // ignore duplicate edge exceptions
+ }
+ }
+ }
+ } );
+ }
+
+ @Test
+ public void performKosaraju()
+ {
+ Set<Set<BaseLabeledVertex>> actual = findStronglyConnectedComponent( graph ).applyingKosarajuSharir();
+ assertTrue( actual.size() > 0 );
+ }
+
+ @Test
+ public void performTarjan()
+ {
+ Set<Set<BaseLabeledVertex>> actual = findStronglyConnectedComponent( graph ).applyingTarjan();
+ assertTrue( actual.size() > 0 );
+ }
+
+}
Propchange: commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java
------------------------------------------------------------------------------
svn:keywords = Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java?rev=1296490&r1=1296489&r2=1296490&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java Fri Mar 2 21:57:44 2012
@@ -89,21 +89,36 @@ public final class DefaultSccAlgorithmSe
final Set<Set<V>> sccs = new HashSet<Set<V>>();
- while ( expandedVertexList.size() > 0 )
+ // insert the expanded vertices in reverse order into a linked hash set
+ // this is needed to quickly remove already found SCCs from the stack
+ final LinkedHashSet<V> stack = new LinkedHashSet<V>();
+ for ( int i = expandedVertexList.size() - 1; i >= 0; i-- )
+ {
+ stack.add(expandedVertexList.get( i ) );
+ }
+
+ while ( stack.size() > 0 )
{
// remove the last element from the expanded vertices list
- final V v = expandedVertexList.remove( expandedVertexList.size() - 1 );
+ final V v = stack.iterator().next();
final Set<V> sccSet = new HashSet<V>();
searchRecursive( reverted, v, sccSet, visitedVertices, false );
// remove all strongly connected components from the expanded list
- expandedVertexList.removeAll( sccSet );
+ stack.removeAll( sccSet );
sccs.add( sccSet );
}
return sccs;
}
+ /**
+ * Performs a depth-first search to create a recursive vertex list.
+ *
+ * @param source the starting vertex
+ * @param visitedVertices a {@link Set} containing all visited vertices
+ * @return the recursively expanded vertex list for Kosaraju's algorithm
+ */
private List<V> getExpandedVertexList( final V source, final Set<V> visitedVertices )
{
final int size = (source != null) ? 13 : graph.getOrder();
Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithmSelector.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithmSelector.java?rev=1296490&r1=1296489&r2=1296490&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithmSelector.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithmSelector.java Fri Mar 2 21:57:44 2012
@@ -46,8 +46,10 @@ public interface SccAlgorithmSelector<V
/**
* Applies the classical Kosaraju's algorithm to find the strongly connected components.
*
- * @param source the source vertex to start the search from
- * @return the input graph strongly connected component.
+ * <p>Note: the runtime complexity is O(V + E) and this algorithm should be chosen
+ * if the number of vertices outweighs the number of edges.</p>
+ *
+ * @return the input graph strongly connected components.
*/
Set<Set<V>> applyingKosarajuSharir();
@@ -62,6 +64,9 @@ public interface SccAlgorithmSelector<V
* Tarjan's algorithm is a variation (slightly faster) on KosarajuSharir's algorithm for finding
* strongly-connected components in a directed graph.
*
+ * <p>Note: the runtime complexity is O(V + E) and this algorithm should be chosen
+ * if the number of edges outweighs the number of vertices.</p>
+ *
* @return the input graph strongly connected component.
*/
Set<Set<V>> applyingTarjan();
Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java?rev=1296490&r1=1296489&r2=1296490&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java (original)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java Fri Mar 2 21:57:44 2012
@@ -21,7 +21,6 @@ package org.apache.commons.graph.scc;
import static org.apache.commons.graph.CommonsGraph.findStronglyConnectedComponent;
import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph;
-import static org.apache.commons.graph.CommonsGraph.newDirectedMutableWeightedGraph;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
@@ -72,44 +71,81 @@ public final class KosarajuSharirTestCas
}
@Test
- public void testEmptyGraph()
+ public void verifyHasStronglyConnectedComponents()
{
- DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer> graph =
- new DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer>();
+ final BaseLabeledVertex a = new BaseLabeledVertex( "A" );
+ final BaseLabeledVertex b = new BaseLabeledVertex( "B" );
+ final BaseLabeledVertex c = new BaseLabeledVertex( "C" );
+ final BaseLabeledVertex d = new BaseLabeledVertex( "D" );
+ final BaseLabeledVertex e = new BaseLabeledVertex( "E" );
+ final BaseLabeledVertex f = new BaseLabeledVertex( "F" );
+ final BaseLabeledVertex g = new BaseLabeledVertex( "G" );
+ final BaseLabeledVertex h = new BaseLabeledVertex( "H" );
- findStronglyConnectedComponent( graph ).applyingKosarajuSharir();
- }
+ DirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> graph =
+ newDirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
+ {
- @Test
- public void testSparse()
- {
- DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer> graph =
- newDirectedMutableWeightedGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>>()
+ public void connect()
{
+ addVertex( a );
+ addVertex( b );
+ addVertex( c );
+ addVertex( d );
+ addVertex( e );
+ addVertex( f );
+ addVertex( g );
+ addVertex( h );
+
+ addEdge( new BaseLabeledEdge( "A -> F" ) ).from( a ).to( f );
+ addEdge( new BaseLabeledEdge( "A -> B" ) ).from( a ).to( b );
+ addEdge( new BaseLabeledEdge( "B -> D" ) ).from( b ).to( d );
+ addEdge( new BaseLabeledEdge( "C -> G" ) ).from( c ).to( g );
+ addEdge( new BaseLabeledEdge( "D -> A" ) ).from( d ).to( a );
+ addEdge( new BaseLabeledEdge( "D -> G" ) ).from( d ).to( g );
+ addEdge( new BaseLabeledEdge( "E -> C" ) ).from( e ).to( c );
+ addEdge( new BaseLabeledEdge( "E -> F" ) ).from( e ).to( f );
+ addEdge( new BaseLabeledEdge( "F -> E" ) ).from( f ).to( e );
+ addEdge( new BaseLabeledEdge( "G -> H" ) ).from( g ).to( h );
+ addEdge( new BaseLabeledEdge( "H -> C" ) ).from( h ).to( c );
+ }
- @Override
- public void connect()
- {
- addVertex( new BaseLabeledVertex( "A" ) );
- addVertex( new BaseLabeledVertex( "B" ) );
- addVertex( new BaseLabeledVertex( "C" ) );
- addVertex( new BaseLabeledVertex( "D" ) );
- addVertex( new BaseLabeledVertex( "E" ) );
- addVertex( new BaseLabeledVertex( "F" ) );
- }
- } );
+ } );
- // expected strong components
- final int expected = 6;
+ Set<Set<BaseLabeledVertex>> expected = new HashSet<Set<BaseLabeledVertex>>();
+ Set<BaseLabeledVertex> scc1 = new HashSet<BaseLabeledVertex>();
+ Collections.addAll( scc1, a, b, d );
+ expected.add( scc1 );
+ Set<BaseLabeledVertex> scc2 = new HashSet<BaseLabeledVertex>();
+ Collections.addAll( scc2, e, f );
+ expected.add( scc2 );
+ Set<BaseLabeledVertex> scc3 = new HashSet<BaseLabeledVertex>();
+ Collections.addAll( scc3, g, h, c );
+ expected.add( scc3 );
- // actual strong components
Set<Set<BaseLabeledVertex>> actual = findStronglyConnectedComponent( graph ).applyingKosarajuSharir();
- assertEquals( actual.size(), expected );
+ assertFalse( actual.isEmpty() );
+ assertEquals( expected, actual );
+
+ Set<BaseLabeledVertex> actualA = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( a );
+
+ assertFalse( actualA.isEmpty() );
+ assertEquals( scc1, actualA );
+
+ Set<BaseLabeledVertex> actualE = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( e );
+
+ assertFalse( actualE.isEmpty() );
+ assertEquals( scc2, actualE );
+
+ Set<BaseLabeledVertex> actualG = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( g );
+
+ assertFalse( actualG.isEmpty() );
+ assertEquals( scc3, actualG );
}
-
+
@Test
- public void verifyHasStronglyConnectedComponents()
+ public void testUnconnectedGraph()
{
final BaseLabeledVertex a = new BaseLabeledVertex( "A" );
final BaseLabeledVertex b = new BaseLabeledVertex( "B" );
@@ -135,12 +171,12 @@ public final class KosarajuSharirTestCas
addVertex( g );
addVertex( h );
- addEdge( new BaseLabeledEdge( "A -> F" ) ).from( a ).to( f );
+ //addEdge( new BaseLabeledEdge( "A -> F" ) ).from( a ).to( f );
addEdge( new BaseLabeledEdge( "A -> B" ) ).from( a ).to( b );
addEdge( new BaseLabeledEdge( "B -> D" ) ).from( b ).to( d );
addEdge( new BaseLabeledEdge( "C -> G" ) ).from( c ).to( g );
addEdge( new BaseLabeledEdge( "D -> A" ) ).from( d ).to( a );
- addEdge( new BaseLabeledEdge( "D -> G" ) ).from( d ).to( g );
+ //addEdge( new BaseLabeledEdge( "D -> G" ) ).from( d ).to( g );
addEdge( new BaseLabeledEdge( "E -> C" ) ).from( e ).to( c );
addEdge( new BaseLabeledEdge( "E -> F" ) ).from( e ).to( f );
addEdge( new BaseLabeledEdge( "F -> E" ) ).from( f ).to( e );
@@ -162,24 +198,24 @@ public final class KosarajuSharirTestCas
expected.add( scc3 );
Set<Set<BaseLabeledVertex>> actual = findStronglyConnectedComponent( graph ).applyingKosarajuSharir();
-
+
assertFalse( actual.isEmpty() );
assertEquals( expected, actual );
-
+
Set<BaseLabeledVertex> actualA = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( a );
assertFalse( actualA.isEmpty() );
assertEquals( scc1, actualA );
-
+
Set<BaseLabeledVertex> actualE = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( e );
assertFalse( actualE.isEmpty() );
assertEquals( scc2, actualE );
-
+
Set<BaseLabeledVertex> actualG = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( g );
assertFalse( actualG.isEmpty() );
- assertEquals( scc3, actualG );
+ assertEquals( scc3, actualG );
}
}