| 1137 | |
| 1138 | template<class Card> template<BC bc> |
| 1139 | forceinline bool |
| 1140 | VarValGraph<Card>::augmenting_path(Node* v) { |
| 1141 | Region r; |
| 1142 | NodeStack ns(r,n_node); |
| 1143 | BitSet visited(r,static_cast<unsigned int>(n_node)); |
| 1144 | Edge** start = r.alloc<Edge*>(n_node); |
| 1145 | |
| 1146 | // keep track of the nodes that have already been visited |
| 1147 | Node* sn = v; |
| 1148 | |
| 1149 | // mark the start partition |
| 1150 | bool sp = sn->type(); |
| 1151 | |
| 1152 | // nodes in sp only follow free edges |
| 1153 | // nodes in V - sp only follow matched edges |
| 1154 | |
| 1155 | for (int i = n_node; i--; ) |
| 1156 | if (i >= n_var) { |
| 1157 | vals[i-n_var]->inedge(nullptr); |
| 1158 | start[i] = vals[i-n_var]->first(); |
| 1159 | } else { |
| 1160 | vars[i]->inedge(nullptr); |
| 1161 | start[i] = vars[i]->first(); |
| 1162 | } |
| 1163 | |
| 1164 | v->inedge(nullptr); |
| 1165 | ns.push(v); |
| 1166 | visited.set(static_cast<unsigned int>(v->index())); |
| 1167 | while (!ns.empty()) { |
| 1168 | Node* vv = ns.top(); |
| 1169 | Edge* e = nullptr; |
| 1170 | if (vv->type() == sp) { |
| 1171 | e = start[vv->index()]; |
| 1172 | while ((e != nullptr) && e->matched(bc)) |
| 1173 | e = e->next(vv->type()); |
| 1174 | } else { |
| 1175 | e = start[vv->index()]; |
| 1176 | while ((e != nullptr) && !e->matched(bc)) |
| 1177 | e = e->next(vv->type()); |
| 1178 | start[vv->index()] = e; |
| 1179 | } |
| 1180 | if (e != nullptr) { |
| 1181 | start[vv->index()] = e->next(vv->type()); |
| 1182 | Node* w = e->getMate(vv->type()); |
| 1183 | if (!visited.get(static_cast<unsigned int>(w->index()))) { |
| 1184 | // unexplored path |
| 1185 | bool m = w->type() ? |
| 1186 | static_cast<ValNode*>(w)->matched(bc) : |
| 1187 | static_cast<VarNode*>(w)->matched(bc); |
| 1188 | if (!m && w->type() != sp) { |
| 1189 | if (vv->inedge() != nullptr) { |
| 1190 | // augmenting path of length l > 1 |
| 1191 | e->match(bc); |
| 1192 | break; |
| 1193 | } else { |
| 1194 | // augmenting path of length l = 1 |
| 1195 | e->match(bc); |
| 1196 | ns.pop(); |