COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 593:7ac52d6a268e in lemon-main


Ignore:
Timestamp:
04/17/09 09:54:14 (16 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.
Files:
2 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

  • test/max_matching_test.cc

    r590 r593  
    139139  const_mat_test.matching(e);
    140140  const_mat_test.matching(n);
     141  const MaxMatching<Graph>::MatchingMap& mmap =
     142    const_mat_test.matchingMap();
     143  e = mmap[n];
    141144  const_mat_test.mate(n);
    142145
    143146  MaxMatching<Graph>::Status stat =
    144     const_mat_test.decomposition(n);
     147    const_mat_test.status(n);
     148  const MaxMatching<Graph>::StatusMap& smap =
     149    const_mat_test.statusMap();
     150  stat = smap[n];
    145151  const_mat_test.barrier(n);
    146  
    147   ignore_unused_variable_warning(stat);
    148152}
    149153
    … …  
    168172  mat_test.run();
    169173 
    170   const_mat_test.matchingValue();
     174  const_mat_test.matchingWeight();
    171175  const_mat_test.matchingSize();
    172176  const_mat_test.matching(e);
    173177  const_mat_test.matching(n);
     178  const MaxWeightedMatching<Graph>::MatchingMap& mmap =
     179    const_mat_test.matchingMap();
     180  e = mmap[n];
    174181  const_mat_test.mate(n);
    175182 
    … …  
    202209  mat_test.run();
    203210 
    204   const_mat_test.matchingValue();
     211  const_mat_test.matchingWeight();
    205212  const_mat_test.matching(e);
    206213  const_mat_test.matching(n);
     214  const MaxWeightedPerfectMatching<Graph>::MatchingMap& mmap =
     215    const_mat_test.matchingMap();
     216  e = mmap[n];
    207217  const_mat_test.mate(n);
    208218 
    … …  
    225235
    226236  for (NodeIt n(graph); n != INVALID; ++n) {
    227     check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN ||
     237    check(mm.status(n) == MaxMatching<SmartGraph>::EVEN ||
    228238          mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition");
    229     if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) {
     239    if (mm.status(n) == MaxMatching<SmartGraph>::ODD) {
    230240      ++barrier_num;
    231241    } else {
    … …  
    240250      ++num;
    241251    }
    242     check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
    243           mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
     252    check(mm.status(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
     253          mm.status(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
    244254          "Wrong Gallai-Edmonds decomposition");
    245255
    246     check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
    247           mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
     256    check(mm.status(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
     257          mm.status(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
    248258          "Wrong Gallai-Edmonds decomposition");
    249259
    250     if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
    251         mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
     260    if (mm.status(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
     261        mm.status(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
    252262      comp.join(graph.u(e), graph.v(e));
    253263    }
    … …  
    257267  int odd_comp_num = 0;
    258268  for (NodeIt n(graph); n != INVALID; ++n) {
    259     if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) {
     269    if (mm.status(n) != MaxMatching<SmartGraph>::ODD) {
    260270      int root = comp.find(n);
    261271      if (comp_root.find(root) == comp_root.end()) {
Note: See TracChangeset for help on using the changeset viewer.