Changes in lemon/matching.h [1081:f1398882a928:945:5b926cc36a4b] in lemon
- File:
-
- 1 edited
-
lemon/matching.h (modified) (29 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/matching.h
r1081 r945 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 115 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 42 42 /// This class implements Edmonds' alternating forest matching algorithm 43 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 45 /// (the default is the empty one). 46 46 /// … … 70 70 ///\brief Status constants for Gallai-Edmonds decomposition. 71 71 /// 72 ///These constants are used for indicating the Gallai-Edmonds 72 ///These constants are used for indicating the Gallai-Edmonds 73 73 ///decomposition of a graph. The nodes with status \c EVEN (or \c D) 74 74 ///induce a subgraph with factor-critical components, the nodes with 75 75 ///status \c ODD (or \c A) form the canonical barrier, and the nodes 76 ///with status \c MATCHED (or \c C) induce a subgraph having a 76 ///with status \c MATCHED (or \c C) induce a subgraph having a 77 77 ///perfect matching. 78 78 enum Status { … … 513 513 } 514 514 515 /// \brief Start Edmonds' algorithm with a heuristic improvement 515 /// \brief Start Edmonds' algorithm with a heuristic improvement 516 516 /// for dense graphs 517 517 /// … … 535 535 /// \brief Run Edmonds' algorithm 536 536 /// 537 /// This function runs Edmonds' algorithm. An additional heuristic of 538 /// postponing shrinks is used for relatively dense graphs 537 /// This function runs Edmonds' algorithm. An additional heuristic of 538 /// postponing shrinks is used for relatively dense graphs 539 539 /// (for which <tt>m>=2*n</tt> holds). 540 540 void run() { … … 557 557 /// \brief Return the size (cardinality) of the matching. 558 558 /// 559 /// This function returns the size (cardinality) of the current matching. 559 /// This function returns the size (cardinality) of the current matching. 560 560 /// After run() it returns the size of the maximum matching in the graph. 561 561 int matchingSize() const { … … 571 571 /// \brief Return \c true if the given edge is in the matching. 572 572 /// 573 /// This function returns \c true if the given edge is in the current 573 /// This function returns \c true if the given edge is in the current 574 574 /// matching. 575 575 bool matching(const Edge& edge) const { … … 580 580 /// 581 581 /// This function returns the matching arc (or edge) incident to the 582 /// given node in the current matching or \c INVALID if the node is 582 /// given node in the current matching or \c INVALID if the node is 583 583 /// not covered by the matching. 584 584 Arc matching(const Node& n) const { … … 596 596 /// \brief Return the mate of the given node. 597 597 /// 598 /// 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 599 599 /// matching or \c INVALID if the node is not covered by the matching. 600 600 Node mate(const Node& n) const { … … 606 606 607 607 /// \name Dual Solution 608 /// Functions to get the dual solution, i.e. the Gallai-Edmonds 608 /// Functions to get the dual solution, i.e. the Gallai-Edmonds 609 609 /// decomposition. 610 610 … … 649 649 /// \f$O(nm\log n)\f$ time complexity. 650 650 /// 651 /// The maximum weighted matching problem is to find a subset of the 652 /// edges in an undirected graph with maximum overall weight for which 651 /// The maximum weighted matching problem is to find a subset of the 652 /// edges in an undirected graph with maximum overall weight for which 653 653 /// each node has at most one incident edge. 654 654 /// It can be formulated with the following linear program. … … 674 674 \frac{\vert B \vert - 1}{2}z_B\f] */ 675 675 /// 676 /// The algorithm can be executed with the run() function. 676 /// The algorithm can be executed with the run() function. 677 677 /// After it the matching (the primal solution) and the dual solution 678 /// can be obtained using the query functions and the 679 /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, 680 /// which is able to iterate on the nodes of a blossom. 678 /// can be obtained using the query functions and the 679 /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, 680 /// which is able to iterate on the nodes of a blossom. 681 681 /// If the value type is integer, then the dual solution is multiplied 682 682 /// by \ref MaxWeightedMatching::dualScale "4". 683 683 /// 684 684 /// \tparam GR The undirected graph type the algorithm runs on. 685 /// \tparam WM The type edge weight map. The default type is 685 /// \tparam WM The type edge weight map. The default type is 686 686 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". 687 687 #ifdef DOXYGEN … … 1721 1721 (*_delta4_index)[i] = _delta4->PRE_HEAP; 1722 1722 } 1723 1723 1724 1724 _delta1->clear(); 1725 1725 _delta2->clear(); … … 1869 1869 1870 1870 /// \name Primal Solution 1871 /// Functions to get the primal solution, i.e. the maximum weighted 1871 /// Functions to get the primal solution, i.e. the maximum weighted 1872 1872 /// matching.\n 1873 1873 /// Either \ref run() or \ref start() function should be called before … … 1908 1908 /// \brief Return \c true if the given edge is in the matching. 1909 1909 /// 1910 /// This function returns \c true if the given edge is in the found 1910 /// This function returns \c true if the given edge is in the found 1911 1911 /// matching. 1912 1912 /// … … 1919 1919 /// 1920 1920 /// This function returns the matching arc (or edge) incident to the 1921 /// given node in the found matching or \c INVALID if the node is 1921 /// given node in the found matching or \c INVALID if the node is 1922 1922 /// not covered by the matching. 1923 1923 /// … … 1937 1937 /// \brief Return the mate of the given node. 1938 1938 /// 1939 /// This function returns the mate of the given node in the found 1939 /// This function returns the mate of the given node in the found 1940 1940 /// matching or \c INVALID if the node is not covered by the matching. 1941 1941 /// … … 1957 1957 /// \brief Return the value of the dual solution. 1958 1958 /// 1959 /// This function returns the value of the dual solution. 1960 /// It should be equal to the primal value scaled by \ref dualScale 1959 /// This function returns the value of the dual solution. 1960 /// It should be equal to the primal value scaled by \ref dualScale 1961 1961 /// "dual scale". 1962 1962 /// … … 2013 2013 /// \brief Iterator for obtaining the nodes of a blossom. 2014 2014 /// 2015 /// This class provides an iterator for obtaining the nodes of the 2015 /// This class provides an iterator for obtaining the nodes of the 2016 2016 /// given blossom. It lists a subset of the nodes. 2017 /// Before using this iterator, you must allocate a 2017 /// Before using this iterator, you must allocate a 2018 2018 /// MaxWeightedMatching class and execute it. 2019 2019 class BlossomIt { … … 2024 2024 /// Constructor to get the nodes of the given variable. 2025 2025 /// 2026 /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or 2027 /// \ref MaxWeightedMatching::start() "algorithm.start()" must be 2026 /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or 2027 /// \ref MaxWeightedMatching::start() "algorithm.start()" must be 2028 2028 /// called before initializing this iterator. 2029 2029 BlossomIt(const MaxWeightedMatching& algorithm, int variable) … … 2078 2078 /// \f$O(nm\log n)\f$ time complexity. 2079 2079 /// 2080 /// The maximum weighted perfect matching problem is to find a subset of 2081 /// the edges in an undirected graph with maximum overall weight for which 2080 /// The maximum weighted perfect matching problem is to find a subset of 2081 /// the edges in an undirected graph with maximum overall weight for which 2082 2082 /// each node has exactly one incident edge. 2083 2083 /// It can be formulated with the following linear program. … … 2102 2102 \frac{\vert B \vert - 1}{2}z_B\f] */ 2103 2103 /// 2104 /// The algorithm can be executed with the run() function. 2104 /// The algorithm can be executed with the run() function. 2105 2105 /// After it the matching (the primal solution) and the dual solution 2106 /// can be obtained using the query functions and the 2107 /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, 2108 /// which is able to iterate on the nodes of a blossom. 2106 /// can be obtained using the query functions and the 2107 /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, 2108 /// which is able to iterate on the nodes of a blossom. 2109 2109 /// If the value type is integer, then the dual solution is multiplied 2110 2110 /// by \ref MaxWeightedMatching::dualScale "4". 2111 2111 /// 2112 2112 /// \tparam GR The undirected graph type the algorithm runs on. 2113 /// \tparam WM The type edge weight map. The default type is 2113 /// \tparam WM The type edge weight map. The default type is 2114 2114 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". 2115 2115 #ifdef DOXYGEN … … 3116 3116 3117 3117 /// \name Primal Solution 3118 /// Functions to get the primal solution, i.e. the maximum weighted 3118 /// Functions to get the primal solution, i.e. the maximum weighted 3119 3119 /// perfect matching.\n 3120 3120 /// Either \ref run() or \ref start() function should be called before … … 3140 3140 /// \brief Return \c true if the given edge is in the matching. 3141 3141 /// 3142 /// This function returns \c true if the given edge is in the found 3142 /// This function returns \c true if the given edge is in the found 3143 3143 /// matching. 3144 3144 /// … … 3151 3151 /// 3152 3152 /// This function returns the matching arc (or edge) incident to the 3153 /// given node in the found matching or \c INVALID if the node is 3153 /// given node in the found matching or \c INVALID if the node is 3154 3154 /// not covered by the matching. 3155 3155 /// … … 3169 3169 /// \brief Return the mate of the given node. 3170 3170 /// 3171 /// This function returns the mate of the given node in the found 3171 /// This function returns the mate of the given node in the found 3172 3172 /// matching or \c INVALID if the node is not covered by the matching. 3173 3173 /// … … 3188 3188 /// \brief Return the value of the dual solution. 3189 3189 /// 3190 /// This function returns the value of the dual solution. 3191 /// It should be equal to the primal value scaled by \ref dualScale 3190 /// This function returns the value of the dual solution. 3191 /// It should be equal to the primal value scaled by \ref dualScale 3192 3192 /// "dual scale". 3193 3193 /// … … 3244 3244 /// \brief Iterator for obtaining the nodes of a blossom. 3245 3245 /// 3246 /// This class provides an iterator for obtaining the nodes of the 3246 /// This class provides an iterator for obtaining the nodes of the 3247 3247 /// given blossom. It lists a subset of the nodes. 3248 /// Before using this iterator, you must allocate a 3248 /// Before using this iterator, you must allocate a 3249 3249 /// MaxWeightedPerfectMatching class and execute it. 3250 3250 class BlossomIt { … … 3255 3255 /// Constructor to get the nodes of the given variable. 3256 3256 /// 3257 /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" 3258 /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" 3257 /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" 3258 /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" 3259 3259 /// must be called before initializing this iterator. 3260 3260 BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
Note: See TracChangeset
for help on using the changeset viewer.
