commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject 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/
Date Fri, 02 Mar 2012 21:57:44 GMT
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 );
     }
 
 }



Mime
View raw message