commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From marcospera...@apache.org
Subject svn commit: r1295981 - in /commons/sandbox/graph/trunk/src: changes/ main/java/org/apache/commons/graph/scc/ test/java/org/apache/commons/graph/scc/
Date Thu, 01 Mar 2012 23:09:41 GMT
Author: marcosperanza
Date: Thu Mar  1 23:09:41 2012
New Revision: 1295981

URL: http://svn.apache.org/viewvc?rev=1295981&view=rev
Log:
[SANDBOX-354] Provide a Tarjan's algorithm implementation

Added:
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java
  (with props)
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/main/java/org/apache/commons/graph/scc/SccAlgorithmSelector.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=1295981&r1=1295980&r2=1295981&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Thu Mar  1 23:09:41 2012
@@ -23,6 +23,9 @@
   </properties>
   <body>
   <release version="0.1" date="201?-??-??" description="First release.">
+    <action dev="marcosperanza" type="fix" issue="SANDBOX-354">
+      Provide a Tarjan's algorithm implementation
+    </action>
     <action dev="marcosperanza" type="fix" issue="SANDBOX-392">
       Add test for Kosaraju Sharir Algorithm
     </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=1295981&r1=1295980&r2=1295981&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 23:09:41 2012
@@ -226,24 +226,26 @@ public final class DefaultSccAlgorithmSe
     /**
      * {@inheritDoc}
      */
-    public Set<V> applyingTarjan()
+    public Set<Set<V>> applyingTarjan()
     {
         final Map<V, TarjanVertexMetaInfo> verticesMetaInfo = new HashMap<V, TarjanVertexMetaInfo>();
         final Stack<V> s = new Stack<V>();
-        final Set<V> stronglyConnectedComponent = new LinkedHashSet<V>();
+        final Set<Set<V>> stronglyConnectedComponents = new LinkedHashSet<Set<V>>();
         Integer index = 0;
 
         for ( V vertex : graph.getVertices() )
         {
             TarjanVertexMetaInfo vertexMetaInfo = getMetaInfo( vertex, verticesMetaInfo );
+            final Set<V> stronglyConnectedComponent = new LinkedHashSet<V>();
 
             if ( vertexMetaInfo.hasUndefinedIndex() )
             {
                 strongConnect( graph, vertex, verticesMetaInfo, s, stronglyConnectedComponent,
index );
+                stronglyConnectedComponents.add( stronglyConnectedComponent );
             }
         }
 
-        return stronglyConnectedComponent;
+        return stronglyConnectedComponents;
     }
 
     private static <V> TarjanVertexMetaInfo getMetaInfo( V vertex, Map<V, TarjanVertexMetaInfo>
verticesMetaInfo )

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=1295981&r1=1295980&r2=1295981&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 23:09:41 2012
@@ -64,6 +64,6 @@ public interface SccAlgorithmSelector<V 
      *
      * @return the input graph strongly connected component.
      */
-    Set<V> applyingTarjan();
+    Set<Set<V>> applyingTarjan();
 
 }

Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java?rev=1295981&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java
(added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java
Thu Mar  1 23:09:41 2012
@@ -0,0 +1,150 @@
+package org.apache.commons.graph.scc;
+
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+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;
+
+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.BaseLabeledWeightedEdge;
+import org.apache.commons.graph.model.DirectedMutableGraph;
+import org.apache.commons.graph.model.DirectedMutableWeightedGraph;
+import org.junit.Test;
+
+/**
+ * Test for Tarjan's algorithm implementation,
+ * see the <a href="http://scienceblogs.com/goodmath/2007/10/computing_strongly_connected_c.php">online</a>
testcase.
+ */
+public final class TarjanTestCase
+{
+
+    @Test( expected = NullPointerException.class )
+    public void testNullGraph()
+    {
+        DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>,
Integer> graph = null;
+        findStronglyConnectedComponent( graph ).applyingTarjan();
+    }
+
+    @Test
+    public void testEmptyGraph()
+    {
+        DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>,
Integer> graph =
+            new DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>,
Integer>();
+
+        findStronglyConnectedComponent( graph ).applyingTarjan();
+    }
+
+    @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 ).applyingTarjan();
+
+        assertEquals( actual.size(), expected );
+    }
+    
+    @Test
+    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>()
+        {
+
+            public void connect()
+            {
+                addVertex( a );
+                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 );
+                addEdge( new BaseLabeledEdge( "B -> D" ) ).from( b ).to( d );
+                addEdge( new BaseLabeledEdge( "C -> G" ) ).from( c ).to( g );
+                addEdge( new BaseLabeledEdge( "D -> A" ) ).from( d ).to( a );
+                addEdge( new BaseLabeledEdge( "D -> G" ) ).from( d ).to( g );
+                addEdge( new BaseLabeledEdge( "E -> C" ) ).from( e ).to( c );
+                addEdge( new BaseLabeledEdge( "E -> F" ) ).from( e ).to( f );
+                addEdge( new BaseLabeledEdge( "F -> E" ) ).from( f ).to( e );
+                addEdge( new BaseLabeledEdge( "G -> H" ) ).from( g ).to( h );
+                addEdge( new BaseLabeledEdge( "H -> C" ) ).from( h ).to( c );
+            }
+
+        } );
+
+        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 ).applyingTarjan();
+        
+        assertFalse( actual.isEmpty() );
+        assertEquals( expected, actual );
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain



Mime
View raw message