Return-Path: X-Original-To: apmail-commons-commits-archive@minotaur.apache.org Delivered-To: apmail-commons-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 5A97E9101 for ; Tue, 6 Mar 2012 20:20:49 +0000 (UTC) Received: (qmail 80973 invoked by uid 500); 6 Mar 2012 20:20:49 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 80904 invoked by uid 500); 6 Mar 2012 20:20:49 -0000 Mailing-List: contact commits-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@commons.apache.org Delivered-To: mailing list commits@commons.apache.org Received: (qmail 80897 invoked by uid 99); 6 Mar 2012 20:20:49 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 06 Mar 2012 20:20:49 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 06 Mar 2012 20:20:41 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id D6D032388865 for ; Tue, 6 Mar 2012 20:20:18 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit 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 -0000 To: commits@commons.apache.org From: marcosperanza@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20120306202018.D6D032388865@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org 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 @@ + + Provide Cheriyan-Mehlhorn/Gabow's strongly connected component algorithm implementation + Switch the Base graph implementation underlying data structures to the thread safe version 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 the Graph vertices type. + * @param the Graph edges type. + * @param the directed graph type + */ +final class CheriyanMehlhornGabowAlgorithm> +{ + + private final G graph; + + private final Set marked = new HashSet(); + + private final Map preorder = new HashMap(); + + private final Map sscId = new HashMap(); + + private final Stack s = new Stack(); + + private final Stack p = new Stack(); + + private int preorderCounter = 0; + + private int sscCounter = 0; + + public CheriyanMehlhornGabowAlgorithm( G graph ) + { + this.graph = graph; + } + + /** + */ + public Set> applyingCheriyanMehlhornGabow() + { + for ( V vertex : graph.getVertices() ) + { + if ( !marked.contains( vertex ) ) + { + dfs( vertex ); + } + } + + final List> indexedSccComponents = new ArrayList>(); + System.out.println( "CheriyanMehlhornGabowAlgorithm.applyingCheriyanMehlhornGabow() " + sscCounter ); + for ( int i = 0; i < sscCounter; i++ ) + { + indexedSccComponents.add( new HashSet() ); + } + + for ( V w : graph.getVertices() ) + { + Set component = indexedSccComponents.get( sscId.get( w ) ); + component.add( w ); + } + + final Set> scc = new HashSet>(); + 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 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 visitedVertices = new HashSet(); - final List expandedVertexList = getExpandedVertexList( source, visitedVertices ); - final DirectedGraph reverted = new RevertedGraph( graph ); - - // remove the last element from the expanded vertices list - final V v = expandedVertexList.remove( expandedVertexList.size() - 1 ); - final Set sccSet = new HashSet(); - searchRecursive( reverted, v, sccSet, visitedVertices, false ); - return sccSet; + return new KosarajuSharirAlgorithm( graph ).applyingKosarajuSharir( source ); } /** @@ -88,159 +62,15 @@ public final class DefaultSccAlgorithmSe */ public Set> applyingKosarajuSharir() { - final Set visitedVertices = new HashSet(); - final List expandedVertexList = getExpandedVertexList( null, visitedVertices ); - final DirectedGraph reverted = new RevertedGraph( graph ); - - final Set> sccs = new HashSet>(); - - // 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 stack = new LinkedHashSet(); - 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 sccSet = new HashSet(); - 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 getExpandedVertexList( final V source, final Set visitedVertices ) - { - final int size = (source != null) ? 13 : graph.getOrder(); - final Set vertices = new HashSet( 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 expandedVertexList = new ArrayList(); - - 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). - * - *

Implementation Note: 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.

