r914:5b926cc36a4b
Tue, 16 Mar 2010 21:12:10
[Not Reviewed]
0 comments (0 inline)
0
2
0
61
1
| ... | ... |
@@ -796,59 +796,78 @@ |
| 796 | 796 |
IntIntMap *_delta4_index; |
| 797 | 797 |
BinHeap<Value, IntIntMap> *_delta4; |
| 798 | 798 |
|
| 799 | 799 |
Value _delta_sum; |
| 800 | 800 |
|
| 801 | 801 |
void createStructures() {
|
| 802 | 802 |
_node_num = countNodes(_graph); |
| 803 | 803 |
_blossom_num = _node_num * 3 / 2; |
| 804 | 804 |
|
| 805 | 805 |
if (!_matching) {
|
| 806 | 806 |
_matching = new MatchingMap(_graph); |
| 807 | 807 |
} |
| 808 |
|
|
| 808 | 809 |
if (!_node_potential) {
|
| 809 | 810 |
_node_potential = new NodePotential(_graph); |
| 810 | 811 |
} |
| 812 |
|
|
| 811 | 813 |
if (!_blossom_set) {
|
| 812 | 814 |
_blossom_index = new IntNodeMap(_graph); |
| 813 | 815 |
_blossom_set = new BlossomSet(*_blossom_index); |
| 814 | 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 | 822 |
if (!_node_index) {
|
| 818 | 823 |
_node_index = new IntNodeMap(_graph); |
| 819 | 824 |
_node_heap_index = new IntArcMap(_graph); |
| 820 | 825 |
_node_data = new RangeMap<NodeData>(_node_num, |
| 821 |
|
|
| 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 | 833 |
if (!_tree_set) {
|
| 825 | 834 |
_tree_set_index = new IntIntMap(_blossom_num); |
| 826 | 835 |
_tree_set = new TreeSet(*_tree_set_index); |
| 836 |
} else {
|
|
| 837 |
_tree_set_index->resize(_blossom_num); |
|
| 827 | 838 |
} |
| 839 |
|
|
| 828 | 840 |
if (!_delta1) {
|
| 829 | 841 |
_delta1_index = new IntNodeMap(_graph); |
| 830 | 842 |
_delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index); |
| 831 | 843 |
} |
| 844 |
|
|
| 832 | 845 |
if (!_delta2) {
|
| 833 | 846 |
_delta2_index = new IntIntMap(_blossom_num); |
| 834 | 847 |
_delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index); |
| 848 |
} else {
|
|
| 849 |
_delta2_index->resize(_blossom_num); |
|
| 835 | 850 |
} |
| 851 |
|
|
| 836 | 852 |
if (!_delta3) {
|
| 837 | 853 |
_delta3_index = new IntEdgeMap(_graph); |
| 838 | 854 |
_delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index); |
| 839 | 855 |
} |
| 856 |
|
|
| 840 | 857 |
if (!_delta4) {
|
| 841 | 858 |
_delta4_index = new IntIntMap(_blossom_num); |
| 842 | 859 |
_delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index); |
| 860 |
} else {
|
|
| 861 |
_delta4_index->resize(_blossom_num); |
|
| 843 | 862 |
} |
| 844 | 863 |
} |
| 845 | 864 |
|
| 846 | 865 |
void destroyStructures() {
|
| 847 | 866 |
_node_num = countNodes(_graph); |
| 848 | 867 |
_blossom_num = _node_num * 3 / 2; |
| 849 | 868 |
|
| 850 | 869 |
if (_matching) {
|
| 851 | 870 |
delete _matching; |
| 852 | 871 |
} |
| 853 | 872 |
if (_node_potential) {
|
| 854 | 873 |
delete _node_potential; |
| ... | ... |
@@ -1676,48 +1695,60 @@ |
| 1676 | 1695 |
/// \name Execution Control |
| 1677 | 1696 |
/// The simplest way to execute the algorithm is to use the |
| 1678 | 1697 |
/// \ref run() member function. |
| 1679 | 1698 |
|
| 1680 | 1699 |
///@{
|
| 1681 | 1700 |
|
| 1682 | 1701 |
/// \brief Initialize the algorithm |
| 1683 | 1702 |
/// |
| 1684 | 1703 |
/// This function initializes the algorithm. |
| 1685 | 1704 |
void init() {
|
| 1686 | 1705 |
createStructures(); |
| 1687 | 1706 |
|
| 1707 |
_blossom_node_list.clear(); |
|
| 1708 |
_blossom_potential.clear(); |
|
| 1709 |
|
|
| 1688 | 1710 |
for (ArcIt e(_graph); e != INVALID; ++e) {
|
| 1689 | 1711 |
(*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
| 1690 | 1712 |
} |
| 1691 | 1713 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1692 | 1714 |
(*_delta1_index)[n] = _delta1->PRE_HEAP; |
| 1693 | 1715 |
} |
| 1694 | 1716 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 1695 | 1717 |
(*_delta3_index)[e] = _delta3->PRE_HEAP; |
| 1696 | 1718 |
} |
| 1697 | 1719 |
for (int i = 0; i < _blossom_num; ++i) {
|
| 1698 | 1720 |
(*_delta2_index)[i] = _delta2->PRE_HEAP; |
| 1699 | 1721 |
(*_delta4_index)[i] = _delta4->PRE_HEAP; |
| 1700 | 1722 |
} |
| 1723 |
|
|
| 1724 |
_delta1->clear(); |
|
| 1725 |
_delta2->clear(); |
|
| 1726 |
_delta3->clear(); |
|
| 1727 |
_delta4->clear(); |
|
| 1728 |
_blossom_set->clear(); |
|
| 1729 |
_tree_set->clear(); |
|
| 1701 | 1730 |
|
| 1702 | 1731 |
int index = 0; |
| 1703 | 1732 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1704 | 1733 |
Value max = 0; |
| 1705 | 1734 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 1706 | 1735 |
if (_graph.target(e) == n) continue; |
| 1707 | 1736 |
if ((dualScale * _weight[e]) / 2 > max) {
|
| 1708 | 1737 |
max = (dualScale * _weight[e]) / 2; |
| 1709 | 1738 |
} |
| 1710 | 1739 |
} |
| 1711 | 1740 |
(*_node_index)[n] = index; |
| 1741 |
(*_node_data)[index].heap_index.clear(); |
|
| 1742 |
(*_node_data)[index].heap.clear(); |
|
| 1712 | 1743 |
(*_node_data)[index].pot = max; |
| 1713 | 1744 |
_delta1->push(n, max); |
| 1714 | 1745 |
int blossom = |
| 1715 | 1746 |
_blossom_set->insert(n, std::numeric_limits<Value>::max()); |
| 1716 | 1747 |
|
| 1717 | 1748 |
_tree_set->insert(blossom); |
| 1718 | 1749 |
|
| 1719 | 1750 |
(*_blossom_data)[blossom].status = EVEN; |
| 1720 | 1751 |
(*_blossom_data)[blossom].pred = INVALID; |
| 1721 | 1752 |
(*_blossom_data)[blossom].next = INVALID; |
| 1722 | 1753 |
(*_blossom_data)[blossom].pot = 0; |
| 1723 | 1754 |
(*_blossom_data)[blossom].offset = 0; |
| ... | ... |
@@ -2189,55 +2220,73 @@ |
| 2189 | 2220 |
IntIntMap *_delta4_index; |
| 2190 | 2221 |
BinHeap<Value, IntIntMap> *_delta4; |
| 2191 | 2222 |
|
| 2192 | 2223 |
Value _delta_sum; |
| 2193 | 2224 |
|
| 2194 | 2225 |
void createStructures() {
|
| 2195 | 2226 |
_node_num = countNodes(_graph); |
| 2196 | 2227 |
_blossom_num = _node_num * 3 / 2; |
| 2197 | 2228 |
|
| 2198 | 2229 |
if (!_matching) {
|
| 2199 | 2230 |
_matching = new MatchingMap(_graph); |
| 2200 | 2231 |
} |
| 2232 |
|
|
| 2201 | 2233 |
if (!_node_potential) {
|
| 2202 | 2234 |
_node_potential = new NodePotential(_graph); |
| 2203 | 2235 |
} |
| 2236 |
|
|
| 2204 | 2237 |
if (!_blossom_set) {
|
| 2205 | 2238 |
_blossom_index = new IntNodeMap(_graph); |
| 2206 | 2239 |
_blossom_set = new BlossomSet(*_blossom_index); |
| 2207 | 2240 |
_blossom_data = new RangeMap<BlossomData>(_blossom_num); |
| 2241 |
} else if (_blossom_data->size() != _blossom_num) {
|
|
| 2242 |
delete _blossom_data; |
|
| 2243 |
_blossom_data = new RangeMap<BlossomData>(_blossom_num); |
|
| 2208 | 2244 |
} |
| 2209 | 2245 |
|
| 2210 | 2246 |
if (!_node_index) {
|
| 2211 | 2247 |
_node_index = new IntNodeMap(_graph); |
| 2212 | 2248 |
_node_heap_index = new IntArcMap(_graph); |
| 2213 | 2249 |
_node_data = new RangeMap<NodeData>(_node_num, |
| 2214 | 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 | 2257 |
if (!_tree_set) {
|
| 2218 | 2258 |
_tree_set_index = new IntIntMap(_blossom_num); |
| 2219 | 2259 |
_tree_set = new TreeSet(*_tree_set_index); |
| 2260 |
} else {
|
|
| 2261 |
_tree_set_index->resize(_blossom_num); |
|
| 2220 | 2262 |
} |
| 2263 |
|
|
| 2221 | 2264 |
if (!_delta2) {
|
| 2222 | 2265 |
_delta2_index = new IntIntMap(_blossom_num); |
| 2223 | 2266 |
_delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index); |
| 2267 |
} else {
|
|
| 2268 |
_delta2_index->resize(_blossom_num); |
|
| 2224 | 2269 |
} |
| 2270 |
|
|
| 2225 | 2271 |
if (!_delta3) {
|
| 2226 | 2272 |
_delta3_index = new IntEdgeMap(_graph); |
| 2227 | 2273 |
_delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index); |
| 2228 | 2274 |
} |
| 2275 |
|
|
| 2229 | 2276 |
if (!_delta4) {
|
| 2230 | 2277 |
_delta4_index = new IntIntMap(_blossom_num); |
| 2231 | 2278 |
_delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index); |
| 2279 |
} else {
|
|
| 2280 |
_delta4_index->resize(_blossom_num); |
|
| 2232 | 2281 |
} |
| 2233 | 2282 |
} |
| 2234 | 2283 |
|
| 2235 | 2284 |
void destroyStructures() {
|
| 2236 | 2285 |
_node_num = countNodes(_graph); |
| 2237 | 2286 |
_blossom_num = _node_num * 3 / 2; |
| 2238 | 2287 |
|
| 2239 | 2288 |
if (_matching) {
|
| 2240 | 2289 |
delete _matching; |
| 2241 | 2290 |
} |
| 2242 | 2291 |
if (_node_potential) {
|
| 2243 | 2292 |
delete _node_potential; |
| ... | ... |
@@ -2917,45 +2966,56 @@ |
| 2917 | 2966 |
/// \name Execution Control |
| 2918 | 2967 |
/// The simplest way to execute the algorithm is to use the |
| 2919 | 2968 |
/// \ref run() member function. |
| 2920 | 2969 |
|
| 2921 | 2970 |
///@{
|
| 2922 | 2971 |
|
| 2923 | 2972 |
/// \brief Initialize the algorithm |
| 2924 | 2973 |
/// |
| 2925 | 2974 |
/// This function initializes the algorithm. |
| 2926 | 2975 |
void init() {
|
| 2927 | 2976 |
createStructures(); |
| 2928 | 2977 |
|
| 2978 |
_blossom_node_list.clear(); |
|
| 2979 |
_blossom_potential.clear(); |
|
| 2980 |
|
|
| 2929 | 2981 |
for (ArcIt e(_graph); e != INVALID; ++e) {
|
| 2930 | 2982 |
(*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; |
| 2931 | 2983 |
} |
| 2932 | 2984 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 2933 | 2985 |
(*_delta3_index)[e] = _delta3->PRE_HEAP; |
| 2934 | 2986 |
} |
| 2935 | 2987 |
for (int i = 0; i < _blossom_num; ++i) {
|
| 2936 | 2988 |
(*_delta2_index)[i] = _delta2->PRE_HEAP; |
| 2937 | 2989 |
(*_delta4_index)[i] = _delta4->PRE_HEAP; |
| 2938 | 2990 |
} |
| 2939 | 2991 |
|
| 2992 |
_delta2->clear(); |
|
| 2993 |
_delta3->clear(); |
|
| 2994 |
_delta4->clear(); |
|
| 2995 |
_blossom_set->clear(); |
|
| 2996 |
_tree_set->clear(); |
|
| 2997 |
|
|
| 2940 | 2998 |
int index = 0; |
| 2941 | 2999 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 2942 | 3000 |
Value max = - std::numeric_limits<Value>::max(); |
| 2943 | 3001 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 2944 | 3002 |
if (_graph.target(e) == n) continue; |
| 2945 | 3003 |
if ((dualScale * _weight[e]) / 2 > max) {
|
| 2946 | 3004 |
max = (dualScale * _weight[e]) / 2; |
| 2947 | 3005 |
} |
| 2948 | 3006 |
} |
| 2949 | 3007 |
(*_node_index)[n] = index; |
| 3008 |
(*_node_data)[index].heap_index.clear(); |
|
| 3009 |
(*_node_data)[index].heap.clear(); |
|
| 2950 | 3010 |
(*_node_data)[index].pot = max; |
| 2951 | 3011 |
int blossom = |
| 2952 | 3012 |
_blossom_set->insert(n, std::numeric_limits<Value>::max()); |
| 2953 | 3013 |
|
| 2954 | 3014 |
_tree_set->insert(blossom); |
| 2955 | 3015 |
|
| 2956 | 3016 |
(*_blossom_data)[blossom].status = EVEN; |
| 2957 | 3017 |
(*_blossom_data)[blossom].pred = INVALID; |
| 2958 | 3018 |
(*_blossom_data)[blossom].next = INVALID; |
| 2959 | 3019 |
(*_blossom_data)[blossom].pot = 0; |
| 2960 | 3020 |
(*_blossom_data)[blossom].offset = 0; |
| 2961 | 3021 |
++index; |
| ... | ... |
@@ -730,25 +730,25 @@ |
| 730 | 730 |
items[idx].next = items[rdx].next; |
| 731 | 731 |
items[items[rdx].next].prev = idx; |
| 732 | 732 |
items[rdx].next = idx; |
| 733 | 733 |
|
| 734 | 734 |
index.set(item, idx); |
| 735 | 735 |
} |
| 736 | 736 |
|
| 737 | 737 |
/// \brief Clears the union-find data structure |
| 738 | 738 |
/// |
| 739 | 739 |
/// Erase each item from the data structure. |
| 740 | 740 |
void clear() {
|
| 741 | 741 |
items.clear(); |
| 742 |
classes.clear; |
|
| 742 |
classes.clear(); |
|
| 743 | 743 |
firstClass = firstFreeClass = firstFreeItem = -1; |
| 744 | 744 |
} |
| 745 | 745 |
|
| 746 | 746 |
/// \brief Gives back the class of the \e item. |
| 747 | 747 |
/// |
| 748 | 748 |
/// Gives back the class of the \e item. |
| 749 | 749 |
int find(const Item &item) const {
|
| 750 | 750 |
return items[index[item]].cls; |
| 751 | 751 |
} |
| 752 | 752 |
|
| 753 | 753 |
/// \brief Gives back a representant item of the component. |
| 754 | 754 |
/// |
| ... | ... |
@@ -1279,24 +1279,33 @@ |
| 1279 | 1279 |
return classes[cls].left == -1; |
| 1280 | 1280 |
} |
| 1281 | 1281 |
|
| 1282 | 1282 |
/// \brief Constructs the union-find. |
| 1283 | 1283 |
/// |
| 1284 | 1284 |
/// Constructs the union-find. |
| 1285 | 1285 |
/// \brief _index The index map of the union-find. The data |
| 1286 | 1286 |
/// structure uses internally for store references. |
| 1287 | 1287 |
HeapUnionFind(ItemIntMap& _index) |
| 1288 | 1288 |
: index(_index), first_class(-1), |
| 1289 | 1289 |
first_free_class(-1), first_free_node(-1) {}
|
| 1290 | 1290 |
|
| 1291 |
/// \brief Clears the union-find data structure |
|
| 1292 |
/// |
|
| 1293 |
/// Erase each item from the data structure. |
|
| 1294 |
void clear() {
|
|
| 1295 |
nodes.clear(); |
|
| 1296 |
classes.clear(); |
|
| 1297 |
first_free_node = first_free_class = first_class = -1; |
|
| 1298 |
} |
|
| 1299 |
|
|
| 1291 | 1300 |
/// \brief Insert a new node into a new component. |
| 1292 | 1301 |
/// |
| 1293 | 1302 |
/// Insert a new node into a new component. |
| 1294 | 1303 |
/// \param item The item of the new node. |
| 1295 | 1304 |
/// \param prio The priority of the new node. |
| 1296 | 1305 |
/// \return The class id of the one-item-heap. |
| 1297 | 1306 |
int insert(const Item& item, const Value& prio) {
|
| 1298 | 1307 |
int id = newNode(); |
| 1299 | 1308 |
nodes[id].item = item; |
| 1300 | 1309 |
nodes[id].prio = prio; |
| 1301 | 1310 |
nodes[id].size = 0; |
| 1302 | 1311 |
|
0 comments (0 inline)