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