lemon/matching.h
changeset 1430 c6aa2cc1af04
parent 1423 8c567e298d7f
equal deleted inserted replaced
10:e050331efcec 11:6ce1347a9985
   741 
   741 
   742     struct BlossomVariable {
   742     struct BlossomVariable {
   743       int begin, end;
   743       int begin, end;
   744       Value value;
   744       Value value;
   745 
   745 
   746       BlossomVariable(int _begin, int _end, Value _value)
   746       BlossomVariable(int _begin, Value _value)
   747         : begin(_begin), end(_end), value(_value) {}
   747           : begin(_begin), end(-1), value(_value) {}
   748 
   748 
   749     };
   749     };
   750 
   750 
   751     typedef std::vector<BlossomVariable> BlossomPotential;
   751     typedef std::vector<BlossomVariable> BlossomPotential;
   752 
   752 
  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;
  2214 
  2234 
  2215     struct BlossomVariable {
  2235     struct BlossomVariable {
  2216       int begin, end;
  2236       int begin, end;
  2217       Value value;
  2237       Value value;
  2218 
  2238 
  2219       BlossomVariable(int _begin, int _end, Value _value)
  2239       BlossomVariable(int _begin, Value _value)
  2220         : begin(_begin), end(_end), value(_value) {}
  2240         : begin(_begin), value(_value) {}
  2221 
  2241 
  2222     };
  2242     };
  2223 
  2243 
  2224     typedef std::vector<BlossomVariable> BlossomPotential;
  2244     typedef std::vector<BlossomVariable> BlossomPotential;
  2225 
  2245 
  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;