808 _blossom_num = _node_num * 3 / 2; |
808 _blossom_num = _node_num * 3 / 2; |
809 |
809 |
810 if (!_matching) { |
810 if (!_matching) { |
811 _matching = new MatchingMap(_graph); |
811 _matching = new MatchingMap(_graph); |
812 } |
812 } |
|
813 |
813 if (!_node_potential) { |
814 if (!_node_potential) { |
814 _node_potential = new NodePotential(_graph); |
815 _node_potential = new NodePotential(_graph); |
815 } |
816 } |
|
817 |
816 if (!_blossom_set) { |
818 if (!_blossom_set) { |
817 _blossom_index = new IntNodeMap(_graph); |
819 _blossom_index = new IntNodeMap(_graph); |
818 _blossom_set = new BlossomSet(*_blossom_index); |
820 _blossom_set = new BlossomSet(*_blossom_index); |
819 _blossom_data = new RangeMap<BlossomData>(_blossom_num); |
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 if (!_node_index) { |
827 if (!_node_index) { |
823 _node_index = new IntNodeMap(_graph); |
828 _node_index = new IntNodeMap(_graph); |
824 _node_heap_index = new IntArcMap(_graph); |
829 _node_heap_index = new IntArcMap(_graph); |
825 _node_data = new RangeMap<NodeData>(_node_num, |
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 if (!_tree_set) { |
838 if (!_tree_set) { |
830 _tree_set_index = new IntIntMap(_blossom_num); |
839 _tree_set_index = new IntIntMap(_blossom_num); |
831 _tree_set = new TreeSet(*_tree_set_index); |
840 _tree_set = new TreeSet(*_tree_set_index); |
832 } |
841 } else { |
|
842 _tree_set_index->resize(_blossom_num); |
|
843 } |
|
844 |
833 if (!_delta1) { |
845 if (!_delta1) { |
834 _delta1_index = new IntNodeMap(_graph); |
846 _delta1_index = new IntNodeMap(_graph); |
835 _delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index); |
847 _delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index); |
836 } |
848 } |
|
849 |
837 if (!_delta2) { |
850 if (!_delta2) { |
838 _delta2_index = new IntIntMap(_blossom_num); |
851 _delta2_index = new IntIntMap(_blossom_num); |
839 _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index); |
852 _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index); |
840 } |
853 } else { |
|
854 _delta2_index->resize(_blossom_num); |
|
855 } |
|
856 |
841 if (!_delta3) { |
857 if (!_delta3) { |
842 _delta3_index = new IntEdgeMap(_graph); |
858 _delta3_index = new IntEdgeMap(_graph); |
843 _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index); |
859 _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index); |
844 } |
860 } |
|
861 |
845 if (!_delta4) { |
862 if (!_delta4) { |
846 _delta4_index = new IntIntMap(_blossom_num); |
863 _delta4_index = new IntIntMap(_blossom_num); |
847 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index); |
864 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index); |
|
865 } else { |
|
866 _delta4_index->resize(_blossom_num); |
848 } |
867 } |
849 } |
868 } |
850 |
869 |
851 void destroyStructures() { |
870 void destroyStructures() { |
852 if (_matching) { |
871 if (_matching) { |
1586 /// |
1605 /// |
1587 /// This function initializes the algorithm. |
1606 /// This function initializes the algorithm. |
1588 void init() { |
1607 void init() { |
1589 createStructures(); |
1608 createStructures(); |
1590 |
1609 |
|
1610 _blossom_node_list.clear(); |
|
1611 _blossom_potential.clear(); |
|
1612 |
1591 for (ArcIt e(_graph); e != INVALID; ++e) { |
1613 for (ArcIt e(_graph); e != INVALID; ++e) { |
1592 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
1614 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
1593 } |
1615 } |
1594 for (NodeIt n(_graph); n != INVALID; ++n) { |
1616 for (NodeIt n(_graph); n != INVALID; ++n) { |
1595 (*_delta1_index)[n] = _delta1->PRE_HEAP; |
1617 (*_delta1_index)[n] = _delta1->PRE_HEAP; |
1599 } |
1621 } |
1600 for (int i = 0; i < _blossom_num; ++i) { |
1622 for (int i = 0; i < _blossom_num; ++i) { |
1601 (*_delta2_index)[i] = _delta2->PRE_HEAP; |
1623 (*_delta2_index)[i] = _delta2->PRE_HEAP; |
1602 (*_delta4_index)[i] = _delta4->PRE_HEAP; |
1624 (*_delta4_index)[i] = _delta4->PRE_HEAP; |
1603 } |
1625 } |
1604 |
1626 |
1605 _unmatched = _node_num; |
1627 _unmatched = _node_num; |
|
1628 |
|
1629 _delta1->clear(); |
|
1630 _delta2->clear(); |
|
1631 _delta3->clear(); |
|
1632 _delta4->clear(); |
|
1633 _blossom_set->clear(); |
|
1634 _tree_set->clear(); |
1606 |
1635 |
1607 int index = 0; |
1636 int index = 0; |
1608 for (NodeIt n(_graph); n != INVALID; ++n) { |
1637 for (NodeIt n(_graph); n != INVALID; ++n) { |
1609 Value max = 0; |
1638 Value max = 0; |
1610 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
1639 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
1612 if ((dualScale * _weight[e]) / 2 > max) { |
1641 if ((dualScale * _weight[e]) / 2 > max) { |
1613 max = (dualScale * _weight[e]) / 2; |
1642 max = (dualScale * _weight[e]) / 2; |
1614 } |
1643 } |
1615 } |
1644 } |
1616 (*_node_index)[n] = index; |
1645 (*_node_index)[n] = index; |
|
1646 (*_node_data)[index].heap_index.clear(); |
|
1647 (*_node_data)[index].heap.clear(); |
1617 (*_node_data)[index].pot = max; |
1648 (*_node_data)[index].pot = max; |
1618 _delta1->push(n, max); |
1649 _delta1->push(n, max); |
1619 int blossom = |
1650 int blossom = |
1620 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
1651 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
1621 |
1652 |
2235 _blossom_num = _node_num * 3 / 2; |
2266 _blossom_num = _node_num * 3 / 2; |
2236 |
2267 |
2237 if (!_matching) { |
2268 if (!_matching) { |
2238 _matching = new MatchingMap(_graph); |
2269 _matching = new MatchingMap(_graph); |
2239 } |
2270 } |
|
2271 |
2240 if (!_node_potential) { |
2272 if (!_node_potential) { |
2241 _node_potential = new NodePotential(_graph); |
2273 _node_potential = new NodePotential(_graph); |
2242 } |
2274 } |
|
2275 |
2243 if (!_blossom_set) { |
2276 if (!_blossom_set) { |
2244 _blossom_index = new IntNodeMap(_graph); |
2277 _blossom_index = new IntNodeMap(_graph); |
2245 _blossom_set = new BlossomSet(*_blossom_index); |
2278 _blossom_set = new BlossomSet(*_blossom_index); |
|
2279 _blossom_data = new RangeMap<BlossomData>(_blossom_num); |
|
2280 } else if (_blossom_data->size() != _blossom_num) { |
|
2281 delete _blossom_data; |
2246 _blossom_data = new RangeMap<BlossomData>(_blossom_num); |
2282 _blossom_data = new RangeMap<BlossomData>(_blossom_num); |
2247 } |
2283 } |
2248 |
2284 |
2249 if (!_node_index) { |
2285 if (!_node_index) { |
2250 _node_index = new IntNodeMap(_graph); |
2286 _node_index = new IntNodeMap(_graph); |
2251 _node_heap_index = new IntArcMap(_graph); |
2287 _node_heap_index = new IntArcMap(_graph); |
2252 _node_data = new RangeMap<NodeData>(_node_num, |
2288 _node_data = new RangeMap<NodeData>(_node_num, |
2253 NodeData(*_node_heap_index)); |
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 if (!_tree_set) { |
2296 if (!_tree_set) { |
2257 _tree_set_index = new IntIntMap(_blossom_num); |
2297 _tree_set_index = new IntIntMap(_blossom_num); |
2258 _tree_set = new TreeSet(*_tree_set_index); |
2298 _tree_set = new TreeSet(*_tree_set_index); |
2259 } |
2299 } else { |
|
2300 _tree_set_index->resize(_blossom_num); |
|
2301 } |
|
2302 |
2260 if (!_delta2) { |
2303 if (!_delta2) { |
2261 _delta2_index = new IntIntMap(_blossom_num); |
2304 _delta2_index = new IntIntMap(_blossom_num); |
2262 _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index); |
2305 _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index); |
2263 } |
2306 } else { |
|
2307 _delta2_index->resize(_blossom_num); |
|
2308 } |
|
2309 |
2264 if (!_delta3) { |
2310 if (!_delta3) { |
2265 _delta3_index = new IntEdgeMap(_graph); |
2311 _delta3_index = new IntEdgeMap(_graph); |
2266 _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index); |
2312 _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index); |
2267 } |
2313 } |
|
2314 |
2268 if (!_delta4) { |
2315 if (!_delta4) { |
2269 _delta4_index = new IntIntMap(_blossom_num); |
2316 _delta4_index = new IntIntMap(_blossom_num); |
2270 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index); |
2317 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index); |
|
2318 } else { |
|
2319 _delta4_index->resize(_blossom_num); |
2271 } |
2320 } |
2272 } |
2321 } |
2273 |
2322 |
2274 void destroyStructures() { |
2323 void destroyStructures() { |
2275 if (_matching) { |
2324 if (_matching) { |
2966 /// |
3015 /// |
2967 /// This function initializes the algorithm. |
3016 /// This function initializes the algorithm. |
2968 void init() { |
3017 void init() { |
2969 createStructures(); |
3018 createStructures(); |
2970 |
3019 |
|
3020 _blossom_node_list.clear(); |
|
3021 _blossom_potential.clear(); |
|
3022 |
2971 for (ArcIt e(_graph); e != INVALID; ++e) { |
3023 for (ArcIt e(_graph); e != INVALID; ++e) { |
2972 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
3024 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
2973 } |
3025 } |
2974 for (EdgeIt e(_graph); e != INVALID; ++e) { |
3026 for (EdgeIt e(_graph); e != INVALID; ++e) { |
2975 (*_delta3_index)[e] = _delta3->PRE_HEAP; |
3027 (*_delta3_index)[e] = _delta3->PRE_HEAP; |
2978 (*_delta2_index)[i] = _delta2->PRE_HEAP; |
3030 (*_delta2_index)[i] = _delta2->PRE_HEAP; |
2979 (*_delta4_index)[i] = _delta4->PRE_HEAP; |
3031 (*_delta4_index)[i] = _delta4->PRE_HEAP; |
2980 } |
3032 } |
2981 |
3033 |
2982 _unmatched = _node_num; |
3034 _unmatched = _node_num; |
|
3035 |
|
3036 _delta2->clear(); |
|
3037 _delta3->clear(); |
|
3038 _delta4->clear(); |
|
3039 _blossom_set->clear(); |
|
3040 _tree_set->clear(); |
2983 |
3041 |
2984 int index = 0; |
3042 int index = 0; |
2985 for (NodeIt n(_graph); n != INVALID; ++n) { |
3043 for (NodeIt n(_graph); n != INVALID; ++n) { |
2986 Value max = - std::numeric_limits<Value>::max(); |
3044 Value max = - std::numeric_limits<Value>::max(); |
2987 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
3045 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
2989 if ((dualScale * _weight[e]) / 2 > max) { |
3047 if ((dualScale * _weight[e]) / 2 > max) { |
2990 max = (dualScale * _weight[e]) / 2; |
3048 max = (dualScale * _weight[e]) / 2; |
2991 } |
3049 } |
2992 } |
3050 } |
2993 (*_node_index)[n] = index; |
3051 (*_node_index)[n] = index; |
|
3052 (*_node_data)[index].heap_index.clear(); |
|
3053 (*_node_data)[index].heap.clear(); |
2994 (*_node_data)[index].pot = max; |
3054 (*_node_data)[index].pot = max; |
2995 int blossom = |
3055 int blossom = |
2996 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
3056 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
2997 |
3057 |
2998 _tree_set->insert(blossom); |
3058 _tree_set->insert(blossom); |