53 /// minus the number of barrier nodes is a lower bound on the |
53 /// minus the number of barrier nodes is a lower bound on the |
54 /// unmatched nodes, and the matching is optimal if and only if this bound is |
54 /// unmatched nodes, and the matching is optimal if and only if this bound is |
55 /// tight. This decomposition can be attained by calling \c |
55 /// tight. This decomposition can be attained by calling \c |
56 /// decomposition() after running the algorithm. |
56 /// decomposition() after running the algorithm. |
57 /// |
57 /// |
58 /// \param _Graph The graph type the algorithm runs on. |
58 /// \param GR The graph type the algorithm runs on. |
59 template <typename _Graph> |
59 template <typename GR> |
60 class MaxMatching { |
60 class MaxMatching { |
61 public: |
61 public: |
62 |
62 |
63 typedef _Graph Graph; |
63 typedef GR Graph; |
64 typedef typename Graph::template NodeMap<typename Graph::Arc> |
64 typedef typename Graph::template NodeMap<typename Graph::Arc> |
65 MatchingMap; |
65 MatchingMap; |
66 |
66 |
67 ///\brief Indicates the Gallai-Edmonds decomposition of the graph. |
67 ///\brief Indicates the Gallai-Edmonds decomposition of the graph. |
68 /// |
68 /// |
461 /// \brief Initialize the matching from a map containing. |
461 /// \brief Initialize the matching from a map containing. |
462 /// |
462 /// |
463 /// Initialize the matching from a \c bool valued \c Edge map. This |
463 /// Initialize the matching from a \c bool valued \c Edge map. This |
464 /// map must have the property that there are no two incident edges |
464 /// map must have the property that there are no two incident edges |
465 /// with true value, ie. it contains a matching. |
465 /// with true value, ie. it contains a matching. |
466 /// \return %True if the map contains a matching. |
466 /// \return \c true if the map contains a matching. |
467 template <typename MatchingMap> |
467 template <typename MatchingMap> |
468 bool matchingInit(const MatchingMap& matching) { |
468 bool matchingInit(const MatchingMap& matching) { |
469 createStructures(); |
469 createStructures(); |
470 |
470 |
471 for (NodeIt n(_graph); n != INVALID; ++n) { |
471 for (NodeIt n(_graph); n != INVALID; ++n) { |
611 /// \brief Weighted matching in general graphs |
611 /// \brief Weighted matching in general graphs |
612 /// |
612 /// |
613 /// This class provides an efficient implementation of Edmond's |
613 /// This class provides an efficient implementation of Edmond's |
614 /// maximum weighted matching algorithm. The implementation is based |
614 /// maximum weighted matching algorithm. The implementation is based |
615 /// on extensive use of priority queues and provides |
615 /// on extensive use of priority queues and provides |
616 /// \f$O(nm\log(n))\f$ time complexity. |
616 /// \f$O(nm\log n)\f$ time complexity. |
617 /// |
617 /// |
618 /// The maximum weighted matching problem is to find undirected |
618 /// The maximum weighted matching problem is to find undirected |
619 /// edges in the graph with maximum overall weight and no two of |
619 /// edges in the graph with maximum overall weight and no two of |
620 /// them shares their ends. The problem can be formulated with the |
620 /// them shares their ends. The problem can be formulated with the |
621 /// following linear program. |
621 /// following linear program. |
645 /// solution can be get with \c nodeValue(), \c blossomNum() and \c |
645 /// solution can be get with \c nodeValue(), \c blossomNum() and \c |
646 /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt |
646 /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt |
647 /// "BlossomIt" nested class, which is able to iterate on the nodes |
647 /// "BlossomIt" nested class, which is able to iterate on the nodes |
648 /// of a blossom. If the value type is integral then the dual |
648 /// of a blossom. If the value type is integral then the dual |
649 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". |
649 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". |
650 template <typename _Graph, |
650 template <typename GR, |
651 typename _WeightMap = typename _Graph::template EdgeMap<int> > |
651 typename WM = typename GR::template EdgeMap<int> > |
652 class MaxWeightedMatching { |
652 class MaxWeightedMatching { |
653 public: |
653 public: |
654 |
654 |
655 typedef _Graph Graph; |
655 ///\e |
656 typedef _WeightMap WeightMap; |
656 typedef GR Graph; |
|
657 ///\e |
|
658 typedef WM WeightMap; |
|
659 ///\e |
657 typedef typename WeightMap::Value Value; |
660 typedef typename WeightMap::Value Value; |
658 |
661 |
659 /// \brief Scaling factor for dual solution |
662 /// \brief Scaling factor for dual solution |
660 /// |
663 /// |
661 /// Scaling factor for dual solution, it is equal to 4 or 1 |
664 /// Scaling factor for dual solution, it is equal to 4 or 1 |
1955 /// \brief Weighted perfect matching in general graphs |
1958 /// \brief Weighted perfect matching in general graphs |
1956 /// |
1959 /// |
1957 /// This class provides an efficient implementation of Edmond's |
1960 /// This class provides an efficient implementation of Edmond's |
1958 /// maximum weighted perfect matching algorithm. The implementation |
1961 /// maximum weighted perfect matching algorithm. The implementation |
1959 /// is based on extensive use of priority queues and provides |
1962 /// is based on extensive use of priority queues and provides |
1960 /// \f$O(nm\log(n))\f$ time complexity. |
1963 /// \f$O(nm\log n)\f$ time complexity. |
1961 /// |
1964 /// |
1962 /// The maximum weighted matching problem is to find undirected |
1965 /// The maximum weighted matching problem is to find undirected |
1963 /// edges in the graph with maximum overall weight and no two of |
1966 /// edges in the graph with maximum overall weight and no two of |
1964 /// them shares their ends and covers all nodes. The problem can be |
1967 /// them shares their ends and covers all nodes. The problem can be |
1965 /// formulated with the following linear program. |
1968 /// formulated with the following linear program. |
1988 /// solution can be get with \c nodeValue(), \c blossomNum() and \c |
1991 /// solution can be get with \c nodeValue(), \c blossomNum() and \c |
1989 /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt |
1992 /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt |
1990 /// "BlossomIt" nested class which is able to iterate on the nodes |
1993 /// "BlossomIt" nested class which is able to iterate on the nodes |
1991 /// of a blossom. If the value type is integral then the dual |
1994 /// of a blossom. If the value type is integral then the dual |
1992 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". |
1995 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". |
1993 template <typename _Graph, |
1996 template <typename GR, |
1994 typename _WeightMap = typename _Graph::template EdgeMap<int> > |
1997 typename WM = typename GR::template EdgeMap<int> > |
1995 class MaxWeightedPerfectMatching { |
1998 class MaxWeightedPerfectMatching { |
1996 public: |
1999 public: |
1997 |
2000 |
1998 typedef _Graph Graph; |
2001 typedef GR Graph; |
1999 typedef _WeightMap WeightMap; |
2002 typedef WM WeightMap; |
2000 typedef typename WeightMap::Value Value; |
2003 typedef typename WeightMap::Value Value; |
2001 |
2004 |
2002 /// \brief Scaling factor for dual solution |
2005 /// \brief Scaling factor for dual solution |
2003 /// |
2006 /// |
2004 /// Scaling factor for dual solution, it is equal to 4 or 1 |
2007 /// Scaling factor for dual solution, it is equal to 4 or 1 |