commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject 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
Date Wed, 07 Mar 2012 08:11:10 GMT
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>();



Mime
View raw message