| 173 | |
| 174 | template<class View> |
| 175 | forceinline bool |
| 176 | Graph<View>::mark(void) { |
| 177 | using namespace ViewValGraph; |
| 178 | |
| 179 | Region r; |
| 180 | |
| 181 | int n_view_visited = 0; |
| 182 | { |
| 183 | // Marks all edges as used that are on simple paths in the graph |
| 184 | // that start from a free (unmatched node) by depth-first-search |
| 185 | Support::StaticStack<ValNode<View>*,Region> visit(r,n_val); |
| 186 | |
| 187 | // Insert all free nodes: they can be only value nodes as we |
| 188 | // have a maximum matching covering all view nodes |
| 189 | count++; |
| 190 | { |
| 191 | ValNode<View>** v = &val; |
| 192 | while (*v != nullptr) |
| 193 | if (!(*v)->matching()) { |
| 194 | if ((*v)->empty()) { |
| 195 | *v = (*v)->next_val(); |
| 196 | n_val--; |
| 197 | } else { |
| 198 | (*v)->min = count; |
| 199 | visit.push(*v); |
| 200 | v = (*v)->next_val_ref(); |
| 201 | } |
| 202 | } else { |
| 203 | v = (*v)->next_val_ref(); |
| 204 | } |
| 205 | } |
| 206 | |
| 207 | // Invariant: only value nodes are on the stack! |
| 208 | while (!visit.empty()) { |
| 209 | ValNode<View>* n = visit.pop(); |
| 210 | for (Edge<View>* e = n->edge_fst(); e != n->edge_lst(); e=e->next()) { |
| 211 | // Get the value node |
| 212 | e->use(); |
| 213 | ViewNode<View>* x = e->view(n); |
| 214 | if (x->min < count) { |
| 215 | n_view_visited++; |
| 216 | x->min = count; |
| 217 | assert(x->edge_fst()->next() == x->edge_lst()); |
| 218 | ValNode<View>* m = x->edge_fst()->val(x); |
| 219 | x->edge_fst()->use(); |
| 220 | if (m->min < count) { |
| 221 | m->min = count; |
| 222 | visit.push(m); |
| 223 | } |
| 224 | } |
| 225 | } |
| 226 | } |
| 227 | } |
| 228 | |
| 229 | // If all view nodes have been visited, also all edges are used! |
| 230 | if (n_view_visited < n_view) { |
| 231 | scc(); |
| 232 | return true; |