COIN-OR::LEMON - Graph Library

Changeset 637:b61354458b59 in lemon for lemon


Ignore:
Timestamp:
04/15/09 12:01:14 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Imporvements for the matching algorithms (#264)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/max_matching.h

    r628 r637  
    3838  /// \ingroup matching
    3939  ///
    40   /// \brief Edmonds' alternating forest maximum matching algorithm.
     40  /// \brief Maximum cardinality matching in general graphs
    4141  ///
    42   /// This class implements Edmonds' alternating forest matching
    43   /// algorithm. The algorithm can be started from an arbitrary initial
    44   /// matching (the default is the empty one)
     42  /// This class implements Edmonds' alternating forest matching algorithm
     43  /// for finding a maximum cardinality matching in a general graph.
     44  /// It can be started from an arbitrary initial matching
     45  /// (the default is the empty one).
    4546  ///
    4647  /// The dual solution of the problem is a map of the nodes to
    47   /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c
    48   /// MATCHED/C showing the Gallai-Edmonds decomposition of the
    49   /// graph. The nodes in \c EVEN/D induce a graph with
    50   /// factor-critical components, the nodes in \c ODD/A form the
    51   /// barrier, and the nodes in \c MATCHED/C induce a graph having a
    52   /// perfect matching. The number of the factor-critical components
     48  /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D),
     49  /// \c ODD (or \c A) and \c MATCHED (or \c C) defining the Gallai-Edmonds
     50  /// decomposition of the graph. The nodes in \c EVEN/D induce a subgraph
     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
     53  /// a perfect matching. The number of the factor-critical components
    5354  /// minus the number of barrier nodes is a lower bound on the
    5455  /// unmatched nodes, and the matching is optimal if and only if this bound is
    55   /// tight. This decomposition can be attained by calling \c
     56  /// tight. This decomposition can be obtained by calling \c
    5657  /// decomposition() after running the algorithm.
    5758  ///
    58   /// \param GR The graph type the algorithm runs on.
     59  /// \tparam GR The graph type the algorithm runs on.
    5960  template <typename GR>
    6061  class MaxMatching {
    6162  public:
    6263
     64    /// The graph type of the algorithm
    6365    typedef GR Graph;
    6466    typedef typename Graph::template NodeMap<typename Graph::Arc>
    6567    MatchingMap;
    6668
    67     ///\brief Indicates the Gallai-Edmonds decomposition of the graph.
    68     ///
    69     ///Indicates the Gallai-Edmonds decomposition of the graph. The
    70     ///nodes with Status \c EVEN/D induce a graph with factor-critical
    71     ///components, the nodes in \c ODD/A form the canonical barrier,
    72     ///and the nodes in \c MATCHED/C induce a graph having a perfect
    73     ///matching.
     69    ///\brief Status constants for Gallai-Edmonds decomposition.
     70    ///
     71    ///These constants are used for indicating the Gallai-Edmonds
     72    ///decomposition of a graph. The nodes with status \c EVEN (or \c D)
     73    ///induce a subgraph with factor-critical components, the nodes with
     74    ///status \c ODD (or \c A) form the canonical barrier, and the nodes
     75    ///with status \c MATCHED (or \c C) induce a subgraph having a
     76    ///perfect matching.
    7477    enum Status {
    75       EVEN = 1, D = 1, MATCHED = 0, C = 0, ODD = -1, A = -1, UNMATCHED = -2
     78      EVEN = 1,       ///< = 1. (\c D is an alias for \c EVEN.)
     79      D = 1,
     80      MATCHED = 0,    ///< = 0. (\c C is an alias for \c MATCHED.)
     81      C = 0,
     82      ODD = -1,       ///< = -1. (\c A is an alias for \c ODD.)
     83      A = -1,
     84      UNMATCHED = -2  ///< = -2.
    7685    };
    7786
     
    339348    }
    340349
    341 
    342 
    343350    void extendOnArc(const Arc& a) {
    344351      Node base = _graph.source(a);
     
    409416    }
    410417
    411     /// \name Execution control
     418    /// \name Execution Control
    412419    /// The simplest way to execute the algorithm is to use the
    413     /// \c run() member function.
    414     /// \n
    415 
    416     /// If you need better control on the execution, you must call
    417     /// \ref init(), \ref greedyInit() or \ref matchingInit()
    418     /// functions first, then you can start the algorithm with the \ref
    419     /// startSparse() or startDense() functions.
     420    /// \c run() member function.\n
     421    /// If you need better control on the execution, you have to call
     422    /// one of the functions \ref init(), \ref greedyInit() or
     423    /// \ref matchingInit() first, then you can start the algorithm with
     424    /// \ref startSparse() or \ref startDense().
    420425
    421426    ///@{
    422427
    423     /// \brief Sets the actual matching to the empty matching.
    424     ///
    425     /// Sets the actual matching to the empty matching.
    426     ///
     428    /// \brief Set the initial matching to the empty matching.
     429    ///
     430    /// This function sets the initial matching to the empty matching.
    427431    void init() {
    428432      createStructures();
     
    433437    }
    434438
    435     ///\brief Finds an initial matching in a greedy way
    436     ///
    437     ///It finds an initial matching in a greedy way.
     439    /// \brief Find an initial matching in a greedy way.
     440    ///
     441    /// This function finds an initial matching in a greedy way.
    438442    void greedyInit() {
    439443      createStructures();
     
    459463
    460464
    461     /// \brief Initialize the matching from a map containing.
    462     ///
    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
    465     /// with true value, ie. it contains a matching.
     465    /// \brief Initialize the matching from a map.
     466    ///
     467    /// This function initializes the matching from a \c bool valued edge
     468    /// map. This map should have the property that there are no two incident
     469    /// edges with \c true value, i.e. it really contains a matching.
    466470    /// \return \c true if the map contains a matching.
    467471    template <typename MatchingMap>
     
    490494    }
    491495
    492     /// \brief Starts Edmonds' algorithm
    493     ///
    494     /// If runs the original Edmonds' algorithm.
     496    /// \brief Start Edmonds' algorithm
     497    ///
     498    /// This function runs the original Edmonds' algorithm.
     499    ///
     500    /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
     501    /// called before using this function.
    495502    void startSparse() {
    496503      for(NodeIt n(_graph); n != INVALID; ++n) {
     
    504511    }
    505512
    506     /// \brief Starts Edmonds' algorithm.
    507     ///
    508     /// It runs Edmonds' algorithm with a heuristic of postponing
     513    /// \brief Start Edmonds' algorithm with a heuristic improvement
     514    /// for dense graphs
     515    ///
     516    /// This function runs Edmonds' algorithm with a heuristic of postponing
    509517    /// shrinks, therefore resulting in a faster algorithm for dense graphs.
     518    ///
     519    /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be
     520    /// called before using this function.
    510521    void startDense() {
    511522      for(NodeIt n(_graph); n != INVALID; ++n) {
     
    520531
    521532
    522     /// \brief Runs Edmonds' algorithm
    523     ///
    524     /// Runs Edmonds' algorithm for sparse graphs (<tt>m<2*n</tt>)
    525     /// or Edmonds' algorithm with a heuristic of
    526     /// postponing shrinks for dense graphs.
     533    /// \brief Run Edmonds' algorithm
     534    ///
     535    /// This function runs Edmonds' algorithm. An additional heuristic of
     536    /// postponing shrinks is used for relatively dense graphs
     537    /// (for which <tt>m>=2*n</tt> holds).
    527538    void run() {
    528539      if (countEdges(_graph) < 2 * countNodes(_graph)) {
     
    537548    /// @}
    538549
    539     /// \name Primal solution
    540     /// Functions to get the primal solution, ie. the matching.
     550    /// \name Primal Solution
     551    /// Functions to get the primal solution, i.e. the maximum matching.
    541552
    542553    /// @{
    543554
    544     ///\brief Returns the size of the current matching.
    545     ///
    546     ///Returns the size of the current matching. After \ref
    547     ///run() it returns the size of the maximum matching in the graph.
     555    /// \brief Return the size (cardinality) of the matching.
     556    ///
     557    /// This function returns the size (cardinality) of the current matching.
     558    /// After run() it returns the size of the maximum matching in the graph.
    548559    int matchingSize() const {
    549560      int size = 0;
     
    556567    }
    557568
    558     /// \brief Returns true when the edge is in the matching.
    559     ///
    560     /// Returns true when the edge is in the matching.
     569    /// \brief Return \c true if the given edge is in the matching.
     570    ///
     571    /// This function returns \c true if the given edge is in the current
     572    /// matching.
    561573    bool matching(const Edge& edge) const {
    562574      return edge == (*_matching)[_graph.u(edge)];
    563575    }
    564576
    565     /// \brief Returns the matching edge incident to the given node.
    566     ///
    567     /// Returns the matching edge of a \c node in the actual matching or
    568     /// INVALID if the \c node is not covered by the actual matching.
     577    /// \brief Return the matching arc (or edge) incident to the given node.
     578    ///
     579    /// This function returns the matching arc (or edge) incident to the
     580    /// given node in the current matching or \c INVALID if the node is
     581    /// not covered by the matching.
    569582    Arc matching(const Node& n) const {
    570583      return (*_matching)[n];
    571584    }
    572585
    573     ///\brief Returns the mate of a node in the actual matching.
    574     ///
    575     ///Returns the mate of a \c node in the actual matching or
    576     ///INVALID if the \c node is not covered by the actual matching.
     586    /// \brief Return the mate of the given node.
     587    ///
     588    /// 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.
    577590    Node mate(const Node& n) const {
    578591      return (*_matching)[n] != INVALID ?
     
    582595    /// @}
    583596
    584     /// \name Dual solution
    585     /// Functions to get the dual solution, ie. the decomposition.
     597    /// \name Dual Solution
     598    /// Functions to get the dual solution, i.e. the Gallai-Edmonds
     599    /// decomposition.
    586600
    587601    /// @{
    588602
    589     /// \brief Returns the class of the node in the Edmonds-Gallai
     603    /// \brief Return the status of the given node in the Edmonds-Gallai
    590604    /// decomposition.
    591605    ///
    592     /// Returns the class of the node in the Edmonds-Gallai
    593     /// decomposition.
     606    /// This function returns the \ref Status "status" of the given node
     607    /// in the Edmonds-Gallai decomposition.
    594608    Status decomposition(const Node& n) const {
    595609      return (*_status)[n];
    596610    }
    597611
    598     /// \brief Returns true when the node is in the barrier.
    599     ///
    600     /// Returns true when the node is in the barrier.
     612    /// \brief Return \c true if the given node is in the barrier.
     613    ///
     614    /// This function returns \c true if the given node is in the barrier.
    601615    bool barrier(const Node& n) const {
    602616      return (*_status)[n] == ODD;
     
    616630  /// \f$O(nm\log n)\f$ time complexity.
    617631  ///
    618   /// The maximum weighted matching problem is to find undirected
    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
    621   /// following linear program.
     632  /// The maximum weighted matching problem is to find a subset of the
     633  /// edges in an undirected graph with maximum overall weight for which
     634  /// each node has at most one incident edge.
     635  /// It can be formulated with the following linear program.
    622636  /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f]
    623637  /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
     
    633647  /// optimality. The solution of the dual problem can be used to check
    634648  /// the result of the algorithm. The dual linear problem is the
     649  /// following.
    635650  /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}
    636651      z_B \ge w_{uv} \quad \forall uv\in E\f] */
     
    640655      \frac{\vert B \vert - 1}{2}z_B\f] */
    641656  ///
    642   /// The algorithm can be executed with \c run() or the \c init() and
    643   /// then the \c start() member functions. After it the matching can
    644   /// be asked with \c matching() or mate() functions. The dual
    645   /// solution can be get with \c nodeValue(), \c blossomNum() and \c
    646   /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
    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
    649   /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
     657  /// The algorithm can be executed with the run() function.
     658  /// After it the matching (the primal solution) and the dual solution
     659  /// can be obtained using the query functions and the
     660  /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class,
     661  /// which is able to iterate on the nodes of a blossom.
     662  /// If the value type is integer, then the dual solution is multiplied
     663  /// by \ref MaxWeightedMatching::dualScale "4".
     664  ///
     665  /// \tparam GR The graph type the algorithm runs on.
     666  /// \tparam WM The type edge weight map. The default type is
     667  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
     668#ifdef DOXYGEN
     669  template <typename GR, typename WM>
     670#else
    650671  template <typename GR,
    651672            typename WM = typename GR::template EdgeMap<int> >
     673#endif
    652674  class MaxWeightedMatching {
    653675  public:
    654676
    655     ///\e
     677    /// The graph type of the algorithm
    656678    typedef GR Graph;
    657     ///\e
     679    /// The type of the edge weight map
    658680    typedef WM WeightMap;
    659     ///\e
     681    /// The value type of the edge weights
    660682    typedef typename WeightMap::Value Value;
    661683
     684    typedef typename Graph::template NodeMap<typename Graph::Arc>
     685    MatchingMap;
     686
    662687    /// \brief Scaling factor for dual solution
    663688    ///
    664     /// Scaling factor for dual solution, it is equal to 4 or 1
     689    /// Scaling factor for dual solution. It is equal to 4 or 1
    665690    /// according to the value type.
    666691    static const int dualScale =
    667692      std::numeric_limits<Value>::is_integer ? 4 : 1;
    668 
    669     typedef typename Graph::template NodeMap<typename Graph::Arc>
    670     MatchingMap;
    671693
    672694  private:
     
    16321654    }
    16331655
    1634     /// \name Execution control
     1656    /// \name Execution Control
    16351657    /// The simplest way to execute the algorithm is to use the
    1636     /// \c run() member function.
     1658    /// \ref run() member function.
    16371659
    16381660    ///@{
     
    16401662    /// \brief Initialize the algorithm
    16411663    ///
    1642     /// Initialize the algorithm
     1664    /// This function initializes the algorithm.
    16431665    void init() {
    16441666      createStructures();
     
    16921714    }
    16931715
    1694     /// \brief Starts the algorithm
    1695     ///
    1696     /// Starts the algorithm
     1716    /// \brief Start the algorithm
     1717    ///
     1718    /// This function starts the algorithm.
     1719    ///
     1720    /// \pre \ref init() must be called before using this function.
    16971721    void start() {
    16981722      enum OpType {
     
    17771801    }
    17781802
    1779     /// \brief Runs %MaxWeightedMatching algorithm.
    1780     ///
    1781     /// This method runs the %MaxWeightedMatching algorithm.
     1803    /// \brief Run the algorithm.
     1804    ///
     1805    /// This method runs the \c %MaxWeightedMatching algorithm.
    17821806    ///
    17831807    /// \note mwm.run() is just a shortcut of the following code.
     
    17931817    /// @}
    17941818
    1795     /// \name Primal solution
    1796     /// Functions to get the primal solution, ie. the matching.
     1819    /// \name Primal Solution
     1820    /// Functions to get the primal solution, i.e. the maximum weighted
     1821    /// matching.\n
     1822    /// Either \ref run() or \ref start() function should be called before
     1823    /// using them.
    17971824
    17981825    /// @{
    17991826
    1800     /// \brief Returns the weight of the matching.
    1801     ///
    1802     /// Returns the weight of the matching.
     1827    /// \brief Return the weight of the matching.
     1828    ///
     1829    /// This function returns the weight of the found matching.
     1830    ///
     1831    /// \pre Either run() or start() must be called before using this function.
    18031832    Value matchingValue() const {
    18041833      Value sum = 0;
     
    18111840    }
    18121841
    1813     /// \brief Returns the cardinality of the matching.
    1814     ///
    1815     /// Returns the cardinality of the matching.
     1842    /// \brief Return the size (cardinality) of the matching.
     1843    ///
     1844    /// This function returns the size (cardinality) of the found matching.
     1845    ///
     1846    /// \pre Either run() or start() must be called before using this function.
    18161847    int matchingSize() const {
    18171848      int num = 0;
     
    18241855    }
    18251856
    1826     /// \brief Returns true when the edge is in the matching.
    1827     ///
    1828     /// Returns true when the edge is in the matching.
     1857    /// \brief Return \c true if the given edge is in the matching.
     1858    ///
     1859    /// This function returns \c true if the given edge is in the found
     1860    /// matching.
     1861    ///
     1862    /// \pre Either run() or start() must be called before using this function.
    18291863    bool matching(const Edge& edge) const {
    18301864      return edge == (*_matching)[_graph.u(edge)];
    18311865    }
    18321866
    1833     /// \brief Returns the incident matching arc.
    1834     ///
    1835     /// Returns the incident matching arc from given node. If the
    1836     /// node is not matched then it gives back \c INVALID.
     1867    /// \brief Return the matching arc (or edge) incident to the given node.
     1868    ///
     1869    /// This function returns the matching arc (or edge) incident to the
     1870    /// given node in the found matching or \c INVALID if the node is
     1871    /// not covered by the matching.
     1872    ///
     1873    /// \pre Either run() or start() must be called before using this function.
    18371874    Arc matching(const Node& node) const {
    18381875      return (*_matching)[node];
    18391876    }
    18401877
    1841     /// \brief Returns the mate of the node.
    1842     ///
    1843     /// Returns the adjancent node in a mathcing arc. If the node is
    1844     /// not matched then it gives back \c INVALID.
     1878    /// \brief Return the mate of the given node.
     1879    ///
     1880    /// This function returns the mate of the given node in the found
     1881    /// matching or \c INVALID if the node is not covered by the matching.
     1882    ///
     1883    /// \pre Either run() or start() must be called before using this function.
    18451884    Node mate(const Node& node) const {
    18461885      return (*_matching)[node] != INVALID ?
     
    18501889    /// @}
    18511890
    1852     /// \name Dual solution
    1853     /// Functions to get the dual solution.
     1891    /// \name Dual Solution
     1892    /// Functions to get the dual solution.\n
     1893    /// Either \ref run() or \ref start() function should be called before
     1894    /// using them.
    18541895
    18551896    /// @{
    18561897
    1857     /// \brief Returns the value of the dual solution.
    1858     ///
    1859     /// Returns the value of the dual solution. It should be equal to
    1860     /// the primal value scaled by \ref dualScale "dual scale".
     1898    /// \brief Return the value of the dual solution.
     1899    ///
     1900    /// This function returns the value of the dual solution.
     1901    /// It should be equal to the primal value scaled by \ref dualScale
     1902    /// "dual scale".
     1903    ///
     1904    /// \pre Either run() or start() must be called before using this function.
    18611905    Value dualValue() const {
    18621906      Value sum = 0;
     
    18701914    }
    18711915
    1872     /// \brief Returns the value of the node.
    1873     ///
    1874     /// Returns the the value of the node.
     1916    /// \brief Return the dual value (potential) of the given node.
     1917    ///
     1918    /// This function returns the dual value (potential) of the given node.
     1919    ///
     1920    /// \pre Either run() or start() must be called before using this function.
    18751921    Value nodeValue(const Node& n) const {
    18761922      return (*_node_potential)[n];
    18771923    }
    18781924
    1879     /// \brief Returns the number of the blossoms in the basis.
    1880     ///
    1881     /// Returns the number of the blossoms in the basis.
     1925    /// \brief Return the number of the blossoms in the basis.
     1926    ///
     1927    /// This function returns the number of the blossoms in the basis.
     1928    ///
     1929    /// \pre Either run() or start() must be called before using this function.
    18821930    /// \see BlossomIt
    18831931    int blossomNum() const {
     
    18851933    }
    18861934
    1887 
    1888     /// \brief Returns the number of the nodes in the blossom.
    1889     ///
    1890     /// Returns the number of the nodes in the blossom.
     1935    /// \brief Return the number of the nodes in the given blossom.
     1936    ///
     1937    /// This function returns the number of the nodes in the given blossom.
     1938    ///
     1939    /// \pre Either run() or start() must be called before using this function.
     1940    /// \see BlossomIt
    18911941    int blossomSize(int k) const {
    18921942      return _blossom_potential[k].end - _blossom_potential[k].begin;
    18931943    }
    18941944
    1895     /// \brief Returns the value of the blossom.
    1896     ///
    1897     /// Returns the the value of the blossom.
    1898     /// \see BlossomIt
     1945    /// \brief Return the dual value (ptential) of the given blossom.
     1946    ///
     1947    /// This function returns the dual value (ptential) of the given blossom.
     1948    ///
     1949    /// \pre Either run() or start() must be called before using this function.
    18991950    Value blossomValue(int k) const {
    19001951      return _blossom_potential[k].value;
    19011952    }
    19021953
    1903     /// \brief Iterator for obtaining the nodes of the blossom.
    1904     ///
    1905     /// Iterator for obtaining the nodes of the blossom. This class
    1906     /// provides a common lemon style iterator for listing a
    1907     /// subset of the nodes.
     1954    /// \brief Iterator for obtaining the nodes of a blossom.
     1955    ///
     1956    /// This class provides an iterator for obtaining the nodes of the
     1957    /// given blossom. It lists a subset of the nodes.
     1958    /// Before using this iterator, you must allocate a
     1959    /// MaxWeightedMatching class and execute it.
    19081960    class BlossomIt {
    19091961    public:
     
    19111963      /// \brief Constructor.
    19121964      ///
    1913       /// Constructor to get the nodes of the variable.
     1965      /// Constructor to get the nodes of the given variable.
     1966      ///
     1967      /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or
     1968      /// \ref MaxWeightedMatching::start() "algorithm.start()" must be
     1969      /// called before initializing this iterator.
    19141970      BlossomIt(const MaxWeightedMatching& algorithm, int variable)
    19151971        : _algorithm(&algorithm)
     
    19191975      }
    19201976
    1921       /// \brief Conversion to node.
     1977      /// \brief Conversion to \c Node.
    19221978      ///
    1923       /// Conversion to node.
     1979      /// Conversion to \c Node.
    19241980      operator Node() const {
    19251981        return _algorithm->_blossom_node_list[_index];
     
    19632019  /// \f$O(nm\log n)\f$ time complexity.
    19642020  ///
    1965   /// The maximum weighted matching problem is to find undirected
    1966   /// edges in the graph with maximum overall weight and no two of
    1967   /// them shares their ends and covers all nodes. The problem can be
    1968   /// formulated with the following linear program.
     2021  /// The maximum weighted perfect matching problem is to find a subset of
     2022  /// the edges in an undirected graph with maximum overall weight for which
     2023  /// each node has exactly one incident edge.
     2024  /// It can be formulated with the following linear program.
    19692025  /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f]
    19702026  /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2}
     
    19802036  /// optimality. The solution of the dual problem can be used to check
    19812037  /// the result of the algorithm. The dual linear problem is the
     2038  /// following.
    19822039  /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}z_B \ge
    19832040      w_{uv} \quad \forall uv\in E\f] */
     
    19862043      \frac{\vert B \vert - 1}{2}z_B\f] */
    19872044  ///
    1988   /// The algorithm can be executed with \c run() or the \c init() and
    1989   /// then the \c start() member functions. After it the matching can
    1990   /// be asked with \c matching() or mate() functions. The dual
    1991   /// solution can be get with \c nodeValue(), \c blossomNum() and \c
    1992   /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
    1993   /// "BlossomIt" nested class which is able to iterate on the nodes
    1994   /// of a blossom. If the value type is integral then the dual
    1995   /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
     2045  /// The algorithm can be executed with the run() function.
     2046  /// After it the matching (the primal solution) and the dual solution
     2047  /// can be obtained using the query functions and the
     2048  /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class,
     2049  /// which is able to iterate on the nodes of a blossom.
     2050  /// If the value type is integer, then the dual solution is multiplied
     2051  /// by \ref MaxWeightedMatching::dualScale "4".
     2052  ///
     2053  /// \tparam GR The graph type the algorithm runs on.
     2054  /// \tparam WM The type edge weight map. The default type is
     2055  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
     2056#ifdef DOXYGEN
     2057  template <typename GR, typename WM>
     2058#else
    19962059  template <typename GR,
    19972060            typename WM = typename GR::template EdgeMap<int> >
     2061#endif
    19982062  class MaxWeightedPerfectMatching {
    19992063  public:
    20002064
     2065    /// The graph type of the algorithm
    20012066    typedef GR Graph;
     2067    /// The type of the edge weight map
    20022068    typedef WM WeightMap;
     2069    /// The value type of the edge weights
    20032070    typedef typename WeightMap::Value Value;
    20042071
     
    28192886    }
    28202887
    2821     /// \name Execution control
     2888    /// \name Execution Control
    28222889    /// The simplest way to execute the algorithm is to use the
    2823     /// \c run() member function.
     2890    /// \ref run() member function.
    28242891
    28252892    ///@{
     
    28272894    /// \brief Initialize the algorithm
    28282895    ///
    2829     /// Initialize the algorithm
     2896    /// This function initializes the algorithm.
    28302897    void init() {
    28312898      createStructures();
     
    28752942    }
    28762943
    2877     /// \brief Starts the algorithm
    2878     ///
    2879     /// Starts the algorithm
     2944    /// \brief Start the algorithm
     2945    ///
     2946    /// This function starts the algorithm.
     2947    ///
     2948    /// \pre \ref init() must be called before using this function.
    28802949    bool start() {
    28812950      enum OpType {
     
    29413010    }
    29423011
    2943     /// \brief Runs %MaxWeightedPerfectMatching algorithm.
    2944     ///
    2945     /// This method runs the %MaxWeightedPerfectMatching algorithm.
    2946     ///
    2947     /// \note mwm.run() is just a shortcut of the following code.
     3012    /// \brief Run the algorithm.
     3013    ///
     3014    /// This method runs the \c %MaxWeightedPerfectMatching algorithm.
     3015    ///
     3016    /// \note mwpm.run() is just a shortcut of the following code.
    29483017    /// \code
    2949     ///   mwm.init();
    2950     ///   mwm.start();
     3018    ///   mwpm.init();
     3019    ///   mwpm.start();
    29513020    /// \endcode
    29523021    bool run() {
     
    29573026    /// @}
    29583027
    2959     /// \name Primal solution
    2960     /// Functions to get the primal solution, ie. the matching.
     3028    /// \name Primal Solution
     3029    /// Functions to get the primal solution, i.e. the maximum weighted
     3030    /// perfect matching.\n
     3031    /// Either \ref run() or \ref start() function should be called before
     3032    /// using them.
    29613033
    29623034    /// @{
    29633035
    2964     /// \brief Returns the matching value.
    2965     ///
    2966     /// Returns the matching value.
     3036    /// \brief Return the weight of the matching.
     3037    ///
     3038    /// This function returns the weight of the found matching.
     3039    ///
     3040    /// \pre Either run() or start() must be called before using this function.
    29673041    Value matchingValue() const {
    29683042      Value sum = 0;
     
    29753049    }
    29763050
    2977     /// \brief Returns true when the edge is in the matching.
    2978     ///
    2979     /// Returns true when the edge is in the matching.
     3051    /// \brief Return \c true if the given edge is in the matching.
     3052    ///
     3053    /// This function returns \c true if the given edge is in the found
     3054    /// matching.
     3055    ///
     3056    /// \pre Either run() or start() must be called before using this function.
    29803057    bool matching(const Edge& edge) const {
    29813058      return static_cast<const Edge&>((*_matching)[_graph.u(edge)]) == edge;
    29823059    }
    29833060
    2984     /// \brief Returns the incident matching edge.
    2985     ///
    2986     /// Returns the incident matching arc from given edge.
     3061    /// \brief Return the matching arc (or edge) incident to the given node.
     3062    ///
     3063    /// This function returns the matching arc (or edge) incident to the
     3064    /// given node in the found matching or \c INVALID if the node is
     3065    /// not covered by the matching.
     3066    ///
     3067    /// \pre Either run() or start() must be called before using this function.
    29873068    Arc matching(const Node& node) const {
    29883069      return (*_matching)[node];
    29893070    }
    29903071
    2991     /// \brief Returns the mate of the node.
    2992     ///
    2993     /// Returns the adjancent node in a mathcing arc.
     3072    /// \brief Return the mate of the given node.
     3073    ///
     3074    /// This function returns the mate of the given node in the found
     3075    /// matching or \c INVALID if the node is not covered by the matching.
     3076    ///
     3077    /// \pre Either run() or start() must be called before using this function.
    29943078    Node mate(const Node& node) const {
    29953079      return _graph.target((*_matching)[node]);
     
    29983082    /// @}
    29993083
    3000     /// \name Dual solution
    3001     /// Functions to get the dual solution.
     3084    /// \name Dual Solution
     3085    /// Functions to get the dual solution.\n
     3086    /// Either \ref run() or \ref start() function should be called before
     3087    /// using them.
    30023088
    30033089    /// @{
    30043090
    3005     /// \brief Returns the value of the dual solution.
    3006     ///
    3007     /// Returns the value of the dual solution. It should be equal to
    3008     /// the primal value scaled by \ref dualScale "dual scale".
     3091    /// \brief Return the value of the dual solution.
     3092    ///
     3093    /// This function returns the value of the dual solution.
     3094    /// It should be equal to the primal value scaled by \ref dualScale
     3095    /// "dual scale".
     3096    ///
     3097    /// \pre Either run() or start() must be called before using this function.
    30093098    Value dualValue() const {
    30103099      Value sum = 0;
     
    30183107    }
    30193108
    3020     /// \brief Returns the value of the node.
    3021     ///
    3022     /// Returns the the value of the node.
     3109    /// \brief Return the dual value (potential) of the given node.
     3110    ///
     3111    /// This function returns the dual value (potential) of the given node.
     3112    ///
     3113    /// \pre Either run() or start() must be called before using this function.
    30233114    Value nodeValue(const Node& n) const {
    30243115      return (*_node_potential)[n];
    30253116    }
    30263117
    3027     /// \brief Returns the number of the blossoms in the basis.
    3028     ///
    3029     /// Returns the number of the blossoms in the basis.
     3118    /// \brief Return the number of the blossoms in the basis.
     3119    ///
     3120    /// This function returns the number of the blossoms in the basis.
     3121    ///
     3122    /// \pre Either run() or start() must be called before using this function.
    30303123    /// \see BlossomIt
    30313124    int blossomNum() const {
     
    30333126    }
    30343127
    3035 
    3036     /// \brief Returns the number of the nodes in the blossom.
    3037     ///
    3038     /// Returns the number of the nodes in the blossom.
     3128    /// \brief Return the number of the nodes in the given blossom.
     3129    ///
     3130    /// This function returns the number of the nodes in the given blossom.
     3131    ///
     3132    /// \pre Either run() or start() must be called before using this function.
     3133    /// \see BlossomIt
    30393134    int blossomSize(int k) const {
    30403135      return _blossom_potential[k].end - _blossom_potential[k].begin;
    30413136    }
    30423137
    3043     /// \brief Returns the value of the blossom.
    3044     ///
    3045     /// Returns the the value of the blossom.
    3046     /// \see BlossomIt
     3138    /// \brief Return the dual value (ptential) of the given blossom.
     3139    ///
     3140    /// This function returns the dual value (ptential) of the given blossom.
     3141    ///
     3142    /// \pre Either run() or start() must be called before using this function.
    30473143    Value blossomValue(int k) const {
    30483144      return _blossom_potential[k].value;
    30493145    }
    30503146
    3051     /// \brief Iterator for obtaining the nodes of the blossom.
    3052     ///
    3053     /// Iterator for obtaining the nodes of the blossom. This class
    3054     /// provides a common lemon style iterator for listing a
    3055     /// subset of the nodes.
     3147    /// \brief Iterator for obtaining the nodes of a blossom.
     3148    ///
     3149    /// This class provides an iterator for obtaining the nodes of the
     3150    /// given blossom. It lists a subset of the nodes.
     3151    /// Before using this iterator, you must allocate a
     3152    /// MaxWeightedPerfectMatching class and execute it.
    30563153    class BlossomIt {
    30573154    public:
     
    30593156      /// \brief Constructor.
    30603157      ///
    3061       /// Constructor to get the nodes of the variable.
     3158      /// Constructor to get the nodes of the given variable.
     3159      ///
     3160      /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()"
     3161      /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()"
     3162      /// must be called before initializing this iterator.
    30623163      BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
    30633164        : _algorithm(&algorithm)
     
    30673168      }
    30683169
    3069       /// \brief Conversion to node.
     3170      /// \brief Conversion to \c Node.
    30703171      ///
    3071       /// Conversion to node.
     3172      /// Conversion to \c Node.
    30723173      operator Node() const {
    30733174        return _algorithm->_blossom_node_list[_index];
     
    30843185      /// \brief Validity checking
    30853186      ///
    3086       /// Checks whether the iterator is invalid.
     3187      /// This function checks whether the iterator is invalid.
    30873188      bool operator==(Invalid) const { return _index == _last; }
    30883189
    30893190      /// \brief Validity checking
    30903191      ///
    3091       /// Checks whether the iterator is valid.
     3192      /// This function checks whether the iterator is valid.
    30923193      bool operator!=(Invalid) const { return _index != _last; }
    30933194
     
    31023203  };
    31033204
    3104 
    31053205} //END OF NAMESPACE LEMON
    31063206
Note: See TracChangeset for help on using the changeset viewer.