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... + } + } + }