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 F08E495ED for ; Fri, 2 Mar 2012 21:58:06 +0000 (UTC) Received: (qmail 71279 invoked by uid 500); 2 Mar 2012 21:58:06 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 71208 invoked by uid 500); 2 Mar 2012 21:58:06 -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 71201 invoked by uid 99); 2 Mar 2012 21:58:06 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 02 Mar 2012 21:58:06 +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; Fri, 02 Mar 2012 21:58:04 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id D48832388860 for ; Fri, 2 Mar 2012 21:57:44 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1296490 - in /commons/sandbox/graph/trunk/src: benchmarks/java/org/apache/commons/graph/scc/ main/java/org/apache/commons/graph/scc/ test/java/org/apache/commons/graph/scc/ Date: Fri, 02 Mar 2012 21:57:44 -0000 To: commits@commons.apache.org From: tn@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20120302215744.D48832388860@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: tn Date: Fri Mar 2 21:57:44 2012 New Revision: 1296490 URL: http://svn.apache.org/viewvc?rev=1296490&view=rev Log: greatly improved speed of Kosarajus algorithm, added more unit tests, SCC benchmark and javadoc with runtime complexity information and algorithm recommendation Added: commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/ commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java (with props) Modified: 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 commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java Added: commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java?rev=1296490&view=auto ============================================================================== --- commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java (added) +++ commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java Fri Mar 2 21:57:44 2012 @@ -0,0 +1,102 @@ +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.String.format; +import static java.lang.String.valueOf; +import static org.apache.commons.graph.CommonsGraph.findStronglyConnectedComponent; +import static org.apache.commons.graph.CommonsGraph.newDirectedMutableGraph; +import static org.junit.Assert.assertTrue; + +import java.util.ArrayList; +import java.util.List; +import java.util.Random; +import java.util.Set; + +import org.apache.commons.graph.GraphException; +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.DirectedMutableGraph; +import org.junit.BeforeClass; +import org.junit.Rule; +import org.junit.Test; + +import com.carrotsearch.junitbenchmarks.BenchmarkRule; +import com.carrotsearch.junitbenchmarks.annotation.AxisRange; +import com.carrotsearch.junitbenchmarks.annotation.BenchmarkMethodChart; + +@AxisRange( min = 0, max = 2 ) +@BenchmarkMethodChart( filePrefix = "strongly-connected-components" ) +public final class SCCAlgorithmBenchmarkTestCase +{ + private static final int NODES = 5000; + private static final int EDGES = 5000; + + @Rule + public BenchmarkRule benchmarkRun = new BenchmarkRule(); + + private static DirectedMutableGraph graph; + + @BeforeClass + public static void setUp() + { + graph = newDirectedMutableGraph( new AbstractGraphConnection() + { + public void connect() + { + List vertices = new ArrayList(); + for ( int i = 0; i < NODES; i++ ) + { + BaseLabeledVertex v = new BaseLabeledVertex( valueOf( i ) ); + addVertex( v ); + vertices.add( v ); + } + + Random r = new Random(); + for ( int i = 0; i < EDGES; i++ ) { + int v1 = r.nextInt(NODES); + int v2 = r.nextInt(NODES); + + try { + addEdge( new BaseLabeledEdge( format( "%s -> %s", v1, v2 ) ) ).from( vertices.get( v1 ) ).to( vertices.get( v2 ) ); + } catch (GraphException e) { + // ignore duplicate edge exceptions + } + } + } + } ); + } + + @Test + public void performKosaraju() + { + Set> actual = findStronglyConnectedComponent( graph ).applyingKosarajuSharir(); + assertTrue( actual.size() > 0 ); + } + + @Test + public void performTarjan() + { + Set> actual = findStronglyConnectedComponent( graph ).applyingTarjan(); + assertTrue( actual.size() > 0 ); + } + +} Propchange: commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java ------------------------------------------------------------------------------ svn:eol-style = native Propchange: commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.java ------------------------------------------------------------------------------ svn:keywords = Id Revision HeadURL Propchange: commons/sandbox/graph/trunk/src/benchmarks/java/org/apache/commons/graph/scc/SCCAlgorithmBenchmarkTestCase.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=1296490&r1=1296489&r2=1296490&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 Fri Mar 2 21:57:44 2012 @@ -89,21 +89,36 @@ public final class DefaultSccAlgorithmSe final Set> sccs = new HashSet>(); - while ( expandedVertexList.size() > 0 ) + // 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 = expandedVertexList.remove( expandedVertexList.size() - 1 ); + 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 - expandedVertexList.removeAll( sccSet ); + 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(); 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=1296490&r1=1296489&r2=1296490&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 Fri Mar 2 21:57:44 2012 @@ -46,8 +46,10 @@ public interface SccAlgorithmSelectorNote: the runtime complexity is O(V + E) and this algorithm should be chosen + * if the number of vertices outweighs the number of edges.

