You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by si...@apache.org on 2012/03/07 09:11:10 UTC
svn commit: r1297872 - in
/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc:
CheriyanMehlhornGabowAlgorithm.java DefaultSccAlgorithmSelector.java
KosarajuSharirAlgorithm.java SccAlgorithm.java TarjanAlgorithm.java
Author: simonetripodi
Date: Wed Mar 7 08:11:10 2012
New Revision: 1297872
URL: http://svn.apache.org/viewvc?rev=1297872&view=rev
Log:
simplify the verbosity of SCC algorithms - related to [SANDBOX-351]
Added:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java (with props)
Modified:
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java
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/KosarajuSharirAlgorithm.java
commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java
Modified: 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=1297872&r1=1297871&r2=1297872&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/CheriyanMehlhornGabowAlgorithm.java Wed Mar 7 08:11:10 2012
@@ -36,9 +36,10 @@ 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
+ * @param <G> the directed graph type
*/
final class CheriyanMehlhornGabowAlgorithm<V extends Vertex, E extends Edge, G extends DirectedGraph<V, E>>
+ implements SccAlgorithm<V>
{
private final G graph;
@@ -56,7 +57,7 @@ final class CheriyanMehlhornGabowAlgorit
private int preorderCounter = 0;
private int sscCounter = 0;
-
+
public CheriyanMehlhornGabowAlgorithm( G graph )
{
this.graph = graph;
@@ -64,7 +65,7 @@ final class CheriyanMehlhornGabowAlgorit
/**
*/
- public Set<Set<V>> applyingCheriyanMehlhornGabow()
+ public Set<Set<V>> perform()
{
for ( V vertex : graph.getVertices() )
{
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=1297872&r1=1297871&r2=1297872&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 Wed Mar 7 08:11:10 2012
@@ -53,7 +53,7 @@ public final class DefaultSccAlgorithmSe
*/
public Set<V> applyingKosarajuSharir( final V source )
{
- return new KosarajuSharirAlgorithm<V, E, G>( graph ).applyingKosarajuSharir( source );
+ return new KosarajuSharirAlgorithm<V, E, G>( graph ).perform( source );
}
/**
@@ -61,7 +61,7 @@ public final class DefaultSccAlgorithmSe
*/
public Set<Set<V>> applyingKosarajuSharir()
{
- return new KosarajuSharirAlgorithm<V, E, G>( graph ).applyingKosarajuSharir();
+ return applying( new KosarajuSharirAlgorithm<V, E, G>( graph ) );
}
/**
@@ -69,7 +69,7 @@ public final class DefaultSccAlgorithmSe
*/
public Set<Set<V>> applyingCheriyanMehlhornGabow()
{
- return new CheriyanMehlhornGabowAlgorithm<V, E, G>( graph ).applyingCheriyanMehlhornGabow();
+ return applying( new CheriyanMehlhornGabowAlgorithm<V, E, G>( graph ) );
}
/**
@@ -77,6 +77,18 @@ public final class DefaultSccAlgorithmSe
*/
public Set<Set<V>> applyingTarjan()
{
- return new TarjanAlgorithm<V, E, G>( graph ).applyingTarjan();
+ return applying( new TarjanAlgorithm<V, E, G>( graph ) );
}
+
+ /**
+ * Just calculates the SCC depending on the selected algorithm.
+ *
+ * @param algorithm
+ * @return
+ */
+ private Set<Set<V>> applying( SccAlgorithm<V> algorithm )
+ {
+ return algorithm.perform();
+ }
+
}
Modified: 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=1297872&r1=1297871&r2=1297872&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/KosarajuSharirAlgorithm.java Wed Mar 7 08:11:10 2012
@@ -44,6 +44,7 @@ import org.apache.commons.graph.model.Re
* @param <G> the directed graph type
*/
final class KosarajuSharirAlgorithm<V extends Vertex, E extends Edge, G extends DirectedGraph<V, E>>
+ implements SccAlgorithm<V>
{
/** The graph. */
private final G graph;
@@ -65,7 +66,7 @@ final class KosarajuSharirAlgorithm<V ex
* @param source the source vertex to start the search from
* @return the input graph strongly connected component.
*/
- public Set<V> applyingKosarajuSharir( final V source )
+ public Set<V> perform( 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 );
@@ -86,7 +87,7 @@ final class KosarajuSharirAlgorithm<V ex
*
* @return the input graph strongly connected component.
*/
- public Set<Set<V>> applyingKosarajuSharir()
+ public Set<Set<V>> perform()
{
final Set<V> visitedVertices = new HashSet<V>();
final List<V> expandedVertexList = getExpandedVertexList( null, visitedVertices );
Added: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java?rev=1297872&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java (added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java Wed Mar 7 08:11:10 2012
@@ -0,0 +1,31 @@
+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.Set;
+
+import org.apache.commons.graph.Vertex;
+
+interface SccAlgorithm<V extends Vertex>
+{
+
+ Set<Set<V>> perform();
+
+}
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/SccAlgorithm.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Modified: 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=1297872&r1=1297871&r2=1297872&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java (original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/scc/TarjanAlgorithm.java Wed Mar 7 08:11:10 2012
@@ -34,12 +34,13 @@ 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>>
+ implements SccAlgorithm<V>
{
private final G graph;
@@ -54,10 +55,10 @@ final class TarjanAlgorithm<V extends Ve
/**
* 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()
+ public Set<Set<V>> perform()
{
final Map<V, TarjanVertexMetaInfo> verticesMetaInfo = new HashMap<V, TarjanVertexMetaInfo>();
final Stack<V> s = new Stack<V>();