> +     * @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 `true` for the first step of Kosaraju's algorithm, > +     * `false` for the second step. > +     */ > +    private void searchRecursive( final DirectedGraph graph, final V source, > +                                  final Collection coll, final Set visited, > +                                  final boolean forward ) > +    { > +        final LinkedList stack = new LinkedList(); > +        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 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  { > >     /** > -     * 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 `source`. >      * >      * @param source the source vertex to start the search from >      * @return the input graph strongly connected component. > @@ -43,6 +44,14 @@ public interface SccAlgorithmSelector     Set 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> 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 graph = >         newDirectedMutableGraph( new AbstractGraphConnection() > @@ -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 ssc = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( a ); > +        Set> expected = new HashSet>(); > +        Set scc1 = new HashSet(); > +        Collections.addAll( scc1, a, b, d ); > +        expected.add( scc1 ); > +        Set scc2 = new HashSet(); > +        Collections.addAll( scc2, e, f ); > +        expected.add( scc2 ); > +        Set scc3 = new HashSet(); > +        Collections.addAll( scc3, g, h, c ); > +        expected.add( scc3 ); > + > +        Set> actual = findStronglyConnectedComponent( graph ).applyingKosarajuSharir(); > + > +        assertFalse( actual.isEmpty() ); > +        assertEquals( expected, actual ); > + > +        Set actualA = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( a ); > + > +        assertFalse( actualA.isEmpty() ); > +        assertEquals( scc1, actualA ); > + > +        Set actualE = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( e ); > + > +        assertFalse( actualE.isEmpty() ); > +        assertEquals( scc2, actualE ); > + > +        Set actualG = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( g ); > > -        assertFalse( ssc.isEmpty() ); > +        assertFalse( actualG.isEmpty() ); > +        assertEquals( scc3, actualG ); >     } > >  } > > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org For additional commands, e-mail: dev-help@commons.apache.org