803 _blossom_num = _node_num * 3 / 2; |
803 _blossom_num = _node_num * 3 / 2; |
804 |
804 |
805 if (!_matching) { |
805 if (!_matching) { |
806 _matching = new MatchingMap(_graph); |
806 _matching = new MatchingMap(_graph); |
807 } |
807 } |
|
808 |
808 if (!_node_potential) { |
809 if (!_node_potential) { |
809 _node_potential = new NodePotential(_graph); |
810 _node_potential = new NodePotential(_graph); |
810 } |
811 } |
|
812 |
811 if (!_blossom_set) { |
813 if (!_blossom_set) { |
812 _blossom_index = new IntNodeMap(_graph); |
814 _blossom_index = new IntNodeMap(_graph); |
813 _blossom_set = new BlossomSet(*_blossom_index); |
815 _blossom_set = new BlossomSet(*_blossom_index); |
814 _blossom_data = new RangeMap<BlossomData>(_blossom_num); |
816 _blossom_data = new RangeMap<BlossomData>(_blossom_num); |
|
817 } else if (_blossom_data->size() != _blossom_num) { |
|
818 delete _blossom_data; |
|
819 _blossom_data = new RangeMap<BlossomData>(_blossom_num); |
815 } |
820 } |
816 |
821 |
817 if (!_node_index) { |
822 if (!_node_index) { |
818 _node_index = new IntNodeMap(_graph); |
823 _node_index = new IntNodeMap(_graph); |
819 _node_heap_index = new IntArcMap(_graph); |
824 _node_heap_index = new IntArcMap(_graph); |
820 _node_data = new RangeMap<NodeData>(_node_num, |
825 _node_data = new RangeMap<NodeData>(_node_num, |
821 NodeData(*_node_heap_index)); |
826 NodeData(*_node_heap_index)); |
|
827 } else { |
|
828 delete _node_data; |
|
829 _node_data = new RangeMap<NodeData>(_node_num, |
|
830 NodeData(*_node_heap_index)); |
822 } |
831 } |
823 |
832 |
824 if (!_tree_set) { |
833 if (!_tree_set) { |
825 _tree_set_index = new IntIntMap(_blossom_num); |
834 _tree_set_index = new IntIntMap(_blossom_num); |
826 _tree_set = new TreeSet(*_tree_set_index); |
835 _tree_set = new TreeSet(*_tree_set_index); |
827 } |
836 } else { |
|
837 _tree_set_index->resize(_blossom_num); |
|
838 } |
|
839 |
828 if (!_delta1) { |
840 if (!_delta1) { |
829 _delta1_index = new IntNodeMap(_graph); |
841 _delta1_index = new IntNodeMap(_graph); |
830 _delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index); |
842 _delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index); |
831 } |
843 } |
|
844 |
832 if (!_delta2) { |
845 if (!_delta2) { |
833 _delta2_index = new IntIntMap(_blossom_num); |
846 _delta2_index = new IntIntMap(_blossom_num); |
834 _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index); |
847 _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index); |
835 } |
848 } else { |
|
849 _delta2_index->resize(_blossom_num); |
|
850 } |
|
851 |
836 if (!_delta3) { |
852 if (!_delta3) { |
837 _delta3_index = new IntEdgeMap(_graph); |
853 _delta3_index = new IntEdgeMap(_graph); |
838 _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index); |
854 _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index); |
839 } |
855 } |
|
856 |
840 if (!_delta4) { |
857 if (!_delta4) { |
841 _delta4_index = new IntIntMap(_blossom_num); |
858 _delta4_index = new IntIntMap(_blossom_num); |
842 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index); |
859 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index); |
|
860 } else { |
|
861 _delta4_index->resize(_blossom_num); |
843 } |
862 } |
844 } |
863 } |
845 |
864 |
846 void destroyStructures() { |
865 void destroyStructures() { |
847 _node_num = countNodes(_graph); |
866 _node_num = countNodes(_graph); |
1683 /// |
1702 /// |
1684 /// This function initializes the algorithm. |
1703 /// This function initializes the algorithm. |
1685 void init() { |
1704 void init() { |
1686 createStructures(); |
1705 createStructures(); |
1687 |
1706 |
|
1707 _blossom_node_list.clear(); |
|
1708 _blossom_potential.clear(); |
|
1709 |
1688 for (ArcIt e(_graph); e != INVALID; ++e) { |
1710 for (ArcIt e(_graph); e != INVALID; ++e) { |
1689 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
1711 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
1690 } |
1712 } |
1691 for (NodeIt n(_graph); n != INVALID; ++n) { |
1713 for (NodeIt n(_graph); n != INVALID; ++n) { |
1692 (*_delta1_index)[n] = _delta1->PRE_HEAP; |
1714 (*_delta1_index)[n] = _delta1->PRE_HEAP; |
1707 if ((dualScale * _weight[e]) / 2 > max) { |
1736 if ((dualScale * _weight[e]) / 2 > max) { |
1708 max = (dualScale * _weight[e]) / 2; |
1737 max = (dualScale * _weight[e]) / 2; |
1709 } |
1738 } |
1710 } |
1739 } |
1711 (*_node_index)[n] = index; |
1740 (*_node_index)[n] = index; |
|
1741 (*_node_data)[index].heap_index.clear(); |
|
1742 (*_node_data)[index].heap.clear(); |
1712 (*_node_data)[index].pot = max; |
1743 (*_node_data)[index].pot = max; |
1713 _delta1->push(n, max); |
1744 _delta1->push(n, max); |
1714 int blossom = |
1745 int blossom = |
1715 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
1746 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
1716 |
1747 |
2196 _blossom_num = _node_num * 3 / 2; |
2227 _blossom_num = _node_num * 3 / 2; |
2197 |
2228 |
2198 if (!_matching) { |
2229 if (!_matching) { |
2199 _matching = new MatchingMap(_graph); |
2230 _matching = new MatchingMap(_graph); |
2200 } |
2231 } |
|
2232 |
2201 if (!_node_potential) { |
2233 if (!_node_potential) { |
2202 _node_potential = new NodePotential(_graph); |
2234 _node_potential = new NodePotential(_graph); |
2203 } |
2235 } |
|
2236 |
2204 if (!_blossom_set) { |
2237 if (!_blossom_set) { |
2205 _blossom_index = new IntNodeMap(_graph); |
2238 _blossom_index = new IntNodeMap(_graph); |
2206 _blossom_set = new BlossomSet(*_blossom_index); |
2239 _blossom_set = new BlossomSet(*_blossom_index); |
|
2240 _blossom_data = new RangeMap<BlossomData>(_blossom_num); |
|
2241 } else if (_blossom_data->size() != _blossom_num) { |
|
2242 delete _blossom_data; |
2207 _blossom_data = new RangeMap<BlossomData>(_blossom_num); |
2243 _blossom_data = new RangeMap<BlossomData>(_blossom_num); |
2208 } |
2244 } |
2209 |
2245 |
2210 if (!_node_index) { |
2246 if (!_node_index) { |
2211 _node_index = new IntNodeMap(_graph); |
2247 _node_index = new IntNodeMap(_graph); |
2212 _node_heap_index = new IntArcMap(_graph); |
2248 _node_heap_index = new IntArcMap(_graph); |
2213 _node_data = new RangeMap<NodeData>(_node_num, |
2249 _node_data = new RangeMap<NodeData>(_node_num, |
2214 NodeData(*_node_heap_index)); |
2250 NodeData(*_node_heap_index)); |
|
2251 } else if (_node_data->size() != _node_num) { |
|
2252 delete _node_data; |
|
2253 _node_data = new RangeMap<NodeData>(_node_num, |
|
2254 NodeData(*_node_heap_index)); |
2215 } |
2255 } |
2216 |
2256 |
2217 if (!_tree_set) { |
2257 if (!_tree_set) { |
2218 _tree_set_index = new IntIntMap(_blossom_num); |
2258 _tree_set_index = new IntIntMap(_blossom_num); |
2219 _tree_set = new TreeSet(*_tree_set_index); |
2259 _tree_set = new TreeSet(*_tree_set_index); |
2220 } |
2260 } else { |
|
2261 _tree_set_index->resize(_blossom_num); |
|
2262 } |
|
2263 |
2221 if (!_delta2) { |
2264 if (!_delta2) { |
2222 _delta2_index = new IntIntMap(_blossom_num); |
2265 _delta2_index = new IntIntMap(_blossom_num); |
2223 _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index); |
2266 _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index); |
2224 } |
2267 } else { |
|
2268 _delta2_index->resize(_blossom_num); |
|
2269 } |
|
2270 |
2225 if (!_delta3) { |
2271 if (!_delta3) { |
2226 _delta3_index = new IntEdgeMap(_graph); |
2272 _delta3_index = new IntEdgeMap(_graph); |
2227 _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index); |
2273 _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index); |
2228 } |
2274 } |
|
2275 |
2229 if (!_delta4) { |
2276 if (!_delta4) { |
2230 _delta4_index = new IntIntMap(_blossom_num); |
2277 _delta4_index = new IntIntMap(_blossom_num); |
2231 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index); |
2278 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index); |
|
2279 } else { |
|
2280 _delta4_index->resize(_blossom_num); |
2232 } |
2281 } |
2233 } |
2282 } |
2234 |
2283 |
2235 void destroyStructures() { |
2284 void destroyStructures() { |
2236 _node_num = countNodes(_graph); |
2285 _node_num = countNodes(_graph); |
2924 /// |
2973 /// |
2925 /// This function initializes the algorithm. |
2974 /// This function initializes the algorithm. |
2926 void init() { |
2975 void init() { |
2927 createStructures(); |
2976 createStructures(); |
2928 |
2977 |
|
2978 _blossom_node_list.clear(); |
|
2979 _blossom_potential.clear(); |
|
2980 |
2929 for (ArcIt e(_graph); e != INVALID; ++e) { |
2981 for (ArcIt e(_graph); e != INVALID; ++e) { |
2930 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
2982 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
2931 } |
2983 } |
2932 for (EdgeIt e(_graph); e != INVALID; ++e) { |
2984 for (EdgeIt e(_graph); e != INVALID; ++e) { |
2933 (*_delta3_index)[e] = _delta3->PRE_HEAP; |
2985 (*_delta3_index)[e] = _delta3->PRE_HEAP; |
2934 } |
2986 } |
2935 for (int i = 0; i < _blossom_num; ++i) { |
2987 for (int i = 0; i < _blossom_num; ++i) { |
2936 (*_delta2_index)[i] = _delta2->PRE_HEAP; |
2988 (*_delta2_index)[i] = _delta2->PRE_HEAP; |
2937 (*_delta4_index)[i] = _delta4->PRE_HEAP; |
2989 (*_delta4_index)[i] = _delta4->PRE_HEAP; |
2938 } |
2990 } |
|
2991 |
|
2992 _delta2->clear(); |
|
2993 _delta3->clear(); |
|
2994 _delta4->clear(); |
|
2995 _blossom_set->clear(); |
|
2996 _tree_set->clear(); |
2939 |
2997 |
2940 int index = 0; |
2998 int index = 0; |
2941 for (NodeIt n(_graph); n != INVALID; ++n) { |
2999 for (NodeIt n(_graph); n != INVALID; ++n) { |
2942 Value max = - std::numeric_limits<Value>::max(); |
3000 Value max = - std::numeric_limits<Value>::max(); |
2943 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
3001 for (OutArcIt e(_graph, n); e != INVALID; ++e) { |
2945 if ((dualScale * _weight[e]) / 2 > max) { |
3003 if ((dualScale * _weight[e]) / 2 > max) { |
2946 max = (dualScale * _weight[e]) / 2; |
3004 max = (dualScale * _weight[e]) / 2; |
2947 } |
3005 } |
2948 } |
3006 } |
2949 (*_node_index)[n] = index; |
3007 (*_node_index)[n] = index; |
|
3008 (*_node_data)[index].heap_index.clear(); |
|
3009 (*_node_data)[index].heap.clear(); |
2950 (*_node_data)[index].pot = max; |
3010 (*_node_data)[index].pot = max; |
2951 int blossom = |
3011 int blossom = |
2952 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
3012 _blossom_set->insert(n, std::numeric_limits<Value>::max()); |
2953 |
3013 |
2954 _tree_set->insert(blossom); |
3014 _tree_set->insert(blossom); |