| 1674 | |
| 1675 | template<class Card> template<BC bc> |
| 1676 | void |
| 1677 | VarValGraph<Card>::dfs(Node* v, |
| 1678 | BitSet& inscc, BitSet& in_unfinished, int dfsnum[], |
| 1679 | NodeStack& roots, NodeStack& unfinished, |
| 1680 | int& count) { |
| 1681 | count++; |
| 1682 | int v_index = v->index(); |
| 1683 | dfsnum[v_index] = count; |
| 1684 | inscc.set(static_cast<unsigned int>(v_index)); |
| 1685 | in_unfinished.set(static_cast<unsigned int>(v_index)); |
| 1686 | |
| 1687 | unfinished.push(v); |
| 1688 | roots.push(v); |
| 1689 | for (Edge* e = v->first(); e != nullptr; e = e->next(v->type())) { |
| 1690 | bool m; |
| 1691 | switch (bc) { |
| 1692 | case LBC: |
| 1693 | m = v->type() ? e->matched(LBC) : !e->matched(LBC); |
| 1694 | break; |
| 1695 | case UBC: |
| 1696 | m = v->type() ? !e->matched(UBC) : e->matched(UBC); |
| 1697 | break; |
| 1698 | default: GECODE_NEVER; |
| 1699 | } |
| 1700 | if (m) { |
| 1701 | Node* w = e->getMate(v->type()); |
| 1702 | int w_index = w->index(); |
| 1703 | |
| 1704 | assert(w_index < n_node); |
| 1705 | if (!inscc.get(static_cast<unsigned int>(w_index))) { |
| 1706 | // w is an uncompleted scc |
| 1707 | w->inedge(e); |
| 1708 | dfs<bc>(w, inscc, in_unfinished, dfsnum, |
| 1709 | roots, unfinished, count); |
| 1710 | } else if (in_unfinished.get(static_cast<unsigned int>(w_index))) { |
| 1711 | // even alternating cycle found mark the edge closing the cycle, |
| 1712 | // completing the scc |
| 1713 | e->use(bc); |
| 1714 | // if w belongs to an scc we detected earlier |
| 1715 | // merge components |
| 1716 | assert(roots.top()->index() < n_node); |
| 1717 | while (dfsnum[roots.top()->index()] > dfsnum[w_index]) { |
| 1718 | roots.pop(); |
| 1719 | } |
| 1720 | } |
| 1721 | } |
| 1722 | } |
| 1723 | |
| 1724 | if (v == roots.top()) { |
| 1725 | while (v != unfinished.top()) { |
| 1726 | // w belongs to the scc with root v |
| 1727 | Node* w = unfinished.top(); |
| 1728 | w->inedge()->use(bc); |
| 1729 | in_unfinished.clear(static_cast<unsigned int>(w->index())); |
| 1730 | unfinished.pop(); |
| 1731 | } |
| 1732 | assert(v == unfinished.top()); |
| 1733 | in_unfinished.clear(static_cast<unsigned int>(v_index)); |