You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Simone Tripodi <si...@apache.org> on 2012/03/01 21:31:43 UTC
Re: svn commit: r1295773 - in /commons/sandbox/graph/trunk/src:
main/java/org/apache/commons/graph/scc/ test/java/org/apache/commons/graph/scc/
: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