1 package org.simantics.scl.compiler.internal.elaboration.utils;
5 * An implementation of Tarjan's algorithms for finding
6 * the strongly connected components of a directed graph.
8 * @author Hannu Niemistö
10 public abstract class StronglyConnectedComponents {
14 private boolean[] inStack;
16 private int stackPos = 0;
17 private int currentId = 0;
20 * Creates new instance of the algorithm for
21 * finding strongly connected components.
22 * Size is the number of vertices of the graph.
24 public StronglyConnectedComponents(int size) {
26 lowId = new int[size];
27 inStack = new boolean[size];
28 stack = new int[size];
29 for(int i=0;i<id.length;++i)
34 * Finds the components.
36 public void findComponents() {
37 for(int i=0;i<id.length;++i)
42 private void visit(int v) {
43 int vId = currentId++;
47 int initialStackPos = stackPos;
48 stack[stackPos++] = v;
51 for(int u : findDependencies(v)) {
55 tempLowId = Math.min(tempLowId, lowId[u]);
58 tempLowId = Math.min(tempLowId, uId);
62 if(vId == tempLowId) {
63 int[] component = new int[stackPos-initialStackPos];
64 while(stackPos > initialStackPos) {
65 int e = stack[--stackPos];
66 component[stackPos - initialStackPos] = e;
69 reportComponent(component);
74 * Returns dependencies of the vertex u.
76 protected abstract int[] findDependencies(int u);
79 * Reports one strongly connected component of
80 * the graph. The components are reported in the
81 * order of dependency.
83 protected abstract void reportComponent(int[] component);