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