Author: marcosperanza Date: Thu Mar 1 23:09:41 2012 New Revision: 1295981 URL: http://svn.apache.org/viewvc?rev=1295981&view=rev Log: [SANDBOX-354] Provide a Tarjan's algorithm implementation
Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java (with props) 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=1295981&r1=1295980&r2=1295981&view=diff ============================================================================== --- commons/sandbox/graph/trunk/src/changes/changes.xml (original) +++ commons/sandbox/graph/trunk/src/changes/changes.xml Thu Mar 1 23:09:41 2012 @@ -23,6 +23,9 @@ </properties> <body> <release version="0.1" date="201?-??-??" description="First release."> + <action dev="marcosperanza" type="fix" issue="SANDBOX-354"> + Provide a Tarjan's algorithm implementation + </action> <action dev="marcosperanza" type="fix" issue="SANDBOX-392"> Add test for Kosaraju Sharir Algorithm </action> 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=1295981&r1=1295980&r2=1295981&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 Thu Mar 1 23:09:41 2012 @@ -226,24 +226,26 @@ public final class DefaultSccAlgorithmSe /** * {@inheritDoc} */ - public Set<V> applyingTarjan() + public Set<Set<V>> applyingTarjan() { final Map<V, TarjanVertexMetaInfo> verticesMetaInfo = new HashMap<V, TarjanVertexMetaInfo>(); final Stack<V> s = new Stack<V>(); - final Set<V> stronglyConnectedComponent = new LinkedHashSet<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 stronglyConnectedComponent; + return stronglyConnectedComponents; } private static <V> TarjanVertexMetaInfo getMetaInfo( V vertex, Map<V, TarjanVertexMetaInfo> verticesMetaInfo ) 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=1295981&r1=1295980&r2=1295981&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 Thu Mar 1 23:09:41 2012 @@ -64,6 +64,6 @@ public interface SccAlgorithmSelector<V * * @return the input graph strongly connected component. */ - Set<V> applyingTarjan(); + Set<Set<V>> applyingTarjan(); } Added: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java?rev=1295981&view=auto ============================================================================== --- commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java (added) +++ commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java Thu Mar 1 23:09:41 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 TarjanTestCase +{ + + @Test( expected = NullPointerException.class ) + public void testNullGraph() + { + DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer> graph = null; + findStronglyConnectedComponent( graph ).applyingTarjan(); + } + + @Test + public void testEmptyGraph() + { + DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer> graph = + new DirectedMutableWeightedGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Integer>, Integer>(); + + findStronglyConnectedComponent( graph ).applyingTarjan(); + } + + @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 ).applyingTarjan(); + + 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 ).applyingTarjan(); + + assertFalse( actual.isEmpty() ); + assertEquals( expected, actual ); + } + +} Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java ------------------------------------------------------------------------------ svn:eol-style = native Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java ------------------------------------------------------------------------------ svn:keywords = Date Author Id Revision HeadURL Propchange: commons/sandbox/graph/trunk/src/test/java/org/apache/commons/graph/scc/TarjanTestCase.java ------------------------------------------------------------------------------ svn:mime-type = text/plain