:O WOW! may I can ask you to mark SANDBOX-353 as resolved, please?
Many thanks in advance! -Simo http://people.apache.org/~simonetripodi/ http://simonetripodi.livejournal.com/ http://twitter.com/simonetripodi http://www.99soft.org/ On Thu, Mar 1, 2012 at 9:27 PM, <t...@apache.org> wrote: > 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 ); > } > > } > > --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org