commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From t.@apache.org
Subject svn commit: r1295773 - in /commons/sandbox/graph/trunk/src: main/java/org/apache/commons/graph/scc/ test/java/org/apache/commons/graph/scc/
Date Thu, 01 Mar 2012 20:27:55 GMT
Author: tn
Date: Thu Mar  1 20:27:55 2012
New Revision: 1295773

URL: http://svn.apache.org/viewvc?rev=1295773&view=rev
Log:
added Kosaraju Sharir algorithm for SCC.

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

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=1295773&r1=1295772&r2=1295773&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
Thu Mar  1 20:27:55 2012
@@ -21,12 +21,14 @@ package org.apache.commons.graph.scc;
 
 import static java.lang.Math.min;
 import static org.apache.commons.graph.CommonsGraph.visit;
-import static org.apache.commons.graph.utils.Assertions.checkNotNull;
-import static org.apache.commons.graph.utils.Assertions.checkState;
 
+import java.util.ArrayList;
+import java.util.Collection;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.Stack;
@@ -58,21 +60,143 @@ public final class DefaultSccAlgorithmSe
     /**
      * {@inheritDoc}
      */
-    public Set<V> applyingKosarajuSharir( V source )
+    public Set<V> applyingKosarajuSharir( final V source )
     {
-        source = checkNotNull( source, "KosarajuSharir algorithm requires a non-null source
vertex" );
-        checkState( graph.containsVertex( source ), "Vertex %s does not exist in the Graph",
source );
-
-        visit( graph ).from( source ).applyingDepthFirstSearch( new KosarajuSharirVisitHandler<V,
E, G>( source ) );
+        final Set<V> visitedVertices = new HashSet<V>();
+        final List<V> expandedVertexList = getExpandedVertexList( source, visitedVertices
);
+        final DirectedGraph<V, E> reverted = new RevertedGraph<V, E>( graph );
+        
+        // remove the last element from the expanded vertices list
+        final V v = expandedVertexList.remove( expandedVertexList.size() - 1 );
+        final Set<V> sccSet = new HashSet<V>();
+        searchRecursive( reverted, v, sccSet, visitedVertices, false );
+        return sccSet;
+    }
+    
+    /**
+     * {@inheritDoc}
+     */
+    public Set<Set<V>> applyingKosarajuSharir()
+    {
+        final Set<V> visitedVertices = new HashSet<V>();
+        final List<V> expandedVertexList = getExpandedVertexList( null, visitedVertices
);
+        final DirectedGraph<V, E> reverted = new RevertedGraph<V, E>( graph );
 
-        DirectedGraph<V, E> reverted = new RevertedGraph<V, E>( graph );
+        final Set<Set<V>> sccs = new HashSet<Set<V>>();
 
-        // TODO FILL ME, algorithm is incomplete
+        while ( expandedVertexList.size() > 0 )
+        {
+            // remove the last element from the expanded vertices list
+            final V v = expandedVertexList.remove( expandedVertexList.size() - 1 );
+            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 );
+            sccs.add( sccSet );
+        }
+        
+        return sccs;
+    }
+    
+    private List<V> getExpandedVertexList( final V source, final Set<V> visitedVertices
)
+    {
+        final int size = (source != null) ? 13 : graph.getOrder();
+        final Set<V> vertices = new HashSet<V>( size );
+        
+        if ( source != null )
+        {
+            vertices.add( source );
+        }
+        else
+        {
+            for ( V vertex : graph.getVertices() )
+            {
+                vertices.add( vertex );
+            }
+        }
+    
+        // use an ArrayList so that subList is fast
+        final ArrayList<V> expandedVertexList = new ArrayList<V>();
 
-        return null;
+        int idx = 0;
+        while ( ! vertices.isEmpty() )
+        {
+            // get the next vertex that has not yet been added to the expanded list
+            final V v = vertices.iterator().next();            
+            searchRecursive( graph, v, expandedVertexList, visitedVertices, true );
+            // remove all expanded vertices from the list of vertices that have to be
+            // still processed. To improve performance, only the items that have been
+            // added to the list since the last iteration are removed
+            vertices.removeAll( expandedVertexList.subList( idx, expandedVertexList.size()
) );
+            idx = expandedVertexList.size();
+        }
+        
+        return expandedVertexList;
     }
 
     /**
+     * Searches a directed graph in iterative depth-first order, while adding the visited
+     * vertices in a recursive manner, i.e. a vertex is added to the result list only 
+     * when the search has finished expanding the vertex (and its subsequent childs).
+     * 
+     * <p><b>Implementation Note:</b> in the first step we look for vertices
that have not
+     * been visited yet, while in the second step we search for vertices that have already
+     * been visited.</p>
+     * @param graph the graph to be search
+     * @param source the start vertex
+     * @param coll the recursive collection of visited vertices
+     * @param visited contains vertices that have been already visited
+     * @param forward <code>true</code> for the first step of Kosaraju's algorithm,
+     * <code>false</code> for the second step.
+     */
+    private void searchRecursive( final DirectedGraph<V, E> graph, final V source,
+                                  final Collection<V> coll, final Set<V> visited,
+                                  final boolean forward )
+    {
+        final LinkedList<V> stack = new LinkedList<V>();
+        stack.addLast( source );
+        
+        while ( !stack.isEmpty() )
+        {
+            final V v = stack.removeLast();
+
+            // if the vertex has already been visited it can be put into the
+            // collection, as we are now finished expanding this vertex
+            // the if takes both cases into account:
+            //  * step1: forward && visited.contains(v)
+            //  * step2: !forward && !visited.contains(v)
+            if ( ! ( forward ^ visited.contains( v ) ) )
+            {
+                coll.add( v );
+                continue;                    
+            }
+
+            // add the current vertex to the stack, so it is visited again
+            // when all connected vertices have been visited
+            stack.addLast( v );
+            if ( forward )
+            {
+                visited.add( v );
+            }
+            else
+            {
+                visited.remove( v );
+            }
+
+            // add all not yet visited vertices that can be reached from this
+            // vertex to the stack
+            for ( V w : graph.getOutbound( v ) )
+            {
+                if ( ! ( forward ^ ! visited.contains( w ) ) )
+                {
+                    stack.addLast( w );
+                }
+            }
+        }
+    }
+    
+    /**
      * {@inheritDoc}
      */
     public Set<V> applyingCheriyanMehlhornGabow()

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=1295773&r1=1295772&r2=1295773&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
Thu Mar  1 20:27:55 2012
@@ -35,7 +35,8 @@ public interface SccAlgorithmSelector<V 
 {
 
     /**
-     * Applies the classical Kosaraju's algorithm to find the strongly connected components,
if exist.
+     * Applies the classical Kosaraju's algorithm to find the strongly connected components
of
+     * a vertex <code>source</code>.
      *
      * @param source the source vertex to start the search from
      * @return the input graph strongly connected component.
@@ -43,6 +44,14 @@ public interface SccAlgorithmSelector<V 
     Set<V> applyingKosarajuSharir( V source );
 
     /**
+     * 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.
+     */
+    Set<Set<V>> applyingKosarajuSharir();
+
+    /**
      * Applies the classical Cheriyan/Mehlhorn/Gabow's algorithm to find the strongly connected
components, if exist.
      *
      * @return the input graph strongly connected component.

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=1295773&r1=1295772&r2=1295773&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
Thu Mar  1 20:27:55 2012
@@ -22,15 +22,17 @@ 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.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 
+import java.util.Collections;
+import java.util.HashSet;
 import java.util.Set;
 
 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.Ignore;
 import org.junit.Test;
 
 /**
@@ -41,10 +43,17 @@ public final class KosarajuSharirTestCas
 {
 
     @Test
-    @Ignore
+    //@Ignore
     public void verifyHasStronglyConnectedComponents()
     {
         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" );
 
         DirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge> graph =
         newDirectedMutableGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledEdge>()
@@ -53,13 +62,13 @@ public final class KosarajuSharirTestCas
             public void connect()
             {
                 addVertex( a );
-                BaseLabeledVertex b = addVertex( new BaseLabeledVertex( "B" ) );
-                BaseLabeledVertex c = addVertex( new BaseLabeledVertex( "C" ) );
-                BaseLabeledVertex d = addVertex( new BaseLabeledVertex( "D" ) );
-                BaseLabeledVertex e = addVertex( new BaseLabeledVertex( "E" ) );
-                BaseLabeledVertex f = addVertex( new BaseLabeledVertex( "F" ) );
-                BaseLabeledVertex g = addVertex( new BaseLabeledVertex( "G" ) );
-                BaseLabeledVertex h = addVertex( new BaseLabeledVertex( "H" ) );
+                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 );
@@ -76,9 +85,36 @@ public final class KosarajuSharirTestCas
 
         } );
 
-        Set<BaseLabeledVertex> ssc = findStronglyConnectedComponent( graph ).applyingKosarajuSharir(
a );
+        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 );
+
+        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( ssc.isEmpty() );
+        assertFalse( actualG.isEmpty() );
+        assertEquals( scc3, actualG );        
     }
 
 }



Mime
View raw message