38 /// \ingroup matching |
38 /// \ingroup matching |
39 /// |
39 /// |
40 /// \brief Maximum cardinality matching in general graphs |
40 /// \brief Maximum cardinality matching in general graphs |
41 /// |
41 /// |
42 /// This class implements Edmonds' alternating forest matching algorithm |
42 /// This class implements Edmonds' alternating forest matching algorithm |
43 /// for finding a maximum cardinality matching in a general graph. |
43 /// for finding a maximum cardinality matching in a general undirected graph. |
44 /// It can be started from an arbitrary initial matching |
44 /// It can be started from an arbitrary initial matching |
45 /// (the default is the empty one). |
45 /// (the default is the empty one). |
46 /// |
46 /// |
47 /// The dual solution of the problem is a map of the nodes to |
47 /// The dual solution of the problem is a map of the nodes to |
48 /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D), |
48 /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D), |
51 /// with factor-critical components, the nodes in \c ODD/A form the |
51 /// with factor-critical components, the nodes in \c ODD/A form the |
52 /// canonical barrier, and the nodes in \c MATCHED/C induce a graph having |
52 /// canonical barrier, and the nodes in \c MATCHED/C induce a graph having |
53 /// a perfect matching. The number of the factor-critical components |
53 /// a perfect matching. The number of the factor-critical components |
54 /// minus the number of barrier nodes is a lower bound on the |
54 /// minus the number of barrier nodes is a lower bound on the |
55 /// unmatched nodes, and the matching is optimal if and only if this bound is |
55 /// unmatched nodes, and the matching is optimal if and only if this bound is |
56 /// tight. This decomposition can be obtained by calling \c |
56 /// tight. This decomposition can be obtained using \ref status() or |
57 /// decomposition() after running the algorithm. |
57 /// \ref statusMap() after running the algorithm. |
58 /// |
58 /// |
59 /// \tparam GR The graph type the algorithm runs on. |
59 /// \tparam GR The undirected graph type the algorithm runs on. |
60 template <typename GR> |
60 template <typename GR> |
61 class MaxMatching { |
61 class MaxMatching { |
62 public: |
62 public: |
63 |
63 |
64 /// The graph type of the algorithm |
64 /// The graph type of the algorithm |
65 typedef GR Graph; |
65 typedef GR Graph; |
|
66 /// The type of the matching map |
66 typedef typename Graph::template NodeMap<typename Graph::Arc> |
67 typedef typename Graph::template NodeMap<typename Graph::Arc> |
67 MatchingMap; |
68 MatchingMap; |
68 |
69 |
69 ///\brief Status constants for Gallai-Edmonds decomposition. |
70 ///\brief Status constants for Gallai-Edmonds decomposition. |
70 /// |
71 /// |
82 ODD = -1, ///< = -1. (\c A is an alias for \c ODD.) |
83 ODD = -1, ///< = -1. (\c A is an alias for \c ODD.) |
83 A = -1, |
84 A = -1, |
84 UNMATCHED = -2 ///< = -2. |
85 UNMATCHED = -2 ///< = -2. |
85 }; |
86 }; |
86 |
87 |
|
88 /// The type of the status map |
87 typedef typename Graph::template NodeMap<Status> StatusMap; |
89 typedef typename Graph::template NodeMap<Status> StatusMap; |
88 |
90 |
89 private: |
91 private: |
90 |
92 |
91 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
93 TEMPLATE_GRAPH_TYPEDEFS(Graph); |
581 /// not covered by the matching. |
583 /// not covered by the matching. |
582 Arc matching(const Node& n) const { |
584 Arc matching(const Node& n) const { |
583 return (*_matching)[n]; |
585 return (*_matching)[n]; |
584 } |
586 } |
585 |
587 |
|
588 /// \brief Return a const reference to the matching map. |
|
589 /// |
|
590 /// This function returns a const reference to a node map that stores |
|
591 /// the matching arc (or edge) incident to each node. |
|
592 const MatchingMap& matchingMap() const { |
|
593 return *_matching; |
|
594 } |
|
595 |
586 /// \brief Return the mate of the given node. |
596 /// \brief Return the mate of the given node. |
587 /// |
597 /// |
588 /// This function returns the mate of the given node in the current |
598 /// This function returns the mate of the given node in the current |
589 /// matching or \c INVALID if the node is not covered by the matching. |
599 /// matching or \c INVALID if the node is not covered by the matching. |
590 Node mate(const Node& n) const { |
600 Node mate(const Node& n) const { |
603 /// \brief Return the status of the given node in the Edmonds-Gallai |
613 /// \brief Return the status of the given node in the Edmonds-Gallai |
604 /// decomposition. |
614 /// decomposition. |
605 /// |
615 /// |
606 /// This function returns the \ref Status "status" of the given node |
616 /// This function returns the \ref Status "status" of the given node |
607 /// in the Edmonds-Gallai decomposition. |
617 /// in the Edmonds-Gallai decomposition. |
608 Status decomposition(const Node& n) const { |
618 Status status(const Node& n) const { |
609 return (*_status)[n]; |
619 return (*_status)[n]; |
|
620 } |
|
621 |
|
622 /// \brief Return a const reference to the status map, which stores |
|
623 /// the Edmonds-Gallai decomposition. |
|
624 /// |
|
625 /// This function returns a const reference to a node map that stores the |
|
626 /// \ref Status "status" of each node in the Edmonds-Gallai decomposition. |
|
627 const StatusMap& statusMap() const { |
|
628 return *_status; |
610 } |
629 } |
611 |
630 |
612 /// \brief Return \c true if the given node is in the barrier. |
631 /// \brief Return \c true if the given node is in the barrier. |
613 /// |
632 /// |
614 /// This function returns \c true if the given node is in the barrier. |
633 /// This function returns \c true if the given node is in the barrier. |
660 /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, |
679 /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, |
661 /// which is able to iterate on the nodes of a blossom. |
680 /// which is able to iterate on the nodes of a blossom. |
662 /// If the value type is integer, then the dual solution is multiplied |
681 /// If the value type is integer, then the dual solution is multiplied |
663 /// by \ref MaxWeightedMatching::dualScale "4". |
682 /// by \ref MaxWeightedMatching::dualScale "4". |
664 /// |
683 /// |
665 /// \tparam GR The graph type the algorithm runs on. |
684 /// \tparam GR The undirected graph type the algorithm runs on. |
666 /// \tparam WM The type edge weight map. The default type is |
685 /// \tparam WM The type edge weight map. The default type is |
667 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
686 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
668 #ifdef DOXYGEN |
687 #ifdef DOXYGEN |
669 template <typename GR, typename WM> |
688 template <typename GR, typename WM> |
670 #else |
689 #else |
679 /// The type of the edge weight map |
698 /// The type of the edge weight map |
680 typedef WM WeightMap; |
699 typedef WM WeightMap; |
681 /// The value type of the edge weights |
700 /// The value type of the edge weights |
682 typedef typename WeightMap::Value Value; |
701 typedef typename WeightMap::Value Value; |
683 |
702 |
|
703 /// The type of the matching map |
684 typedef typename Graph::template NodeMap<typename Graph::Arc> |
704 typedef typename Graph::template NodeMap<typename Graph::Arc> |
685 MatchingMap; |
705 MatchingMap; |
686 |
706 |
687 /// \brief Scaling factor for dual solution |
707 /// \brief Scaling factor for dual solution |
688 /// |
708 /// |
1827 /// \brief Return the weight of the matching. |
1847 /// \brief Return the weight of the matching. |
1828 /// |
1848 /// |
1829 /// This function returns the weight of the found matching. |
1849 /// This function returns the weight of the found matching. |
1830 /// |
1850 /// |
1831 /// \pre Either run() or start() must be called before using this function. |
1851 /// \pre Either run() or start() must be called before using this function. |
1832 Value matchingValue() const { |
1852 Value matchingWeight() const { |
1833 Value sum = 0; |
1853 Value sum = 0; |
1834 for (NodeIt n(_graph); n != INVALID; ++n) { |
1854 for (NodeIt n(_graph); n != INVALID; ++n) { |
1835 if ((*_matching)[n] != INVALID) { |
1855 if ((*_matching)[n] != INVALID) { |
1836 sum += _weight[(*_matching)[n]]; |
1856 sum += _weight[(*_matching)[n]]; |
1837 } |
1857 } |
1871 /// not covered by the matching. |
1891 /// not covered by the matching. |
1872 /// |
1892 /// |
1873 /// \pre Either run() or start() must be called before using this function. |
1893 /// \pre Either run() or start() must be called before using this function. |
1874 Arc matching(const Node& node) const { |
1894 Arc matching(const Node& node) const { |
1875 return (*_matching)[node]; |
1895 return (*_matching)[node]; |
|
1896 } |
|
1897 |
|
1898 /// \brief Return a const reference to the matching map. |
|
1899 /// |
|
1900 /// This function returns a const reference to a node map that stores |
|
1901 /// the matching arc (or edge) incident to each node. |
|
1902 const MatchingMap& matchingMap() const { |
|
1903 return *_matching; |
1876 } |
1904 } |
1877 |
1905 |
1878 /// \brief Return the mate of the given node. |
1906 /// \brief Return the mate of the given node. |
1879 /// |
1907 /// |
1880 /// This function returns the mate of the given node in the found |
1908 /// This function returns the mate of the given node in the found |
2048 /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, |
2076 /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, |
2049 /// which is able to iterate on the nodes of a blossom. |
2077 /// which is able to iterate on the nodes of a blossom. |
2050 /// If the value type is integer, then the dual solution is multiplied |
2078 /// If the value type is integer, then the dual solution is multiplied |
2051 /// by \ref MaxWeightedMatching::dualScale "4". |
2079 /// by \ref MaxWeightedMatching::dualScale "4". |
2052 /// |
2080 /// |
2053 /// \tparam GR The graph type the algorithm runs on. |
2081 /// \tparam GR The undirected graph type the algorithm runs on. |
2054 /// \tparam WM The type edge weight map. The default type is |
2082 /// \tparam WM The type edge weight map. The default type is |
2055 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
2083 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". |
2056 #ifdef DOXYGEN |
2084 #ifdef DOXYGEN |
2057 template <typename GR, typename WM> |
2085 template <typename GR, typename WM> |
2058 #else |
2086 #else |
2074 /// Scaling factor for dual solution, it is equal to 4 or 1 |
2102 /// Scaling factor for dual solution, it is equal to 4 or 1 |
2075 /// according to the value type. |
2103 /// according to the value type. |
2076 static const int dualScale = |
2104 static const int dualScale = |
2077 std::numeric_limits<Value>::is_integer ? 4 : 1; |
2105 std::numeric_limits<Value>::is_integer ? 4 : 1; |
2078 |
2106 |
|
2107 /// The type of the matching map |
2079 typedef typename Graph::template NodeMap<typename Graph::Arc> |
2108 typedef typename Graph::template NodeMap<typename Graph::Arc> |
2080 MatchingMap; |
2109 MatchingMap; |
2081 |
2110 |
2082 private: |
2111 private: |
2083 |
2112 |
3036 /// \brief Return the weight of the matching. |
3065 /// \brief Return the weight of the matching. |
3037 /// |
3066 /// |
3038 /// This function returns the weight of the found matching. |
3067 /// This function returns the weight of the found matching. |
3039 /// |
3068 /// |
3040 /// \pre Either run() or start() must be called before using this function. |
3069 /// \pre Either run() or start() must be called before using this function. |
3041 Value matchingValue() const { |
3070 Value matchingWeight() const { |
3042 Value sum = 0; |
3071 Value sum = 0; |
3043 for (NodeIt n(_graph); n != INVALID; ++n) { |
3072 for (NodeIt n(_graph); n != INVALID; ++n) { |
3044 if ((*_matching)[n] != INVALID) { |
3073 if ((*_matching)[n] != INVALID) { |
3045 sum += _weight[(*_matching)[n]]; |
3074 sum += _weight[(*_matching)[n]]; |
3046 } |
3075 } |
3065 /// not covered by the matching. |
3094 /// not covered by the matching. |
3066 /// |
3095 /// |
3067 /// \pre Either run() or start() must be called before using this function. |
3096 /// \pre Either run() or start() must be called before using this function. |
3068 Arc matching(const Node& node) const { |
3097 Arc matching(const Node& node) const { |
3069 return (*_matching)[node]; |
3098 return (*_matching)[node]; |
|
3099 } |
|
3100 |
|
3101 /// \brief Return a const reference to the matching map. |
|
3102 /// |
|
3103 /// This function returns a const reference to a node map that stores |
|
3104 /// the matching arc (or edge) incident to each node. |
|
3105 const MatchingMap& matchingMap() const { |
|
3106 return *_matching; |
3070 } |
3107 } |
3071 |
3108 |
3072 /// \brief Return the mate of the given node. |
3109 /// \brief Return the mate of the given node. |
3073 /// |
3110 /// |
3074 /// This function returns the mate of the given node in the found |
3111 /// This function returns the mate of the given node in the found |