r868:0513ccfea967
Sun, 20 Sep 2009 21:38:24
[Not Reviewed]
0 comments (0 inline)
0
1
0
231
350
| ... | ... |
@@ -15,10 +15,10 @@ |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 |
#ifndef LEMON_MAX_MATCHING_H |
|
| 20 |
#define LEMON_MAX_MATCHING_H |
|
| 19 |
#ifndef LEMON_MATCHING_H |
|
| 20 |
#define LEMON_MATCHING_H |
|
| 21 | 21 |
|
| 22 | 22 |
#include <vector> |
| 23 | 23 |
#include <queue> |
| 24 | 24 |
#include <set> |
| ... | ... |
@@ -40,9 +40,9 @@ |
| 40 | 40 |
/// \brief Maximum cardinality matching in general graphs |
| 41 | 41 |
/// |
| 42 | 42 |
/// This class implements Edmonds' alternating forest matching algorithm |
| 43 | 43 |
/// for finding a maximum cardinality matching in a general undirected graph. |
| 44 |
/// It can be started from an arbitrary initial matching |
|
| 44 |
/// It can be started from an arbitrary initial matching |
|
| 45 | 45 |
/// (the default is the empty one). |
| 46 | 46 |
/// |
| 47 | 47 |
/// The dual solution of the problem is a map of the nodes to |
| 48 | 48 |
/// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D), |
| ... | ... |
@@ -68,13 +68,13 @@ |
| 68 | 68 |
MatchingMap; |
| 69 | 69 |
|
| 70 | 70 |
///\brief Status constants for Gallai-Edmonds decomposition. |
| 71 | 71 |
/// |
| 72 |
///These constants are used for indicating the Gallai-Edmonds |
|
| 72 |
///These constants are used for indicating the Gallai-Edmonds |
|
| 73 | 73 |
///decomposition of a graph. The nodes with status \c EVEN (or \c D) |
| 74 | 74 |
///induce a subgraph with factor-critical components, the nodes with |
| 75 | 75 |
///status \c ODD (or \c A) form the canonical barrier, and the nodes |
| 76 |
///with status \c MATCHED (or \c C) induce a subgraph having a |
|
| 76 |
///with status \c MATCHED (or \c C) induce a subgraph having a |
|
| 77 | 77 |
///perfect matching. |
| 78 | 78 |
enum Status {
|
| 79 | 79 |
EVEN = 1, ///< = 1. (\c D is an alias for \c EVEN.) |
| 80 | 80 |
D = 1, |
| ... | ... |
@@ -511,9 +511,9 @@ |
| 511 | 511 |
} |
| 512 | 512 |
} |
| 513 | 513 |
} |
| 514 | 514 |
|
| 515 |
/// \brief Start Edmonds' algorithm with a heuristic improvement |
|
| 515 |
/// \brief Start Edmonds' algorithm with a heuristic improvement |
|
| 516 | 516 |
/// for dense graphs |
| 517 | 517 |
/// |
| 518 | 518 |
/// This function runs Edmonds' algorithm with a heuristic of postponing |
| 519 | 519 |
/// shrinks, therefore resulting in a faster algorithm for dense graphs. |
| ... | ... |
@@ -533,10 +533,10 @@ |
| 533 | 533 |
|
| 534 | 534 |
|
| 535 | 535 |
/// \brief Run Edmonds' algorithm |
| 536 | 536 |
/// |
| 537 |
/// This function runs Edmonds' algorithm. An additional heuristic of |
|
| 538 |
/// postponing shrinks is used for relatively dense graphs |
|
| 537 |
/// This function runs Edmonds' algorithm. An additional heuristic of |
|
| 538 |
/// postponing shrinks is used for relatively dense graphs |
|
| 539 | 539 |
/// (for which <tt>m>=2*n</tt> holds). |
| 540 | 540 |
void run() {
|
| 541 | 541 |
if (countEdges(_graph) < 2 * countNodes(_graph)) {
|
| 542 | 542 |
greedyInit(); |
| ... | ... |
@@ -555,9 +555,9 @@ |
| 555 | 555 |
/// @{
|
| 556 | 556 |
|
| 557 | 557 |
/// \brief Return the size (cardinality) of the matching. |
| 558 | 558 |
/// |
| 559 |
/// This function returns the size (cardinality) of the current matching. |
|
| 559 |
/// This function returns the size (cardinality) of the current matching. |
|
| 560 | 560 |
/// After run() it returns the size of the maximum matching in the graph. |
| 561 | 561 |
int matchingSize() const {
|
| 562 | 562 |
int size = 0; |
| 563 | 563 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| ... | ... |
@@ -569,18 +569,18 @@ |
| 569 | 569 |
} |
| 570 | 570 |
|
| 571 | 571 |
/// \brief Return \c true if the given edge is in the matching. |
| 572 | 572 |
/// |
| 573 |
/// This function returns \c true if the given edge is in the current |
|
| 573 |
/// This function returns \c true if the given edge is in the current |
|
| 574 | 574 |
/// matching. |
| 575 | 575 |
bool matching(const Edge& edge) const {
|
| 576 | 576 |
return edge == (*_matching)[_graph.u(edge)]; |
| 577 | 577 |
} |
| 578 | 578 |
|
| 579 | 579 |
/// \brief Return the matching arc (or edge) incident to the given node. |
| 580 | 580 |
/// |
| 581 | 581 |
/// This function returns the matching arc (or edge) incident to the |
| 582 |
/// given node in the current matching or \c INVALID if the node is |
|
| 582 |
/// given node in the current matching or \c INVALID if the node is |
|
| 583 | 583 |
/// not covered by the matching. |
| 584 | 584 |
Arc matching(const Node& n) const {
|
| 585 | 585 |
return (*_matching)[n]; |
| 586 | 586 |
} |
| ... | ... |
@@ -594,9 +594,9 @@ |
| 594 | 594 |
} |
| 595 | 595 |
|
| 596 | 596 |
/// \brief Return the mate of the given node. |
| 597 | 597 |
/// |
| 598 |
/// This function returns the mate of the given node in the current |
|
| 598 |
/// This function returns the mate of the given node in the current |
|
| 599 | 599 |
/// matching or \c INVALID if the node is not covered by the matching. |
| 600 | 600 |
Node mate(const Node& n) const {
|
| 601 | 601 |
return (*_matching)[n] != INVALID ? |
| 602 | 602 |
_graph.target((*_matching)[n]) : INVALID; |
| ... | ... |
@@ -604,9 +604,9 @@ |
| 604 | 604 |
|
| 605 | 605 |
/// @} |
| 606 | 606 |
|
| 607 | 607 |
/// \name Dual Solution |
| 608 |
/// Functions to get the dual solution, i.e. the Gallai-Edmonds |
|
| 608 |
/// Functions to get the dual solution, i.e. the Gallai-Edmonds |
|
| 609 | 609 |
/// decomposition. |
| 610 | 610 |
|
| 611 | 611 |
/// @{
|
| 612 | 612 |
|
| ... | ... |
@@ -647,10 +647,10 @@ |
| 647 | 647 |
/// maximum weighted matching algorithm. The implementation is based |
| 648 | 648 |
/// on extensive use of priority queues and provides |
| 649 | 649 |
/// \f$O(nm\log n)\f$ time complexity. |
| 650 | 650 |
/// |
| 651 |
/// The maximum weighted matching problem is to find a subset of the |
|
| 652 |
/// edges in an undirected graph with maximum overall weight for which |
|
| 651 |
/// The maximum weighted matching problem is to find a subset of the |
|
| 652 |
/// edges in an undirected graph with maximum overall weight for which |
|
| 653 | 653 |
/// each node has at most one incident edge. |
| 654 | 654 |
/// It can be formulated with the following linear program. |
| 655 | 655 |
/// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f]
|
| 656 | 656 |
/** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
|
| ... | ... |
@@ -672,18 +672,18 @@ |
| 672 | 672 |
/// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f]
|
| 673 | 673 |
/** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
|
| 674 | 674 |
\frac{\vert B \vert - 1}{2}z_B\f] */
|
| 675 | 675 |
/// |
| 676 |
/// The algorithm can be executed with the run() function. |
|
| 676 |
/// The algorithm can be executed with the run() function. |
|
| 677 | 677 |
/// After it the matching (the primal solution) and the dual solution |
| 678 |
/// can be obtained using the query functions and the |
|
| 679 |
/// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, |
|
| 680 |
/// |
|
| 678 |
/// can be obtained using the query functions and the |
|
| 679 |
/// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, |
|
| 680 |
/// which is able to iterate on the nodes of a blossom. |
|
| 681 | 681 |
/// If the value type is integer, then the dual solution is multiplied |
| 682 | 682 |
/// by \ref MaxWeightedMatching::dualScale "4". |
| 683 | 683 |
/// |
| 684 | 684 |
/// \tparam GR The undirected graph type the algorithm runs on. |
| 685 |
/// \tparam WM The type edge weight map. The default type is |
|
| 685 |
/// \tparam WM The type edge weight map. The default type is |
|
| 686 | 686 |
/// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
| 687 | 687 |
#ifdef DOXYGEN |
| 688 | 688 |
template <typename GR, typename WM> |
| 689 | 689 |
#else |
| ... | ... |
@@ -744,9 +744,9 @@ |
| 744 | 744 |
|
| 745 | 745 |
typedef RangeMap<int> IntIntMap; |
| 746 | 746 |
|
| 747 | 747 |
enum Status {
|
| 748 |
EVEN = -1, MATCHED = 0, ODD = 1 |
|
| 748 |
EVEN = -1, MATCHED = 0, ODD = 1 |
|
| 749 | 749 |
}; |
| 750 | 750 |
|
| 751 | 751 |
typedef HeapUnionFind<Value, IntNodeMap> BlossomSet; |
| 752 | 752 |
struct BlossomData {
|
| ... | ... |
@@ -843,11 +843,8 @@ |
| 843 | 843 |
} |
| 844 | 844 |
} |
| 845 | 845 |
|
| 846 | 846 |
void destroyStructures() {
|
| 847 |
_node_num = countNodes(_graph); |
|
| 848 |
_blossom_num = _node_num * 3 / 2; |
|
| 849 |
|
|
| 850 | 847 |
if (_matching) {
|
| 851 | 848 |
delete _matching; |
| 852 | 849 |
} |
| 853 | 850 |
if (_node_potential) {
|
| ... | ... |
@@ -921,12 +918,8 @@ |
| 921 | 918 |
if ((*_blossom_data)[vb].status == EVEN) {
|
| 922 | 919 |
if (_delta3->state(e) != _delta3->IN_HEAP && blossom != vb) {
|
| 923 | 920 |
_delta3->push(e, rw / 2); |
| 924 | 921 |
} |
| 925 |
} else if ((*_blossom_data)[vb].status == UNMATCHED) {
|
|
| 926 |
if (_delta3->state(e) != _delta3->IN_HEAP) {
|
|
| 927 |
_delta3->push(e, rw); |
|
| 928 |
} |
|
| 929 | 922 |
} else {
|
| 930 | 923 |
typename std::map<int, Arc>::iterator it = |
| 931 | 924 |
(*_node_data)[vi].heap_index.find(tree); |
| 932 | 925 |
|
| ... | ... |
@@ -948,204 +941,8 @@ |
| 948 | 941 |
if (_delta2->state(vb) != _delta2->IN_HEAP) {
|
| 949 | 942 |
_delta2->push(vb, _blossom_set->classPrio(vb) - |
| 950 | 943 |
(*_blossom_data)[vb].offset); |
| 951 | 944 |
} else if ((*_delta2)[vb] > _blossom_set->classPrio(vb) - |
| 952 |
(*_blossom_data)[vb].offset){
|
|
| 953 |
_delta2->decrease(vb, _blossom_set->classPrio(vb) - |
|
| 954 |
(*_blossom_data)[vb].offset); |
|
| 955 |
} |
|
| 956 |
} |
|
| 957 |
} |
|
| 958 |
} |
|
| 959 |
} |
|
| 960 |
} |
|
| 961 |
(*_blossom_data)[blossom].offset = 0; |
|
| 962 |
} |
|
| 963 |
|
|
| 964 |
void matchedToOdd(int blossom) {
|
|
| 965 |
if (_delta2->state(blossom) == _delta2->IN_HEAP) {
|
|
| 966 |
_delta2->erase(blossom); |
|
| 967 |
} |
|
| 968 |
(*_blossom_data)[blossom].offset += _delta_sum; |
|
| 969 |
if (!_blossom_set->trivial(blossom)) {
|
|
| 970 |
_delta4->push(blossom, (*_blossom_data)[blossom].pot / 2 + |
|
| 971 |
(*_blossom_data)[blossom].offset); |
|
| 972 |
} |
|
| 973 |
} |
|
| 974 |
|
|
| 975 |
void evenToMatched(int blossom, int tree) {
|
|
| 976 |
if (!_blossom_set->trivial(blossom)) {
|
|
| 977 |
(*_blossom_data)[blossom].pot += 2 * _delta_sum; |
|
| 978 |
} |
|
| 979 |
|
|
| 980 |
for (typename BlossomSet::ItemIt n(*_blossom_set, blossom); |
|
| 981 |
n != INVALID; ++n) {
|
|
| 982 |
int ni = (*_node_index)[n]; |
|
| 983 |
(*_node_data)[ni].pot -= _delta_sum; |
|
| 984 |
|
|
| 985 |
_delta1->erase(n); |
|
| 986 |
|
|
| 987 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
|
| 988 |
Node v = _graph.source(e); |
|
| 989 |
int vb = _blossom_set->find(v); |
|
| 990 |
int vi = (*_node_index)[v]; |
|
| 991 |
|
|
| 992 |
Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot - |
|
| 993 |
dualScale * _weight[e]; |
|
| 994 |
|
|
| 995 |
if (vb == blossom) {
|
|
| 996 |
if (_delta3->state(e) == _delta3->IN_HEAP) {
|
|
| 997 |
_delta3->erase(e); |
|
| 998 |
} |
|
| 999 |
} else if ((*_blossom_data)[vb].status == EVEN) {
|
|
| 1000 |
|
|
| 1001 |
if (_delta3->state(e) == _delta3->IN_HEAP) {
|
|
| 1002 |
_delta3->erase(e); |
|
| 1003 |
} |
|
| 1004 |
|
|
| 1005 |
int vt = _tree_set->find(vb); |
|
| 1006 |
|
|
| 1007 |
if (vt != tree) {
|
|
| 1008 |
|
|
| 1009 |
Arc r = _graph.oppositeArc(e); |
|
| 1010 |
|
|
| 1011 |
typename std::map<int, Arc>::iterator it = |
|
| 1012 |
(*_node_data)[ni].heap_index.find(vt); |
|
| 1013 |
|
|
| 1014 |
if (it != (*_node_data)[ni].heap_index.end()) {
|
|
| 1015 |
if ((*_node_data)[ni].heap[it->second] > rw) {
|
|
| 1016 |
(*_node_data)[ni].heap.replace(it->second, r); |
|
| 1017 |
(*_node_data)[ni].heap.decrease(r, rw); |
|
| 1018 |
it->second = r; |
|
| 1019 |
} |
|
| 1020 |
} else {
|
|
| 1021 |
(*_node_data)[ni].heap.push(r, rw); |
|
| 1022 |
(*_node_data)[ni].heap_index.insert(std::make_pair(vt, r)); |
|
| 1023 |
} |
|
| 1024 |
|
|
| 1025 |
if ((*_blossom_set)[n] > (*_node_data)[ni].heap.prio()) {
|
|
| 1026 |
_blossom_set->decrease(n, (*_node_data)[ni].heap.prio()); |
|
| 1027 |
|
|
| 1028 |
if (_delta2->state(blossom) != _delta2->IN_HEAP) {
|
|
| 1029 |
_delta2->push(blossom, _blossom_set->classPrio(blossom) - |
|
| 1030 |
(*_blossom_data)[blossom].offset); |
|
| 1031 |
} else if ((*_delta2)[blossom] > |
|
| 1032 |
_blossom_set->classPrio(blossom) - |
|
| 1033 |
(*_blossom_data)[blossom].offset){
|
|
| 1034 |
_delta2->decrease(blossom, _blossom_set->classPrio(blossom) - |
|
| 1035 |
(*_blossom_data)[blossom].offset); |
|
| 1036 |
} |
|
| 1037 |
} |
|
| 1038 |
} |
|
| 1039 |
|
|
| 1040 |
} else if ((*_blossom_data)[vb].status == UNMATCHED) {
|
|
| 1041 |
if (_delta3->state(e) == _delta3->IN_HEAP) {
|
|
| 1042 |
_delta3->erase(e); |
|
| 1043 |
} |
|
| 1044 |
} else {
|
|
| 1045 |
|
|
| 1046 |
typename std::map<int, Arc>::iterator it = |
|
| 1047 |
(*_node_data)[vi].heap_index.find(tree); |
|
| 1048 |
|
|
| 1049 |
if (it != (*_node_data)[vi].heap_index.end()) {
|
|
| 1050 |
(*_node_data)[vi].heap.erase(it->second); |
|
| 1051 |
(*_node_data)[vi].heap_index.erase(it); |
|
| 1052 |
if ((*_node_data)[vi].heap.empty()) {
|
|
| 1053 |
_blossom_set->increase(v, std::numeric_limits<Value>::max()); |
|
| 1054 |
} else if ((*_blossom_set)[v] < (*_node_data)[vi].heap.prio()) {
|
|
| 1055 |
_blossom_set->increase(v, (*_node_data)[vi].heap.prio()); |
|
| 1056 |
} |
|
| 1057 |
|
|
| 1058 |
if ((*_blossom_data)[vb].status == MATCHED) {
|
|
| 1059 |
if (_blossom_set->classPrio(vb) == |
|
| 1060 |
std::numeric_limits<Value>::max()) {
|
|
| 1061 |
_delta2->erase(vb); |
|
| 1062 |
} else if ((*_delta2)[vb] < _blossom_set->classPrio(vb) - |
|
| 1063 |
(*_blossom_data)[vb].offset) {
|
|
| 1064 |
_delta2->increase(vb, _blossom_set->classPrio(vb) - |
|
| 1065 |
(*_blossom_data)[vb].offset); |
|
| 1066 |
} |
|
| 1067 |
} |
|
| 1068 |
} |
|
| 1069 |
} |
|
| 1070 |
} |
|
| 1071 |
} |
|
| 1072 |
} |
|
| 1073 |
|
|
| 1074 |
void oddToMatched(int blossom) {
|
|
| 1075 |
(*_blossom_data)[blossom].offset -= _delta_sum; |
|
| 1076 |
|
|
| 1077 |
if (_blossom_set->classPrio(blossom) != |
|
| 1078 |
std::numeric_limits<Value>::max()) {
|
|
| 1079 |
_delta2->push(blossom, _blossom_set->classPrio(blossom) - |
|
| 1080 |
(*_blossom_data)[blossom].offset); |
|
| 1081 |
} |
|
| 1082 |
|
|
| 1083 |
if (!_blossom_set->trivial(blossom)) {
|
|
| 1084 |
_delta4->erase(blossom); |
|
| 1085 |
} |
|
| 1086 |
} |
|
| 1087 |
|
|
| 1088 |
void oddToEven(int blossom, int tree) {
|
|
| 1089 |
if (!_blossom_set->trivial(blossom)) {
|
|
| 1090 |
_delta4->erase(blossom); |
|
| 1091 |
(*_blossom_data)[blossom].pot -= |
|
| 1092 |
2 * (2 * _delta_sum - (*_blossom_data)[blossom].offset); |
|
| 1093 |
} |
|
| 1094 |
|
|
| 1095 |
for (typename BlossomSet::ItemIt n(*_blossom_set, blossom); |
|
| 1096 |
n != INVALID; ++n) {
|
|
| 1097 |
int ni = (*_node_index)[n]; |
|
| 1098 |
|
|
| 1099 |
_blossom_set->increase(n, std::numeric_limits<Value>::max()); |
|
| 1100 |
|
|
| 1101 |
(*_node_data)[ni].heap.clear(); |
|
| 1102 |
(*_node_data)[ni].heap_index.clear(); |
|
| 1103 |
(*_node_data)[ni].pot += |
|
| 1104 |
2 * _delta_sum - (*_blossom_data)[blossom].offset; |
|
| 1105 |
|
|
| 1106 |
_delta1->push(n, (*_node_data)[ni].pot); |
|
| 1107 |
|
|
| 1108 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
|
| 1109 |
Node v = _graph.source(e); |
|
| 1110 |
int vb = _blossom_set->find(v); |
|
| 1111 |
int vi = (*_node_index)[v]; |
|
| 1112 |
|
|
| 1113 |
Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot - |
|
| 1114 |
dualScale * _weight[e]; |
|
| 1115 |
|
|
| 1116 |
if ((*_blossom_data)[vb].status == EVEN) {
|
|
| 1117 |
if (_delta3->state(e) != _delta3->IN_HEAP && blossom != vb) {
|
|
| 1118 |
_delta3->push(e, rw / 2); |
|
| 1119 |
} |
|
| 1120 |
} else if ((*_blossom_data)[vb].status == UNMATCHED) {
|
|
| 1121 |
if (_delta3->state(e) != _delta3->IN_HEAP) {
|
|
| 1122 |
_delta3->push(e, rw); |
|
| 1123 |
} |
|
| 1124 |
} else {
|
|
| 1125 |
|
|
| 1126 |
typename std::map<int, Arc>::iterator it = |
|
| 1127 |
(*_node_data)[vi].heap_index.find(tree); |
|
| 1128 |
|
|
| 1129 |
if (it != (*_node_data)[vi].heap_index.end()) {
|
|
| 1130 |
if ((*_node_data)[vi].heap[it->second] > rw) {
|
|
| 1131 |
(*_node_data)[vi].heap.replace(it->second, e); |
|
| 1132 |
(*_node_data)[vi].heap.decrease(e, rw); |
|
| 1133 |
it->second = e; |
|
| 1134 |
} |
|
| 1135 |
} else {
|
|
| 1136 |
(*_node_data)[vi].heap.push(e, rw); |
|
| 1137 |
(*_node_data)[vi].heap_index.insert(std::make_pair(tree, e)); |
|
| 1138 |
} |
|
| 1139 |
|
|
| 1140 |
if ((*_blossom_set)[v] > (*_node_data)[vi].heap.prio()) {
|
|
| 1141 |
_blossom_set->decrease(v, (*_node_data)[vi].heap.prio()); |
|
| 1142 |
|
|
| 1143 |
if ((*_blossom_data)[vb].status == MATCHED) {
|
|
| 1144 |
if (_delta2->state(vb) != _delta2->IN_HEAP) {
|
|
| 1145 |
_delta2->push(vb, _blossom_set->classPrio(vb) - |
|
| 1146 |
(*_blossom_data)[vb].offset); |
|
| 1147 |
} else if ((*_delta2)[vb] > _blossom_set->classPrio(vb) - |
|
| 1148 | 945 |
(*_blossom_data)[vb].offset) {
|
| 1149 | 946 |
_delta2->decrease(vb, _blossom_set->classPrio(vb) - |
| 1150 | 947 |
(*_blossom_data)[vb].offset); |
| 1151 | 948 |
} |
| ... | ... |
@@ -1156,101 +953,193 @@ |
| 1156 | 953 |
} |
| 1157 | 954 |
(*_blossom_data)[blossom].offset = 0; |
| 1158 | 955 |
} |
| 1159 | 956 |
|
| 1160 |
|
|
| 1161 |
void matchedToUnmatched(int blossom) {
|
|
| 957 |
void matchedToOdd(int blossom) {
|
|
| 1162 | 958 |
if (_delta2->state(blossom) == _delta2->IN_HEAP) {
|
| 1163 | 959 |
_delta2->erase(blossom); |
| 1164 | 960 |
} |
| 961 |
(*_blossom_data)[blossom].offset += _delta_sum; |
|
| 962 |
if (!_blossom_set->trivial(blossom)) {
|
|
| 963 |
_delta4->push(blossom, (*_blossom_data)[blossom].pot / 2 + |
|
| 964 |
(*_blossom_data)[blossom].offset); |
|
| 965 |
} |
|
| 966 |
} |
|
| 967 |
|
|
| 968 |
void evenToMatched(int blossom, int tree) {
|
|
| 969 |
if (!_blossom_set->trivial(blossom)) {
|
|
| 970 |
(*_blossom_data)[blossom].pot += 2 * _delta_sum; |
|
| 971 |
} |
|
| 1165 | 972 |
|
| 1166 | 973 |
for (typename BlossomSet::ItemIt n(*_blossom_set, blossom); |
| 1167 | 974 |
n != INVALID; ++n) {
|
| 1168 | 975 |
int ni = (*_node_index)[n]; |
| 1169 |
|
|
| 1170 |
_blossom_set->increase(n, std::numeric_limits<Value>::max()); |
|
| 1171 |
|
|
| 1172 |
(*_node_data)[ni].heap.clear(); |
|
| 1173 |
(*_node_data)[ni].heap_index.clear(); |
|
| 1174 |
|
|
| 1175 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
|
| 1176 |
Node v = _graph.target(e); |
|
| 976 |
(*_node_data)[ni].pot -= _delta_sum; |
|
| 977 |
|
|
| 978 |
_delta1->erase(n); |
|
| 979 |
|
|
| 980 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
|
| 981 |
Node v = _graph.source(e); |
|
| 1177 | 982 |
int vb = _blossom_set->find(v); |
| 1178 | 983 |
int vi = (*_node_index)[v]; |
| 1179 | 984 |
|
| 1180 | 985 |
Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot - |
| 1181 | 986 |
dualScale * _weight[e]; |
| 1182 | 987 |
|
| 1183 |
if ((*_blossom_data)[vb].status == EVEN) {
|
|
| 1184 |
if (_delta3->state(e) != _delta3->IN_HEAP) {
|
|
| 1185 |
|
|
| 988 |
if (vb == blossom) {
|
|
| 989 |
if (_delta3->state(e) == _delta3->IN_HEAP) {
|
|
| 990 |
_delta3->erase(e); |
|
| 991 |
} |
|
| 992 |
} else if ((*_blossom_data)[vb].status == EVEN) {
|
|
| 993 |
|
|
| 994 |
if (_delta3->state(e) == _delta3->IN_HEAP) {
|
|
| 995 |
_delta3->erase(e); |
|
| 996 |
} |
|
| 997 |
|
|
| 998 |
int vt = _tree_set->find(vb); |
|
| 999 |
|
|
| 1000 |
if (vt != tree) {
|
|
| 1001 |
|
|
| 1002 |
Arc r = _graph.oppositeArc(e); |
|
| 1003 |
|
|
| 1004 |
typename std::map<int, Arc>::iterator it = |
|
| 1005 |
(*_node_data)[ni].heap_index.find(vt); |
|
| 1006 |
|
|
| 1007 |
if (it != (*_node_data)[ni].heap_index.end()) {
|
|
| 1008 |
if ((*_node_data)[ni].heap[it->second] > rw) {
|
|
| 1009 |
(*_node_data)[ni].heap.replace(it->second, r); |
|
| 1010 |
(*_node_data)[ni].heap.decrease(r, rw); |
|
| 1011 |
it->second = r; |
|
| 1012 |
} |
|
| 1013 |
} else {
|
|
| 1014 |
(*_node_data)[ni].heap.push(r, rw); |
|
| 1015 |
(*_node_data)[ni].heap_index.insert(std::make_pair(vt, r)); |
|
| 1016 |
} |
|
| 1017 |
|
|
| 1018 |
if ((*_blossom_set)[n] > (*_node_data)[ni].heap.prio()) {
|
|
| 1019 |
_blossom_set->decrease(n, (*_node_data)[ni].heap.prio()); |
|
| 1020 |
|
|
| 1021 |
if (_delta2->state(blossom) != _delta2->IN_HEAP) {
|
|
| 1022 |
_delta2->push(blossom, _blossom_set->classPrio(blossom) - |
|
| 1023 |
(*_blossom_data)[blossom].offset); |
|
| 1024 |
} else if ((*_delta2)[blossom] > |
|
| 1025 |
_blossom_set->classPrio(blossom) - |
|
| 1026 |
(*_blossom_data)[blossom].offset){
|
|
| 1027 |
_delta2->decrease(blossom, _blossom_set->classPrio(blossom) - |
|
| 1028 |
(*_blossom_data)[blossom].offset); |
|
| 1029 |
} |
|
| 1030 |
} |
|
| 1031 |
} |
|
| 1032 |
} else {
|
|
| 1033 |
|
|
| 1034 |
typename std::map<int, Arc>::iterator it = |
|
| 1035 |
(*_node_data)[vi].heap_index.find(tree); |
|
| 1036 |
|
|
| 1037 |
if (it != (*_node_data)[vi].heap_index.end()) {
|
|
| 1038 |
(*_node_data)[vi].heap.erase(it->second); |
|
| 1039 |
(*_node_data)[vi].heap_index.erase(it); |
|
| 1040 |
if ((*_node_data)[vi].heap.empty()) {
|
|
| 1041 |
_blossom_set->increase(v, std::numeric_limits<Value>::max()); |
|
| 1042 |
} else if ((*_blossom_set)[v] < (*_node_data)[vi].heap.prio()) {
|
|
| 1043 |
_blossom_set->increase(v, (*_node_data)[vi].heap.prio()); |
|
| 1044 |
} |
|
| 1045 |
|
|
| 1046 |
if ((*_blossom_data)[vb].status == MATCHED) {
|
|
| 1047 |
if (_blossom_set->classPrio(vb) == |
|
| 1048 |
std::numeric_limits<Value>::max()) {
|
|
| 1049 |
_delta2->erase(vb); |
|
| 1050 |
} else if ((*_delta2)[vb] < _blossom_set->classPrio(vb) - |
|
| 1051 |
(*_blossom_data)[vb].offset) {
|
|
| 1052 |
_delta2->increase(vb, _blossom_set->classPrio(vb) - |
|
| 1053 |
(*_blossom_data)[vb].offset); |
|
| 1054 |
} |
|
| 1055 |
} |
|
| 1186 | 1056 |
} |
| 1187 | 1057 |
} |
| 1188 | 1058 |
} |
| 1189 | 1059 |
} |
| 1190 | 1060 |
} |
| 1191 | 1061 |
|
| 1192 |
void |
|
| 1062 |
void oddToMatched(int blossom) {
|
|
| 1063 |
(*_blossom_data)[blossom].offset -= _delta_sum; |
|
| 1064 |
|
|
| 1065 |
if (_blossom_set->classPrio(blossom) != |
|
| 1066 |
std::numeric_limits<Value>::max()) {
|
|
| 1067 |
_delta2->push(blossom, _blossom_set->classPrio(blossom) - |
|
| 1068 |
(*_blossom_data)[blossom].offset); |
|
| 1069 |
} |
|
| 1070 |
|
|
| 1071 |
if (!_blossom_set->trivial(blossom)) {
|
|
| 1072 |
_delta4->erase(blossom); |
|
| 1073 |
} |
|
| 1074 |
} |
|
| 1075 |
|
|
| 1076 |
void oddToEven(int blossom, int tree) {
|
|
| 1077 |
if (!_blossom_set->trivial(blossom)) {
|
|
| 1078 |
_delta4->erase(blossom); |
|
| 1079 |
(*_blossom_data)[blossom].pot -= |
|
| 1080 |
2 * (2 * _delta_sum - (*_blossom_data)[blossom].offset); |
|
| 1081 |
} |
|
| 1082 |
|
|
| 1193 | 1083 |
for (typename BlossomSet::ItemIt n(*_blossom_set, blossom); |
| 1194 | 1084 |
n != INVALID; ++n) {
|
| 1195 | 1085 |
int ni = (*_node_index)[n]; |
| 1196 | 1086 |
|
| 1087 |
_blossom_set->increase(n, std::numeric_limits<Value>::max()); |
|
| 1088 |
|
|
| 1089 |
(*_node_data)[ni].heap.clear(); |
|
| 1090 |
(*_node_data)[ni].heap_index.clear(); |
|
| 1091 |
(*_node_data)[ni].pot += |
|
| 1092 |
2 * _delta_sum - (*_blossom_data)[blossom].offset; |
|
| 1093 |
|
|
| 1094 |
_delta1->push(n, (*_node_data)[ni].pot); |
|
| 1095 |
|
|
| 1197 | 1096 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
| 1198 | 1097 |
Node v = _graph.source(e); |
| 1199 | 1098 |
int vb = _blossom_set->find(v); |
| 1200 | 1099 |
int vi = (*_node_index)[v]; |
| 1201 | 1100 |
|
| 1202 | 1101 |
Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot - |
| 1203 | 1102 |
dualScale * _weight[e]; |
| 1204 | 1103 |
|
| 1205 |
if (vb == blossom) {
|
|
| 1206 |
if (_delta3->state(e) == _delta3->IN_HEAP) {
|
|
| 1207 |
|
|
| 1104 |
if ((*_blossom_data)[vb].status == EVEN) {
|
|
| 1105 |
if (_delta3->state(e) != _delta3->IN_HEAP && blossom != vb) {
|
|
| 1106 |
_delta3->push(e, rw / 2); |
|
| 1208 | 1107 |
} |
| 1209 |
} else if ((*_blossom_data)[vb].status == EVEN) {
|
|
| 1210 |
|
|
| 1211 |
if (_delta3->state(e) == _delta3->IN_HEAP) {
|
|
| 1212 |
_delta3->erase(e); |
|
| 1213 |
} |
|
| 1214 |
|
|
| 1215 |
int vt = _tree_set->find(vb); |
|
| 1216 |
|
|
| 1217 |
|
|
| 1108 |
} else {
|
|
| 1218 | 1109 |
|
| 1219 | 1110 |
typename std::map<int, Arc>::iterator it = |
| 1220 |
(*_node_data)[ni].heap_index.find(vt); |
|
| 1221 |
|
|
| 1222 |
if (it != (*_node_data)[ni].heap_index.end()) {
|
|
| 1223 |
if ((*_node_data)[ni].heap[it->second] > rw) {
|
|
| 1224 |
(*_node_data)[ni].heap.replace(it->second, r); |
|
| 1225 |
(*_node_data)[ni].heap.decrease(r, rw); |
|
| 1226 |
|
|
| 1111 |
(*_node_data)[vi].heap_index.find(tree); |
|
| 1112 |
|
|
| 1113 |
if (it != (*_node_data)[vi].heap_index.end()) {
|
|
| 1114 |
if ((*_node_data)[vi].heap[it->second] > rw) {
|
|
| 1115 |
(*_node_data)[vi].heap.replace(it->second, e); |
|
| 1116 |
(*_node_data)[vi].heap.decrease(e, rw); |
|
| 1117 |
it->second = e; |
|
| 1227 | 1118 |
} |
| 1228 | 1119 |
} else {
|
| 1229 |
(*_node_data)[ni].heap.push(r, rw); |
|
| 1230 |
(*_node_data)[ni].heap_index.insert(std::make_pair(vt, r)); |
|
| 1120 |
(*_node_data)[vi].heap.push(e, rw); |
|
| 1121 |
(*_node_data)[vi].heap_index.insert(std::make_pair(tree, e)); |
|
| 1231 | 1122 |
} |
| 1232 | 1123 |
|
| 1233 |
if ((*_blossom_set)[n] > (*_node_data)[ni].heap.prio()) {
|
|
| 1234 |
_blossom_set->decrease(n, (*_node_data)[ni].heap.prio()); |
|
| 1235 |
|
|
| 1236 |
if (_delta2->state(blossom) != _delta2->IN_HEAP) {
|
|
| 1237 |
_delta2->push(blossom, _blossom_set->classPrio(blossom) - |
|
| 1238 |
(*_blossom_data)[blossom].offset); |
|
| 1239 |
} else if ((*_delta2)[blossom] > _blossom_set->classPrio(blossom)- |
|
| 1240 |
(*_blossom_data)[blossom].offset){
|
|
| 1241 |
_delta2->decrease(blossom, _blossom_set->classPrio(blossom) - |
|
| 1242 |
(*_blossom_data)[blossom].offset); |
|
| 1124 |
if ((*_blossom_set)[v] > (*_node_data)[vi].heap.prio()) {
|
|
| 1125 |
_blossom_set->decrease(v, (*_node_data)[vi].heap.prio()); |
|
| 1126 |
|
|
| 1127 |
if ((*_blossom_data)[vb].status == MATCHED) {
|
|
| 1128 |
if (_delta2->state(vb) != _delta2->IN_HEAP) {
|
|
| 1129 |
_delta2->push(vb, _blossom_set->classPrio(vb) - |
|
| 1130 |
(*_blossom_data)[vb].offset); |
|
| 1131 |
} else if ((*_delta2)[vb] > _blossom_set->classPrio(vb) - |
|
| 1132 |
(*_blossom_data)[vb].offset) {
|
|
| 1133 |
_delta2->decrease(vb, _blossom_set->classPrio(vb) - |
|
| 1134 |
(*_blossom_data)[vb].offset); |
|
| 1135 |
} |
|
| 1243 | 1136 |
} |
| 1244 | 1137 |
} |
| 1245 |
|
|
| 1246 |
} else if ((*_blossom_data)[vb].status == UNMATCHED) {
|
|
| 1247 |
if (_delta3->state(e) == _delta3->IN_HEAP) {
|
|
| 1248 |
_delta3->erase(e); |
|
| 1249 |
} |
|
| 1250 | 1138 |
} |
| 1251 | 1139 |
} |
| 1252 | 1140 |
} |
| 1141 |
(*_blossom_data)[blossom].offset = 0; |
|
| 1253 | 1142 |
} |
| 1254 | 1143 |
|
| 1255 | 1144 |
void alternatePath(int even, int tree) {
|
| 1256 | 1145 |
int odd; |
| ... | ... |
@@ -1293,41 +1182,44 @@ |
| 1293 | 1182 |
|
| 1294 | 1183 |
alternatePath(blossom, tree); |
| 1295 | 1184 |
destroyTree(tree); |
| 1296 | 1185 |
|
| 1297 |
(*_blossom_data)[blossom].status = UNMATCHED; |
|
| 1298 | 1186 |
(*_blossom_data)[blossom].base = node; |
| 1299 |
|
|
| 1187 |
(*_blossom_data)[blossom].next = INVALID; |
|
| 1300 | 1188 |
} |
| 1301 | 1189 |
|
| 1302 |
|
|
| 1303 | 1190 |
void augmentOnEdge(const Edge& edge) {
|
| 1304 | 1191 |
|
| 1305 | 1192 |
int left = _blossom_set->find(_graph.u(edge)); |
| 1306 | 1193 |
int right = _blossom_set->find(_graph.v(edge)); |
| 1307 | 1194 |
|
| 1308 |
if ((*_blossom_data)[left].status == EVEN) {
|
|
| 1309 |
int left_tree = _tree_set->find(left); |
|
| 1310 |
alternatePath(left, left_tree); |
|
| 1311 |
destroyTree(left_tree); |
|
| 1312 |
} else {
|
|
| 1313 |
(*_blossom_data)[left].status = MATCHED; |
|
| 1314 |
unmatchedToMatched(left); |
|
| 1315 |
} |
|
| 1316 |
|
|
| 1317 |
if ((*_blossom_data)[right].status == EVEN) {
|
|
| 1318 |
int right_tree = _tree_set->find(right); |
|
| 1319 |
alternatePath(right, right_tree); |
|
| 1320 |
destroyTree(right_tree); |
|
| 1321 |
} else {
|
|
| 1322 |
(*_blossom_data)[right].status = MATCHED; |
|
| 1323 |
unmatchedToMatched(right); |
|
| 1324 |
|
|
| 1195 |
int left_tree = _tree_set->find(left); |
|
| 1196 |
alternatePath(left, left_tree); |
|
| 1197 |
destroyTree(left_tree); |
|
| 1198 |
|
|
| 1199 |
int right_tree = _tree_set->find(right); |
|
| 1200 |
alternatePath(right, right_tree); |
|
| 1201 |
destroyTree(right_tree); |
|
| 1325 | 1202 |
|
| 1326 | 1203 |
(*_blossom_data)[left].next = _graph.direct(edge, true); |
| 1327 | 1204 |
(*_blossom_data)[right].next = _graph.direct(edge, false); |
| 1328 | 1205 |
} |
| 1329 | 1206 |
|
| 1207 |
void augmentOnArc(const Arc& arc) {
|
|
| 1208 |
|
|
| 1209 |
int left = _blossom_set->find(_graph.source(arc)); |
|
| 1210 |
int right = _blossom_set->find(_graph.target(arc)); |
|
| 1211 |
|
|
| 1212 |
(*_blossom_data)[left].status = MATCHED; |
|
| 1213 |
|
|
| 1214 |
int right_tree = _tree_set->find(right); |
|
| 1215 |
alternatePath(right, right_tree); |
|
| 1216 |
destroyTree(right_tree); |
|
| 1217 |
|
|
| 1218 |
(*_blossom_data)[left].next = arc; |
|
| 1219 |
(*_blossom_data)[right].next = _graph.oppositeArc(arc); |
|
| 1220 |
} |
|
| 1221 |
|
|
| 1330 | 1222 |
void extendOnArc(const Arc& arc) {
|
| 1331 | 1223 |
int base = _blossom_set->find(_graph.target(arc)); |
| 1332 | 1224 |
int tree = _tree_set->find(base); |
| 1333 | 1225 |
|
| ... | ... |
@@ -1528,9 +1420,9 @@ |
| 1528 | 1420 |
matchedToOdd(sb); |
| 1529 | 1421 |
_tree_set->insert(sb, tree); |
| 1530 | 1422 |
(*_blossom_data)[sb].pred = pred; |
| 1531 | 1423 |
(*_blossom_data)[sb].next = |
| 1532 |
|
|
| 1424 |
_graph.oppositeArc((*_blossom_data)[tb].next); |
|
| 1533 | 1425 |
|
| 1534 | 1426 |
pred = (*_blossom_data)[ub].next; |
| 1535 | 1427 |
|
| 1536 | 1428 |
(*_blossom_data)[tb].status = EVEN; |
| ... | ... |
@@ -1628,9 +1520,9 @@ |
| 1628 | 1520 |
blossoms.push_back(c); |
| 1629 | 1521 |
} |
| 1630 | 1522 |
|
| 1631 | 1523 |
for (int i = 0; i < int(blossoms.size()); ++i) {
|
| 1632 |
if ((*_blossom_data)[blossoms[i]]. |
|
| 1524 |
if ((*_blossom_data)[blossoms[i]].next != INVALID) {
|
|
| 1633 | 1525 |
|
| 1634 | 1526 |
Value offset = (*_blossom_data)[blossoms[i]].offset; |
| 1635 | 1527 |
(*_blossom_data)[blossoms[i]].pot += 2 * offset; |
| 1636 | 1528 |
for (typename BlossomSet::ItemIt n(*_blossom_set, blossoms[i]); |
| ... | ... |
@@ -1756,14 +1648,13 @@ |
| 1756 | 1648 |
|
| 1757 | 1649 |
Value d4 = !_delta4->empty() ? |
| 1758 | 1650 |
_delta4->prio() : std::numeric_limits<Value>::max(); |
| 1759 | 1651 |
|
| 1760 |
_delta_sum = |
|
| 1652 |
_delta_sum = d3; OpType ot = D3; |
|
| 1653 |
if (d1 < _delta_sum) { _delta_sum = d1; ot = D1; }
|
|
| 1761 | 1654 |
if (d2 < _delta_sum) { _delta_sum = d2; ot = D2; }
|
| 1762 |
if (d3 < _delta_sum) { _delta_sum = d3; ot = D3; }
|
|
| 1763 | 1655 |
if (d4 < _delta_sum) { _delta_sum = d4; ot = D4; }
|
| 1764 | 1656 |
|
| 1765 |
|
|
| 1766 | 1657 |
switch (ot) {
|
| 1767 | 1658 |
case D1: |
| 1768 | 1659 |
{
|
| 1769 | 1660 |
Node n = _delta1->top(); |
| ... | ... |
@@ -1774,10 +1665,15 @@ |
| 1774 | 1665 |
case D2: |
| 1775 | 1666 |
{
|
| 1776 | 1667 |
int blossom = _delta2->top(); |
| 1777 | 1668 |
Node n = _blossom_set->classTop(blossom); |
| 1778 |
Arc e = (*_node_data)[(*_node_index)[n]].heap.top(); |
|
| 1779 |
extendOnArc(e); |
|
| 1669 |
Arc a = (*_node_data)[(*_node_index)[n]].heap.top(); |
|
| 1670 |
if ((*_blossom_data)[blossom].next == INVALID) {
|
|
| 1671 |
augmentOnArc(a); |
|
| 1672 |
--unmatched; |
|
| 1673 |
} else {
|
|
| 1674 |
extendOnArc(a); |
|
| 1675 |
} |
|
| 1780 | 1676 |
} |
| 1781 | 1677 |
break; |
| 1782 | 1678 |
case D3: |
| 1783 | 1679 |
{
|
| ... | ... |
@@ -1788,22 +1684,10 @@ |
| 1788 | 1684 |
|
| 1789 | 1685 |
if (left_blossom == right_blossom) {
|
| 1790 | 1686 |
_delta3->pop(); |
| 1791 | 1687 |
} else {
|
| 1792 |
int left_tree; |
|
| 1793 |
if ((*_blossom_data)[left_blossom].status == EVEN) {
|
|
| 1794 |
left_tree = _tree_set->find(left_blossom); |
|
| 1795 |
} else {
|
|
| 1796 |
left_tree = -1; |
|
| 1797 |
++unmatched; |
|
| 1798 |
} |
|
| 1799 |
int right_tree; |
|
| 1800 |
if ((*_blossom_data)[right_blossom].status == EVEN) {
|
|
| 1801 |
right_tree = _tree_set->find(right_blossom); |
|
| 1802 |
} else {
|
|
| 1803 |
right_tree = -1; |
|
| 1804 |
++unmatched; |
|
| 1805 |
} |
|
| 1688 |
int left_tree = _tree_set->find(left_blossom); |
|
| 1689 |
int right_tree = _tree_set->find(right_blossom); |
|
| 1806 | 1690 |
|
| 1807 | 1691 |
if (left_tree == right_tree) {
|
| 1808 | 1692 |
shrinkOnEdge(e, left_tree); |
| 1809 | 1693 |
} else {
|
| ... | ... |
@@ -1836,9 +1720,9 @@ |
| 1836 | 1720 |
|
| 1837 | 1721 |
/// @} |
| 1838 | 1722 |
|
| 1839 | 1723 |
/// \name Primal Solution |
| 1840 |
/// Functions to get the primal solution, i.e. the maximum weighted |
|
| 1724 |
/// Functions to get the primal solution, i.e. the maximum weighted |
|
| 1841 | 1725 |
/// matching.\n |
| 1842 | 1726 |
/// Either \ref run() or \ref start() function should be called before |
| 1843 | 1727 |
/// using them. |
| 1844 | 1728 |
|
| ... | ... |
@@ -1855,9 +1739,9 @@ |
| 1855 | 1739 |
if ((*_matching)[n] != INVALID) {
|
| 1856 | 1740 |
sum += _weight[(*_matching)[n]]; |
| 1857 | 1741 |
} |
| 1858 | 1742 |
} |
| 1859 |
return sum / |
|
| 1743 |
return sum / 2; |
|
| 1860 | 1744 |
} |
| 1861 | 1745 |
|
| 1862 | 1746 |
/// \brief Return the size (cardinality) of the matching. |
| 1863 | 1747 |
/// |
| ... | ... |
@@ -1875,9 +1759,9 @@ |
| 1875 | 1759 |
} |
| 1876 | 1760 |
|
| 1877 | 1761 |
/// \brief Return \c true if the given edge is in the matching. |
| 1878 | 1762 |
/// |
| 1879 |
/// This function returns \c true if the given edge is in the found |
|
| 1763 |
/// This function returns \c true if the given edge is in the found |
|
| 1880 | 1764 |
/// matching. |
| 1881 | 1765 |
/// |
| 1882 | 1766 |
/// \pre Either run() or start() must be called before using this function. |
| 1883 | 1767 |
bool matching(const Edge& edge) const {
|
| ... | ... |
@@ -1886,9 +1770,9 @@ |
| 1886 | 1770 |
|
| 1887 | 1771 |
/// \brief Return the matching arc (or edge) incident to the given node. |
| 1888 | 1772 |
/// |
| 1889 | 1773 |
/// This function returns the matching arc (or edge) incident to the |
| 1890 |
/// given node in the found matching or \c INVALID if the node is |
|
| 1774 |
/// given node in the found matching or \c INVALID if the node is |
|
| 1891 | 1775 |
/// not covered by the matching. |
| 1892 | 1776 |
/// |
| 1893 | 1777 |
/// \pre Either run() or start() must be called before using this function. |
| 1894 | 1778 |
Arc matching(const Node& node) const {
|
| ... | ... |
@@ -1904,9 +1788,9 @@ |
| 1904 | 1788 |
} |
| 1905 | 1789 |
|
| 1906 | 1790 |
/// \brief Return the mate of the given node. |
| 1907 | 1791 |
/// |
| 1908 |
/// This function returns the mate of the given node in the found |
|
| 1792 |
/// This function returns the mate of the given node in the found |
|
| 1909 | 1793 |
/// matching or \c INVALID if the node is not covered by the matching. |
| 1910 | 1794 |
/// |
| 1911 | 1795 |
/// \pre Either run() or start() must be called before using this function. |
| 1912 | 1796 |
Node mate(const Node& node) const {
|
| ... | ... |
@@ -1924,10 +1808,10 @@ |
| 1924 | 1808 |
/// @{
|
| 1925 | 1809 |
|
| 1926 | 1810 |
/// \brief Return the value of the dual solution. |
| 1927 | 1811 |
/// |
| 1928 |
/// This function returns the value of the dual solution. |
|
| 1929 |
/// It should be equal to the primal value scaled by \ref dualScale |
|
| 1812 |
/// This function returns the value of the dual solution. |
|
| 1813 |
/// It should be equal to the primal value scaled by \ref dualScale |
|
| 1930 | 1814 |
/// "dual scale". |
| 1931 | 1815 |
/// |
| 1932 | 1816 |
/// \pre Either run() or start() must be called before using this function. |
| 1933 | 1817 |
Value dualValue() const {
|
| ... | ... |
@@ -1980,21 +1864,21 @@ |
| 1980 | 1864 |
} |
| 1981 | 1865 |
|
| 1982 | 1866 |
/// \brief Iterator for obtaining the nodes of a blossom. |
| 1983 | 1867 |
/// |
| 1984 |
/// This class provides an iterator for obtaining the nodes of the |
|
| 1868 |
/// This class provides an iterator for obtaining the nodes of the |
|
| 1985 | 1869 |
/// given blossom. It lists a subset of the nodes. |
| 1986 |
/// Before using this iterator, you must allocate a |
|
| 1870 |
/// Before using this iterator, you must allocate a |
|
| 1987 | 1871 |
/// MaxWeightedMatching class and execute it. |
| 1988 | 1872 |
class BlossomIt {
|
| 1989 | 1873 |
public: |
| 1990 | 1874 |
|
| 1991 | 1875 |
/// \brief Constructor. |
| 1992 | 1876 |
/// |
| 1993 | 1877 |
/// Constructor to get the nodes of the given variable. |
| 1994 | 1878 |
/// |
| 1995 |
/// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or |
|
| 1996 |
/// \ref MaxWeightedMatching::start() "algorithm.start()" must be |
|
| 1879 |
/// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or |
|
| 1880 |
/// \ref MaxWeightedMatching::start() "algorithm.start()" must be |
|
| 1997 | 1881 |
/// called before initializing this iterator. |
| 1998 | 1882 |
BlossomIt(const MaxWeightedMatching& algorithm, int variable) |
| 1999 | 1883 |
: _algorithm(&algorithm) |
| 2000 | 1884 |
{
|
| ... | ... |
@@ -2045,10 +1929,10 @@ |
| 2045 | 1929 |
/// maximum weighted perfect matching algorithm. The implementation |
| 2046 | 1930 |
/// is based on extensive use of priority queues and provides |
| 2047 | 1931 |
/// \f$O(nm\log n)\f$ time complexity. |
| 2048 | 1932 |
/// |
| 2049 |
/// The maximum weighted perfect matching problem is to find a subset of |
|
| 2050 |
/// the edges in an undirected graph with maximum overall weight for which |
|
| 1933 |
/// The maximum weighted perfect matching problem is to find a subset of |
|
| 1934 |
/// the edges in an undirected graph with maximum overall weight for which |
|
| 2051 | 1935 |
/// each node has exactly one incident edge. |
| 2052 | 1936 |
/// It can be formulated with the following linear program. |
| 2053 | 1937 |
/// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f]
|
| 2054 | 1938 |
/** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
|
| ... | ... |
@@ -2069,18 +1953,18 @@ |
| 2069 | 1953 |
/// \f[z_B \ge 0 \quad \forall B \in \mathcal{O}\f]
|
| 2070 | 1954 |
/** \f[\min \sum_{u \in V}y_u + \sum_{B \in \mathcal{O}}
|
| 2071 | 1955 |
\frac{\vert B \vert - 1}{2}z_B\f] */
|
| 2072 | 1956 |
/// |
| 2073 |
/// The algorithm can be executed with the run() function. |
|
| 1957 |
/// The algorithm can be executed with the run() function. |
|
| 2074 | 1958 |
/// After it the matching (the primal solution) and the dual solution |
| 2075 |
/// can be obtained using the query functions and the |
|
| 2076 |
/// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, |
|
| 2077 |
/// |
|
| 1959 |
/// can be obtained using the query functions and the |
|
| 1960 |
/// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, |
|
| 1961 |
/// which is able to iterate on the nodes of a blossom. |
|
| 2078 | 1962 |
/// If the value type is integer, then the dual solution is multiplied |
| 2079 | 1963 |
/// by \ref MaxWeightedMatching::dualScale "4". |
| 2080 | 1964 |
/// |
| 2081 | 1965 |
/// \tparam GR The undirected graph type the algorithm runs on. |
| 2082 |
/// \tparam WM The type edge weight map. The default type is |
|
| 1966 |
/// \tparam WM The type edge weight map. The default type is |
|
| 2083 | 1967 |
/// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
| 2084 | 1968 |
#ifdef DOXYGEN |
| 2085 | 1969 |
template <typename GR, typename WM> |
| 2086 | 1970 |
#else |
| ... | ... |
@@ -2232,11 +2116,8 @@ |
| 2232 | 2116 |
} |
| 2233 | 2117 |
} |
| 2234 | 2118 |
|
| 2235 | 2119 |
void destroyStructures() {
|
| 2236 |
_node_num = countNodes(_graph); |
|
| 2237 |
_blossom_num = _node_num * 3 / 2; |
|
| 2238 |
|
|
| 2239 | 2120 |
if (_matching) {
|
| 2240 | 2121 |
delete _matching; |
| 2241 | 2122 |
} |
| 2242 | 2123 |
if (_node_potential) {
|
| ... | ... |
@@ -2990,10 +2871,10 @@ |
| 2990 | 2871 |
|
| 2991 | 2872 |
Value d4 = !_delta4->empty() ? |
| 2992 | 2873 |
_delta4->prio() : std::numeric_limits<Value>::max(); |
| 2993 | 2874 |
|
| 2994 |
_delta_sum = d2; OpType ot = D2; |
|
| 2995 |
if (d3 < _delta_sum) { _delta_sum = d3; ot = D3; }
|
|
| 2875 |
_delta_sum = d3; OpType ot = D3; |
|
| 2876 |
if (d2 < _delta_sum) { _delta_sum = d2; ot = D2; }
|
|
| 2996 | 2877 |
if (d4 < _delta_sum) { _delta_sum = d4; ot = D4; }
|
| 2997 | 2878 |
|
| 2998 | 2879 |
if (_delta_sum == std::numeric_limits<Value>::max()) {
|
| 2999 | 2880 |
return false; |
| ... | ... |
@@ -3054,9 +2935,9 @@ |
| 3054 | 2935 |
|
| 3055 | 2936 |
/// @} |
| 3056 | 2937 |
|
| 3057 | 2938 |
/// \name Primal Solution |
| 3058 |
/// Functions to get the primal solution, i.e. the maximum weighted |
|
| 2939 |
/// Functions to get the primal solution, i.e. the maximum weighted |
|
| 3059 | 2940 |
/// perfect matching.\n |
| 3060 | 2941 |
/// Either \ref run() or \ref start() function should be called before |
| 3061 | 2942 |
/// using them. |
| 3062 | 2943 |
|
| ... | ... |
@@ -3073,14 +2954,14 @@ |
| 3073 | 2954 |
if ((*_matching)[n] != INVALID) {
|
| 3074 | 2955 |
sum += _weight[(*_matching)[n]]; |
| 3075 | 2956 |
} |
| 3076 | 2957 |
} |
| 3077 |
return sum / |
|
| 2958 |
return sum / 2; |
|
| 3078 | 2959 |
} |
| 3079 | 2960 |
|
| 3080 | 2961 |
/// \brief Return \c true if the given edge is in the matching. |
| 3081 | 2962 |
/// |
| 3082 |
/// This function returns \c true if the given edge is in the found |
|
| 2963 |
/// This function returns \c true if the given edge is in the found |
|
| 3083 | 2964 |
/// matching. |
| 3084 | 2965 |
/// |
| 3085 | 2966 |
/// \pre Either run() or start() must be called before using this function. |
| 3086 | 2967 |
bool matching(const Edge& edge) const {
|
| ... | ... |
@@ -3089,9 +2970,9 @@ |
| 3089 | 2970 |
|
| 3090 | 2971 |
/// \brief Return the matching arc (or edge) incident to the given node. |
| 3091 | 2972 |
/// |
| 3092 | 2973 |
/// This function returns the matching arc (or edge) incident to the |
| 3093 |
/// given node in the found matching or \c INVALID if the node is |
|
| 2974 |
/// given node in the found matching or \c INVALID if the node is |
|
| 3094 | 2975 |
/// not covered by the matching. |
| 3095 | 2976 |
/// |
| 3096 | 2977 |
/// \pre Either run() or start() must be called before using this function. |
| 3097 | 2978 |
Arc matching(const Node& node) const {
|
| ... | ... |
@@ -3107,9 +2988,9 @@ |
| 3107 | 2988 |
} |
| 3108 | 2989 |
|
| 3109 | 2990 |
/// \brief Return the mate of the given node. |
| 3110 | 2991 |
/// |
| 3111 |
/// This function returns the mate of the given node in the found |
|
| 2992 |
/// This function returns the mate of the given node in the found |
|
| 3112 | 2993 |
/// matching or \c INVALID if the node is not covered by the matching. |
| 3113 | 2994 |
/// |
| 3114 | 2995 |
/// \pre Either run() or start() must be called before using this function. |
| 3115 | 2996 |
Node mate(const Node& node) const {
|
| ... | ... |
@@ -3126,10 +3007,10 @@ |
| 3126 | 3007 |
/// @{
|
| 3127 | 3008 |
|
| 3128 | 3009 |
/// \brief Return the value of the dual solution. |
| 3129 | 3010 |
/// |
| 3130 |
/// This function returns the value of the dual solution. |
|
| 3131 |
/// It should be equal to the primal value scaled by \ref dualScale |
|
| 3011 |
/// This function returns the value of the dual solution. |
|
| 3012 |
/// It should be equal to the primal value scaled by \ref dualScale |
|
| 3132 | 3013 |
/// "dual scale". |
| 3133 | 3014 |
/// |
| 3134 | 3015 |
/// \pre Either run() or start() must be called before using this function. |
| 3135 | 3016 |
Value dualValue() const {
|
| ... | ... |
@@ -3182,21 +3063,21 @@ |
| 3182 | 3063 |
} |
| 3183 | 3064 |
|
| 3184 | 3065 |
/// \brief Iterator for obtaining the nodes of a blossom. |
| 3185 | 3066 |
/// |
| 3186 |
/// This class provides an iterator for obtaining the nodes of the |
|
| 3067 |
/// This class provides an iterator for obtaining the nodes of the |
|
| 3187 | 3068 |
/// given blossom. It lists a subset of the nodes. |
| 3188 |
/// Before using this iterator, you must allocate a |
|
| 3069 |
/// Before using this iterator, you must allocate a |
|
| 3189 | 3070 |
/// MaxWeightedPerfectMatching class and execute it. |
| 3190 | 3071 |
class BlossomIt {
|
| 3191 | 3072 |
public: |
| 3192 | 3073 |
|
| 3193 | 3074 |
/// \brief Constructor. |
| 3194 | 3075 |
/// |
| 3195 | 3076 |
/// Constructor to get the nodes of the given variable. |
| 3196 | 3077 |
/// |
| 3197 |
/// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" |
|
| 3198 |
/// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" |
|
| 3078 |
/// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" |
|
| 3079 |
/// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" |
|
| 3199 | 3080 |
/// must be called before initializing this iterator. |
| 3200 | 3081 |
BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable) |
| 3201 | 3082 |
: _algorithm(&algorithm) |
| 3202 | 3083 |
{
|
| ... | ... |
@@ -3240,5 +3121,5 @@ |
| 3240 | 3121 |
}; |
| 3241 | 3122 |
|
| 3242 | 3123 |
} //END OF NAMESPACE LEMON |
| 3243 | 3124 |
|
| 3244 |
#endif // |
|
| 3125 |
#endif //LEMON_MATCHING_H |
0 comments (0 inline)