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 ); } }