... |
... |
@@ -810,41 +810,60 @@
|
810 |
810 |
if (!_matching) {
|
811 |
811 |
_matching = new MatchingMap(_graph);
|
812 |
812 |
}
|
|
813 |
|
813 |
814 |
if (!_node_potential) {
|
814 |
815 |
_node_potential = new NodePotential(_graph);
|
815 |
816 |
}
|
|
817 |
|
816 |
818 |
if (!_blossom_set) {
|
817 |
819 |
_blossom_index = new IntNodeMap(_graph);
|
818 |
820 |
_blossom_set = new BlossomSet(*_blossom_index);
|
819 |
821 |
_blossom_data = new RangeMap<BlossomData>(_blossom_num);
|
|
822 |
} else if (_blossom_data->size() != _blossom_num) {
|
|
823 |
delete _blossom_data;
|
|
824 |
_blossom_data = new RangeMap<BlossomData>(_blossom_num);
|
820 |
825 |
}
|
821 |
826 |
|
822 |
827 |
if (!_node_index) {
|
823 |
828 |
_node_index = new IntNodeMap(_graph);
|
824 |
829 |
_node_heap_index = new IntArcMap(_graph);
|
825 |
830 |
_node_data = new RangeMap<NodeData>(_node_num,
|
826 |
|
NodeData(*_node_heap_index));
|
|
831 |
NodeData(*_node_heap_index));
|
|
832 |
} else {
|
|
833 |
delete _node_data;
|
|
834 |
_node_data = new RangeMap<NodeData>(_node_num,
|
|
835 |
NodeData(*_node_heap_index));
|
827 |
836 |
}
|
828 |
837 |
|
829 |
838 |
if (!_tree_set) {
|
830 |
839 |
_tree_set_index = new IntIntMap(_blossom_num);
|
831 |
840 |
_tree_set = new TreeSet(*_tree_set_index);
|
|
841 |
} else {
|
|
842 |
_tree_set_index->resize(_blossom_num);
|
832 |
843 |
}
|
|
844 |
|
833 |
845 |
if (!_delta1) {
|
834 |
846 |
_delta1_index = new IntNodeMap(_graph);
|
835 |
847 |
_delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index);
|
836 |
848 |
}
|
|
849 |
|
837 |
850 |
if (!_delta2) {
|
838 |
851 |
_delta2_index = new IntIntMap(_blossom_num);
|
839 |
852 |
_delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
|
|
853 |
} else {
|
|
854 |
_delta2_index->resize(_blossom_num);
|
840 |
855 |
}
|
|
856 |
|
841 |
857 |
if (!_delta3) {
|
842 |
858 |
_delta3_index = new IntEdgeMap(_graph);
|
843 |
859 |
_delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
|
844 |
860 |
}
|
|
861 |
|
845 |
862 |
if (!_delta4) {
|
846 |
863 |
_delta4_index = new IntIntMap(_blossom_num);
|
847 |
864 |
_delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
|
|
865 |
} else {
|
|
866 |
_delta4_index->resize(_blossom_num);
|
848 |
867 |
}
|
849 |
868 |
}
|
850 |
869 |
|
... |
... |
@@ -1588,6 +1607,9 @@
|
1588 |
1607 |
void init() {
|
1589 |
1608 |
createStructures();
|
1590 |
1609 |
|
|
1610 |
_blossom_node_list.clear();
|
|
1611 |
_blossom_potential.clear();
|
|
1612 |
|
1591 |
1613 |
for (ArcIt e(_graph); e != INVALID; ++e) {
|
1592 |
1614 |
(*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
|
1593 |
1615 |
}
|
... |
... |
@@ -1601,9 +1623,16 @@
|
1601 |
1623 |
(*_delta2_index)[i] = _delta2->PRE_HEAP;
|
1602 |
1624 |
(*_delta4_index)[i] = _delta4->PRE_HEAP;
|
1603 |
1625 |
}
|
1604 |
|
|
|
1626 |
|
1605 |
1627 |
_unmatched = _node_num;
|
1606 |
1628 |
|
|
1629 |
_delta1->clear();
|
|
1630 |
_delta2->clear();
|
|
1631 |
_delta3->clear();
|
|
1632 |
_delta4->clear();
|
|
1633 |
_blossom_set->clear();
|
|
1634 |
_tree_set->clear();
|
|
1635 |
|
1607 |
1636 |
int index = 0;
|
1608 |
1637 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
1609 |
1638 |
Value max = 0;
|
... |
... |
@@ -1614,6 +1643,8 @@
|
1614 |
1643 |
}
|
1615 |
1644 |
}
|
1616 |
1645 |
(*_node_index)[n] = index;
|
|
1646 |
(*_node_data)[index].heap_index.clear();
|
|
1647 |
(*_node_data)[index].heap.clear();
|
1617 |
1648 |
(*_node_data)[index].pot = max;
|
1618 |
1649 |
_delta1->push(n, max);
|
1619 |
1650 |
int blossom =
|
... |
... |
@@ -2237,13 +2268,18 @@
|
2237 |
2268 |
if (!_matching) {
|
2238 |
2269 |
_matching = new MatchingMap(_graph);
|
2239 |
2270 |
}
|
|
2271 |
|
2240 |
2272 |
if (!_node_potential) {
|
2241 |
2273 |
_node_potential = new NodePotential(_graph);
|
2242 |
2274 |
}
|
|
2275 |
|
2243 |
2276 |
if (!_blossom_set) {
|
2244 |
2277 |
_blossom_index = new IntNodeMap(_graph);
|
2245 |
2278 |
_blossom_set = new BlossomSet(*_blossom_index);
|
2246 |
2279 |
_blossom_data = new RangeMap<BlossomData>(_blossom_num);
|
|
2280 |
} else if (_blossom_data->size() != _blossom_num) {
|
|
2281 |
delete _blossom_data;
|
|
2282 |
_blossom_data = new RangeMap<BlossomData>(_blossom_num);
|
2247 |
2283 |
}
|
2248 |
2284 |
|
2249 |
2285 |
if (!_node_index) {
|
... |
... |
@@ -2251,23 +2287,36 @@
|
2251 |
2287 |
_node_heap_index = new IntArcMap(_graph);
|
2252 |
2288 |
_node_data = new RangeMap<NodeData>(_node_num,
|
2253 |
2289 |
NodeData(*_node_heap_index));
|
|
2290 |
} else if (_node_data->size() != _node_num) {
|
|
2291 |
delete _node_data;
|
|
2292 |
_node_data = new RangeMap<NodeData>(_node_num,
|
|
2293 |
NodeData(*_node_heap_index));
|
2254 |
2294 |
}
|
2255 |
2295 |
|
2256 |
2296 |
if (!_tree_set) {
|
2257 |
2297 |
_tree_set_index = new IntIntMap(_blossom_num);
|
2258 |
2298 |
_tree_set = new TreeSet(*_tree_set_index);
|
|
2299 |
} else {
|
|
2300 |
_tree_set_index->resize(_blossom_num);
|
2259 |
2301 |
}
|
|
2302 |
|
2260 |
2303 |
if (!_delta2) {
|
2261 |
2304 |
_delta2_index = new IntIntMap(_blossom_num);
|
2262 |
2305 |
_delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
|
|
2306 |
} else {
|
|
2307 |
_delta2_index->resize(_blossom_num);
|
2263 |
2308 |
}
|
|
2309 |
|
2264 |
2310 |
if (!_delta3) {
|
2265 |
2311 |
_delta3_index = new IntEdgeMap(_graph);
|
2266 |
2312 |
_delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
|
2267 |
2313 |
}
|
|
2314 |
|
2268 |
2315 |
if (!_delta4) {
|
2269 |
2316 |
_delta4_index = new IntIntMap(_blossom_num);
|
2270 |
2317 |
_delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
|
|
2318 |
} else {
|
|
2319 |
_delta4_index->resize(_blossom_num);
|
2271 |
2320 |
}
|
2272 |
2321 |
}
|
2273 |
2322 |
|
... |
... |
@@ -2968,6 +3017,9 @@
|
2968 |
3017 |
void init() {
|
2969 |
3018 |
createStructures();
|
2970 |
3019 |
|
|
3020 |
_blossom_node_list.clear();
|
|
3021 |
_blossom_potential.clear();
|
|
3022 |
|
2971 |
3023 |
for (ArcIt e(_graph); e != INVALID; ++e) {
|
2972 |
3024 |
(*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
|
2973 |
3025 |
}
|
... |
... |
@@ -2981,6 +3033,12 @@
|
2981 |
3033 |
|
2982 |
3034 |
_unmatched = _node_num;
|
2983 |
3035 |
|
|
3036 |
_delta2->clear();
|
|
3037 |
_delta3->clear();
|
|
3038 |
_delta4->clear();
|
|
3039 |
_blossom_set->clear();
|
|
3040 |
_tree_set->clear();
|
|
3041 |
|
2984 |
3042 |
int index = 0;
|
2985 |
3043 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
2986 |
3044 |
Value max = - std::numeric_limits<Value>::max();
|
... |
... |
@@ -2991,6 +3049,8 @@
|
2991 |
3049 |
}
|
2992 |
3050 |
}
|
2993 |
3051 |
(*_node_index)[n] = index;
|
|
3052 |
(*_node_data)[index].heap_index.clear();
|
|
3053 |
(*_node_data)[index].heap.clear();
|
2994 |
3054 |
(*_node_data)[index].pot = max;
|
2995 |
3055 |
int blossom =
|
2996 |
3056 |
_blossom_set->insert(n, std::numeric_limits<Value>::max());
|