| 139 | |
| 140 | template<class View> |
| 141 | forceinline void |
| 142 | Graph<View>::scc(void) { |
| 143 | Region r; |
| 144 | |
| 145 | Support::StaticStack<Node<View>*,Region> scc(r,n_val+n_view); |
| 146 | Support::StaticStack<Node<View>*,Region> visit(r,n_val+n_view); |
| 147 | |
| 148 | count++; |
| 149 | unsigned int cnt0 = count; |
| 150 | unsigned int cnt1 = count; |
| 151 | |
| 152 | for (int i=0; i<n_view; i++) |
| 153 | /* |
| 154 | * The following test is subtle: for scc, the test should be: |
| 155 | * view[i]->min < count |
| 156 | * However, if view[i] < count-1, then the node has already been |
| 157 | * reached on a path and all edges connected to the node have been |
| 158 | * marked anyway! So just ignore this node altogether for scc. |
| 159 | */ |
| 160 | if (view[i]->min < count-1) { |
| 161 | Node<View>* w = view[i]; |
| 162 | start: |
| 163 | w->low = w->min = cnt0++; |
| 164 | scc.push(w); |
| 165 | Edge<View>* e = w->edge_fst(); |
| 166 | while (e != w->edge_lst()) { |
| 167 | if (e->dst(w)->min < count) { |
| 168 | visit.push(w); w->iter = e; |
| 169 | w=e->dst(w); |
| 170 | goto start; |
| 171 | } |
| 172 | next: |
| 173 | if (e->dst(w)->low < w->min) |
| 174 | w->min = e->dst(w)->low; |
| 175 | e = e->next(); |
| 176 | } |
| 177 | if (w->min < w->low) { |
| 178 | w->low = w->min; |
| 179 | } else { |
| 180 | Node<View>* v; |
| 181 | do { |
| 182 | v = scc.pop(); |
| 183 | v->comp = cnt1; |
| 184 | v->low = UINT_MAX; |
| 185 | } while (v != w); |
| 186 | cnt1++; |
| 187 | } |
| 188 | if (!visit.empty()) { |
| 189 | w=visit.pop(); e=w->iter; goto next; |
| 190 | } |
| 191 | } |
| 192 | count = cnt0+1; |
| 193 | } |
| 194 | |
| 195 | |
| 196 | }}} |