| 51 | |
| 52 | template<class View> |
| 53 | inline void |
| 54 | computesccs(ViewArray<View>& x, ViewArray<View>& y, |
| 55 | int phi[], SccComponent sinfo[], int scclist[]) { |
| 56 | |
| 57 | // number of sccs is bounded by xs (number of x-nodes) |
| 58 | int xs = x.size(); |
| 59 | Region r; |
| 60 | Support::StaticStack<int,Region> cs(r,xs); |
| 61 | |
| 62 | //select an y node from the graph |
| 63 | for (int j = 0; j < xs; j++) { |
| 64 | int yjmin = y[j].min(); // the processed min |
| 65 | while (!cs.empty() && x[phi[sinfo[cs.top()].rightmost]].max() < yjmin) { |
| 66 | // the topmost scc cannot "reach" y_j or a node to the right of it |
| 67 | cs.pop(); |
| 68 | } |
| 69 | |
| 70 | // a component has the form C(y-Node, matching x-Node) |
| 71 | // C is a minimal scc in the oriented intersection graph |
| 72 | // we only store y_j-Node, since \phi(j) gives the matching X-node |
| 73 | int i = phi[j]; |
| 74 | int ximin = x[i].min(); |
| 75 | while (!cs.empty() && ximin <= y[sinfo[cs.top()].rightmost].max()) { |
| 76 | // y_j can "reach" cs.top() , |
| 77 | // i.e. component c can reach component cs.top() |
| 78 | // merge c and cs.top() into new component |
| 79 | int top = cs.top(); |
| 80 | // connecting |
| 81 | sinfo[sinfo[j].leftmost].left = top; |
| 82 | sinfo[top].right = sinfo[j].leftmost; |
| 83 | // moving leftmost |
| 84 | sinfo[j].leftmost = sinfo[top].leftmost; |
| 85 | // moving rightmost |
| 86 | sinfo[sinfo[top].leftmost].rightmost = j; |
| 87 | cs.pop(); |
| 88 | } |
| 89 | cs.push(j); |
| 90 | } |
| 91 | cs.reset(); |
| 92 | |
| 93 | |
| 94 | // now we mark all components with the respective scc-number |
| 95 | // labeling is bound by O(k) which is bound by O(n) |
| 96 | |
| 97 | for (int i = 0; i < xs; i++) { |
| 98 | if (sinfo[i].left == i) { // only label variables in sccs |
| 99 | int scc = sinfo[i].rightmost; |
| 100 | int z = i; |
| 101 | //bound by the size of the largest scc = k |
| 102 | while (sinfo[z].right != z) { |
| 103 | sinfo[z].rightmost = scc; |
| 104 | scclist[phi[z]] = scc; |
| 105 | z = sinfo[z].right; |
| 106 | } |
| 107 | sinfo[z].rightmost = scc; |
| 108 | scclist[phi[z]] = scc; |
| 109 | } |
| 110 | } |