svn commit: r1203739 - in /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc: CheriyanMehlhornGabow.java CheriyanMehlhornGabowVisitHandler.java

[si...@apache.org]

Author: simonetripodi
Date: Fri Nov 18 16:48:03 2011
New Revision: 1203739

URL: http://svn.apache.org/viewvc?rev=1203739&view=rev
Log:
moving algorithm logic to the DFS handler

Modified:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabow.java
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabowVisitHandler.java

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabow.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabow.java?rev=1203739&r1=1203738&r2=1203739&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabow.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabow.java Fri Nov 18 16:48:03 2011
@@ -23,11 +23,11 @@ import static org.apache.commons.graph.v
 
 import java.util.HashSet;
 import java.util.Set;
-import java.util.Stack;
 
 import org.apache.commons.graph.DirectedGraph;
 import org.apache.commons.graph.Edge;
 import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.visit.GraphVisitHandler;
 
 /**
  * Contains the Cheriyan/Mehlhorn/Gabow's strongly connected component algorithm implementation.
@@ -53,17 +53,14 @@ public final class CheriyanMehlhornGabow
     public static <V extends Vertex, E extends Edge> void hasStronglyConnectedComponent( DirectedGraph<V, E> graph )
     {
         final Set<V> marked = new HashSet<V>();
-        final Stack<V> s = new Stack<V>();
-        final Stack<V> p = new Stack<V>();
+
+        final GraphVisitHandler<V, E> visitHandler = new CheriyanMehlhornGabowVisitHandler<V, E>( graph, marked );
 
         for ( V vertex : graph.getVertices() )
         {
-            if ( marked.add( vertex ) )
+            if ( !marked.contains( vertex ) )
             {
-                s.push( vertex );
-                p.push( vertex );
-
-                depthFirstSearch( graph, vertex, new CheriyanMehlhornGabowVisitHandler<V, E>() );
+                depthFirstSearch( graph, vertex, visitHandler );
             }
         }
     }

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabowVisitHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabowVisitHandler.java?rev=1203739&r1=1203738&r2=1203739&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabowVisitHandler.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabowVisitHandler.java Fri Nov 18 16:48:03 2011
@@ -19,6 +19,12 @@ package org.apache.commons.graph.ssc;
  * under the License.
  */
 
+import static org.apache.commons.graph.visit.Visit.depthFirstSearch;
+
+import java.util.Set;
+import java.util.Stack;
+
+import org.apache.commons.graph.DirectedGraph;
 import org.apache.commons.graph.Edge;
 import org.apache.commons.graph.Vertex;
 import org.apache.commons.graph.visit.BaseGraphVisitHandler;
@@ -34,4 +40,39 @@ final class CheriyanMehlhornGabowVisitHa
     extends BaseGraphVisitHandler<V, E>
 {
 
+    private final DirectedGraph<V, E> graph;
+
+    private final Set<V> marked;
+
+    private final Stack<V> s = new Stack<V>();
+
+    private final Stack<V> p = new Stack<V>();
+
+    public CheriyanMehlhornGabowVisitHandler( DirectedGraph<V, E> graph, Set<V> marked )
+    {
+        this.graph = graph;
+        this.marked = marked;
+    }
+
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public void discoverVertex( V vertex )
+    {
+        marked.add( vertex );
+        s.push( vertex );
+        p.push( vertex );
+
+        for ( V adjacent : graph.getOutbound( vertex ) )
+        {
+            if ( !marked.contains( adjacent ) )
+            {
+                depthFirstSearch( graph, adjacent, this );
+            }
+            // TODO else...
+        }
+    }
+
 }