Changeset 2463:19651a04d056 in lemon-0.x
- Timestamp:
- 08/21/07 15:22:21 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3301
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bipartite_matching.h
r2462 r2463 360 360 for (ANodeIt it(*graph); it != INVALID; ++it) { 361 361 if (anode_matching[it] != INVALID) { 362 mm [anode_matching[it]] = true;362 mm.set(anode_matching[it], true); 363 363 } 364 364 } … … 373 373 int matching(MatchingMap& mm) const { 374 374 for (UEdgeIt it(*graph); it != INVALID; ++it) { 375 mm [it] = it == anode_matching[graph->aNode(it)];375 mm.set(it, it == anode_matching[graph->aNode(it)]); 376 376 } 377 377 return matching_size; 378 378 } 379 379 380 ///Gives back the matching in an ANodeMap. 381 382 ///Gives back the matching in an ANodeMap. The parameter should 383 ///be a write ANodeMap of UEdge values. 384 ///\return The number of the matching edges. 385 template<class MatchingMap> 386 int aMatching(MatchingMap& mm) const { 387 for (ANodeIt it(*graph); it != INVALID; ++it) { 388 mm.set(it, anode_matching[it]); 389 } 390 return matching_size; 391 } 392 393 ///Gives back the matching in a BNodeMap. 394 395 ///Gives back the matching in a BNodeMap. The parameter should 396 ///be a write BNodeMap of UEdge values. 397 ///\return The number of the matching edges. 398 template<class MatchingMap> 399 int bMatching(MatchingMap& mm) const { 400 for (BNodeIt it(*graph); it != INVALID; ++it) { 401 mm.set(it, bnode_matching[it]); 402 } 403 return matching_size; 404 } 380 405 381 406 /// \brief Return true if the given uedge is in the matching. … … 446 471 int size = 0; 447 472 for (ANodeIt it(*graph); it != INVALID; ++it) { 448 covering [it] = !areached[it] && anode_matching[it] != INVALID;473 covering.set(it, !areached[it] && anode_matching[it] != INVALID); 449 474 if (!areached[it] && anode_matching[it] != INVALID) { 450 475 ++size; … … 452 477 } 453 478 for (BNodeIt it(*graph); it != INVALID; ++it) { 454 covering [it] = breached[it];479 covering.set(it, breached[it]); 455 480 if (breached[it]) { 456 481 ++size; … … 500 525 501 526 for (ANodeIt it(*graph); it != INVALID; ++it) { 502 barrier [it] = areached[it] || anode_matching[it] == INVALID;527 barrier.set(it, areached[it] || anode_matching[it] == INVALID); 503 528 } 504 529 } … … 544 569 545 570 for (BNodeIt it(*graph); it != INVALID; ++it) { 546 barrier [it] = !breached[it];571 barrier.set(it, !breached[it]); 547 572 } 548 573 } … … 569 594 /// 570 595 /// \param graph The bipartite graph. 571 /// \retval matching The undirected edge map which will be set to 572 /// the matching. 596 /// \return The size of the matching. 597 template <typename BpUGraph> 598 int maxBipartiteMatching(const BpUGraph& graph) { 599 MaxBipartiteMatching<BpUGraph> bpmatching(graph); 600 bpmatching.run(); 601 return bpmatching.matchingSize(); 602 } 603 604 /// \ingroup matching 605 /// 606 /// \brief Maximum cardinality bipartite matching 607 /// 608 /// This function calculates the maximum cardinality matching 609 /// in a bipartite graph. It gives back the matching in an undirected 610 /// edge map. 611 /// 612 /// \param graph The bipartite graph. 613 /// \retval matching The ANodeMap of UEdges which will be set to covered 614 /// matching undirected edge. 573 615 /// \return The size of the matching. 574 616 template <typename BpUGraph, typename MatchingMap> … … 576 618 MaxBipartiteMatching<BpUGraph> bpmatching(graph); 577 619 bpmatching.run(); 578 bpmatching.matching(matching); 620 bpmatching.aMatching(matching); 621 return bpmatching.matchingSize(); 622 } 623 624 /// \ingroup matching 625 /// 626 /// \brief Maximum cardinality bipartite matching 627 /// 628 /// This function calculates the maximum cardinality matching 629 /// in a bipartite graph. It gives back the matching in an undirected 630 /// edge map. 631 /// 632 /// \param graph The bipartite graph. 633 /// \retval matching The ANodeMap of UEdges which will be set to covered 634 /// matching undirected edge. 635 /// \retval barrier The BNodeMap of bools which will be set to a barrier 636 /// of the BNode-set. 637 /// \return The size of the matching. 638 template <typename BpUGraph, typename MatchingMap, typename BarrierMap> 639 int maxBipartiteMatching(const BpUGraph& graph, 640 MatchingMap& matching, BarrierMap& barrier) { 641 MaxBipartiteMatching<BpUGraph> bpmatching(graph); 642 bpmatching.run(); 643 bpmatching.aMatching(matching); 644 bpmatching.bBarrier(barrier); 579 645 return bpmatching.matchingSize(); 580 646 } … … 988 1054 void potential(PotentialMap& pt) const { 989 1055 for (ANodeIt it(*graph); it != INVALID; ++it) { 990 pt [it] = anode_potential[it];1056 pt.set(it, anode_potential[it]); 991 1057 } 992 1058 for (BNodeIt it(*graph); it != INVALID; ++it) { 993 pt [it] = bnode_potential[it];1059 pt.set(it, bnode_potential[it]); 994 1060 } 995 1061 } … … 1004 1070 for (ANodeIt it(*graph); it != INVALID; ++it) { 1005 1071 if (anode_matching[it] != INVALID) { 1006 mm [anode_matching[it]] = true;1072 mm.set(anode_matching[it], true); 1007 1073 } 1008 1074 } … … 1017 1083 int matching(MatchingMap& mm) const { 1018 1084 for (UEdgeIt it(*graph); it != INVALID; ++it) { 1019 mm[it] = it == anode_matching[graph->aNode(it)]; 1085 mm.set(it, it == anode_matching[graph->aNode(it)]); 1086 } 1087 return matching_size; 1088 } 1089 1090 ///Gives back the matching in an ANodeMap. 1091 1092 ///Gives back the matching in an ANodeMap. The parameter should 1093 ///be a write ANodeMap of UEdge values. 1094 ///\return The number of the matching edges. 1095 template<class MatchingMap> 1096 int aMatching(MatchingMap& mm) const { 1097 for (ANodeIt it(*graph); it != INVALID; ++it) { 1098 mm.set(it, anode_matching[it]); 1099 } 1100 return matching_size; 1101 } 1102 1103 ///Gives back the matching in a BNodeMap. 1104 1105 ///Gives back the matching in a BNodeMap. The parameter should 1106 ///be a write BNodeMap of UEdge values. 1107 ///\return The number of the matching edges. 1108 template<class MatchingMap> 1109 int bMatching(MatchingMap& mm) const { 1110 for (BNodeIt it(*graph); it != INVALID; ++it) { 1111 mm.set(it, bnode_matching[it]); 1020 1112 } 1021 1113 return matching_size; … … 1534 1626 /// \brief Gives back the potential in the NodeMap 1535 1627 /// 1536 /// Gives back the potential in the NodeMap. The potential is optimal with1537 /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for1538 /// each matching edges and \f$ \pi(a) - \pi(b) +w(ab) \ge 0 \f$1539 /// for each edges. 1628 /// Gives back the potential in the NodeMap. The matching is optimal 1629 /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$ 1630 /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$ 1631 /// for each edges. 1540 1632 template <typename PotentialMap> 1541 1633 void potential(PotentialMap& pt) const { 1542 1634 for (ANodeIt it(*graph); it != INVALID; ++it) { 1543 pt [it] = anode_potential[it];1635 pt.set(it, anode_potential[it]); 1544 1636 } 1545 1637 for (BNodeIt it(*graph); it != INVALID; ++it) { 1546 pt [it] = bnode_potential[it];1638 pt.set(it, bnode_potential[it]); 1547 1639 } 1548 1640 } … … 1557 1649 for (ANodeIt it(*graph); it != INVALID; ++it) { 1558 1650 if (anode_matching[it] != INVALID) { 1559 mm [anode_matching[it]] = true;1651 mm.set(anode_matching[it], true); 1560 1652 } 1561 1653 } … … 1570 1662 int matching(MatchingMap& mm) const { 1571 1663 for (UEdgeIt it(*graph); it != INVALID; ++it) { 1572 mm [it] = it == anode_matching[graph->aNode(it)];1664 mm.set(it, it == anode_matching[graph->aNode(it)]); 1573 1665 } 1574 1666 return matching_size; 1575 1667 } 1576 1668 1669 /// \brief Gives back the matching in an ANodeMap. 1670 /// 1671 /// Gives back the matching in an ANodeMap. The parameter should 1672 /// be a write ANodeMap of UEdge values. 1673 /// \return The number of the matching edges. 1674 template<class MatchingMap> 1675 int aMatching(MatchingMap& mm) const { 1676 for (ANodeIt it(*graph); it != INVALID; ++it) { 1677 mm.set(it, anode_matching[it]); 1678 } 1679 return matching_size; 1680 } 1681 1682 /// \brief Gives back the matching in a BNodeMap. 1683 /// 1684 /// Gives back the matching in a BNodeMap. The parameter should 1685 /// be a write BNodeMap of UEdge values. 1686 /// \return The number of the matching edges. 1687 template<class MatchingMap> 1688 int bMatching(MatchingMap& mm) const { 1689 for (BNodeIt it(*graph); it != INVALID; ++it) { 1690 mm.set(it, bnode_matching[it]); 1691 } 1692 return matching_size; 1693 } 1577 1694 1578 1695 /// \brief Return true if the given uedge is in the matching. … … 1656 1773 /// \brief Minimum cost maximum cardinality bipartite matching 1657 1774 /// 1658 /// This function calculates the m inimum cost matching of the maximum1659 /// cardinality matchings of a bipartite graph. It gives back the matching1660 /// inan undirected edge map.1775 /// This function calculates the maximum cardinality matching with 1776 /// minimum cost of a bipartite graph. It gives back the matching in 1777 /// an undirected edge map. 1661 1778 /// 1662 1779 /// \param graph The bipartite graph. -
lemon/pr_bipartite_matching.h
r2462 r2463 316 316 ///@{ 317 317 318 /// \briefSet true all matching uedge in the map.319 /// 320 /// 321 /// 322 /// 318 ///Set true all matching uedge in the map. 319 320 ///Set true all matching uedge in the map. It does not change the 321 ///value mapped to the other uedges. 322 ///\return The number of the matching edges. 323 323 template <typename MatchingMap> 324 324 int quickMatching(MatchingMap& mm) const { … … 329 329 } 330 330 331 /// \briefSet true all matching uedge in the map and the others to false.331 ///Set true all matching uedge in the map and the others to false. 332 332 333 333 ///Set true all matching uedge in the map and the others to false. … … 337 337 for (UEdgeIt e(_g);e!=INVALID;++e) { 338 338 mm.set(e,e==_matching[_g.aNode(e)]); 339 } 340 return _matching_size; 341 } 342 343 ///Gives back the matching in an ANodeMap. 344 345 ///Gives back the matching in an ANodeMap. The parameter should 346 ///be a write ANodeMap of UEdge values. 347 ///\return The number of the matching edges. 348 template<class MatchingMap> 349 int aMatching(MatchingMap& mm) const { 350 for (ANodeIt n(_g);n!=INVALID;++n) { 351 mm.set(n,_matching[n]); 352 } 353 return _matching_size; 354 } 355 356 ///Gives back the matching in a BNodeMap. 357 358 ///Gives back the matching in a BNodeMap. The parameter should 359 ///be a write BNodeMap of UEdge values. 360 ///\return The number of the matching edges. 361 template<class MatchingMap> 362 int bMatching(MatchingMap& mm) const { 363 for (BNodeIt n(_g);n!=INVALID;++n) { 364 mm.set(n,INVALID); 365 } 366 for (ANodeIt n(_g);n!=INVALID;++n) { 367 if (_matching[n]!=INVALID) 368 mm.set(_g.bNode(_matching[n]),_matching[n]); 339 369 } 340 370 return _matching_size; … … 458 488 ///in a bipartite graph \c g. 459 489 ///\param g An undirected bipartite graph. 460 ///\retval matching A write UEdgeMap of value type \c bool. 461 /// The found edges will be returned in this map. 490 ///\retval matching A write ANodeMap of value type \c UEdge. 491 /// The found edges will be returned in this map, 492 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one 493 /// that covers the node \c n. 462 494 ///\return The cardinality of the maximum matching. 463 495 /// … … 469 501 PrBipartiteMatching<Graph> bpm(g); 470 502 bpm.run(); 471 bpm. matching(matching);503 bpm.aMatching(matching); 472 504 return bpm.matchingSize(); 473 505 } … … 479 511 ///in a bipartite graph \c g. 480 512 ///\param g An undirected bipartite graph. 481 ///\retval matching A write UEdgeMap of value type \c bool. 482 /// The found edges will be returned in this map. 513 ///\retval matching A write ANodeMap of value type \c UEdge. 514 /// The found edges will be returned in this map, 515 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one 516 /// that covers the node \c n. 483 517 ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set 484 518 /// exactly once for each BNode. The nodes with \c true value represent … … 495 529 PrBipartiteMatching<Graph> bpm(g); 496 530 bpm.run(); 497 bpm. matching(matching);531 bpm.aMatching(matching); 498 532 bpm.bBarrier(barrier); 499 533 return bpm.matchingSize(); … … 522 556 ///This function finds a perfect matching in a bipartite graph \c g. 523 557 ///\param g An undirected bipartite graph. 524 ///\retval matching A write UEdgeMap of value type \c bool. 525 /// The found edges will be returned in this map. 558 ///\retval matching A write ANodeMap of value type \c UEdge. 559 /// The found edges will be returned in this map, 560 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one 561 /// that covers the node \c n. 526 562 /// The values are unchanged if the graph 527 563 /// has no perfect matching. … … 534 570 { 535 571 PrBipartiteMatching<Graph> bpm(g); 536 bool ret = bpm. runPerfect();537 if (ret) bpm. matching(matching);572 bool ret = bpm.checkedRunPerfect(); 573 if (ret) bpm.aMatching(matching); 538 574 return ret; 539 575 } … … 544 580 ///This function finds a perfect matching in a bipartite graph \c g. 545 581 ///\param g An undirected bipartite graph. 546 ///\retval matching A readwrite UEdgeMap of value type \c bool. 547 /// The found edges will be returned in this map. 582 ///\retval matching A write ANodeMap of value type \c UEdge. 583 /// The found edges will be returned in this map, 584 /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one 585 /// that covers the node \c n. 548 586 /// The values are unchanged if the graph 549 587 /// has no perfect matching. … … 558 596 ///on the push-relabel principle. 559 597 template<class Graph,class MT, class GT> 560 intprPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier)598 bool prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier) 561 599 { 562 600 PrBipartiteMatching<Graph> bpm(g); 563 bool ret=bpm. runPerfect();601 bool ret=bpm.checkedRunPerfect(); 564 602 if(ret) 565 bpm. matching(matching);603 bpm.aMatching(matching); 566 604 else 567 605 bpm.bBarrier(barrier); -
test/bipartite_matching_test.cc
r2462 r2463 137 137 138 138 { 139 Graph:: UEdgeMap<bool> mm(graph);139 Graph::ANodeMap<UEdge> mm(graph); 140 140 141 141 check(max_cardinality == maxBipartiteMatching(graph, mm), 142 142 "WRONG MATCHING"); 143 143 144 for (ANodeIt it(graph); it != INVALID; ++it) { 145 int num = 0; 146 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { 147 if (mm[jt]) ++num; 144 for (BNodeIt it(graph); it != INVALID; ++it) { 145 int num = 0; 146 147 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { 148 if (mm[graph.aNode(jt)] == jt) ++num; 149 } 150 check(num <= 1, "INVALID PRIMAL"); 151 } 152 } 153 154 { 155 Graph::ANodeMap<UEdge> mm(graph); 156 157 check(max_cardinality == prBipartiteMatching(graph, mm), 158 "WRONG MATCHING"); 159 160 for (BNodeIt it(graph); it != INVALID; ++it) { 161 int num = 0; 162 163 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { 164 if (mm[graph.aNode(jt)] == jt) ++num; 148 165 } 149 166 check(num <= 1, "INVALID PRIMAL");
Note: See TracChangeset
for help on using the changeset viewer.