> + =C2=A0 =C2=A0 * @param graph the graph to be search > + =C2=A0 =C2=A0 * @param source the start vertex > + =C2=A0 =C2=A0 * @param coll the recursive collection of visited vertice= s > + =C2=A0 =C2=A0 * @param visited contains vertices that have been already= visited > + =C2=A0 =C2=A0 * @param forward `true` for the first step of = Kosaraju's algorithm, > + =C2=A0 =C2=A0 * `false` for the second step. > + =C2=A0 =C2=A0 */ > + =C2=A0 =C2=A0private void searchRecursive( final DirectedGraph gr= aph, final V source, > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0final Collection coll, f= inal Set visited, > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0final boolean forward ) > + =C2=A0 =C2=A0{ > + =C2=A0 =C2=A0 =C2=A0 =C2=A0final LinkedList stack =3D new LinkedList= (); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0stack.addLast( source ); > + > + =C2=A0 =C2=A0 =C2=A0 =C2=A0while ( !stack.isEmpty() ) > + =C2=A0 =C2=A0 =C2=A0 =C2=A0{ > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0final V v =3D stack.removeLast= (); > + > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// if the vertex has already b= een visited it can be put into the > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// collection, as we are now f= inished expanding this vertex > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// the if takes both cases int= o account: > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// =C2=A0* step1: forward && v= isited.contains(v) > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// =C2=A0* step2: !forward && = !visited.contains(v) > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if ( ! ( forward ^ visited.con= tains( v ) ) ) > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0{ > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0coll.add( v ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0continue; > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0} > + > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// add the current vertex to t= he stack, so it is visited again > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// when all connected vertices= have been visited > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0stack.addLast( v ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if ( forward ) > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0{ > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0visited.add( v )= ; > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0} > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0else > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0{ > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0visited.remove( = v ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0} > + > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// add all not yet visited ver= tices that can be reached from this > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0// vertex to the stack > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0for ( V w : graph.getOutbound(= v ) ) > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0{ > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0if ( ! ( forward= ^ ! visited.contains( w ) ) ) > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0{ > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0st= ack.addLast( w ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0} > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0} > + =C2=A0 =C2=A0 =C2=A0 =C2=A0} > + =C2=A0 =C2=A0} > + > + =C2=A0 =C2=A0/** > =C2=A0 =C2=A0 =C2=A0* {@inheritDoc} > =C2=A0 =C2=A0 =C2=A0*/ > =C2=A0 =C2=A0 public Set applyingCheriyanMehlhornGabow() > > Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/gr= aph/scc/SccAlgorithmSelector.java > URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/ja= va/org/apache/commons/graph/scc/SccAlgorithmSelector.java?rev=3D1295773&r1= =3D1295772&r2=3D1295773&view=3Ddiff > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D > --- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/sc= c/SccAlgorithmSelector.java (original) > +++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/sc= c/SccAlgorithmSelector.java Thu Mar =C2=A01 20:27:55 2012 > @@ -35,7 +35,8 @@ public interface SccAlgorithmSelector =C2=A0{ > > =C2=A0 =C2=A0 /** > - =C2=A0 =C2=A0 * Applies the classical Kosaraju's algorithm to find the = strongly connected components, if exist. > + =C2=A0 =C2=A0 * Applies the classical Kosaraju's algorithm to find the = strongly connected components of > + =C2=A0 =C2=A0 * a vertex `source`. > =C2=A0 =C2=A0 =C2=A0* > =C2=A0 =C2=A0 =C2=A0* @param source the source vertex to start the search= from > =C2=A0 =C2=A0 =C2=A0* @return the input graph strongly connected componen= t. > @@ -43,6 +44,14 @@ public interface SccAlgorithmSelector =C2=A0 =C2=A0 Set applyingKosarajuSharir( V source ); > > =C2=A0 =C2=A0 /** > + =C2=A0 =C2=A0 * Applies the classical Kosaraju's algorithm to find the = strongly connected components. > + =C2=A0 =C2=A0 * > + =C2=A0 =C2=A0 * @param source the source vertex to start the search fro= m > + =C2=A0 =C2=A0 * @return the input graph strongly connected component. > + =C2=A0 =C2=A0 */ > + =C2=A0 =C2=A0Set> applyingKosarajuSharir(); > + > + =C2=A0 =C2=A0/** > =C2=A0 =C2=A0 =C2=A0* Applies the classical Cheriyan/Mehlhorn/Gabow's alg= orithm to find the strongly connected components, if exist. > =C2=A0 =C2=A0 =C2=A0* > =C2=A0 =C2=A0 =C2=A0* @return the input graph strongly connected componen= t. > > Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/gr= aph/scc/KosarajuSharirTestCase.java > URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/ja= va/org/apache/commons/graph/scc/KosarajuSharirTestCase.java?rev=3D1295773&r= 1=3D1295772&r2=3D1295773&view=3Ddiff > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D > --- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/sc= c/KosarajuSharirTestCase.java (original) > +++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/sc= c/KosarajuSharirTestCase.java Thu Mar =C2=A01 20:27:55 2012 > @@ -22,15 +22,17 @@ package org.apache.commons.graph.scc; > =C2=A0import static org.apache.commons.graph.CommonsGraph.findStronglyCon= nectedComponent; > =C2=A0import static org.apache.commons.graph.CommonsGraph.newDirectedMuta= bleGraph; > > +import static org.junit.Assert.assertEquals; > =C2=A0import static org.junit.Assert.assertFalse; > > +import java.util.Collections; > +import java.util.HashSet; > =C2=A0import java.util.Set; > > =C2=A0import org.apache.commons.graph.builder.AbstractGraphConnection; > =C2=A0import org.apache.commons.graph.model.BaseLabeledEdge; > =C2=A0import org.apache.commons.graph.model.BaseLabeledVertex; > =C2=A0import org.apache.commons.graph.model.DirectedMutableGraph; > -import org.junit.Ignore; > =C2=A0import org.junit.Test; > > =C2=A0/** > @@ -41,10 +43,17 @@ public final class KosarajuSharirTestCas > =C2=A0{ > > =C2=A0 =C2=A0 @Test > - =C2=A0 =C2=A0@Ignore > + =C2=A0 =C2=A0//@Ignore > =C2=A0 =C2=A0 public void verifyHasStronglyConnectedComponents() > =C2=A0 =C2=A0 { > =C2=A0 =C2=A0 =C2=A0 =C2=A0 final BaseLabeledVertex a =3D new BaseLabeled= Vertex( "A" ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0final BaseLabeledVertex b =3D new BaseLabele= dVertex( "B" ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0final BaseLabeledVertex c =3D new BaseLabele= dVertex( "C" ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0final BaseLabeledVertex d =3D new BaseLabele= dVertex( "D" ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0final BaseLabeledVertex e =3D new BaseLabele= dVertex( "E" ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0final BaseLabeledVertex f =3D new BaseLabele= dVertex( "F" ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0final BaseLabeledVertex g =3D new BaseLabele= dVertex( "G" ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0final BaseLabeledVertex h =3D new BaseLabele= dVertex( "H" ); > > =C2=A0 =C2=A0 =C2=A0 =C2=A0 DirectedMutableGraph graph =3D > =C2=A0 =C2=A0 =C2=A0 =C2=A0 newDirectedMutableGraph( new AbstractGraphCon= nection() > @@ -53,13 +62,13 @@ public final class KosarajuSharirTestCas > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 public void connect() > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 { > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 addVertex( a ); > - =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0BaseLabeledVerte= x b =3D addVertex( new BaseLabeledVertex( "B" ) ); > - =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0BaseLabeledVerte= x c =3D addVertex( new BaseLabeledVertex( "C" ) ); > - =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0BaseLabeledVerte= x d =3D addVertex( new BaseLabeledVertex( "D" ) ); > - =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0BaseLabeledVerte= x e =3D addVertex( new BaseLabeledVertex( "E" ) ); > - =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0BaseLabeledVerte= x f =3D addVertex( new BaseLabeledVertex( "F" ) ); > - =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0BaseLabeledVerte= x g =3D addVertex( new BaseLabeledVertex( "G" ) ); > - =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0BaseLabeledVerte= x h =3D addVertex( new BaseLabeledVertex( "H" ) ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0addVertex( b ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0addVertex( c ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0addVertex( d ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0addVertex( e ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0addVertex( f ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0addVertex( g ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0addVertex( h ); > > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 addEdge( new Base= LabeledEdge( "A -> F" ) ).from( a ).to( f ); > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 addEdge( new Base= LabeledEdge( "A -> B" ) ).from( a ).to( b ); > @@ -76,9 +85,36 @@ public final class KosarajuSharirTestCas > > =C2=A0 =C2=A0 =C2=A0 =C2=A0 } ); > > - =C2=A0 =C2=A0 =C2=A0 =C2=A0Set ssc =3D findStronglyC= onnectedComponent( graph ).applyingKosarajuSharir( a ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0Set> expected =3D new= HashSet>(); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0Set scc1 =3D new HashSet<= BaseLabeledVertex>(); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0Collections.addAll( scc1, a, b, d ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0expected.add( scc1 ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0Set scc2 =3D new HashSet<= BaseLabeledVertex>(); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0Collections.addAll( scc2, e, f ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0expected.add( scc2 ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0Set scc3 =3D new HashSet<= BaseLabeledVertex>(); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0Collections.addAll( scc3, g, h, c ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0expected.add( scc3 ); > + > + =C2=A0 =C2=A0 =C2=A0 =C2=A0Set> actual =3D findS= tronglyConnectedComponent( graph ).applyingKosarajuSharir(); > + > + =C2=A0 =C2=A0 =C2=A0 =C2=A0assertFalse( actual.isEmpty() ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0assertEquals( expected, actual ); > + > + =C2=A0 =C2=A0 =C2=A0 =C2=A0Set actualA =3D findStron= glyConnectedComponent( graph ).applyingKosarajuSharir( a ); > + > + =C2=A0 =C2=A0 =C2=A0 =C2=A0assertFalse( actualA.isEmpty() ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0assertEquals( scc1, actualA ); > + > + =C2=A0 =C2=A0 =C2=A0 =C2=A0Set actualE =3D findStron= glyConnectedComponent( graph ).applyingKosarajuSharir( e ); > + > + =C2=A0 =C2=A0 =C2=A0 =C2=A0assertFalse( actualE.isEmpty() ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0assertEquals( scc2, actualE ); > + > + =C2=A0 =C2=A0 =C2=A0 =C2=A0Set actualG =3D findStron= glyConnectedComponent( graph ).applyingKosarajuSharir( g ); > > - =C2=A0 =C2=A0 =C2=A0 =C2=A0assertFalse( ssc.isEmpty() ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0assertFalse( actualG.isEmpty() ); > + =C2=A0 =C2=A0 =C2=A0 =C2=A0assertEquals( scc3, actualG ); > =C2=A0 =C2=A0 } > > =C2=A0} > > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org For additional commands, e-mail: dev-help@commons.apache.org