bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/internal/elaboration/utils/StronglyConnectedComponents.java

   1 package org.simantics.scl.compiler.internal.elaboration.utils;
   2
   3
   4 /**
   5  * An implementation of Tarjan's algorithms for finding
   6  * the strongly connected components of a directed graph.
   7  *
   8  * @author Hannu Niemist&ouml;
   9  */
  10 public abstract class StronglyConnectedComponents {
  11
  12     private int[] id;
  13     private int[] lowId;
  14     private boolean[] inStack;
  15     private int[] stack;
  16     private int stackPos = 0;
  17     private int currentId = 0;
  18
  19     /**
  20      * Creates new instance of the algorithm for
  21      * finding strongly connected components.
  22      * Size is the number of vertices of the graph.
  23      */
  24     public StronglyConnectedComponents(int size) {
  25         id = new 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)
  30             id[i] = -1;
  31     }
  32
  33     /**
  34      * Finds the components.
  35      */
  36     public void findComponents() {
  37         for(int i=0;i<id.length;++i)
  38             if(id[i] < 0)
  39                 visit(i);
  40     }
  41
  42     private void visit(int v) {
  43         int vId = currentId++;
  44         id[v] = vId;
  45         int tempLowId = vId;
  46
  47         int initialStackPos = stackPos;
  48         stack[stackPos++] = v;
  49         inStack[v] = true;
  50
  51         for(int u : findDependencies(v)) {
  52             int uId = id[u];
  53             if(uId < 0) {
  54                 visit(u);
  55                 tempLowId = Math.min(tempLowId, lowId[u]);
  56             }
  57             else if(inStack[u])
  58                 tempLowId = Math.min(tempLowId, uId);
  59         }
  60
  61         lowId[v] = tempLowId;
  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;
  67                 inStack[e] = false;
  68             }
  69             reportComponent(component);
  70         }
  71     }
  72
  73     /**
  74      * Returns dependencies of the vertex u.
  75      */
  76     protected abstract int[] findDependencies(int u);
  77
  78     /**
  79      * Reports one strongly connected component of
  80      * the graph. The components are reported in the
  81      * order of dependency.
  82      */
  83     protected abstract void reportComponent(int[] component);
  84
  85 }