357 /// \return The number of the matching edges. |
357 /// \return The number of the matching edges. |
358 template <typename MatchingMap> |
358 template <typename MatchingMap> |
359 int quickMatching(MatchingMap& mm) const { |
359 int quickMatching(MatchingMap& mm) const { |
360 for (ANodeIt it(*graph); it != INVALID; ++it) { |
360 for (ANodeIt it(*graph); it != INVALID; ++it) { |
361 if (anode_matching[it] != INVALID) { |
361 if (anode_matching[it] != INVALID) { |
362 mm[anode_matching[it]] = true; |
362 mm.set(anode_matching[it], true); |
363 } |
363 } |
364 } |
364 } |
365 return matching_size; |
365 return matching_size; |
366 } |
366 } |
367 |
367 |
370 /// Set true all matching uedge in the map and the others to false. |
370 /// Set true all matching uedge in the map and the others to false. |
371 /// \return The number of the matching edges. |
371 /// \return The number of the matching edges. |
372 template <typename MatchingMap> |
372 template <typename MatchingMap> |
373 int matching(MatchingMap& mm) const { |
373 int matching(MatchingMap& mm) const { |
374 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
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 return matching_size; |
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 /// \brief Return true if the given uedge is in the matching. |
406 /// \brief Return true if the given uedge is in the matching. |
382 /// |
407 /// |
383 /// It returns true if the given uedge is in the matching. |
408 /// It returns true if the given uedge is in the matching. |
384 bool matchingEdge(const UEdge& edge) const { |
409 bool matchingEdge(const UEdge& edge) const { |
443 queue.swap(newqueue); |
468 queue.swap(newqueue); |
444 } |
469 } |
445 |
470 |
446 int size = 0; |
471 int size = 0; |
447 for (ANodeIt it(*graph); it != INVALID; ++it) { |
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 if (!areached[it] && anode_matching[it] != INVALID) { |
474 if (!areached[it] && anode_matching[it] != INVALID) { |
450 ++size; |
475 ++size; |
451 } |
476 } |
452 } |
477 } |
453 for (BNodeIt it(*graph); it != INVALID; ++it) { |
478 for (BNodeIt it(*graph); it != INVALID; ++it) { |
454 covering[it] = breached[it]; |
479 covering.set(it, breached[it]); |
455 if (breached[it]) { |
480 if (breached[it]) { |
456 ++size; |
481 ++size; |
457 } |
482 } |
458 } |
483 } |
459 return size; |
484 return size; |
566 /// This function calculates the maximum cardinality matching |
591 /// This function calculates the maximum cardinality matching |
567 /// in a bipartite graph. It gives back the matching in an undirected |
592 /// in a bipartite graph. It gives back the matching in an undirected |
568 /// edge map. |
593 /// edge map. |
569 /// |
594 /// |
570 /// \param graph The bipartite graph. |
595 /// \param graph The bipartite graph. |
571 /// \retval matching The undirected edge map which will be set to |
596 /// \return The size of the matching. |
572 /// 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 /// \return The size of the matching. |
615 /// \return The size of the matching. |
574 template <typename BpUGraph, typename MatchingMap> |
616 template <typename BpUGraph, typename MatchingMap> |
575 int maxBipartiteMatching(const BpUGraph& graph, MatchingMap& matching) { |
617 int maxBipartiteMatching(const BpUGraph& graph, MatchingMap& matching) { |
576 MaxBipartiteMatching<BpUGraph> bpmatching(graph); |
618 MaxBipartiteMatching<BpUGraph> bpmatching(graph); |
577 bpmatching.run(); |
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 return bpmatching.matchingSize(); |
645 return bpmatching.matchingSize(); |
580 } |
646 } |
581 |
647 |
582 /// \brief Default traits class for weighted bipartite matching algoritms. |
648 /// \brief Default traits class for weighted bipartite matching algoritms. |
583 /// |
649 /// |
985 /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$ |
1051 /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$ |
986 /// for each edges. |
1052 /// for each edges. |
987 template <typename PotentialMap> |
1053 template <typename PotentialMap> |
988 void potential(PotentialMap& pt) const { |
1054 void potential(PotentialMap& pt) const { |
989 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1055 for (ANodeIt it(*graph); it != INVALID; ++it) { |
990 pt[it] = anode_potential[it]; |
1056 pt.set(it, anode_potential[it]); |
991 } |
1057 } |
992 for (BNodeIt it(*graph); it != INVALID; ++it) { |
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 } |
996 |
1062 |
997 /// \brief Set true all matching uedge in the map. |
1063 /// \brief Set true all matching uedge in the map. |
998 /// |
1064 /// |
1001 /// \return The number of the matching edges. |
1067 /// \return The number of the matching edges. |
1002 template <typename MatchingMap> |
1068 template <typename MatchingMap> |
1003 int quickMatching(MatchingMap& mm) const { |
1069 int quickMatching(MatchingMap& mm) const { |
1004 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1070 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1005 if (anode_matching[it] != INVALID) { |
1071 if (anode_matching[it] != INVALID) { |
1006 mm[anode_matching[it]] = true; |
1072 mm.set(anode_matching[it], true); |
1007 } |
1073 } |
1008 } |
1074 } |
1009 return matching_size; |
1075 return matching_size; |
1010 } |
1076 } |
1011 |
1077 |
1014 /// Set true all matching uedge in the map and the others to false. |
1080 /// Set true all matching uedge in the map and the others to false. |
1015 /// \return The number of the matching edges. |
1081 /// \return The number of the matching edges. |
1016 template <typename MatchingMap> |
1082 template <typename MatchingMap> |
1017 int matching(MatchingMap& mm) const { |
1083 int matching(MatchingMap& mm) const { |
1018 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
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 return matching_size; |
1113 return matching_size; |
1022 } |
1114 } |
1023 |
1115 |
1024 |
1116 |
1531 |
1623 |
1532 ///@{ |
1624 ///@{ |
1533 |
1625 |
1534 /// \brief Gives back the potential in the NodeMap |
1626 /// \brief Gives back the potential in the NodeMap |
1535 /// |
1627 /// |
1536 /// Gives back the potential in the NodeMap. The potential is optimal with |
1628 /// Gives back the potential in the NodeMap. The matching is optimal |
1537 /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for |
1629 /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$ |
1538 /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$ |
1630 /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$ |
1539 /// for each edges. |
1631 /// for each edges. |
1540 template <typename PotentialMap> |
1632 template <typename PotentialMap> |
1541 void potential(PotentialMap& pt) const { |
1633 void potential(PotentialMap& pt) const { |
1542 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1634 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1543 pt[it] = anode_potential[it]; |
1635 pt.set(it, anode_potential[it]); |
1544 } |
1636 } |
1545 for (BNodeIt it(*graph); it != INVALID; ++it) { |
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 } |
1549 |
1641 |
1550 /// \brief Set true all matching uedge in the map. |
1642 /// \brief Set true all matching uedge in the map. |
1551 /// |
1643 /// |
1554 /// \return The number of the matching edges. |
1646 /// \return The number of the matching edges. |
1555 template <typename MatchingMap> |
1647 template <typename MatchingMap> |
1556 int quickMatching(MatchingMap& mm) const { |
1648 int quickMatching(MatchingMap& mm) const { |
1557 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1649 for (ANodeIt it(*graph); it != INVALID; ++it) { |
1558 if (anode_matching[it] != INVALID) { |
1650 if (anode_matching[it] != INVALID) { |
1559 mm[anode_matching[it]] = true; |
1651 mm.set(anode_matching[it], true); |
1560 } |
1652 } |
1561 } |
1653 } |
1562 return matching_size; |
1654 return matching_size; |
1563 } |
1655 } |
1564 |
1656 |
1567 /// Set true all matching uedge in the map and the others to false. |
1659 /// Set true all matching uedge in the map and the others to false. |
1568 /// \return The number of the matching edges. |
1660 /// \return The number of the matching edges. |
1569 template <typename MatchingMap> |
1661 template <typename MatchingMap> |
1570 int matching(MatchingMap& mm) const { |
1662 int matching(MatchingMap& mm) const { |
1571 for (UEdgeIt it(*graph); it != INVALID; ++it) { |
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 return matching_size; |
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 /// \brief Return true if the given uedge is in the matching. |
1695 /// \brief Return true if the given uedge is in the matching. |
1579 /// |
1696 /// |
1580 /// It returns true if the given uedge is in the matching. |
1697 /// It returns true if the given uedge is in the matching. |
1581 bool matchingEdge(const UEdge& edge) const { |
1698 bool matchingEdge(const UEdge& edge) const { |
1653 |
1770 |
1654 /// \ingroup matching |
1771 /// \ingroup matching |
1655 /// |
1772 /// |
1656 /// \brief Minimum cost maximum cardinality bipartite matching |
1773 /// \brief Minimum cost maximum cardinality bipartite matching |
1657 /// |
1774 /// |
1658 /// This function calculates the minimum cost matching of the maximum |
1775 /// This function calculates the maximum cardinality matching with |
1659 /// cardinality matchings of a bipartite graph. It gives back the matching |
1776 /// minimum cost of a bipartite graph. It gives back the matching in |
1660 /// in an undirected edge map. |
1777 /// an undirected edge map. |
1661 /// |
1778 /// |
1662 /// \param graph The bipartite graph. |
1779 /// \param graph The bipartite graph. |
1663 /// \param cost The undirected edge map which contains the costs. |
1780 /// \param cost The undirected edge map which contains the costs. |
1664 /// \retval matching The undirected edge map which will be set to |
1781 /// \retval matching The undirected edge map which will be set to |
1665 /// the matching. |
1782 /// the matching. |