r868:0513ccfea967
Sun, 20 Sep 2009 21:38:24
[Not Reviewed]
0 comments (0 inline)
0
1
0
38
157
| ... | ... |
@@ -18,4 +18,4 @@ |
| 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 |
|
| ... | ... |
@@ -747,3 +747,3 @@ |
| 747 | 747 |
enum Status {
|
| 748 |
EVEN = -1, MATCHED = 0, ODD = 1 |
|
| 748 |
EVEN = -1, MATCHED = 0, ODD = 1 |
|
| 749 | 749 |
}; |
| ... | ... |
@@ -846,5 +846,2 @@ |
| 846 | 846 |
void destroyStructures() {
|
| 847 |
_node_num = countNodes(_graph); |
|
| 848 |
_blossom_num = _node_num * 3 / 2; |
|
| 849 |
|
|
| 850 | 847 |
if (_matching) {
|
| ... | ... |
@@ -924,6 +921,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 {
|
| ... | ... |
@@ -1038,7 +1031,2 @@ |
| 1038 | 1031 |
} |
| 1039 |
|
|
| 1040 |
} else if ((*_blossom_data)[vb].status == UNMATCHED) {
|
|
| 1041 |
if (_delta3->state(e) == _delta3->IN_HEAP) {
|
|
| 1042 |
_delta3->erase(e); |
|
| 1043 |
} |
|
| 1044 | 1032 |
} else {
|
| ... | ... |
@@ -1119,6 +1107,2 @@ |
| 1119 | 1107 |
} |
| 1120 |
} else if ((*_blossom_data)[vb].status == UNMATCHED) {
|
|
| 1121 |
if (_delta3->state(e) != _delta3->IN_HEAP) {
|
|
| 1122 |
_delta3->push(e, rw); |
|
| 1123 |
} |
|
| 1124 | 1108 |
} else {
|
| ... | ... |
@@ -1159,97 +1143,2 @@ |
| 1159 | 1143 |
|
| 1160 |
|
|
| 1161 |
void matchedToUnmatched(int blossom) {
|
|
| 1162 |
if (_delta2->state(blossom) == _delta2->IN_HEAP) {
|
|
| 1163 |
_delta2->erase(blossom); |
|
| 1164 |
} |
|
| 1165 |
|
|
| 1166 |
for (typename BlossomSet::ItemIt n(*_blossom_set, blossom); |
|
| 1167 |
n != INVALID; ++n) {
|
|
| 1168 |
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); |
|
| 1177 |
int vb = _blossom_set->find(v); |
|
| 1178 |
int vi = (*_node_index)[v]; |
|
| 1179 |
|
|
| 1180 |
Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot - |
|
| 1181 |
dualScale * _weight[e]; |
|
| 1182 |
|
|
| 1183 |
if ((*_blossom_data)[vb].status == EVEN) {
|
|
| 1184 |
if (_delta3->state(e) != _delta3->IN_HEAP) {
|
|
| 1185 |
_delta3->push(e, rw); |
|
| 1186 |
} |
|
| 1187 |
} |
|
| 1188 |
} |
|
| 1189 |
} |
|
| 1190 |
} |
|
| 1191 |
|
|
| 1192 |
void unmatchedToMatched(int blossom) {
|
|
| 1193 |
for (typename BlossomSet::ItemIt n(*_blossom_set, blossom); |
|
| 1194 |
n != INVALID; ++n) {
|
|
| 1195 |
int ni = (*_node_index)[n]; |
|
| 1196 |
|
|
| 1197 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
|
| 1198 |
Node v = _graph.source(e); |
|
| 1199 |
int vb = _blossom_set->find(v); |
|
| 1200 |
int vi = (*_node_index)[v]; |
|
| 1201 |
|
|
| 1202 |
Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot - |
|
| 1203 |
dualScale * _weight[e]; |
|
| 1204 |
|
|
| 1205 |
if (vb == blossom) {
|
|
| 1206 |
if (_delta3->state(e) == _delta3->IN_HEAP) {
|
|
| 1207 |
_delta3->erase(e); |
|
| 1208 |
} |
|
| 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 |
Arc r = _graph.oppositeArc(e); |
|
| 1218 |
|
|
| 1219 |
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 |
it->second = r; |
|
| 1227 |
} |
|
| 1228 |
} else {
|
|
| 1229 |
(*_node_data)[ni].heap.push(r, rw); |
|
| 1230 |
(*_node_data)[ni].heap_index.insert(std::make_pair(vt, r)); |
|
| 1231 |
} |
|
| 1232 |
|
|
| 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); |
|
| 1243 |
} |
|
| 1244 |
} |
|
| 1245 |
|
|
| 1246 |
} else if ((*_blossom_data)[vb].status == UNMATCHED) {
|
|
| 1247 |
if (_delta3->state(e) == _delta3->IN_HEAP) {
|
|
| 1248 |
_delta3->erase(e); |
|
| 1249 |
} |
|
| 1250 |
} |
|
| 1251 |
} |
|
| 1252 |
} |
|
| 1253 |
} |
|
| 1254 |
|
|
| 1255 | 1144 |
void alternatePath(int even, int tree) {
|
| ... | ... |
@@ -1296,7 +1185,5 @@ |
| 1296 | 1185 |
|
| 1297 |
(*_blossom_data)[blossom].status = UNMATCHED; |
|
| 1298 | 1186 |
(*_blossom_data)[blossom].base = node; |
| 1299 |
matchedToUnmatched(blossom); |
|
| 1300 |
} |
|
| 1301 |
|
|
| 1187 |
(*_blossom_data)[blossom].next = INVALID; |
|
| 1188 |
} |
|
| 1302 | 1189 |
|
| ... | ... |
@@ -1307,3 +1194,2 @@ |
| 1307 | 1194 |
|
| 1308 |
if ((*_blossom_data)[left].status == EVEN) {
|
|
| 1309 | 1195 |
int left_tree = _tree_set->find(left); |
| ... | ... |
@@ -1311,8 +1197,3 @@ |
| 1311 | 1197 |
destroyTree(left_tree); |
| 1312 |
} else {
|
|
| 1313 |
(*_blossom_data)[left].status = MATCHED; |
|
| 1314 |
unmatchedToMatched(left); |
|
| 1315 |
} |
|
| 1316 |
|
|
| 1317 |
if ((*_blossom_data)[right].status == EVEN) {
|
|
| 1198 |
|
|
| 1318 | 1199 |
int right_tree = _tree_set->find(right); |
| ... | ... |
@@ -1320,6 +1201,2 @@ |
| 1320 | 1201 |
destroyTree(right_tree); |
| 1321 |
} else {
|
|
| 1322 |
(*_blossom_data)[right].status = MATCHED; |
|
| 1323 |
unmatchedToMatched(right); |
|
| 1324 |
} |
|
| 1325 | 1202 |
|
| ... | ... |
@@ -1329,2 +1206,17 @@ |
| 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) {
|
| ... | ... |
@@ -1631,3 +1523,3 @@ |
| 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 |
|
| ... | ... |
@@ -1759,8 +1651,7 @@ |
| 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) {
|
| ... | ... |
@@ -1777,4 +1668,9 @@ |
| 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 |
} |
| ... | ... |
@@ -1791,16 +1687,4 @@ |
| 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 |
|
| ... | ... |
@@ -1858,3 +1742,3 @@ |
| 1858 | 1742 |
} |
| 1859 |
return sum / |
|
| 1743 |
return sum / 2; |
|
| 1860 | 1744 |
} |
| ... | ... |
@@ -2235,5 +2119,2 @@ |
| 2235 | 2119 |
void destroyStructures() {
|
| 2236 |
_node_num = countNodes(_graph); |
|
| 2237 |
_blossom_num = _node_num * 3 / 2; |
|
| 2238 |
|
|
| 2239 | 2120 |
if (_matching) {
|
| ... | ... |
@@ -2993,4 +2874,4 @@ |
| 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; }
|
| ... | ... |
@@ -3076,3 +2957,3 @@ |
| 3076 | 2957 |
} |
| 3077 |
return sum / |
|
| 2958 |
return sum / 2; |
|
| 3078 | 2959 |
} |
| ... | ... |
@@ -3243,2 +3124,2 @@ |
| 3243 | 3124 |
|
| 3244 |
#endif // |
|
| 3125 |
#endif //LEMON_MATCHING_H |
0 comments (0 inline)