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