commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From simonetrip...@apache.org
Subject svn commit: r1203296 - in /commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents: Tarjan.java TarjanVertexMetaInfo.java
Date Thu, 17 Nov 2011 17:36:54 GMT
Author: simonetripodi
Date: Thu Nov 17 17:36:54 2011
New Revision: 1203296

URL: http://svn.apache.org/viewvc?rev=1203296&view=rev
Log:
first checkin of Tarjan's algorithm implementation

Added:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/TarjanVertexMetaInfo.java
  (with props)
Modified:
    commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/Tarjan.java

Modified: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/Tarjan.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/Tarjan.java?rev=1203296&r1=1203295&r2=1203296&view=diff
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/Tarjan.java
(original)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/Tarjan.java
Thu Nov 17 17:36:54 2011
@@ -19,9 +19,101 @@ package org.apache.commons.graph.connect
  * under the License.
  */
 
+import static java.lang.Math.min;
+
+import java.util.HashMap;
+import java.util.HashSet;
+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;
+
+/**
+ * Tarjan's algorithm is a variation (slightly faster) on {@link KosarajuSharir}'s algorithm
for finding
+ * strongly-connected components in a directed graph.
+ */
 public final class Tarjan
 {
 
-    // TODO
+    /**
+     * Applies the classical Tarjan's algorithm to find the strongly connected components,
if exist.
+     *
+     * @param <V> the Graph vertices type.
+     * @param <E> the Graph edges type.
+     * @param graph the Graph which strongly connected component has to be verified.
+     * @return
+     */
+    public static <V extends Vertex, E extends Edge> Set<V> getStronglyConnectedComponent(
DirectedGraph<V, E> graph )
+    {
+        final Map<V, TarjanVertexMetaInfo> verticesMetaInfo = new HashMap<V, TarjanVertexMetaInfo>();
+        final Stack<V> s = new Stack<V>();
+        final Set<V> stronglyConnectedComponent = new HashSet<V>();
+        Integer index = 0;
+
+        for ( V vertex : graph.getVertices() )
+        {
+            TarjanVertexMetaInfo vertexMetaInfo = getMetaInfo( vertex, verticesMetaInfo );
+
+            if ( vertexMetaInfo.hasUndefinedIndex() )
+            {
+                strongConnect( graph, vertex, verticesMetaInfo, s, stronglyConnectedComponent,
index );
+            }
+        }
+
+        return stronglyConnectedComponent;
+    }
+
+    private static <V> TarjanVertexMetaInfo getMetaInfo( V vertex, Map<V, TarjanVertexMetaInfo>
verticesMetaInfo )
+    {
+        TarjanVertexMetaInfo vertexMetaInfo = verticesMetaInfo.get( vertex );
+        if ( vertexMetaInfo == null )
+        {
+            vertexMetaInfo = new TarjanVertexMetaInfo();
+            verticesMetaInfo.put( vertex, vertexMetaInfo );
+        }
+        return vertexMetaInfo;
+    }
+
+    private static <V extends Vertex, E extends Edge> void strongConnect( DirectedGraph<V,
E> graph,
+                                                                          V vertex,
+                                                                          Map<V, TarjanVertexMetaInfo>
verticesMetaInfo,
+                                                                          Stack<V>
s,
+                                                                          Set<V> 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/connectedcomponents/TarjanVertexMetaInfo.java
URL: http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/TarjanVertexMetaInfo.java?rev=1203296&view=auto
==============================================================================
--- commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/TarjanVertexMetaInfo.java
(added)
+++ commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/TarjanVertexMetaInfo.java
Thu Nov 17 17:36:54 2011
@@ -0,0 +1,56 @@
+package org.apache.commons.graph.connectedcomponents;
+
+/*
+ * 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.
+ */
+
+final class TarjanVertexMetaInfo
+{
+
+    private static final int UNDEFINED = -1;
+
+    private int index = UNDEFINED;
+
+    private int lowLink = UNDEFINED;
+
+    public int getIndex()
+    {
+        return index;
+    }
+
+    public boolean hasUndefinedIndex()
+    {
+        return UNDEFINED == index;
+    }
+
+    public void setIndex( int index )
+    {
+        this.index = index;
+    }
+
+    public int getLowLink()
+    {
+        return lowLink;
+    }
+
+    public void setLowLink( int lowLink )
+    {
+        this.lowLink = lowLink;
+    }
+
+}

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/TarjanVertexMetaInfo.java
------------------------------------------------------------------------------
    svn:eol-style = native

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/TarjanVertexMetaInfo.java
------------------------------------------------------------------------------
    svn:keywords = Date Author Id Revision HeadURL

Propchange: commons/sandbox/graph/trunk/src/main/java/org/apache/commons/graph/connectedcomponents/TarjanVertexMetaInfo.java
------------------------------------------------------------------------------
    svn:mime-type = text/plain



Mime
View raw message