r962:07ec2b52e53d
Wed, 17 Mar 2010 10:29:57
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -801,59 +801,78 @@ |
| 801 | 801 |
int _unmatched; |
| 802 | 802 |
|
| 803 | 803 |
typedef MaxWeightedFractionalMatching<Graph, WeightMap> FractionalMatching; |
| 804 | 804 |
FractionalMatching *_fractional; |
| 805 | 805 |
|
| 806 | 806 |
void createStructures() {
|
| 807 | 807 |
_node_num = countNodes(_graph); |
| 808 | 808 |
_blossom_num = _node_num * 3 / 2; |
| 809 | 809 |
|
| 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 |
|
|
| 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 |
|
| 851 | 870 |
void destroyStructures() {
|
| 852 | 871 |
if (_matching) {
|
| 853 | 872 |
delete _matching; |
| 854 | 873 |
} |
| 855 | 874 |
if (_node_potential) {
|
| 856 | 875 |
delete _node_potential; |
| 857 | 876 |
} |
| 858 | 877 |
if (_blossom_set) {
|
| 859 | 878 |
delete _blossom_index; |
| ... | ... |
@@ -1579,50 +1598,62 @@ |
| 1579 | 1598 |
/// \name Execution Control |
| 1580 | 1599 |
/// The simplest way to execute the algorithm is to use the |
| 1581 | 1600 |
/// \ref run() member function. |
| 1582 | 1601 |
|
| 1583 | 1602 |
///@{
|
| 1584 | 1603 |
|
| 1585 | 1604 |
/// \brief Initialize the algorithm |
| 1586 | 1605 |
/// |
| 1587 | 1606 |
/// This function initializes the algorithm. |
| 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 |
} |
| 1594 | 1616 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 1595 | 1617 |
(*_delta1_index)[n] = _delta1->PRE_HEAP; |
| 1596 | 1618 |
} |
| 1597 | 1619 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 1598 | 1620 |
(*_delta3_index)[e] = _delta3->PRE_HEAP; |
| 1599 | 1621 |
} |
| 1600 | 1622 |
for (int i = 0; i < _blossom_num; ++i) {
|
| 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; |
| 1610 | 1639 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 1611 | 1640 |
if (_graph.target(e) == n) continue; |
| 1612 | 1641 |
if ((dualScale * _weight[e]) / 2 > max) {
|
| 1613 | 1642 |
max = (dualScale * _weight[e]) / 2; |
| 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 = |
| 1620 | 1651 |
_blossom_set->insert(n, std::numeric_limits<Value>::max()); |
| 1621 | 1652 |
|
| 1622 | 1653 |
_tree_set->insert(blossom); |
| 1623 | 1654 |
|
| 1624 | 1655 |
(*_blossom_data)[blossom].status = EVEN; |
| 1625 | 1656 |
(*_blossom_data)[blossom].pred = INVALID; |
| 1626 | 1657 |
(*_blossom_data)[blossom].next = INVALID; |
| 1627 | 1658 |
(*_blossom_data)[blossom].pot = 0; |
| 1628 | 1659 |
(*_blossom_data)[blossom].offset = 0; |
| ... | ... |
@@ -2228,55 +2259,73 @@ |
| 2228 | 2259 |
|
| 2229 | 2260 |
typedef MaxWeightedPerfectFractionalMatching<Graph, WeightMap> |
| 2230 | 2261 |
FractionalMatching; |
| 2231 | 2262 |
FractionalMatching *_fractional; |
| 2232 | 2263 |
|
| 2233 | 2264 |
void createStructures() {
|
| 2234 | 2265 |
_node_num = countNodes(_graph); |
| 2235 | 2266 |
_blossom_num = _node_num * 3 / 2; |
| 2236 | 2267 |
|
| 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) {
|
| 2250 | 2286 |
_node_index = new IntNodeMap(_graph); |
| 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 |
|
| 2274 | 2323 |
void destroyStructures() {
|
| 2275 | 2324 |
if (_matching) {
|
| 2276 | 2325 |
delete _matching; |
| 2277 | 2326 |
} |
| 2278 | 2327 |
if (_node_potential) {
|
| 2279 | 2328 |
delete _node_potential; |
| 2280 | 2329 |
} |
| 2281 | 2330 |
if (_blossom_set) {
|
| 2282 | 2331 |
delete _blossom_index; |
| ... | ... |
@@ -2959,47 +3008,58 @@ |
| 2959 | 3008 |
/// \name Execution Control |
| 2960 | 3009 |
/// The simplest way to execute the algorithm is to use the |
| 2961 | 3010 |
/// \ref run() member function. |
| 2962 | 3011 |
|
| 2963 | 3012 |
///@{
|
| 2964 | 3013 |
|
| 2965 | 3014 |
/// \brief Initialize the algorithm |
| 2966 | 3015 |
/// |
| 2967 | 3016 |
/// This function initializes the algorithm. |
| 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 |
} |
| 2974 | 3026 |
for (EdgeIt e(_graph); e != INVALID; ++e) {
|
| 2975 | 3027 |
(*_delta3_index)[e] = _delta3->PRE_HEAP; |
| 2976 | 3028 |
} |
| 2977 | 3029 |
for (int i = 0; i < _blossom_num; ++i) {
|
| 2978 | 3030 |
(*_delta2_index)[i] = _delta2->PRE_HEAP; |
| 2979 | 3031 |
(*_delta4_index)[i] = _delta4->PRE_HEAP; |
| 2980 | 3032 |
} |
| 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(); |
| 2987 | 3045 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 2988 | 3046 |
if (_graph.target(e) == n) continue; |
| 2989 | 3047 |
if ((dualScale * _weight[e]) / 2 > max) {
|
| 2990 | 3048 |
max = (dualScale * _weight[e]) / 2; |
| 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()); |
| 2997 | 3057 |
|
| 2998 | 3058 |
_tree_set->insert(blossom); |
| 2999 | 3059 |
|
| 3000 | 3060 |
(*_blossom_data)[blossom].status = EVEN; |
| 3001 | 3061 |
(*_blossom_data)[blossom].pred = INVALID; |
| 3002 | 3062 |
(*_blossom_data)[blossom].next = INVALID; |
| 3003 | 3063 |
(*_blossom_data)[blossom].pot = 0; |
| 3004 | 3064 |
(*_blossom_data)[blossom].offset = 0; |
| 3005 | 3065 |
++index; |
| ... | ... |
@@ -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)