You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ma...@apache.org on 2012/03/06 21:20:18 UTC
svn commit: r1297678 - in /commons/sandbox/graph/trunk/src: changes/
main/java/org/apache/commons/graph/scc/
test/java/org/apache/commons/graph/scc/
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