lemon/matching.h
changeset 1430 c6aa2cc1af04
parent 1423 8c567e298d7f
     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