1519 (*_blossom_data)[subblossoms[ib]].pred = pred; |
1519 (*_blossom_data)[subblossoms[ib]].pred = pred; |
1520 } |
1520 } |
1521 _tree_set->erase(blossom); |
1521 _tree_set->erase(blossom); |
1522 } |
1522 } |
1523 |
1523 |
|
1524 struct ExtractBlossomItem { |
|
1525 int blossom; |
|
1526 Node base; |
|
1527 Arc matching; |
|
1528 int close_index; |
|
1529 ExtractBlossomItem(int _blossom, Node _base, |
|
1530 Arc _matching, int _close_index) |
|
1531 : blossom(_blossom), base(_base), matching(_matching), |
|
1532 close_index(_close_index) {} |
|
1533 }; |
|
1534 |
1524 void extractBlossom(int blossom, const Node& base, const Arc& matching) { |
1535 void extractBlossom(int blossom, const Node& base, const Arc& matching) { |
1525 if (_blossom_set->trivial(blossom)) { |
1536 std::vector<ExtractBlossomItem> stack; |
1526 int bi = (*_node_index)[base]; |
1537 std::vector<int> close_stack; |
1527 Value pot = (*_node_data)[bi].pot; |
1538 stack.push_back(ExtractBlossomItem(blossom, base, matching, 0)); |
1528 |
1539 while (!stack.empty()) { |
1529 (*_matching)[base] = matching; |
1540 if (_blossom_set->trivial(stack.back().blossom)) { |
1530 _blossom_node_list.push_back(base); |
1541 int bi = (*_node_index)[stack.back().base]; |
1531 (*_node_potential)[base] = pot; |
1542 Value pot = (*_node_data)[bi].pot; |
1532 } else { |
1543 |
1533 |
1544 (*_matching)[stack.back().base] = stack.back().matching; |
1534 Value pot = (*_blossom_data)[blossom].pot; |
1545 (*_node_potential)[stack.back().base] = pot; |
1535 int bn = _blossom_node_list.size(); |
1546 _blossom_node_list.push_back(stack.back().base); |
1536 |
1547 while (int(close_stack.size()) > stack.back().close_index) { |
1537 std::vector<int> subblossoms; |
1548 _blossom_potential[close_stack.back()].end = _blossom_node_list.size(); |
1538 _blossom_set->split(blossom, std::back_inserter(subblossoms)); |
1549 close_stack.pop_back(); |
1539 int b = _blossom_set->find(base); |
1550 } |
1540 int ib = -1; |
1551 stack.pop_back(); |
1541 for (int i = 0; i < int(subblossoms.size()); ++i) { |
1552 } else { |
1542 if (subblossoms[i] == b) { ib = i; break; } |
1553 Value pot = (*_blossom_data)[stack.back().blossom].pot; |
1543 } |
1554 int bn = _blossom_node_list.size(); |
1544 |
1555 close_stack.push_back(_blossom_potential.size()); |
1545 for (int i = 1; i < int(subblossoms.size()); i += 2) { |
1556 _blossom_potential.push_back(BlossomVariable(bn, pot)); |
1546 int sb = subblossoms[(ib + i) % subblossoms.size()]; |
1557 |
1547 int tb = subblossoms[(ib + i + 1) % subblossoms.size()]; |
1558 std::vector<int> subblossoms; |
1548 |
1559 _blossom_set->split(stack.back().blossom, std::back_inserter(subblossoms)); |
1549 Arc m = (*_blossom_data)[tb].next; |
1560 int b = _blossom_set->find(stack.back().base); |
1550 extractBlossom(sb, _graph.target(m), _graph.oppositeArc(m)); |
1561 int ib = -1; |
1551 extractBlossom(tb, _graph.source(m), m); |
1562 for (int i = 0; i < int(subblossoms.size()); ++i) { |
1552 } |
1563 if (subblossoms[i] == b) { ib = i; break; } |
1553 extractBlossom(subblossoms[ib], base, matching); |
1564 } |
1554 |
1565 |
1555 int en = _blossom_node_list.size(); |
1566 stack.back().blossom = subblossoms[ib]; |
1556 |
1567 for (int i = 1; i < int(subblossoms.size()); i += 2) { |
1557 _blossom_potential.push_back(BlossomVariable(bn, en, pot)); |
1568 int sb = subblossoms[(ib + i) % subblossoms.size()]; |
|
1569 int tb = subblossoms[(ib + i + 1) % subblossoms.size()]; |
|
1570 |
|
1571 Arc m = (*_blossom_data)[tb].next; |
|
1572 stack.push_back(ExtractBlossomItem( |
|
1573 sb, _graph.target(m), _graph.oppositeArc(m), close_stack.size())); |
|
1574 stack.push_back(ExtractBlossomItem( |
|
1575 tb, _graph.source(m), m, close_stack.size())); |
|
1576 } |
|
1577 } |
1558 } |
1578 } |
1559 } |
1579 } |
1560 |
1580 |
1561 void extractMatching() { |
1581 void extractMatching() { |
1562 std::vector<int> blossoms; |
1582 std::vector<int> blossoms; |
2947 (*_blossom_data)[subblossoms[ib]].pred = pred; |
2967 (*_blossom_data)[subblossoms[ib]].pred = pred; |
2948 } |
2968 } |
2949 _tree_set->erase(blossom); |
2969 _tree_set->erase(blossom); |
2950 } |
2970 } |
2951 |
2971 |
|
2972 struct ExtractBlossomItem { |
|
2973 int blossom; |
|
2974 Node base; |
|
2975 Arc matching; |
|
2976 int close_index; |
|
2977 ExtractBlossomItem(int _blossom, Node _base, |
|
2978 Arc _matching, int _close_index) |
|
2979 : blossom(_blossom), base(_base), matching(_matching), |
|
2980 close_index(_close_index) {} |
|
2981 }; |
|
2982 |
2952 void extractBlossom(int blossom, const Node& base, const Arc& matching) { |
2983 void extractBlossom(int blossom, const Node& base, const Arc& matching) { |
2953 if (_blossom_set->trivial(blossom)) { |
2984 std::vector<ExtractBlossomItem> stack; |
2954 int bi = (*_node_index)[base]; |
2985 std::vector<int> close_stack; |
2955 Value pot = (*_node_data)[bi].pot; |
2986 stack.push_back(ExtractBlossomItem(blossom, base, matching, 0)); |
2956 |
2987 while (!stack.empty()) { |
2957 (*_matching)[base] = matching; |
2988 if (_blossom_set->trivial(stack.back().blossom)) { |
2958 _blossom_node_list.push_back(base); |
2989 int bi = (*_node_index)[stack.back().base]; |
2959 (*_node_potential)[base] = pot; |
2990 Value pot = (*_node_data)[bi].pot; |
2960 } else { |
2991 |
2961 |
2992 (*_matching)[stack.back().base] = stack.back().matching; |
2962 Value pot = (*_blossom_data)[blossom].pot; |
2993 (*_node_potential)[stack.back().base] = pot; |
2963 int bn = _blossom_node_list.size(); |
2994 _blossom_node_list.push_back(stack.back().base); |
2964 |
2995 while (int(close_stack.size()) > stack.back().close_index) { |
2965 std::vector<int> subblossoms; |
2996 _blossom_potential[close_stack.back()].end = _blossom_node_list.size(); |
2966 _blossom_set->split(blossom, std::back_inserter(subblossoms)); |
2997 close_stack.pop_back(); |
2967 int b = _blossom_set->find(base); |
2998 } |
2968 int ib = -1; |
2999 stack.pop_back(); |
2969 for (int i = 0; i < int(subblossoms.size()); ++i) { |
3000 } else { |
2970 if (subblossoms[i] == b) { ib = i; break; } |
3001 Value pot = (*_blossom_data)[stack.back().blossom].pot; |
2971 } |
3002 int bn = _blossom_node_list.size(); |
2972 |
3003 close_stack.push_back(_blossom_potential.size()); |
2973 for (int i = 1; i < int(subblossoms.size()); i += 2) { |
3004 _blossom_potential.push_back(BlossomVariable(bn, pot)); |
2974 int sb = subblossoms[(ib + i) % subblossoms.size()]; |
3005 |
2975 int tb = subblossoms[(ib + i + 1) % subblossoms.size()]; |
3006 std::vector<int> subblossoms; |
2976 |
3007 _blossom_set->split(stack.back().blossom, std::back_inserter(subblossoms)); |
2977 Arc m = (*_blossom_data)[tb].next; |
3008 int b = _blossom_set->find(stack.back().base); |
2978 extractBlossom(sb, _graph.target(m), _graph.oppositeArc(m)); |
3009 int ib = -1; |
2979 extractBlossom(tb, _graph.source(m), m); |
3010 for (int i = 0; i < int(subblossoms.size()); ++i) { |
2980 } |
3011 if (subblossoms[i] == b) { ib = i; break; } |
2981 extractBlossom(subblossoms[ib], base, matching); |
3012 } |
2982 |
3013 |
2983 int en = _blossom_node_list.size(); |
3014 stack.back().blossom = subblossoms[ib]; |
2984 |
3015 for (int i = 1; i < int(subblossoms.size()); i += 2) { |
2985 _blossom_potential.push_back(BlossomVariable(bn, en, pot)); |
3016 int sb = subblossoms[(ib + i) % subblossoms.size()]; |
|
3017 int tb = subblossoms[(ib + i + 1) % subblossoms.size()]; |
|
3018 |
|
3019 Arc m = (*_blossom_data)[tb].next; |
|
3020 stack.push_back(ExtractBlossomItem( |
|
3021 sb, _graph.target(m), _graph.oppositeArc(m), close_stack.size())); |
|
3022 stack.push_back(ExtractBlossomItem( |
|
3023 tb, _graph.source(m), m, close_stack.size())); |
|
3024 } |
|
3025 } |
2986 } |
3026 } |
2987 } |
3027 } |
2988 |
3028 |
2989 void extractMatching() { |
3029 void extractMatching() { |
2990 std::vector<int> blossoms; |
3030 std::vector<int> blossoms; |