commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Simone Tripodi <simonetrip...@apache.org>
Subject Re: svn commit: r1295773 - in /commons/sandbox/graph/trunk/src: main/java/org/apache/commons/graph/scc/ test/java/org/apache/commons/graph/scc/
Date Thu, 01 Mar 2012 20:31:43 GMT
: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


Mime
View raw message