Migrated source code from Simantics SVN

[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / internal / elaboration / utils / StronglyConnectedComponents.java

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/utils/StronglyConnectedComponents.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/utils/StronglyConnectedComponents.java
new file mode 100644 (file)
index 0000000..2d9a60e
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/utils/StronglyConnectedComponents.java
@@ -0,0 +1,85 @@
+package org.simantics.scl.compiler.internal.elaboration.utils;
+
+
+/**
+ * An implementation of Tarjan's algorithms for finding
+ * the strongly connected components of a directed graph.
+ * 
+ * @author Hannu Niemistö
+ */
+public abstract class StronglyConnectedComponents {
+
+    private int[] id;
+    private int[] lowId;
+    private boolean[] inStack;
+    private int[] stack;
+    private int stackPos = 0;
+    private int currentId = 0;  
+
+    /**
+     * Creates new instance of the algorithm for
+     * finding strongly connected components. 
+     * Size is the number of vertices of the graph.
+     */
+    public StronglyConnectedComponents(int size) {
+        id = new int[size];
+        lowId = new int[size];
+        inStack = new boolean[size];
+        stack = new int[size];
+        for(int i=0;i<id.length;++i)
+            id[i] = -1;
+    }
+
+    /**
+     * Finds the components.
+     */
+    public void findComponents() {
+        for(int i=0;i<id.length;++i)
+            if(id[i] < 0)
+                visit(i);
+    }
+
+    private void visit(int v) {
+        int vId = currentId++;
+        id[v] = vId;
+        int tempLowId = vId;   
+
+        int initialStackPos = stackPos;
+        stack[stackPos++] = v;
+        inStack[v] = true;
+
+        for(int u : findDependencies(v)) {
+            int uId = id[u];
+            if(uId < 0) {
+                visit(u);
+                tempLowId = Math.min(tempLowId, lowId[u]);
+            }
+            else if(inStack[u])
+                tempLowId = Math.min(tempLowId, uId);
+        }
+
+        lowId[v] = tempLowId;          
+        if(vId == tempLowId) {
+            int[] component = new int[stackPos-initialStackPos];
+            while(stackPos > initialStackPos) {
+                int e = stack[--stackPos];
+                component[stackPos - initialStackPos] = e;
+                inStack[e] = false;
+            }
+            reportComponent(component);
+        }
+    }
+
+    /**
+     * Returns dependencies of the vertex u.
+     */
+    protected abstract int[] findDependencies(int u);
+
+    /**
+     * Reports one strongly connected component of
+     * the graph. The components are reported in the
+     * order of dependency.
+     */
+    protected abstract void reportComponent(int[] component);
+
+}