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

[si...@apache.org]

Author: simonetripodi
Date: Sun Nov 20 17:52:50 2011
New Revision: 1204199

URL: http://svn.apache.org/viewvc?rev=1204199&view=rev
Log:
completed the last iteration when discovering edges

Modified:
    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/CheriyanMehlhornGabowVisitHandler.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/ssc/CheriyanMehlhornGabowVisitHandler.java?rev=1204199&r1=1204198&r2=1204199&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 Sun Nov 20 17:52:50 2011
@@ -46,6 +46,8 @@ final class CheriyanMehlhornGabowVisitHa
 
     private final Map<V, Integer> preorder = new HashMap<V, Integer>();
 
+    private final Map<V, Integer> sscId = new HashMap<V, Integer>();
+
     private final Set<V> marked;
 
     private final Stack<V> s = new Stack<V>();
@@ -54,6 +56,8 @@ final class CheriyanMehlhornGabowVisitHa
 
     private int preorderCounter = 0;
 
+    private int sscCounter = 0;
+
     public CheriyanMehlhornGabowVisitHandler( DirectedGraph<V, E> graph, Set<V> marked )
     {
         this.graph = graph;
@@ -81,7 +85,27 @@ final class CheriyanMehlhornGabowVisitHa
         {
             depthFirstSearch( graph, tail, this );
         }
-        // TODO else...
+        else if ( !sscId.containsKey( tail ) )
+        {
+            while ( preorder.get( p.peek() ) > preorder.get( tail ) )
+            {
+                p.pop();
+            }
+        }
+
+        // found strong component containing head
+        if ( head.equals( p.peek() ) )
+        {
+            p.pop();
+            V w;
+            do
+            {
+                w = s.pop();
+                sscId.put( w, sscCounter );
+            }
+            while ( !head.equals( w ) );
+            sscCounter++;
+        }
     }
 
 }