COIN-OR::LEMON - Graph Library

Changeset 590:b61354458b59 in lemon-main


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)

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r586 r590  
    436436\brief Algorithms for finding matchings in graphs and bipartite graphs.
    437437
    438 This group contains algorithm objects and functions to calculate
     438This group contains the algorithms for calculating
    439439matchings in graphs and bipartite graphs. The general matching problem is
    440 finding a subset of the arcs which does not shares common endpoints.
     440finding a subset of the edges for which each node has at most one incident
     441edge.
    441442
    442443There are several different algorithms for calculate matchings in
  • lemon/max_matching.h

    r581 r590  
    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
  • test/max_matching_test.cc

    r440 r590  
    2121#include <vector>
    2222#include <queue>
    23 #include <lemon/math.h>
    2423#include <cstdlib>
    2524
    2625#include <lemon/max_matching.h>
    2726#include <lemon/smart_graph.h>
     27#include <lemon/concepts/graph.h>
     28#include <lemon/concepts/maps.h>
    2829#include <lemon/lgf_reader.h>
     30#include <lemon/math.h>
    2931
    3032#include "test_tools.h"
     
    111113};
    112114
     115void checkMaxMatchingCompile()
     116{
     117  typedef concepts::Graph Graph;
     118  typedef Graph::Node Node;
     119  typedef Graph::Edge Edge;
     120  typedef Graph::EdgeMap<bool> MatMap;
     121
     122  Graph g;
     123  Node n;
     124  Edge e;
     125  MatMap mat(g);
     126
     127  MaxMatching<Graph> mat_test(g);
     128  const MaxMatching<Graph>&
     129    const_mat_test = mat_test;
     130
     131  mat_test.init();
     132  mat_test.greedyInit();
     133  mat_test.matchingInit(mat);
     134  mat_test.startSparse();
     135  mat_test.startDense();
     136  mat_test.run();
     137 
     138  const_mat_test.matchingSize();
     139  const_mat_test.matching(e);
     140  const_mat_test.matching(n);
     141  const_mat_test.mate(n);
     142
     143  MaxMatching<Graph>::Status stat =
     144    const_mat_test.decomposition(n);
     145  const_mat_test.barrier(n);
     146 
     147  ignore_unused_variable_warning(stat);
     148}
     149
     150void checkMaxWeightedMatchingCompile()
     151{
     152  typedef concepts::Graph Graph;
     153  typedef Graph::Node Node;
     154  typedef Graph::Edge Edge;
     155  typedef Graph::EdgeMap<int> WeightMap;
     156
     157  Graph g;
     158  Node n;
     159  Edge e;
     160  WeightMap w(g);
     161
     162  MaxWeightedMatching<Graph> mat_test(g, w);
     163  const MaxWeightedMatching<Graph>&
     164    const_mat_test = mat_test;
     165
     166  mat_test.init();
     167  mat_test.start();
     168  mat_test.run();
     169 
     170  const_mat_test.matchingValue();
     171  const_mat_test.matchingSize();
     172  const_mat_test.matching(e);
     173  const_mat_test.matching(n);
     174  const_mat_test.mate(n);
     175 
     176  int k = 0;
     177  const_mat_test.dualValue();
     178  const_mat_test.nodeValue(n);
     179  const_mat_test.blossomNum();
     180  const_mat_test.blossomSize(k);
     181  const_mat_test.blossomValue(k);
     182}
     183
     184void checkMaxWeightedPerfectMatchingCompile()
     185{
     186  typedef concepts::Graph Graph;
     187  typedef Graph::Node Node;
     188  typedef Graph::Edge Edge;
     189  typedef Graph::EdgeMap<int> WeightMap;
     190
     191  Graph g;
     192  Node n;
     193  Edge e;
     194  WeightMap w(g);
     195
     196  MaxWeightedPerfectMatching<Graph> mat_test(g, w);
     197  const MaxWeightedPerfectMatching<Graph>&
     198    const_mat_test = mat_test;
     199
     200  mat_test.init();
     201  mat_test.start();
     202  mat_test.run();
     203 
     204  const_mat_test.matchingValue();
     205  const_mat_test.matching(e);
     206  const_mat_test.matching(n);
     207  const_mat_test.mate(n);
     208 
     209  int k = 0;
     210  const_mat_test.dualValue();
     211  const_mat_test.nodeValue(n);
     212  const_mat_test.blossomNum();
     213  const_mat_test.blossomSize(k);
     214  const_mat_test.blossomValue(k);
     215}
     216
    113217void checkMatching(const SmartGraph& graph,
    114218                   const MaxMatching<SmartGraph>& mm) {
Note: See TracChangeset for help on using the changeset viewer.