COIN-OR::LEMON - Graph Library

Changeset 593:7ac52d6a268e in lemon-1.2 for lemon


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

Extend and modify the interface of matching algorithms (#265)

  • Rename decomposition() to status() in MaxMatching?.
  • Add a new query function statusMap() to MaxMatching?.
  • Add a new query function matchingMap() to all the three classes.
  • Rename matchingValue() to matchingWeight() in the weighted matching classes.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/max_matching.h

    r590 r593  
    4141  ///
    4242  /// This class implements Edmonds' alternating forest matching algorithm
    43   /// for finding a maximum cardinality matching in a general graph.
     43  /// for finding a maximum cardinality matching in a general undirected graph.
    4444  /// It can be started from an arbitrary initial matching
    4545  /// (the default is the empty one).
     
    5454  /// minus the number of barrier nodes is a lower bound on the
    5555  /// unmatched nodes, and the matching is optimal if and only if this bound is
    56   /// tight. This decomposition can be obtained by calling \c
    57   /// decomposition() after running the algorithm.
     56  /// tight. This decomposition can be obtained using \ref status() or
     57  /// \ref statusMap() after running the algorithm.
    5858  ///
    59   /// \tparam GR The graph type the algorithm runs on.
     59  /// \tparam GR The undirected graph type the algorithm runs on.
    6060  template <typename GR>
    6161  class MaxMatching {
     
    6464    /// The graph type of the algorithm
    6565    typedef GR Graph;
     66    /// The type of the matching map
    6667    typedef typename Graph::template NodeMap<typename Graph::Arc>
    6768    MatchingMap;
     
    8586    };
    8687
     88    /// The type of the status map
    8789    typedef typename Graph::template NodeMap<Status> StatusMap;
    8890
     
    584586    }
    585587
     588    /// \brief Return a const reference to the matching map.
     589    ///
     590    /// This function returns a const reference to a node map that stores
     591    /// the matching arc (or edge) incident to each node.
     592    const MatchingMap& matchingMap() const {
     593      return *_matching;
     594    }
     595
    586596    /// \brief Return the mate of the given node.
    587597    ///
     
    606616    /// This function returns the \ref Status "status" of the given node
    607617    /// in the Edmonds-Gallai decomposition.
    608     Status decomposition(const Node& n) const {
     618    Status status(const Node& n) const {
    609619      return (*_status)[n];
     620    }
     621
     622    /// \brief Return a const reference to the status map, which stores
     623    /// the Edmonds-Gallai decomposition.
     624    ///
     625    /// This function returns a const reference to a node map that stores the
     626    /// \ref Status "status" of each node in the Edmonds-Gallai decomposition.
     627    const StatusMap& statusMap() const {
     628      return *_status;
    610629    }
    611630
     
    663682  /// by \ref MaxWeightedMatching::dualScale "4".
    664683  ///
    665   /// \tparam GR The graph type the algorithm runs on.
     684  /// \tparam GR The undirected graph type the algorithm runs on.
    666685  /// \tparam WM The type edge weight map. The default type is
    667686  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
     
    682701    typedef typename WeightMap::Value Value;
    683702
     703    /// The type of the matching map
    684704    typedef typename Graph::template NodeMap<typename Graph::Arc>
    685705    MatchingMap;
     
    18301850    ///
    18311851    /// \pre Either run() or start() must be called before using this function.
    1832     Value matchingValue() const {
     1852    Value matchingWeight() const {
    18331853      Value sum = 0;
    18341854      for (NodeIt n(_graph); n != INVALID; ++n) {
     
    18741894    Arc matching(const Node& node) const {
    18751895      return (*_matching)[node];
     1896    }
     1897
     1898    /// \brief Return a const reference to the matching map.
     1899    ///
     1900    /// This function returns a const reference to a node map that stores
     1901    /// the matching arc (or edge) incident to each node.
     1902    const MatchingMap& matchingMap() const {
     1903      return *_matching;
    18761904    }
    18771905
     
    20512079  /// by \ref MaxWeightedMatching::dualScale "4".
    20522080  ///
    2053   /// \tparam GR The graph type the algorithm runs on.
     2081  /// \tparam GR The undirected graph type the algorithm runs on.
    20542082  /// \tparam WM The type edge weight map. The default type is
    20552083  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
     
    20772105      std::numeric_limits<Value>::is_integer ? 4 : 1;
    20782106
     2107    /// The type of the matching map
    20792108    typedef typename Graph::template NodeMap<typename Graph::Arc>
    20802109    MatchingMap;
     
    30393068    ///
    30403069    /// \pre Either run() or start() must be called before using this function.
    3041     Value matchingValue() const {
     3070    Value matchingWeight() const {
    30423071      Value sum = 0;
    30433072      for (NodeIt n(_graph); n != INVALID; ++n) {
     
    30683097    Arc matching(const Node& node) const {
    30693098      return (*_matching)[node];
     3099    }
     3100
     3101    /// \brief Return a const reference to the matching map.
     3102    ///
     3103    /// This function returns a const reference to a node map that stores
     3104    /// the matching arc (or edge) incident to each node.
     3105    const MatchingMap& matchingMap() const {
     3106      return *_matching;
    30703107    }
    30713108
Note: See TracChangeset for help on using the changeset viewer.