COIN-OR::LEMON - Graph Library

Changeset 1081:f1398882a928 in lemon for lemon/matching.h


Ignore:
Timestamp:
08/08/11 12:36:16 (8 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.1
Phase:
public
Tags:
r1.1.4
Message:

Unify sources

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/matching.h

    r945 r1081  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2011
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    4242  /// This class implements Edmonds' alternating forest matching algorithm
    4343  /// 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
    4545  /// (the default is the empty one).
    4646  ///
     
    7070    ///\brief Status constants for Gallai-Edmonds decomposition.
    7171    ///
    72     ///These constants are used for indicating the Gallai-Edmonds 
     72    ///These constants are used for indicating the Gallai-Edmonds
    7373    ///decomposition of a graph. The nodes with status \c EVEN (or \c D)
    7474    ///induce a subgraph with factor-critical components, the nodes with
    7575    ///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
    7777    ///perfect matching.
    7878    enum Status {
     
    513513    }
    514514
    515     /// \brief Start Edmonds' algorithm with a heuristic improvement 
     515    /// \brief Start Edmonds' algorithm with a heuristic improvement
    516516    /// for dense graphs
    517517    ///
     
    535535    /// \brief Run Edmonds' algorithm
    536536    ///
    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
    539539    /// (for which <tt>m>=2*n</tt> holds).
    540540    void run() {
     
    557557    /// \brief Return the size (cardinality) of the matching.
    558558    ///
    559     /// This function returns the size (cardinality) of the current matching. 
     559    /// This function returns the size (cardinality) of the current matching.
    560560    /// After run() it returns the size of the maximum matching in the graph.
    561561    int matchingSize() const {
     
    571571    /// \brief Return \c true if the given edge is in the matching.
    572572    ///
    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
    574574    /// matching.
    575575    bool matching(const Edge& edge) const {
     
    580580    ///
    581581    /// 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
    583583    /// not covered by the matching.
    584584    Arc matching(const Node& n) const {
     
    596596    /// \brief Return the mate of the given node.
    597597    ///
    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
    599599    /// matching or \c INVALID if the node is not covered by the matching.
    600600    Node mate(const Node& n) const {
     
    606606
    607607    /// \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
    609609    /// decomposition.
    610610
     
    649649  /// \f$O(nm\log n)\f$ time complexity.
    650650  ///
    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
    653653  /// each node has at most one incident edge.
    654654  /// It can be formulated with the following linear program.
     
    674674      \frac{\vert B \vert - 1}{2}z_B\f] */
    675675  ///
    676   /// The algorithm can be executed with the run() function. 
     676  /// The algorithm can be executed with the run() function.
    677677  /// 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.
    681681  /// If the value type is integer, then the dual solution is multiplied
    682682  /// by \ref MaxWeightedMatching::dualScale "4".
    683683  ///
    684684  /// \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
    686686  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
    687687#ifdef DOXYGEN
     
    17211721        (*_delta4_index)[i] = _delta4->PRE_HEAP;
    17221722      }
    1723      
     1723
    17241724      _delta1->clear();
    17251725      _delta2->clear();
     
    18691869
    18701870    /// \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
    18721872    /// matching.\n
    18731873    /// Either \ref run() or \ref start() function should be called before
     
    19081908    /// \brief Return \c true if the given edge is in the matching.
    19091909    ///
    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
    19111911    /// matching.
    19121912    ///
     
    19191919    ///
    19201920    /// 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
    19221922    /// not covered by the matching.
    19231923    ///
     
    19371937    /// \brief Return the mate of the given node.
    19381938    ///
    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
    19401940    /// matching or \c INVALID if the node is not covered by the matching.
    19411941    ///
     
    19571957    /// \brief Return the value of the dual solution.
    19581958    ///
    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
    19611961    /// "dual scale".
    19621962    ///
     
    20132013    /// \brief Iterator for obtaining the nodes of a blossom.
    20142014    ///
    2015     /// This class provides an iterator for obtaining the nodes of the 
     2015    /// This class provides an iterator for obtaining the nodes of the
    20162016    /// 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
    20182018    /// MaxWeightedMatching class and execute it.
    20192019    class BlossomIt {
     
    20242024      /// Constructor to get the nodes of the given variable.
    20252025      ///
    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
    20282028      /// called before initializing this iterator.
    20292029      BlossomIt(const MaxWeightedMatching& algorithm, int variable)
     
    20782078  /// \f$O(nm\log n)\f$ time complexity.
    20792079  ///
    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
    20822082  /// each node has exactly one incident edge.
    20832083  /// It can be formulated with the following linear program.
     
    21022102      \frac{\vert B \vert - 1}{2}z_B\f] */
    21032103  ///
    2104   /// The algorithm can be executed with the run() function. 
     2104  /// The algorithm can be executed with the run() function.
    21052105  /// 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.
    21092109  /// If the value type is integer, then the dual solution is multiplied
    21102110  /// by \ref MaxWeightedMatching::dualScale "4".
    21112111  ///
    21122112  /// \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
    21142114  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
    21152115#ifdef DOXYGEN
     
    31163116
    31173117    /// \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
    31193119    /// perfect matching.\n
    31203120    /// Either \ref run() or \ref start() function should be called before
     
    31403140    /// \brief Return \c true if the given edge is in the matching.
    31413141    ///
    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
    31433143    /// matching.
    31443144    ///
     
    31513151    ///
    31523152    /// 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
    31543154    /// not covered by the matching.
    31553155    ///
     
    31693169    /// \brief Return the mate of the given node.
    31703170    ///
    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
    31723172    /// matching or \c INVALID if the node is not covered by the matching.
    31733173    ///
     
    31883188    /// \brief Return the value of the dual solution.
    31893189    ///
    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
    31923192    /// "dual scale".
    31933193    ///
     
    32443244    /// \brief Iterator for obtaining the nodes of a blossom.
    32453245    ///
    3246     /// This class provides an iterator for obtaining the nodes of the 
     3246    /// This class provides an iterator for obtaining the nodes of the
    32473247    /// 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
    32493249    /// MaxWeightedPerfectMatching class and execute it.
    32503250    class BlossomIt {
     
    32553255      /// Constructor to get the nodes of the given variable.
    32563256      ///
    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()"
    32593259      /// must be called before initializing this iterator.
    32603260      BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
Note: See TracChangeset for help on using the changeset viewer.