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 23:08:40 UTC
Re: svn commit: r1295924 - in /commons/sandbox/graph/trunk/src:
changes/changes.xml main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java
test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java
Ciao Marco,
+ DirectedMutableWeightedGraph<BaseLabeledVertex,
BaseLabeledWeightedEdge<Integer>, Integer> graph =
+ newDirectedMutableWeightedGraph( new
AbstractGraphConnection<BaseLabeledVertex,
BaseLabeledWeightedEdge<Integer>>()
+ {
+ @Override
+ public void connect()
+ {
+ }
+
+ } );
it would be more readable if you just create the graph instance, in
these cases empty configuration is quiet useless ;)
best,
-Simo
http://people.apache.org/~simonetripodi/
http://simonetripodi.livejournal.com/
http://twitter.com/simonetripodi
http://www.99soft.org/
On Thu, Mar 1, 2012 at 10:51 PM, <ma...@apache.org> wrote:
> Author: marcosperanza
> Date: Thu Mar 1 21:51:40 2012
> New Revision: 1295924
>
> URL: http://svn.apache.org/viewvc?rev=1295924&view=rev
> Log:
> [SANDBOX-392] Add test for Kosaraju Sharir Algorithm
>
> Modified:
> commons/sandbox/graph/trunk/src/changes/changes.xml
> commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/DefaultSccAlgorithmSelector.java
> commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java
>
> Modified: commons/sandbox/graph/trunk/src/changes/changes.xml
> URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/changes/changes.xml?rev=1295924&r1=1295923&r2=1295924&view=diff
> ==============================================================================
> --- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
> +++ commons/sandbox/graph/trunk/src/changes/changes.xml Thu Mar 1 21:51:40 2012
> @@ -23,6 +23,9 @@
> </properties>
> <body>
> <release version="0.1" date="201?-??-??" description="First release.">
> + <action dev="marcosperanza" type="fix" issue="SANDBOX-392">
> + Add test for Kosaraju Sharir Algorithm
> + </action>
> <action dev="tn" type="fix" issue="SANDBOX-353">
> Provide a Kosaraju-Sharir's algorithm implementation
> </action>
>
> 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=1295924&r1=1295923&r2=1295924&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 21:51:40 2012
> @@ -21,6 +21,8 @@ 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.checkState;
> +import static org.apache.commons.graph.utils.Assertions.checkNotNull;
>
> import java.util.ArrayList;
> import java.util.Collection;
> @@ -62,6 +64,9 @@ public final class DefaultSccAlgorithmSe
> */
> public Set<V> applyingKosarajuSharir( final V source )
> {
> + checkNotNull( source, "Kosaraju Sharir algorithm cannot be calculated without expressing the source vertex" );
> + checkState( graph.containsVertex( source ), "Vertex %s does not exist in the Graph", 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 );
>
> 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=1295924&r1=1295923&r2=1295924&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 21:51:40 2012
> @@ -21,7 +21,7 @@ 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.apache.commons.graph.CommonsGraph.newDirectedMutableWeightedGraph;
> import static org.junit.Assert.assertEquals;
> import static org.junit.Assert.assertFalse;
>
> @@ -32,7 +32,9 @@ 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.BaseLabeledWeightedEdge;
> import org.apache.commons.graph.model.DirectedMutableGraph;
> +import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
> import org.junit.Test;
>
> /**
> @@ -42,8 +44,93 @@ import org.junit.Test;
> public final class KosarajuSharirTestCase
> {
>
> + @Test( expected = NullPointerException.class )
> + public void testNullGraph()
> + {
> + DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer> graph = null;
> + findStronglyConnectedComponent( graph ).applyingKosarajuSharir();
> + }
> +
> + @Test( expected = NullPointerException.class )
> + public void testNullVertices()
> + {
> +
> + final BaseLabeledVertex a = null;
> +
> + DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer> graph =
> + newDirectedMutableWeightedGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>>()
> + {
> + @Override
> + public void connect()
> + {
> + }
> +
> + } );
> +
> + findStronglyConnectedComponent( graph ).applyingKosarajuSharir( a );
> + }
> +
> + @Test( expected = IllegalStateException.class )
> + public void testNotExistVertex()
> + {
> + DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer> graph =
> + newDirectedMutableWeightedGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>>()
> + {
> + @Override
> + public void connect()
> + {
> + }
> +
> + } );
> +
> + findStronglyConnectedComponent( graph ).applyingKosarajuSharir( new BaseLabeledVertex( "NOT EXISTS" ) );
> + }
> +
> + @Test
> + public void testEmptyGraph()
> + {
> + DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer> graph =
> + newDirectedMutableWeightedGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>>()
> + {
> + @Override
> + public void connect()
> + {
> + }
> +
> + } );
> +
> + findStronglyConnectedComponent( graph ).applyingKosarajuSharir();
> + }
> +
> + @Test
> + public void testSparse()
> + {
> + DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer> graph =
> + newDirectedMutableWeightedGraph( new AbstractGraphConnection<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>>()
> + {
> +
> + @Override
> + public void connect()
> + {
> + addVertex( new BaseLabeledVertex( "A" ) );
> + addVertex( new BaseLabeledVertex( "B" ) );
> + addVertex( new BaseLabeledVertex( "C" ) );
> + addVertex( new BaseLabeledVertex( "D" ) );
> + addVertex( new BaseLabeledVertex( "E" ) );
> + addVertex( new BaseLabeledVertex( "F" ) );
> + }
> + } );
> +
> + // expected strong components
> + final int expected = 6;
> +
> + // actual strong components
> + Set<Set<BaseLabeledVertex>> actual = findStronglyConnectedComponent( graph ).applyingKosarajuSharir();
> +
> + assertEquals( actual.size(), expected );
> + }
> +
> @Test
> - //@Ignore
> public void verifyHasStronglyConnectedComponents()
> {
> final BaseLabeledVertex a = new BaseLabeledVertex( "A" );
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org