lemon/max_matching.h
changeset 592 2ebfdb89ec66
parent 559 c5fd2d996909
child 590 b61354458b59
equal deleted inserted replaced
5:99828e8cc26c 6:68d165361847
   280         Node node = _graph.u(e);
   280         Node node = _graph.u(e);
   281         Arc arc = _graph.direct(e, true);
   281         Arc arc = _graph.direct(e, true);
   282         Node base = (*_blossom_rep)[_blossom_set->find(node)];
   282         Node base = (*_blossom_rep)[_blossom_set->find(node)];
   283 
   283 
   284         while (base != nca) {
   284         while (base != nca) {
   285           _ear->set(node, arc);
   285           (*_ear)[node] = arc;
   286 
   286 
   287           Node n = node;
   287           Node n = node;
   288           while (n != base) {
   288           while (n != base) {
   289             n = _graph.target((*_matching)[n]);
   289             n = _graph.target((*_matching)[n]);
   290             Arc a = (*_ear)[n];
   290             Arc a = (*_ear)[n];
   291             n = _graph.target(a);
   291             n = _graph.target(a);
   292             _ear->set(n, _graph.oppositeArc(a));
   292             (*_ear)[n] = _graph.oppositeArc(a);
   293           }
   293           }
   294           node = _graph.target((*_matching)[base]);
   294           node = _graph.target((*_matching)[base]);
   295           _tree_set->erase(base);
   295           _tree_set->erase(base);
   296           _tree_set->erase(node);
   296           _tree_set->erase(node);
   297           _blossom_set->insert(node, _blossom_set->find(base));
   297           _blossom_set->insert(node, _blossom_set->find(base));
   298           _status->set(node, EVEN);
   298           (*_status)[node] = EVEN;
   299           _node_queue[_last++] = node;
   299           _node_queue[_last++] = node;
   300           arc = _graph.oppositeArc((*_ear)[node]);
   300           arc = _graph.oppositeArc((*_ear)[node]);
   301           node = _graph.target((*_ear)[node]);
   301           node = _graph.target((*_ear)[node]);
   302           base = (*_blossom_rep)[_blossom_set->find(node)];
   302           base = (*_blossom_rep)[_blossom_set->find(node)];
   303           _blossom_set->join(_graph.target(arc), base);
   303           _blossom_set->join(_graph.target(arc), base);
   304         }
   304         }
   305       }
   305       }
   306 
   306 
   307       _blossom_rep->set(_blossom_set->find(nca), nca);
   307       (*_blossom_rep)[_blossom_set->find(nca)] = nca;
   308 
   308 
   309       {
   309       {
   310 
   310 
   311         Node node = _graph.v(e);
   311         Node node = _graph.v(e);
   312         Arc arc = _graph.direct(e, false);
   312         Arc arc = _graph.direct(e, false);
   313         Node base = (*_blossom_rep)[_blossom_set->find(node)];
   313         Node base = (*_blossom_rep)[_blossom_set->find(node)];
   314 
   314 
   315         while (base != nca) {
   315         while (base != nca) {
   316           _ear->set(node, arc);
   316           (*_ear)[node] = arc;
   317 
   317 
   318           Node n = node;
   318           Node n = node;
   319           while (n != base) {
   319           while (n != base) {
   320             n = _graph.target((*_matching)[n]);
   320             n = _graph.target((*_matching)[n]);
   321             Arc a = (*_ear)[n];
   321             Arc a = (*_ear)[n];
   322             n = _graph.target(a);
   322             n = _graph.target(a);
   323             _ear->set(n, _graph.oppositeArc(a));
   323             (*_ear)[n] = _graph.oppositeArc(a);
   324           }
   324           }
   325           node = _graph.target((*_matching)[base]);
   325           node = _graph.target((*_matching)[base]);
   326           _tree_set->erase(base);
   326           _tree_set->erase(base);
   327           _tree_set->erase(node);
   327           _tree_set->erase(node);
   328           _blossom_set->insert(node, _blossom_set->find(base));
   328           _blossom_set->insert(node, _blossom_set->find(base));
   329           _status->set(node, EVEN);
   329           (*_status)[node] = EVEN;
   330           _node_queue[_last++] = node;
   330           _node_queue[_last++] = node;
   331           arc = _graph.oppositeArc((*_ear)[node]);
   331           arc = _graph.oppositeArc((*_ear)[node]);
   332           node = _graph.target((*_ear)[node]);
   332           node = _graph.target((*_ear)[node]);
   333           base = (*_blossom_rep)[_blossom_set->find(node)];
   333           base = (*_blossom_rep)[_blossom_set->find(node)];
   334           _blossom_set->join(_graph.target(arc), base);
   334           _blossom_set->join(_graph.target(arc), base);
   335         }
   335         }
   336       }
   336       }
   337 
   337 
   338       _blossom_rep->set(_blossom_set->find(nca), nca);
   338       (*_blossom_rep)[_blossom_set->find(nca)] = nca;
   339     }
   339     }
   340 
   340 
   341 
   341 
   342 
   342 
   343     void extendOnArc(const Arc& a) {
   343     void extendOnArc(const Arc& a) {
   344       Node base = _graph.source(a);
   344       Node base = _graph.source(a);
   345       Node odd = _graph.target(a);
   345       Node odd = _graph.target(a);
   346 
   346 
   347       _ear->set(odd, _graph.oppositeArc(a));
   347       (*_ear)[odd] = _graph.oppositeArc(a);
   348       Node even = _graph.target((*_matching)[odd]);
   348       Node even = _graph.target((*_matching)[odd]);
   349       _blossom_rep->set(_blossom_set->insert(even), even);
   349       (*_blossom_rep)[_blossom_set->insert(even)] = even;
   350       _status->set(odd, ODD);
   350       (*_status)[odd] = ODD;
   351       _status->set(even, EVEN);
   351       (*_status)[even] = EVEN;
   352       int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(base)]);
   352       int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(base)]);
   353       _tree_set->insert(odd, tree);
   353       _tree_set->insert(odd, tree);
   354       _tree_set->insert(even, tree);
   354       _tree_set->insert(even, tree);
   355       _node_queue[_last++] = even;
   355       _node_queue[_last++] = even;
   356 
   356 
   360       Node even = _graph.source(a);
   360       Node even = _graph.source(a);
   361       Node odd = _graph.target(a);
   361       Node odd = _graph.target(a);
   362 
   362 
   363       int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(even)]);
   363       int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(even)]);
   364 
   364 
   365       _matching->set(odd, _graph.oppositeArc(a));
   365       (*_matching)[odd] = _graph.oppositeArc(a);
   366       _status->set(odd, MATCHED);
   366       (*_status)[odd] = MATCHED;
   367 
   367 
   368       Arc arc = (*_matching)[even];
   368       Arc arc = (*_matching)[even];
   369       _matching->set(even, a);
   369       (*_matching)[even] = a;
   370 
   370 
   371       while (arc != INVALID) {
   371       while (arc != INVALID) {
   372         odd = _graph.target(arc);
   372         odd = _graph.target(arc);
   373         arc = (*_ear)[odd];
   373         arc = (*_ear)[odd];
   374         even = _graph.target(arc);
   374         even = _graph.target(arc);
   375         _matching->set(odd, arc);
   375         (*_matching)[odd] = arc;
   376         arc = (*_matching)[even];
   376         arc = (*_matching)[even];
   377         _matching->set(even, _graph.oppositeArc((*_matching)[odd]));
   377         (*_matching)[even] = _graph.oppositeArc((*_matching)[odd]);
   378       }
   378       }
   379 
   379 
   380       for (typename TreeSet::ItemIt it(*_tree_set, tree);
   380       for (typename TreeSet::ItemIt it(*_tree_set, tree);
   381            it != INVALID; ++it) {
   381            it != INVALID; ++it) {
   382         if ((*_status)[it] == ODD) {
   382         if ((*_status)[it] == ODD) {
   383           _status->set(it, MATCHED);
   383           (*_status)[it] = MATCHED;
   384         } else {
   384         } else {
   385           int blossom = _blossom_set->find(it);
   385           int blossom = _blossom_set->find(it);
   386           for (typename BlossomSet::ItemIt jt(*_blossom_set, blossom);
   386           for (typename BlossomSet::ItemIt jt(*_blossom_set, blossom);
   387                jt != INVALID; ++jt) {
   387                jt != INVALID; ++jt) {
   388             _status->set(jt, MATCHED);
   388             (*_status)[jt] = MATCHED;
   389           }
   389           }
   390           _blossom_set->eraseClass(blossom);
   390           _blossom_set->eraseClass(blossom);
   391         }
   391         }
   392       }
   392       }
   393       _tree_set->eraseClass(tree);
   393       _tree_set->eraseClass(tree);
   425     /// Sets the actual matching to the empty matching.
   425     /// Sets the actual matching to the empty matching.
   426     ///
   426     ///
   427     void init() {
   427     void init() {
   428       createStructures();
   428       createStructures();
   429       for(NodeIt n(_graph); n != INVALID; ++n) {
   429       for(NodeIt n(_graph); n != INVALID; ++n) {
   430         _matching->set(n, INVALID);
   430         (*_matching)[n] = INVALID;
   431         _status->set(n, UNMATCHED);
   431         (*_status)[n] = UNMATCHED;
   432       }
   432       }
   433     }
   433     }
   434 
   434 
   435     ///\brief Finds an initial matching in a greedy way
   435     ///\brief Finds an initial matching in a greedy way
   436     ///
   436     ///
   437     ///It finds an initial matching in a greedy way.
   437     ///It finds an initial matching in a greedy way.
   438     void greedyInit() {
   438     void greedyInit() {
   439       createStructures();
   439       createStructures();
   440       for (NodeIt n(_graph); n != INVALID; ++n) {
   440       for (NodeIt n(_graph); n != INVALID; ++n) {
   441         _matching->set(n, INVALID);
   441         (*_matching)[n] = INVALID;
   442         _status->set(n, UNMATCHED);
   442         (*_status)[n] = UNMATCHED;
   443       }
   443       }
   444       for (NodeIt n(_graph); n != INVALID; ++n) {
   444       for (NodeIt n(_graph); n != INVALID; ++n) {
   445         if ((*_matching)[n] == INVALID) {
   445         if ((*_matching)[n] == INVALID) {
   446           for (OutArcIt a(_graph, n); a != INVALID ; ++a) {
   446           for (OutArcIt a(_graph, n); a != INVALID ; ++a) {
   447             Node v = _graph.target(a);
   447             Node v = _graph.target(a);
   448             if ((*_matching)[v] == INVALID && v != n) {
   448             if ((*_matching)[v] == INVALID && v != n) {
   449               _matching->set(n, a);
   449               (*_matching)[n] = a;
   450               _status->set(n, MATCHED);
   450               (*_status)[n] = MATCHED;
   451               _matching->set(v, _graph.oppositeArc(a));
   451               (*_matching)[v] = _graph.oppositeArc(a);
   452               _status->set(v, MATCHED);
   452               (*_status)[v] = MATCHED;
   453               break;
   453               break;
   454             }
   454             }
   455           }
   455           }
   456         }
   456         }
   457       }
   457       }
   467     template <typename MatchingMap>
   467     template <typename MatchingMap>
   468     bool matchingInit(const MatchingMap& matching) {
   468     bool matchingInit(const MatchingMap& matching) {
   469       createStructures();
   469       createStructures();
   470 
   470 
   471       for (NodeIt n(_graph); n != INVALID; ++n) {
   471       for (NodeIt n(_graph); n != INVALID; ++n) {
   472         _matching->set(n, INVALID);
   472         (*_matching)[n] = INVALID;
   473         _status->set(n, UNMATCHED);
   473         (*_status)[n] = UNMATCHED;
   474       }
   474       }
   475       for(EdgeIt e(_graph); e!=INVALID; ++e) {
   475       for(EdgeIt e(_graph); e!=INVALID; ++e) {
   476         if (matching[e]) {
   476         if (matching[e]) {
   477 
   477 
   478           Node u = _graph.u(e);
   478           Node u = _graph.u(e);
   479           if ((*_matching)[u] != INVALID) return false;
   479           if ((*_matching)[u] != INVALID) return false;
   480           _matching->set(u, _graph.direct(e, true));
   480           (*_matching)[u] = _graph.direct(e, true);
   481           _status->set(u, MATCHED);
   481           (*_status)[u] = MATCHED;
   482 
   482 
   483           Node v = _graph.v(e);
   483           Node v = _graph.v(e);
   484           if ((*_matching)[v] != INVALID) return false;
   484           if ((*_matching)[v] != INVALID) return false;
   485           _matching->set(v, _graph.direct(e, false));
   485           (*_matching)[v] = _graph.direct(e, false);
   486           _status->set(v, MATCHED);
   486           (*_status)[v] = MATCHED;
   487         }
   487         }
   488       }
   488       }
   489       return true;
   489       return true;
   490     }
   490     }
   491 
   491 
   495     void startSparse() {
   495     void startSparse() {
   496       for(NodeIt n(_graph); n != INVALID; ++n) {
   496       for(NodeIt n(_graph); n != INVALID; ++n) {
   497         if ((*_status)[n] == UNMATCHED) {
   497         if ((*_status)[n] == UNMATCHED) {
   498           (*_blossom_rep)[_blossom_set->insert(n)] = n;
   498           (*_blossom_rep)[_blossom_set->insert(n)] = n;
   499           _tree_set->insert(n);
   499           _tree_set->insert(n);
   500           _status->set(n, EVEN);
   500           (*_status)[n] = EVEN;
   501           processSparse(n);
   501           processSparse(n);
   502         }
   502         }
   503       }
   503       }
   504     }
   504     }
   505 
   505 
   510     void startDense() {
   510     void startDense() {
   511       for(NodeIt n(_graph); n != INVALID; ++n) {
   511       for(NodeIt n(_graph); n != INVALID; ++n) {
   512         if ((*_status)[n] == UNMATCHED) {
   512         if ((*_status)[n] == UNMATCHED) {
   513           (*_blossom_rep)[_blossom_set->insert(n)] = n;
   513           (*_blossom_rep)[_blossom_set->insert(n)] = n;
   514           _tree_set->insert(n);
   514           _tree_set->insert(n);
   515           _status->set(n, EVEN);
   515           (*_status)[n] = EVEN;
   516           processDense(n);
   516           processDense(n);
   517         }
   517         }
   518       }
   518       }
   519     }
   519     }
   520 
   520 
  1546     void extractBlossom(int blossom, const Node& base, const Arc& matching) {
  1546     void extractBlossom(int blossom, const Node& base, const Arc& matching) {
  1547       if (_blossom_set->trivial(blossom)) {
  1547       if (_blossom_set->trivial(blossom)) {
  1548         int bi = (*_node_index)[base];
  1548         int bi = (*_node_index)[base];
  1549         Value pot = (*_node_data)[bi].pot;
  1549         Value pot = (*_node_data)[bi].pot;
  1550 
  1550 
  1551         _matching->set(base, matching);
  1551         (*_matching)[base] = matching;
  1552         _blossom_node_list.push_back(base);
  1552         _blossom_node_list.push_back(base);
  1553         _node_potential->set(base, pot);
  1553         (*_node_potential)[base] = pot;
  1554       } else {
  1554       } else {
  1555 
  1555 
  1556         Value pot = (*_blossom_data)[blossom].pot;
  1556         Value pot = (*_blossom_data)[blossom].pot;
  1557         int bn = _blossom_node_list.size();
  1557         int bn = _blossom_node_list.size();
  1558 
  1558 
  1642     /// Initialize the algorithm
  1642     /// Initialize the algorithm
  1643     void init() {
  1643     void init() {
  1644       createStructures();
  1644       createStructures();
  1645 
  1645 
  1646       for (ArcIt e(_graph); e != INVALID; ++e) {
  1646       for (ArcIt e(_graph); e != INVALID; ++e) {
  1647         _node_heap_index->set(e, BinHeap<Value, IntArcMap>::PRE_HEAP);
  1647         (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
  1648       }
  1648       }
  1649       for (NodeIt n(_graph); n != INVALID; ++n) {
  1649       for (NodeIt n(_graph); n != INVALID; ++n) {
  1650         _delta1_index->set(n, _delta1->PRE_HEAP);
  1650         (*_delta1_index)[n] = _delta1->PRE_HEAP;
  1651       }
  1651       }
  1652       for (EdgeIt e(_graph); e != INVALID; ++e) {
  1652       for (EdgeIt e(_graph); e != INVALID; ++e) {
  1653         _delta3_index->set(e, _delta3->PRE_HEAP);
  1653         (*_delta3_index)[e] = _delta3->PRE_HEAP;
  1654       }
  1654       }
  1655       for (int i = 0; i < _blossom_num; ++i) {
  1655       for (int i = 0; i < _blossom_num; ++i) {
  1656         _delta2_index->set(i, _delta2->PRE_HEAP);
  1656         (*_delta2_index)[i] = _delta2->PRE_HEAP;
  1657         _delta4_index->set(i, _delta4->PRE_HEAP);
  1657         (*_delta4_index)[i] = _delta4->PRE_HEAP;
  1658       }
  1658       }
  1659 
  1659 
  1660       int index = 0;
  1660       int index = 0;
  1661       for (NodeIt n(_graph); n != INVALID; ++n) {
  1661       for (NodeIt n(_graph); n != INVALID; ++n) {
  1662         Value max = 0;
  1662         Value max = 0;
  1664           if (_graph.target(e) == n) continue;
  1664           if (_graph.target(e) == n) continue;
  1665           if ((dualScale * _weight[e]) / 2 > max) {
  1665           if ((dualScale * _weight[e]) / 2 > max) {
  1666             max = (dualScale * _weight[e]) / 2;
  1666             max = (dualScale * _weight[e]) / 2;
  1667           }
  1667           }
  1668         }
  1668         }
  1669         _node_index->set(n, index);
  1669         (*_node_index)[n] = index;
  1670         (*_node_data)[index].pot = max;
  1670         (*_node_data)[index].pot = max;
  1671         _delta1->push(n, max);
  1671         _delta1->push(n, max);
  1672         int blossom =
  1672         int blossom =
  1673           _blossom_set->insert(n, std::numeric_limits<Value>::max());
  1673           _blossom_set->insert(n, std::numeric_limits<Value>::max());
  1674 
  1674 
  2739     void extractBlossom(int blossom, const Node& base, const Arc& matching) {
  2739     void extractBlossom(int blossom, const Node& base, const Arc& matching) {
  2740       if (_blossom_set->trivial(blossom)) {
  2740       if (_blossom_set->trivial(blossom)) {
  2741         int bi = (*_node_index)[base];
  2741         int bi = (*_node_index)[base];
  2742         Value pot = (*_node_data)[bi].pot;
  2742         Value pot = (*_node_data)[bi].pot;
  2743 
  2743 
  2744         _matching->set(base, matching);
  2744         (*_matching)[base] = matching;
  2745         _blossom_node_list.push_back(base);
  2745         _blossom_node_list.push_back(base);
  2746         _node_potential->set(base, pot);
  2746         (*_node_potential)[base] = pot;
  2747       } else {
  2747       } else {
  2748 
  2748 
  2749         Value pot = (*_blossom_data)[blossom].pot;
  2749         Value pot = (*_blossom_data)[blossom].pot;
  2750         int bn = _blossom_node_list.size();
  2750         int bn = _blossom_node_list.size();
  2751 
  2751 
  2829     /// Initialize the algorithm
  2829     /// Initialize the algorithm
  2830     void init() {
  2830     void init() {
  2831       createStructures();
  2831       createStructures();
  2832 
  2832 
  2833       for (ArcIt e(_graph); e != INVALID; ++e) {
  2833       for (ArcIt e(_graph); e != INVALID; ++e) {
  2834         _node_heap_index->set(e, BinHeap<Value, IntArcMap>::PRE_HEAP);
  2834         (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
  2835       }
  2835       }
  2836       for (EdgeIt e(_graph); e != INVALID; ++e) {
  2836       for (EdgeIt e(_graph); e != INVALID; ++e) {
  2837         _delta3_index->set(e, _delta3->PRE_HEAP);
  2837         (*_delta3_index)[e] = _delta3->PRE_HEAP;
  2838       }
  2838       }
  2839       for (int i = 0; i < _blossom_num; ++i) {
  2839       for (int i = 0; i < _blossom_num; ++i) {
  2840         _delta2_index->set(i, _delta2->PRE_HEAP);
  2840         (*_delta2_index)[i] = _delta2->PRE_HEAP;
  2841         _delta4_index->set(i, _delta4->PRE_HEAP);
  2841         (*_delta4_index)[i] = _delta4->PRE_HEAP;
  2842       }
  2842       }
  2843 
  2843 
  2844       int index = 0;
  2844       int index = 0;
  2845       for (NodeIt n(_graph); n != INVALID; ++n) {
  2845       for (NodeIt n(_graph); n != INVALID; ++n) {
  2846         Value max = - std::numeric_limits<Value>::max();
  2846         Value max = - std::numeric_limits<Value>::max();
  2848           if (_graph.target(e) == n) continue;
  2848           if (_graph.target(e) == n) continue;
  2849           if ((dualScale * _weight[e]) / 2 > max) {
  2849           if ((dualScale * _weight[e]) / 2 > max) {
  2850             max = (dualScale * _weight[e]) / 2;
  2850             max = (dualScale * _weight[e]) / 2;
  2851           }
  2851           }
  2852         }
  2852         }
  2853         _node_index->set(n, index);
  2853         (*_node_index)[n] = index;
  2854         (*_node_data)[index].pot = max;
  2854         (*_node_data)[index].pot = max;
  2855         int blossom =
  2855         int blossom =
  2856           _blossom_set->insert(n, std::numeric_limits<Value>::max());
  2856           _blossom_set->insert(n, std::numeric_limits<Value>::max());
  2857 
  2857 
  2858         _tree_set->insert(blossom);
  2858         _tree_set->insert(blossom);