+ * + * @return the input graph strongly connected components. */ Set> applyingKosarajuSharir(); @@ -62,6 +64,9 @@ public interface SccAlgorithmSelectorNote: the runtime complexity is O(V + E) and this algorithm should be chosen + * if the number of edges outweighs the number of vertices.

+ * * @return the input graph strongly connected component. */ Set> applyingTarjan(); Modified: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java?rev=1296490&r1=1296489&r2=1296490&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java (original) +++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/KosarajuSharirTestCase.java Fri Mar 2 21:57:44 2012 @@ -21,7 +21,6 @@ package org.apache.commons.graph.scc; 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; @@ -72,44 +71,81 @@ public final class KosarajuSharirTestCas } @Test - public void testEmptyGraph() + public void verifyHasStronglyConnectedComponents() { - DirectedMutableWeightedGraph, Integer> graph = - new DirectedMutableWeightedGraph, Integer>(); + 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" ); - findStronglyConnectedComponent( graph ).applyingKosarajuSharir(); - } + DirectedMutableGraph graph = + newDirectedMutableGraph( new AbstractGraphConnection() + { - @Test - public void testSparse() - { - DirectedMutableWeightedGraph, Integer> graph = - newDirectedMutableWeightedGraph( 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 ); + } - @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; + 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 ); - // actual strong components Set> actual = findStronglyConnectedComponent( graph ).applyingKosarajuSharir(); - assertEquals( actual.size(), expected ); + assertFalse( actual.isEmpty() ); + assertEquals( expected, actual ); + + Set actualA = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( a ); + + assertFalse( actualA.isEmpty() ); + assertEquals( scc1, actualA ); + + Set actualE = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( e ); + + assertFalse( actualE.isEmpty() ); + assertEquals( scc2, actualE ); + + Set actualG = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( g ); + + assertFalse( actualG.isEmpty() ); + assertEquals( scc3, actualG ); } - + @Test - public void verifyHasStronglyConnectedComponents() + public void testUnconnectedGraph() { final BaseLabeledVertex a = new BaseLabeledVertex( "A" ); final BaseLabeledVertex b = new BaseLabeledVertex( "B" ); @@ -135,12 +171,12 @@ public final class KosarajuSharirTestCas addVertex( g ); addVertex( h ); - addEdge( new BaseLabeledEdge( "A -> F" ) ).from( a ).to( f ); + //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( "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 ); @@ -162,24 +198,24 @@ public final class KosarajuSharirTestCas expected.add( scc3 ); Set> actual = findStronglyConnectedComponent( graph ).applyingKosarajuSharir(); - + assertFalse( actual.isEmpty() ); assertEquals( expected, actual ); - + Set actualA = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( a ); assertFalse( actualA.isEmpty() ); assertEquals( scc1, actualA ); - + Set actualE = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( e ); assertFalse( actualE.isEmpty() ); assertEquals( scc2, actualE ); - + Set actualG = findStronglyConnectedComponent( graph ).applyingKosarajuSharir( g ); assertFalse( actualG.isEmpty() ); - assertEquals( scc3, actualG ); + assertEquals( scc3, actualG ); } }