| 84 | |
| 85 | template<class View> |
| 86 | forceinline bool |
| 87 | Graph<View>::match(ViewNodeStack& m, ViewNode<View>* x) { |
| 88 | count++; |
| 89 | start: |
| 90 | // Try to find matching edge cheaply: is there a free edge around? |
| 91 | { |
| 92 | Edge<View>* e = x->val_edges(); |
| 93 | // This holds true as domains are never empty |
| 94 | assert(e != nullptr); |
| 95 | do { |
| 96 | if (!e->val(x)->matching()) { |
| 97 | e->revert(x); e->val(x)->matching(e); |
| 98 | // Found a matching, revert all edges on stack |
| 99 | while (!m.empty()) { |
| 100 | x = m.pop(); e = x->iter; |
| 101 | e->val(x)->matching()->revert(e->val(x)); |
| 102 | e->revert(x); e->val(x)->matching(e); |
| 103 | } |
| 104 | return true; |
| 105 | } |
| 106 | e = e->next_edge(); |
| 107 | } while (e != nullptr); |
| 108 | } |
| 109 | // No, find matching edge by augmenting path method |
| 110 | Edge<View>* e = x->val_edges(); |
| 111 | do { |
| 112 | if (e->val(x)->matching()->view(e->val(x))->min < count) { |
| 113 | e->val(x)->matching()->view(e->val(x))->min = count; |
| 114 | m.push(x); x->iter = e; |
| 115 | x = e->val(x)->matching()->view(e->val(x)); |
| 116 | goto start; |
| 117 | } |
| 118 | next: |
| 119 | e = e->next_edge(); |
| 120 | } while (e != nullptr); |
| 121 | if (!m.empty()) { |
| 122 | x = m.pop(); e = x->iter; goto next; |
| 123 | } |
| 124 | // All nodes and edges unsuccessfully tried |
| 125 | return false; |
| 126 | } |
| 127 | |
| 128 | template<class View> |
| 129 | forceinline void |