Changeset 628:aa1804409f29 in lemon for lemon/max_matching.h
- Timestamp:
- 04/14/09 10:35:38 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/max_matching.h
r606 r628 283 283 284 284 while (base != nca) { 285 _ear->set(node, arc);285 (*_ear)[node] = arc; 286 286 287 287 Node n = node; … … 290 290 Arc a = (*_ear)[n]; 291 291 n = _graph.target(a); 292 _ear->set(n, _graph.oppositeArc(a));292 (*_ear)[n] = _graph.oppositeArc(a); 293 293 } 294 294 node = _graph.target((*_matching)[base]); … … 296 296 _tree_set->erase(node); 297 297 _blossom_set->insert(node, _blossom_set->find(base)); 298 _status->set(node, EVEN);298 (*_status)[node] = EVEN; 299 299 _node_queue[_last++] = node; 300 300 arc = _graph.oppositeArc((*_ear)[node]); … … 305 305 } 306 306 307 _blossom_rep->set(_blossom_set->find(nca), nca);307 (*_blossom_rep)[_blossom_set->find(nca)] = nca; 308 308 309 309 { … … 314 314 315 315 while (base != nca) { 316 _ear->set(node, arc);316 (*_ear)[node] = arc; 317 317 318 318 Node n = node; … … 321 321 Arc a = (*_ear)[n]; 322 322 n = _graph.target(a); 323 _ear->set(n, _graph.oppositeArc(a));323 (*_ear)[n] = _graph.oppositeArc(a); 324 324 } 325 325 node = _graph.target((*_matching)[base]); … … 327 327 _tree_set->erase(node); 328 328 _blossom_set->insert(node, _blossom_set->find(base)); 329 _status->set(node, EVEN);329 (*_status)[node] = EVEN; 330 330 _node_queue[_last++] = node; 331 331 arc = _graph.oppositeArc((*_ear)[node]); … … 336 336 } 337 337 338 _blossom_rep->set(_blossom_set->find(nca), nca);338 (*_blossom_rep)[_blossom_set->find(nca)] = nca; 339 339 } 340 340 … … 345 345 Node odd = _graph.target(a); 346 346 347 _ear->set(odd, _graph.oppositeArc(a));347 (*_ear)[odd] = _graph.oppositeArc(a); 348 348 Node even = _graph.target((*_matching)[odd]); 349 _blossom_rep->set(_blossom_set->insert(even), even);350 _status->set(odd, ODD);351 _status->set(even, EVEN);349 (*_blossom_rep)[_blossom_set->insert(even)] = even; 350 (*_status)[odd] = ODD; 351 (*_status)[even] = EVEN; 352 352 int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(base)]); 353 353 _tree_set->insert(odd, tree); … … 363 363 int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(even)]); 364 364 365 _matching->set(odd, _graph.oppositeArc(a));366 _status->set(odd, MATCHED);365 (*_matching)[odd] = _graph.oppositeArc(a); 366 (*_status)[odd] = MATCHED; 367 367 368 368 Arc arc = (*_matching)[even]; 369 _matching->set(even, a);369 (*_matching)[even] = a; 370 370 371 371 while (arc != INVALID) { … … 373 373 arc = (*_ear)[odd]; 374 374 even = _graph.target(arc); 375 _matching->set(odd, arc);375 (*_matching)[odd] = arc; 376 376 arc = (*_matching)[even]; 377 _matching->set(even, _graph.oppositeArc((*_matching)[odd]));377 (*_matching)[even] = _graph.oppositeArc((*_matching)[odd]); 378 378 } 379 379 … … 381 381 it != INVALID; ++it) { 382 382 if ((*_status)[it] == ODD) { 383 _status->set(it, MATCHED);383 (*_status)[it] = MATCHED; 384 384 } else { 385 385 int blossom = _blossom_set->find(it); 386 386 for (typename BlossomSet::ItemIt jt(*_blossom_set, blossom); 387 387 jt != INVALID; ++jt) { 388 _status->set(jt, MATCHED);388 (*_status)[jt] = MATCHED; 389 389 } 390 390 _blossom_set->eraseClass(blossom); … … 428 428 createStructures(); 429 429 for(NodeIt n(_graph); n != INVALID; ++n) { 430 _matching->set(n, INVALID);431 _status->set(n, UNMATCHED);430 (*_matching)[n] = INVALID; 431 (*_status)[n] = UNMATCHED; 432 432 } 433 433 } … … 439 439 createStructures(); 440 440 for (NodeIt n(_graph); n != INVALID; ++n) { 441 _matching->set(n, INVALID);442 _status->set(n, UNMATCHED);441 (*_matching)[n] = INVALID; 442 (*_status)[n] = UNMATCHED; 443 443 } 444 444 for (NodeIt n(_graph); n != INVALID; ++n) { … … 447 447 Node v = _graph.target(a); 448 448 if ((*_matching)[v] == INVALID && v != n) { 449 _matching->set(n, a);450 _status->set(n, MATCHED);451 _matching->set(v, _graph.oppositeArc(a));452 _status->set(v, MATCHED);449 (*_matching)[n] = a; 450 (*_status)[n] = MATCHED; 451 (*_matching)[v] = _graph.oppositeArc(a); 452 (*_status)[v] = MATCHED; 453 453 break; 454 454 } … … 470 470 471 471 for (NodeIt n(_graph); n != INVALID; ++n) { 472 _matching->set(n, INVALID);473 _status->set(n, UNMATCHED);472 (*_matching)[n] = INVALID; 473 (*_status)[n] = UNMATCHED; 474 474 } 475 475 for(EdgeIt e(_graph); e!=INVALID; ++e) { … … 478 478 Node u = _graph.u(e); 479 479 if ((*_matching)[u] != INVALID) return false; 480 _matching->set(u, _graph.direct(e, true));481 _status->set(u, MATCHED);480 (*_matching)[u] = _graph.direct(e, true); 481 (*_status)[u] = MATCHED; 482 482 483 483 Node v = _graph.v(e); 484 484 if ((*_matching)[v] != INVALID) return false; 485 _matching->set(v, _graph.direct(e, false));486 _status->set(v, MATCHED);485 (*_matching)[v] = _graph.direct(e, false); 486 (*_status)[v] = MATCHED; 487 487 } 488 488 } … … 498 498 (*_blossom_rep)[_blossom_set->insert(n)] = n; 499 499 _tree_set->insert(n); 500 _status->set(n, EVEN);500 (*_status)[n] = EVEN; 501 501 processSparse(n); 502 502 } … … 513 513 (*_blossom_rep)[_blossom_set->insert(n)] = n; 514 514 _tree_set->insert(n); 515 _status->set(n, EVEN);515 (*_status)[n] = EVEN; 516 516 processDense(n); 517 517 } … … 1549 1549 Value pot = (*_node_data)[bi].pot; 1550 1550 1551 _matching->set(base, matching);1551 (*_matching)[base] = matching; 1552 1552 _blossom_node_list.push_back(base); 1553 _node_potential->set(base, pot);1553 (*_node_potential)[base] = pot; 1554 1554 } else { 1555 1555 … … 1645 1645 1646 1646 for (ArcIt e(_graph); e != INVALID; ++e) { 1647 _node_heap_index->set(e, BinHeap<Value, IntArcMap>::PRE_HEAP);1647 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; 1648 1648 } 1649 1649 for (NodeIt n(_graph); n != INVALID; ++n) { 1650 _delta1_index->set(n, _delta1->PRE_HEAP);1650 (*_delta1_index)[n] = _delta1->PRE_HEAP; 1651 1651 } 1652 1652 for (EdgeIt e(_graph); e != INVALID; ++e) { 1653 _delta3_index->set(e, _delta3->PRE_HEAP);1653 (*_delta3_index)[e] = _delta3->PRE_HEAP; 1654 1654 } 1655 1655 for (int i = 0; i < _blossom_num; ++i) { 1656 _delta2_index->set(i, _delta2->PRE_HEAP);1657 _delta4_index->set(i, _delta4->PRE_HEAP);1656 (*_delta2_index)[i] = _delta2->PRE_HEAP; 1657 (*_delta4_index)[i] = _delta4->PRE_HEAP; 1658 1658 } 1659 1659 … … 1667 1667 } 1668 1668 } 1669 _node_index->set(n, index);1669 (*_node_index)[n] = index; 1670 1670 (*_node_data)[index].pot = max; 1671 1671 _delta1->push(n, max); … … 2742 2742 Value pot = (*_node_data)[bi].pot; 2743 2743 2744 _matching->set(base, matching);2744 (*_matching)[base] = matching; 2745 2745 _blossom_node_list.push_back(base); 2746 _node_potential->set(base, pot);2746 (*_node_potential)[base] = pot; 2747 2747 } else { 2748 2748 … … 2832 2832 2833 2833 for (ArcIt e(_graph); e != INVALID; ++e) { 2834 _node_heap_index->set(e, BinHeap<Value, IntArcMap>::PRE_HEAP);2834 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP; 2835 2835 } 2836 2836 for (EdgeIt e(_graph); e != INVALID; ++e) { 2837 _delta3_index->set(e, _delta3->PRE_HEAP);2837 (*_delta3_index)[e] = _delta3->PRE_HEAP; 2838 2838 } 2839 2839 for (int i = 0; i < _blossom_num; ++i) { 2840 _delta2_index->set(i, _delta2->PRE_HEAP);2841 _delta4_index->set(i, _delta4->PRE_HEAP);2840 (*_delta2_index)[i] = _delta2->PRE_HEAP; 2841 (*_delta4_index)[i] = _delta4->PRE_HEAP; 2842 2842 } 2843 2843 … … 2851 2851 } 2852 2852 } 2853 _node_index->set(n, index);2853 (*_node_index)[n] = index; 2854 2854 (*_node_data)[index].pot = max; 2855 2855 int blossom =
Note: See TracChangeset
for help on using the changeset viewer.