- * @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 true for the first step of Kosaraju's algorithm, - * false for the second step. - */ - private void searchRecursive( final DirectedGraph g, final V source, - final Collection coll, final Set visited, - final boolean forward ) - { - final LinkedList stack = new LinkedList(); - 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( graph ).applyingKosarajuSharir(); } /** * {@inheritDoc} */ - public Set applyingCheriyanMehlhornGabow() + public Set> applyingCheriyanMehlhornGabow() { - final Set marked = new HashSet(); - - final GraphVisitHandler visitHandler = new CheriyanMehlhornGabowVisitHandler( 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( graph ).applyingCheriyanMehlhornGabow(); } /** @@ -248,74 +78,6 @@ public final class DefaultSccAlgorithmSe */ public Set> applyingTarjan() { - final Map verticesMetaInfo = new HashMap(); - final Stack s = new Stack(); - final Set> stronglyConnectedComponents = new LinkedHashSet>(); - Integer index = 0; - - for ( V vertex : graph.getVertices() ) - { - TarjanVertexMetaInfo vertexMetaInfo = getMetaInfo( vertex, verticesMetaInfo ); - final Set stronglyConnectedComponent = new LinkedHashSet(); - - if ( vertexMetaInfo.hasUndefinedIndex() ) - { - strongConnect( graph, vertex, verticesMetaInfo, s, stronglyConnectedComponent, index ); - stronglyConnectedComponents.add( stronglyConnectedComponent ); - } - } - - return stronglyConnectedComponents; - } - - private static TarjanVertexMetaInfo getMetaInfo( V vertex, Map verticesMetaInfo ) - { - TarjanVertexMetaInfo vertexMetaInfo = verticesMetaInfo.get( vertex ); - if ( vertexMetaInfo == null ) - { - vertexMetaInfo = new TarjanVertexMetaInfo(); - verticesMetaInfo.put( vertex, vertexMetaInfo ); - } - return vertexMetaInfo; + return new TarjanAlgorithm( graph ).applyingTarjan(); } - - private static void strongConnect( DirectedGraph graph, - V vertex, - Map verticesMetaInfo, - Stack s, - Set 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 the Graph vertices type. + * @param the Graph edges type. + * @param the directed graph type + */ +final class KosarajuSharirAlgorithm> +{ + + 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 source. + * + * @param source the source vertex to start the search from + * @return the input graph strongly connected component. + */ + public Set 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 visitedVertices = new HashSet(); + final List expandedVertexList = getExpandedVertexList( source, visitedVertices ); + final DirectedGraph reverted = new RevertedGraph( graph ); + + // remove the last element from the expanded vertices list + final V v = expandedVertexList.remove( expandedVertexList.size() - 1 ); + final Set sccSet = new HashSet(); + 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> applyingKosarajuSharir() + { + final Set visitedVertices = new HashSet(); + final List expandedVertexList = getExpandedVertexList( null, visitedVertices ); + final DirectedGraph reverted = new RevertedGraph( graph ); + + final Set> sccs = new HashSet>(); + + // 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 stack = new LinkedHashSet(); + 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 sccSet = new HashSet(); + 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 getExpandedVertexList( final V source, final Set visitedVertices ) + { + final int size = (source != null) ? 13 : graph.getOrder(); + final Set vertices = new HashSet( 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 expandedVertexList = new ArrayList(); + + 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). + * + *

Implementation Note: 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.

+ * @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 true for the first step of Kosaraju's algorithm, + * false for the second step. + */ + private void searchRecursive( final DirectedGraph g, final V source, + final Collection coll, final Set visited, + final boolean forward ) + { + final LinkedList stack = new LinkedList(); + 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 applyingCheriyanMehlhornGabow(); + Set> 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 the Graph vertices type. + * @param the Graph edges type. + * @param the directed graph type + */ +final class TarjanAlgorithm> +{ + + 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> applyingTarjan() + { + final Map verticesMetaInfo = new HashMap(); + final Stack s = new Stack(); + final Set> stronglyConnectedComponents = new LinkedHashSet>(); + Integer index = 0; + + for ( V vertex : graph.getVertices() ) + { + TarjanVertexMetaInfo vertexMetaInfo = getMetaInfo( vertex, verticesMetaInfo ); + final Set stronglyConnectedComponent = new LinkedHashSet(); + + if ( vertexMetaInfo.hasUndefinedIndex() ) + { + strongConnect( graph, vertex, verticesMetaInfo, s, stronglyConnectedComponent, index ); + stronglyConnectedComponents.add( stronglyConnectedComponent ); + } + } + + return stronglyConnectedComponents; + } + + private static TarjanVertexMetaInfo getMetaInfo( V vertex, Map verticesMetaInfo ) + { + TarjanVertexMetaInfo vertexMetaInfo = verticesMetaInfo.get( vertex ); + if ( vertexMetaInfo == null ) + { + vertexMetaInfo = new TarjanVertexMetaInfo(); + verticesMetaInfo.put( vertex, vertexMetaInfo ); + } + return vertexMetaInfo; + } + + private static void strongConnect( DirectedGraph graph, + V vertex, + Map verticesMetaInfo, + Stack s, + Set 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 online testcase. + */ +public final class CheriyanMehlhornGabowTestCase +{ + + @Test( expected = NullPointerException.class ) + public void testNullGraph() + { + DirectedMutableWeightedGraph, Integer> graph = null; + findStronglyConnectedComponent( graph ).applyingCheriyanMehlhornGabow(); + } + + @Test + public void testEmptyGraph() + { + DirectedMutableWeightedGraph, Integer> graph = + new DirectedMutableWeightedGraph, Integer>(); + + findStronglyConnectedComponent( graph ).applyingCheriyanMehlhornGabow(); + } + + @Test + public void testSparse() + { + DirectedMutableWeightedGraph, Integer> graph = + newDirectedMutableWeightedGraph( new AbstractGraphConnection>() + { + + @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> 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 graph = + newDirectedMutableGraph( new AbstractGraphConnection() + { + + 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> expected = new HashSet>(); + Set scc1 = new HashSet(); + Collections.addAll( scc1, a, b, d ); + expected.add( scc1 ); + Set scc2 = new HashSet(); + Collections.addAll( scc2, e, f ); + expected.add( scc2 ); + Set scc3 = new HashSet(); + Collections.addAll( scc3, g, h, c ); + expected.add( scc3 ); + + Set> 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