Changeset 2463:19651a04d056 in lemon-0.x for lemon/bipartite_matching.h
- Timestamp:
- 08/21/07 15:22:21 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3301
- File:
-
- 1 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.
Note: See TracChangeset
for help on using the changeset viewer.