commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From marcospera...@apache.org
Subject svn commit: r1297678 - in /commons/sandbox/graph/trunk/src: changes/ main/java/org/apache/commons/graph/scc/ test/java/org/apache/commons/graph/scc/
Date Tue, 06 Mar 2012 20:20:18 GMT
Author: marcosperanza
Date: Tue Mar  6 20:20:17 2012
New Revision: 1297678

URL: http://svn.apache.org/viewvc?rev=1297678&view=rev
Log:
[SANDBOX-352] - Provide Cheriyan-Mehlhorn/Gabow's strongly connected component algorithm implementation

Added:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java
  (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java
  (with props)
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java
  (with props)
    commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowTestCase.java
  (with props)
Removed:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowVisitHandler.java
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=1297678&r1=1297677&r2=1297678&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/changes/changes.xml (original)
+++ commons/sandbox/graph/trunk/src/changes/changes.xml Tue Mar  6 20:20:17 2012
@@ -23,6 +23,9 @@
   </properties>
   <body>
   <release version="0.1" date="201?-??-??" description="First release.">
+    <action dev="marcosperanza" type="fix" issue="SANDBOX-352">
+      Provide Cheriyan-Mehlhorn/Gabow's strongly connected component algorithm implementation
+    </action>
     <action dev="simonetripodi" type="fix" issue="SANDBOX-400">
       Switch the Base graph implementation underlying data structures to the thread safe
version
     </action>

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java?rev=1297678&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java
Tue Mar  6 20:20:17 2012
@@ -0,0 +1,129 @@
+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 java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+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;
+
+/**
+ * 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 <G> the directed graph type 
+ */
+final class CheriyanMehlhornGabowAlgorithm<V extends Vertex, E extends Edge, G extends
DirectedGraph<V, E>>
+{
+
+    private final G graph;
+
+    private final Set<V> marked = new HashSet<V>();
+
+    private final Map<V, Integer> preorder = new HashMap<V, Integer>();
+
+    private final Map<V, Integer> sscId = new HashMap<V, Integer>();
+
+    private final Stack<V> s = new Stack<V>();
+
+    private final Stack<V> p = new Stack<V>();
+
+    private int preorderCounter = 0;
+
+    private int sscCounter = 0;
+    
+    public CheriyanMehlhornGabowAlgorithm( G graph )
+    {
+        this.graph = graph;
+    }
+
+    /**
+     */
+    public Set<Set<V>> applyingCheriyanMehlhornGabow()
+    {
+        for ( V vertex : graph.getVertices() )
+        {
+            if ( !marked.contains( vertex ) )
+            {
+                dfs( vertex );
+            }
+        }
+
+        final List<Set<V>> indexedSccComponents = new ArrayList<Set<V>>();
+        System.out.println( "CheriyanMehlhornGabowAlgorithm.applyingCheriyanMehlhornGabow()
" + sscCounter );
+        for ( int i = 0; i < sscCounter; i++ )
+        {
+            indexedSccComponents.add( new HashSet<V>() );
+        }
+
+        for ( V w : graph.getVertices() )
+        {
+            Set<V> component = indexedSccComponents.get( sscId.get( w ) );
+            component.add( w );
+        }
+
+        final Set<Set<V>> scc = new HashSet<Set<V>>();
+        scc.addAll( indexedSccComponents );
+        return scc;
+    }
+
+    private void dfs( V vertex )
+    {
+        marked.add( vertex );
+        preorder.put( vertex, preorderCounter++ );
+        s.push( vertex );
+        p.push( vertex );
+        for ( V w : graph.getConnectedVertices( vertex ) )
+        {
+            if ( !marked.contains( w ) )
+            {
+                dfs( w );
+            }
+            else if ( sscId.get( w ) == null )
+            {
+                while ( preorder.get( p.peek() ) > preorder.get( w ) )
+                {
+                    p.pop();
+                }
+            }
+        }
+
+        if ( p.peek().equals( vertex ) )
+        {
+            p.pop();
+            V w = null;
+            do
+            {
+                w = s.pop();
+                sscId.put( w, sscCounter );
+            }
+            while ( !vertex.equals( w ) );
+            sscCounter++;
+        }
+    }
+}

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

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

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

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=1297678&r1=1297677&r2=1297678&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
Tue Mar  6 20:20:17 2012
@@ -19,27 +19,12 @@ package org.apache.commons.graph.scc;
  * under the License.
  */
 
-import static java.lang.Math.min;
-import static org.apache.commons.graph.CommonsGraph.visit;
-import static org.apache.commons.graph.utils.Assertions.checkState;
-import static org.apache.commons.graph.utils.Assertions.checkNotNull;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.LinkedHashSet;
-import java.util.LinkedList;
-import java.util.List;
-import java.util.Map;
 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.Graph;
 import org.apache.commons.graph.Vertex;
-import org.apache.commons.graph.model.RevertedGraph;
-import org.apache.commons.graph.visit.GraphVisitHandler;
 
 /**
  * {@link SccAlgorithmSelector} implementation
@@ -69,18 +54,7 @@ public final class DefaultSccAlgorithmSe
      */
     public Set<V> applyingKosarajuSharir( final V source )
     {
-        checkNotNull( source, "Kosaraju Sharir algorithm cannot be calculated without expressing
the source vertex" );
-        checkState( graph.containsVertex( source ), "Vertex %s does not exist in the Graph",
source );
-
-        final Set<V> visitedVertices = new HashSet<V>();
-        final List<V> expandedVertexList = getExpandedVertexList( source, visitedVertices
);
-        final DirectedGraph<V, E> reverted = new RevertedGraph<V, E>( graph );
-
-        // remove the last element from the expanded vertices list
-        final V v = expandedVertexList.remove( expandedVertexList.size() - 1 );
-        final Set<V> sccSet = new HashSet<V>();
-        searchRecursive( reverted, v, sccSet, visitedVertices, false );
-        return sccSet;
+        return new KosarajuSharirAlgorithm<V, E, G>( graph ).applyingKosarajuSharir(
source );
     }
 
     /**
@@ -88,159 +62,15 @@ public final class DefaultSccAlgorithmSe
      */
     public Set<Set<V>> applyingKosarajuSharir()
     {
-        final Set<V> visitedVertices = new HashSet<V>();
-        final List<V> expandedVertexList = getExpandedVertexList( null, visitedVertices
);
-        final DirectedGraph<V, E> reverted = new RevertedGraph<V, E>( graph );
-
-        final Set<Set<V>> sccs = new HashSet<Set<V>>();
-
-        // insert the expanded vertices in reverse order into a linked hash set
-        // this is needed to quickly remove already found SCCs from the stack
-        final LinkedHashSet<V> stack = new LinkedHashSet<V>();
-        for ( int i = expandedVertexList.size() - 1; i >= 0; i-- )
-        {
-            stack.add(expandedVertexList.get( i ) );
-        }
-
-        while ( stack.size() > 0 )
-        {
-            // remove the last element from the expanded vertices list
-            final V v = stack.iterator().next();
-            final Set<V> sccSet = new HashSet<V>();
-            searchRecursive( reverted, v, sccSet, visitedVertices, false );
-
-            // remove all strongly connected components from the expanded list
-            stack.removeAll( sccSet );
-            sccs.add( sccSet );
-        }
-
-        return sccs;
-    }
-
-    /**
-     * Performs a depth-first search to create a recursive vertex list.
-     *
-     * @param source the starting vertex
-     * @param visitedVertices a {@link Set} containing all visited vertices
-     * @return the recursively expanded vertex list for Kosaraju's algorithm
-     */
-    private List<V> getExpandedVertexList( final V source, final Set<V> visitedVertices
)
-    {
-        final int size = (source != null) ? 13 : graph.getOrder();
-        final Set<V> vertices = new HashSet<V>( size );
-
-        if ( source != null )
-        {
-            vertices.add( source );
-        }
-        else
-        {
-            for ( V vertex : graph.getVertices() )
-            {
-                vertices.add( vertex );
-            }
-        }
-
-        // use an ArrayList so that subList is fast
-        final ArrayList<V> expandedVertexList = new ArrayList<V>();
-
-        int idx = 0;
-        while ( ! vertices.isEmpty() )
-        {
-            // get the next vertex that has not yet been added to the expanded list
-            final V v = vertices.iterator().next();
-            searchRecursive( graph, v, expandedVertexList, visitedVertices, true );
-            // remove all expanded vertices from the list of vertices that have to be
-            // still processed. To improve performance, only the items that have been
-            // added to the list since the last iteration are removed
-            vertices.removeAll( expandedVertexList.subList( idx, expandedVertexList.size()
) );
-            idx = expandedVertexList.size();
-        }
-
-        return expandedVertexList;
-    }
-
-    /**
-     * Searches a directed graph in iterative depth-first order, while adding the visited
-     * vertices in a recursive manner, i.e. a vertex is added to the result list only
-     * when the search has finished expanding the vertex (and its subsequent childs).
-     *
-     * <p><b>Implementation Note:</b> in the first step we look for vertices
that have not
-     * been visited yet, while in the second step we search for vertices that have already
-     * been visited.</p>
-     * @param g the graph to be search
-     * @param source the start vertex
-     * @param coll the recursive collection of visited vertices
-     * @param visited contains vertices that have been already visited
-     * @param forward <code>true</code> for the first step of Kosaraju's algorithm,
-     * <code>false</code> for the second step.
-     */
-    private void searchRecursive( final DirectedGraph<V, E> g, final V source,
-                                  final Collection<V> coll, final Set<V> visited,
-                                  final boolean forward )
-    {
-        final LinkedList<V> stack = new LinkedList<V>();
-        stack.addLast( source );
-
-        while ( !stack.isEmpty() )
-        {
-            final V v = stack.removeLast();
-
-            // if the vertex has already been visited it can be put into the
-            // collection, as we are now finished expanding this vertex
-            // the if takes both cases into account:
-            //  * step1: forward && visited.contains(v)
-            //  * step2: !forward && !visited.contains(v)
-            if ( ! ( forward ^ visited.contains( v ) ) )
-            {
-                coll.add( v );
-                continue;
-            }
-
-            // add the current vertex to the stack, so it is visited again
-            // when all connected vertices have been visited
-            stack.addLast( v );
-            if ( forward )
-            {
-                visited.add( v );
-            }
-            else
-            {
-                visited.remove( v );
-            }
-
-            // add all not yet visited vertices that can be reached from this
-            // vertex to the stack
-            for ( V w : g.getOutbound( v ) )
-            {
-                if ( ! ( forward ^ ! visited.contains( w ) ) )
-                {
-                    stack.addLast( w );
-                }
-            }
-        }
+        return new KosarajuSharirAlgorithm<V, E, G>( graph ).applyingKosarajuSharir();
     }
 
     /**
      * {@inheritDoc}
      */
-    public Set<V> applyingCheriyanMehlhornGabow()
+    public Set<Set<V>> applyingCheriyanMehlhornGabow()
     {
-        final Set<V> marked = new HashSet<V>();
-
-        final GraphVisitHandler<V, E, G, Void> visitHandler = new CheriyanMehlhornGabowVisitHandler<V,
E, G>( graph, marked );
-
-        for ( V vertex : graph.getVertices() )
-        {
-            if ( !marked.contains( vertex ) )
-            {
-                visit( graph ).from( vertex ).applyingDepthFirstSearch( visitHandler );
-            }
-        }
-
-        // TODO FILL ME, algorithm is incomplete
-
-        return null;
+        return new CheriyanMehlhornGabowAlgorithm<V, E, G>( graph ).applyingCheriyanMehlhornGabow();
     }
 
     /**
@@ -248,74 +78,6 @@ public final class DefaultSccAlgorithmSe
      */
     public Set<Set<V>> applyingTarjan()
     {
-        final Map<V, TarjanVertexMetaInfo> verticesMetaInfo = new HashMap<V, TarjanVertexMetaInfo>();
-        final Stack<V> s = new Stack<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 stronglyConnectedComponents;
-    }
-
-    private static <V> TarjanVertexMetaInfo getMetaInfo( V vertex, Map<V, TarjanVertexMetaInfo>
verticesMetaInfo )
-    {
-        TarjanVertexMetaInfo vertexMetaInfo = verticesMetaInfo.get( vertex );
-        if ( vertexMetaInfo == null )
-        {
-            vertexMetaInfo = new TarjanVertexMetaInfo();
-            verticesMetaInfo.put( vertex, vertexMetaInfo );
-        }
-        return vertexMetaInfo;
+        return new TarjanAlgorithm<V, E, G>( graph ).applyingTarjan();
     }
-
-    private static <V extends Vertex, E extends Edge> void strongConnect( DirectedGraph<V,
E> graph,
-                                                                          V vertex,
-                                                                          Map<V, TarjanVertexMetaInfo>
verticesMetaInfo,
-                                                                          Stack<V>
s,
-                                                                          Set<V> stronglyConnectedComponent,
-                                                                          Integer index )
-    {
-        TarjanVertexMetaInfo vertexMetaInfo = getMetaInfo( vertex, verticesMetaInfo );
-        vertexMetaInfo.setIndex( index );
-        vertexMetaInfo.setLowLink( index );
-        index++;
-        s.push( vertex );
-
-        for ( V adjacent : graph.getOutbound( vertex ) )
-        {
-            TarjanVertexMetaInfo adjacentMetaInfo = getMetaInfo( adjacent, verticesMetaInfo
);
-            if ( adjacentMetaInfo.hasUndefinedIndex() )
-            {
-                strongConnect( graph, adjacent, verticesMetaInfo, s, stronglyConnectedComponent,
index );
-                vertexMetaInfo.setLowLink( min( vertexMetaInfo.getLowLink(), adjacentMetaInfo.getLowLink()
) );
-            }
-            else if ( s.contains( adjacent ) )
-            {
-                vertexMetaInfo.setLowLink( min( vertexMetaInfo.getLowLink(), adjacentMetaInfo.getIndex()
) );
-            }
-        }
-
-        if ( vertexMetaInfo.getLowLink() == vertexMetaInfo.getIndex() )
-        {
-            V v;
-            do
-            {
-                v = s.pop();
-                stronglyConnectedComponent.add( v );
-            }
-            while ( !vertex.equals( v ) );
-        }
-    }
-
 }

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java?rev=1297678&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java
Tue Mar  6 20:20:17 2012
@@ -0,0 +1,220 @@
+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.utils.Assertions.checkNotNull;
+import static org.apache.commons.graph.utils.Assertions.checkState;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.commons.graph.DirectedGraph;
+import org.apache.commons.graph.Edge;
+import org.apache.commons.graph.Vertex;
+import org.apache.commons.graph.model.RevertedGraph;
+
+/**
+ * Implements the classical Kosaraju's algorithm to find the strongly connected components
+ * 
+ * @param <V> the Graph vertices type.
+ * @param <E> the Graph edges type.
+ * @param <G> the directed graph type 
+ */
+final class KosarajuSharirAlgorithm<V extends Vertex, E extends Edge, G extends DirectedGraph<V,
E>>
+{
+
+    private final G graph;
+
+    public KosarajuSharirAlgorithm( G graph )
+    {
+        this.graph = graph;
+    }
+    
+    /**
+     * Applies the classical Kosaraju's algorithm to find the strongly connected components
of
+     * a vertex <code>source</code>.
+     *
+     * @param source the source vertex to start the search from
+     * @return the input graph strongly connected component.
+     */
+    public Set<V> applyingKosarajuSharir( final V source )
+    {
+        checkNotNull( source, "Kosaraju Sharir algorithm cannot be calculated without expressing
the source vertex" );
+        checkState( graph.containsVertex( source ), "Vertex %s does not exist in the Graph",
source );
+
+        final Set<V> visitedVertices = new HashSet<V>();
+        final List<V> expandedVertexList = getExpandedVertexList( source, visitedVertices
);
+        final DirectedGraph<V, E> reverted = new RevertedGraph<V, E>( graph );
+
+        // remove the last element from the expanded vertices list
+        final V v = expandedVertexList.remove( expandedVertexList.size() - 1 );
+        final Set<V> sccSet = new HashSet<V>();
+        searchRecursive( reverted, v, sccSet, visitedVertices, false );
+        return sccSet;
+    }
+
+    /**
+     * Applies the classical Kosaraju's algorithm to find the strongly connected components.
+     *
+     * @param source the source vertex to start the search from
+     * @return the input graph strongly connected component.
+     */
+    public Set<Set<V>> applyingKosarajuSharir()
+    {
+        final Set<V> visitedVertices = new HashSet<V>();
+        final List<V> expandedVertexList = getExpandedVertexList( null, visitedVertices
);
+        final DirectedGraph<V, E> reverted = new RevertedGraph<V, E>( graph );
+
+        final Set<Set<V>> sccs = new HashSet<Set<V>>();
+
+        // insert the expanded vertices in reverse order into a linked hash set
+        // this is needed to quickly remove already found SCCs from the stack
+        final LinkedHashSet<V> stack = new LinkedHashSet<V>();
+        for ( int i = expandedVertexList.size() - 1; i >= 0; i-- )
+        {
+            stack.add(expandedVertexList.get( i ) );
+        }
+
+        while ( stack.size() > 0 )
+        {
+            // remove the last element from the expanded vertices list
+            final V v = stack.iterator().next();
+            final Set<V> sccSet = new HashSet<V>();
+            searchRecursive( reverted, v, sccSet, visitedVertices, false );
+
+            // remove all strongly connected components from the expanded list
+            stack.removeAll( sccSet );
+            sccs.add( sccSet );
+        }
+
+        return sccs;
+    }
+
+    /**
+     * Performs a depth-first search to create a recursive vertex list.
+     *
+     * @param source the starting vertex
+     * @param visitedVertices a {@link Set} containing all visited vertices
+     * @return the recursively expanded vertex list for Kosaraju's algorithm
+     */
+    private List<V> getExpandedVertexList( final V source, final Set<V> visitedVertices
)
+    {
+        final int size = (source != null) ? 13 : graph.getOrder();
+        final Set<V> vertices = new HashSet<V>( size );
+
+        if ( source != null )
+        {
+            vertices.add( source );
+        }
+        else
+        {
+            for ( V vertex : graph.getVertices() )
+            {
+                vertices.add( vertex );
+            }
+        }
+
+        // use an ArrayList so that subList is fast
+        final ArrayList<V> expandedVertexList = new ArrayList<V>();
+
+        int idx = 0;
+        while ( ! vertices.isEmpty() )
+        {
+            // get the next vertex that has not yet been added to the expanded list
+            final V v = vertices.iterator().next();
+            searchRecursive( graph, v, expandedVertexList, visitedVertices, true );
+            // remove all expanded vertices from the list of vertices that have to be
+            // still processed. To improve performance, only the items that have been
+            // added to the list since the last iteration are removed
+            vertices.removeAll( expandedVertexList.subList( idx, expandedVertexList.size()
) );
+            idx = expandedVertexList.size();
+        }
+
+        return expandedVertexList;
+    }
+
+    /**
+     * Searches a directed graph in iterative depth-first order, while adding the visited
+     * vertices in a recursive manner, i.e. a vertex is added to the result list only
+     * when the search has finished expanding the vertex (and its subsequent childs).
+     *
+     * <p><b>Implementation Note:</b> in the first step we look for vertices
that have not
+     * been visited yet, while in the second step we search for vertices that have already
+     * been visited.</p>
+     * @param g the graph to be search
+     * @param source the start vertex
+     * @param coll the recursive collection of visited vertices
+     * @param visited contains vertices that have been already visited
+     * @param forward <code>true</code> for the first step of Kosaraju's algorithm,
+     * <code>false</code> for the second step.
+     */
+    private void searchRecursive( final DirectedGraph<V, E> g, final V source,
+                                  final Collection<V> coll, final Set<V> visited,
+                                  final boolean forward )
+    {
+        final LinkedList<V> stack = new LinkedList<V>();
+        stack.addLast( source );
+
+        while ( !stack.isEmpty() )
+        {
+            final V v = stack.removeLast();
+
+            // if the vertex has already been visited it can be put into the
+            // collection, as we are now finished expanding this vertex
+            // the if takes both cases into account:
+            //  * step1: forward && visited.contains(v)
+            //  * step2: !forward && !visited.contains(v)
+            if ( ! ( forward ^ visited.contains( v ) ) )
+            {
+                coll.add( v );
+                continue;
+            }
+
+            // add the current vertex to the stack, so it is visited again
+            // when all connected vertices have been visited
+            stack.addLast( v );
+            if ( forward )
+            {
+                visited.add( v );
+            }
+            else
+            {
+                visited.remove( v );
+            }
+
+            // add all not yet visited vertices that can be reached from this
+            // vertex to the stack
+            for ( V w : g.getOutbound( v ) )
+            {
+                if ( ! ( forward ^ ! visited.contains( w ) ) )
+                {
+                    stack.addLast( w );
+                }
+            }
+        }
+    }
+
+}

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

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

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

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=1297678&r1=1297677&r2=1297678&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
Tue Mar  6 20:20:17 2012
@@ -58,7 +58,7 @@ public interface SccAlgorithmSelector<V 
      *
      * @return the input graph strongly connected component.
      */
-    Set<V> applyingCheriyanMehlhornGabow();
+    Set<Set<V>> applyingCheriyanMehlhornGabow();
 
     /**
      * Tarjan's algorithm is a variation (slightly faster) on KosarajuSharir's algorithm
for finding

Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java?rev=1297678&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java
Tue Mar  6 20:20:17 2012
@@ -0,0 +1,131 @@
+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 java.lang.Math.min;
+
+import java.util.HashMap;
+import java.util.LinkedHashSet;
+import java.util.Map;
+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;
+
+/**
+ * Implements Tarjan's algorithm is a variation (slightly faster) on KosarajuSharir's algorithm
for finding
+ * strongly-connected components in a directed graph.
+ * 
+ * @param <V> the Graph vertices type.
+ * @param <E> the Graph edges type.
+ * @param <G> the directed graph type
+ */
+final class TarjanAlgorithm<V extends Vertex, E extends Edge, G extends DirectedGraph<V,
E>>
+{
+
+    private final G graph;
+
+    /**
+     */
+    public TarjanAlgorithm( G graph )
+    {
+        this.graph = graph;
+    }
+
+    /**
+     * Tarjan's algorithm is a variation (slightly faster) on KosarajuSharir's algorithm
for finding strongly-connected
+     * components in a directed graph.
+     * 
+     * @return the input graph strongly connected component.
+     */
+    public Set<Set<V>> applyingTarjan()
+    {
+        final Map<V, TarjanVertexMetaInfo> verticesMetaInfo = new HashMap<V, TarjanVertexMetaInfo>();
+        final Stack<V> s = new Stack<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 stronglyConnectedComponents;
+    }
+
+    private static <V> TarjanVertexMetaInfo getMetaInfo( V vertex, Map<V, TarjanVertexMetaInfo>
verticesMetaInfo )
+    {
+        TarjanVertexMetaInfo vertexMetaInfo = verticesMetaInfo.get( vertex );
+        if ( vertexMetaInfo == null )
+        {
+            vertexMetaInfo = new TarjanVertexMetaInfo();
+            verticesMetaInfo.put( vertex, vertexMetaInfo );
+        }
+        return vertexMetaInfo;
+    }
+
+    private static <V extends Vertex, E extends Edge> void strongConnect( DirectedGraph<V,
E> graph,
+                                                                          V vertex,
+                                                                          Map<V, TarjanVertexMetaInfo>
verticesMetaInfo,
+                                                                          Stack<V>
s,
+                                                                          Set<V> stronglyConnectedComponent,
+                                                                          Integer index )
+    {
+        TarjanVertexMetaInfo vertexMetaInfo = getMetaInfo( vertex, verticesMetaInfo );
+        vertexMetaInfo.setIndex( index );
+        vertexMetaInfo.setLowLink( index );
+        index++;
+        s.push( vertex );
+
+        for ( V adjacent : graph.getOutbound( vertex ) )
+        {
+            TarjanVertexMetaInfo adjacentMetaInfo = getMetaInfo( adjacent, verticesMetaInfo
);
+            if ( adjacentMetaInfo.hasUndefinedIndex() )
+            {
+                strongConnect( graph, adjacent, verticesMetaInfo, s, stronglyConnectedComponent,
index );
+                vertexMetaInfo.setLowLink( min( vertexMetaInfo.getLowLink(), adjacentMetaInfo.getLowLink()
) );
+            }
+            else if ( s.contains( adjacent ) )
+            {
+                vertexMetaInfo.setLowLink( min( vertexMetaInfo.getLowLink(), adjacentMetaInfo.getIndex()
) );
+            }
+        }
+
+        if ( vertexMetaInfo.getLowLink() == vertexMetaInfo.getIndex() )
+        {
+            V v;
+            do
+            {
+                v = s.pop();
+                stronglyConnectedComponent.add( v );
+            }
+            while ( !vertex.equals( v ) );
+        }
+    }
+}

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

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

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

Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowTestCase.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowTestCase.java?rev=1297678&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowTestCase.java
(added)
+++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowTestCase.java
Tue Mar  6 20:20:17 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 CheriyanMehlhornGabowTestCase
+{
+
+    @Test( expected = NullPointerException.class )
+    public void testNullGraph()
+    {
+        DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>,
Integer> graph = null;
+        findStronglyConnectedComponent( graph ).applyingCheriyanMehlhornGabow();
+    }
+
+    @Test
+    public void testEmptyGraph()
+    {
+        DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>,
Integer> graph =
+            new DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>,
Integer>();
+
+        findStronglyConnectedComponent( graph ).applyingCheriyanMehlhornGabow();
+    }
+
+    @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 ).applyingCheriyanMehlhornGabow();
+
+        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 ).applyingCheriyanMehlhornGabow();
+        
+        assertFalse( actual.isEmpty() );
+        assertEquals( expected, actual );
+    }
+
+}

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

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

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



Mime
View raw message