X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Felaboration%2Futils%2FStronglyConnectedComponents.java;fp=bundles%2Forg.simantics.scl.compiler%2Fsrc%2Forg%2Fsimantics%2Fscl%2Fcompiler%2Finternal%2Felaboration%2Futils%2FStronglyConnectedComponents.java;h=2d9a60ef06aa709a0e75756476e3231d96ba741a;hb=969bd23cab98a79ca9101af33334000879fb60c5;hp=0000000000000000000000000000000000000000;hpb=866dba5cd5a3929bbeae85991796acb212338a08;p=simantics%2Fplatform.git

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
index 000000000..2d9a60ef0
--- /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);
+
+}