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

[si...@apache.org]

Author: simonetripodi
Date: Fri Nov 18 16:27:45 2011
New Revision: 1203723

URL: http://svn.apache.org/viewvc?rev=1203723&view=rev
Log:
first steps of Gabow algorithm

Modified:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabow.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=1203723&r1=1203722&r2=1203723&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:27:45 2011
@@ -19,6 +19,16 @@ package org.apache.commons.graph.ssc;
  * under the License.
  */
 
+import static org.apache.commons.graph.visit.Visit.depthFirstSearch;
+
+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;
+
 /**
  * Contains the Cheriyan/Mehlhorn/Gabow's strongly connected component algorithm implementation.
  */
@@ -33,4 +43,29 @@ public final class CheriyanMehlhornGabow
         // do nothing
     }
 
+    /**
+     * Applies the classical Cheriyan/Mehlhorn/Gabow's algorithm to find the strongly connected components, if exist.
+     *
+     * @param <V> the Graph vertices type.
+     * @param <E> the Graph edges type.
+     * @param graph the Graph which strongly connected component has to be verified.
+     */
+    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>();
+
+        for ( V vertex : graph.getVertices() )
+        {
+            if ( marked.add( vertex ) )
+            {
+                s.push( vertex );
+                p.push( vertex );
+
+                depthFirstSearch( graph, vertex, new CheriyanMehlhornGabowVisitHandler<V, E>() );
+            }
+        }
+    }
+
 }