You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by tn...@apache.org on 2012/03/01 21:27:55 UTC
svn commit: r1295773 - in /commons/sandbox/graph/trunk/src:
main/java/org/apache/commons/graph/scc/
test/java/org/apache/commons/graph/scc/
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 );
}
}
Re: svn commit: r1295773 - in /commons/sandbox/graph/trunk/src:
main/java/org/apache/commons/graph/scc/ test/java/org/apache/commons/graph/scc/
Posted by Simone Tripodi <si...@apache.org>.
: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, <tn...@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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org