1.1 --- a/lemon/matching.h Thu Jan 21 18:58:37 2021 +0100
1.2 +++ b/lemon/matching.h Thu Feb 25 09:46:12 2021 +0100
1.3 @@ -743,8 +743,8 @@
1.4 int begin, end;
1.5 Value value;
1.6
1.7 - BlossomVariable(int _begin, int _end, Value _value)
1.8 - : begin(_begin), end(_end), value(_value) {}
1.9 + BlossomVariable(int _begin, Value _value)
1.10 + : begin(_begin), end(-1), value(_value) {}
1.11
1.12 };
1.13
1.14 @@ -1521,40 +1521,60 @@
1.15 _tree_set->erase(blossom);
1.16 }
1.17
1.18 + struct ExtractBlossomItem {
1.19 + int blossom;
1.20 + Node base;
1.21 + Arc matching;
1.22 + int close_index;
1.23 + ExtractBlossomItem(int _blossom, Node _base,
1.24 + Arc _matching, int _close_index)
1.25 + : blossom(_blossom), base(_base), matching(_matching),
1.26 + close_index(_close_index) {}
1.27 + };
1.28 +
1.29 void extractBlossom(int blossom, const Node& base, const Arc& matching) {
1.30 - if (_blossom_set->trivial(blossom)) {
1.31 - int bi = (*_node_index)[base];
1.32 - Value pot = (*_node_data)[bi].pot;
1.33 -
1.34 - (*_matching)[base] = matching;
1.35 - _blossom_node_list.push_back(base);
1.36 - (*_node_potential)[base] = pot;
1.37 - } else {
1.38 -
1.39 - Value pot = (*_blossom_data)[blossom].pot;
1.40 - int bn = _blossom_node_list.size();
1.41 -
1.42 - std::vector<int> subblossoms;
1.43 - _blossom_set->split(blossom, std::back_inserter(subblossoms));
1.44 - int b = _blossom_set->find(base);
1.45 - int ib = -1;
1.46 - for (int i = 0; i < int(subblossoms.size()); ++i) {
1.47 - if (subblossoms[i] == b) { ib = i; break; }
1.48 + std::vector<ExtractBlossomItem> stack;
1.49 + std::vector<int> close_stack;
1.50 + stack.push_back(ExtractBlossomItem(blossom, base, matching, 0));
1.51 + while (!stack.empty()) {
1.52 + if (_blossom_set->trivial(stack.back().blossom)) {
1.53 + int bi = (*_node_index)[stack.back().base];
1.54 + Value pot = (*_node_data)[bi].pot;
1.55 +
1.56 + (*_matching)[stack.back().base] = stack.back().matching;
1.57 + (*_node_potential)[stack.back().base] = pot;
1.58 + _blossom_node_list.push_back(stack.back().base);
1.59 + while (int(close_stack.size()) > stack.back().close_index) {
1.60 + _blossom_potential[close_stack.back()].end = _blossom_node_list.size();
1.61 + close_stack.pop_back();
1.62 + }
1.63 + stack.pop_back();
1.64 + } else {
1.65 + Value pot = (*_blossom_data)[stack.back().blossom].pot;
1.66 + int bn = _blossom_node_list.size();
1.67 + close_stack.push_back(_blossom_potential.size());
1.68 + _blossom_potential.push_back(BlossomVariable(bn, pot));
1.69 +
1.70 + std::vector<int> subblossoms;
1.71 + _blossom_set->split(stack.back().blossom, std::back_inserter(subblossoms));
1.72 + int b = _blossom_set->find(stack.back().base);
1.73 + int ib = -1;
1.74 + for (int i = 0; i < int(subblossoms.size()); ++i) {
1.75 + if (subblossoms[i] == b) { ib = i; break; }
1.76 + }
1.77 +
1.78 + stack.back().blossom = subblossoms[ib];
1.79 + for (int i = 1; i < int(subblossoms.size()); i += 2) {
1.80 + int sb = subblossoms[(ib + i) % subblossoms.size()];
1.81 + int tb = subblossoms[(ib + i + 1) % subblossoms.size()];
1.82 +
1.83 + Arc m = (*_blossom_data)[tb].next;
1.84 + stack.push_back(ExtractBlossomItem(
1.85 + sb, _graph.target(m), _graph.oppositeArc(m), close_stack.size()));
1.86 + stack.push_back(ExtractBlossomItem(
1.87 + tb, _graph.source(m), m, close_stack.size()));
1.88 + }
1.89 }
1.90 -
1.91 - for (int i = 1; i < int(subblossoms.size()); i += 2) {
1.92 - int sb = subblossoms[(ib + i) % subblossoms.size()];
1.93 - int tb = subblossoms[(ib + i + 1) % subblossoms.size()];
1.94 -
1.95 - Arc m = (*_blossom_data)[tb].next;
1.96 - extractBlossom(sb, _graph.target(m), _graph.oppositeArc(m));
1.97 - extractBlossom(tb, _graph.source(m), m);
1.98 - }
1.99 - extractBlossom(subblossoms[ib], base, matching);
1.100 -
1.101 - int en = _blossom_node_list.size();
1.102 -
1.103 - _blossom_potential.push_back(BlossomVariable(bn, en, pot));
1.104 }
1.105 }
1.106
1.107 @@ -2216,8 +2236,8 @@
1.108 int begin, end;
1.109 Value value;
1.110
1.111 - BlossomVariable(int _begin, int _end, Value _value)
1.112 - : begin(_begin), end(_end), value(_value) {}
1.113 + BlossomVariable(int _begin, Value _value)
1.114 + : begin(_begin), value(_value) {}
1.115
1.116 };
1.117
1.118 @@ -2949,40 +2969,60 @@
1.119 _tree_set->erase(blossom);
1.120 }
1.121
1.122 + struct ExtractBlossomItem {
1.123 + int blossom;
1.124 + Node base;
1.125 + Arc matching;
1.126 + int close_index;
1.127 + ExtractBlossomItem(int _blossom, Node _base,
1.128 + Arc _matching, int _close_index)
1.129 + : blossom(_blossom), base(_base), matching(_matching),
1.130 + close_index(_close_index) {}
1.131 + };
1.132 +
1.133 void extractBlossom(int blossom, const Node& base, const Arc& matching) {
1.134 - if (_blossom_set->trivial(blossom)) {
1.135 - int bi = (*_node_index)[base];
1.136 - Value pot = (*_node_data)[bi].pot;
1.137 -
1.138 - (*_matching)[base] = matching;
1.139 - _blossom_node_list.push_back(base);
1.140 - (*_node_potential)[base] = pot;
1.141 - } else {
1.142 -
1.143 - Value pot = (*_blossom_data)[blossom].pot;
1.144 - int bn = _blossom_node_list.size();
1.145 -
1.146 - std::vector<int> subblossoms;
1.147 - _blossom_set->split(blossom, std::back_inserter(subblossoms));
1.148 - int b = _blossom_set->find(base);
1.149 - int ib = -1;
1.150 - for (int i = 0; i < int(subblossoms.size()); ++i) {
1.151 - if (subblossoms[i] == b) { ib = i; break; }
1.152 + std::vector<ExtractBlossomItem> stack;
1.153 + std::vector<int> close_stack;
1.154 + stack.push_back(ExtractBlossomItem(blossom, base, matching, 0));
1.155 + while (!stack.empty()) {
1.156 + if (_blossom_set->trivial(stack.back().blossom)) {
1.157 + int bi = (*_node_index)[stack.back().base];
1.158 + Value pot = (*_node_data)[bi].pot;
1.159 +
1.160 + (*_matching)[stack.back().base] = stack.back().matching;
1.161 + (*_node_potential)[stack.back().base] = pot;
1.162 + _blossom_node_list.push_back(stack.back().base);
1.163 + while (int(close_stack.size()) > stack.back().close_index) {
1.164 + _blossom_potential[close_stack.back()].end = _blossom_node_list.size();
1.165 + close_stack.pop_back();
1.166 + }
1.167 + stack.pop_back();
1.168 + } else {
1.169 + Value pot = (*_blossom_data)[stack.back().blossom].pot;
1.170 + int bn = _blossom_node_list.size();
1.171 + close_stack.push_back(_blossom_potential.size());
1.172 + _blossom_potential.push_back(BlossomVariable(bn, pot));
1.173 +
1.174 + std::vector<int> subblossoms;
1.175 + _blossom_set->split(stack.back().blossom, std::back_inserter(subblossoms));
1.176 + int b = _blossom_set->find(stack.back().base);
1.177 + int ib = -1;
1.178 + for (int i = 0; i < int(subblossoms.size()); ++i) {
1.179 + if (subblossoms[i] == b) { ib = i; break; }
1.180 + }
1.181 +
1.182 + stack.back().blossom = subblossoms[ib];
1.183 + for (int i = 1; i < int(subblossoms.size()); i += 2) {
1.184 + int sb = subblossoms[(ib + i) % subblossoms.size()];
1.185 + int tb = subblossoms[(ib + i + 1) % subblossoms.size()];
1.186 +
1.187 + Arc m = (*_blossom_data)[tb].next;
1.188 + stack.push_back(ExtractBlossomItem(
1.189 + sb, _graph.target(m), _graph.oppositeArc(m), close_stack.size()));
1.190 + stack.push_back(ExtractBlossomItem(
1.191 + tb, _graph.source(m), m, close_stack.size()));
1.192 + }
1.193 }
1.194 -
1.195 - for (int i = 1; i < int(subblossoms.size()); i += 2) {
1.196 - int sb = subblossoms[(ib + i) % subblossoms.size()];
1.197 - int tb = subblossoms[(ib + i + 1) % subblossoms.size()];
1.198 -
1.199 - Arc m = (*_blossom_data)[tb].next;
1.200 - extractBlossom(sb, _graph.target(m), _graph.oppositeArc(m));
1.201 - extractBlossom(tb, _graph.source(m), m);
1.202 - }
1.203 - extractBlossom(subblossoms[ib], base, matching);
1.204 -
1.205 - int en = _blossom_node_list.size();
1.206 -
1.207 - _blossom_potential.push_back(BlossomVariable(bn, en, pot));
1.208 }
1.209 }
1.210