author Balazs Dezso Fri, 22 Jan 2021 10:55:32 +0100 changeset 1430 c6aa2cc1af04 parent 1423 8c567e298d7f child 1431 4a170261cc54
Factor out recursion from weighted matching algorithms (#638)
 lemon/matching.h file | annotate | diff | comparison | revisions
```     1.1 --- a/lemon/matching.h	Sat Oct 27 13:00:48 2018 +0200
1.2 +++ b/lemon/matching.h	Fri Jan 22 10:55:32 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
```