commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From marcospera...@apache.org
Subject 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
Date Thu, 01 Mar 2012 21:51:41 GMT
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" );



Mime
View raw message