Extend and modify the interface of matching algorithms (#265)
authorPeter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 09:54:14 +0200
changeset 5857ac52d6a268e
parent 582 b61354458b59
child 586 d657c71db7db
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.
lemon/max_matching.h
test/max_matching_test.cc
     1.1 --- a/lemon/max_matching.h	Wed Apr 15 12:01:14 2009 +0200
     1.2 +++ b/lemon/max_matching.h	Fri Apr 17 09:54:14 2009 +0200
     1.3 @@ -40,7 +40,7 @@
     1.4    /// \brief Maximum cardinality matching in general graphs
     1.5    ///
     1.6    /// This class implements Edmonds' alternating forest matching algorithm
     1.7 -  /// for finding a maximum cardinality matching in a general graph. 
     1.8 +  /// for finding a maximum cardinality matching in a general undirected graph.
     1.9    /// It can be started from an arbitrary initial matching 
    1.10    /// (the default is the empty one).
    1.11    ///
    1.12 @@ -53,16 +53,17 @@
    1.13    /// a perfect matching. The number of the factor-critical components
    1.14    /// minus the number of barrier nodes is a lower bound on the
    1.15    /// unmatched nodes, and the matching is optimal if and only if this bound is
    1.16 -  /// tight. This decomposition can be obtained by calling \c
    1.17 -  /// decomposition() after running the algorithm.
    1.18 +  /// tight. This decomposition can be obtained using \ref status() or
    1.19 +  /// \ref statusMap() after running the algorithm.
    1.20    ///
    1.21 -  /// \tparam GR The graph type the algorithm runs on.
    1.22 +  /// \tparam GR The undirected graph type the algorithm runs on.
    1.23    template <typename GR>
    1.24    class MaxMatching {
    1.25    public:
    1.26  
    1.27      /// The graph type of the algorithm
    1.28      typedef GR Graph;
    1.29 +    /// The type of the matching map
    1.30      typedef typename Graph::template NodeMap<typename Graph::Arc>
    1.31      MatchingMap;
    1.32  
    1.33 @@ -84,6 +85,7 @@
    1.34        UNMATCHED = -2  ///< = -2.
    1.35      };
    1.36  
    1.37 +    /// The type of the status map
    1.38      typedef typename Graph::template NodeMap<Status> StatusMap;
    1.39  
    1.40    private:
    1.41 @@ -583,6 +585,14 @@
    1.42        return (*_matching)[n];
    1.43      }
    1.44  
    1.45 +    /// \brief Return a const reference to the matching map.
    1.46 +    ///
    1.47 +    /// This function returns a const reference to a node map that stores
    1.48 +    /// the matching arc (or edge) incident to each node.
    1.49 +    const MatchingMap& matchingMap() const {
    1.50 +      return *_matching;
    1.51 +    }
    1.52 +
    1.53      /// \brief Return the mate of the given node.
    1.54      ///
    1.55      /// This function returns the mate of the given node in the current 
    1.56 @@ -605,10 +615,19 @@
    1.57      ///
    1.58      /// This function returns the \ref Status "status" of the given node
    1.59      /// in the Edmonds-Gallai decomposition.
    1.60 -    Status decomposition(const Node& n) const {
    1.61 +    Status status(const Node& n) const {
    1.62        return (*_status)[n];
    1.63      }
    1.64  
    1.65 +    /// \brief Return a const reference to the status map, which stores
    1.66 +    /// the Edmonds-Gallai decomposition.
    1.67 +    ///
    1.68 +    /// This function returns a const reference to a node map that stores the
    1.69 +    /// \ref Status "status" of each node in the Edmonds-Gallai decomposition.
    1.70 +    const StatusMap& statusMap() const {
    1.71 +      return *_status;
    1.72 +    }
    1.73 +
    1.74      /// \brief Return \c true if the given node is in the barrier.
    1.75      ///
    1.76      /// This function returns \c true if the given node is in the barrier.
    1.77 @@ -662,7 +681,7 @@
    1.78    /// If the value type is integer, then the dual solution is multiplied
    1.79    /// by \ref MaxWeightedMatching::dualScale "4".
    1.80    ///
    1.81 -  /// \tparam GR The graph type the algorithm runs on.
    1.82 +  /// \tparam GR The undirected graph type the algorithm runs on.
    1.83    /// \tparam WM The type edge weight map. The default type is 
    1.84    /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
    1.85  #ifdef DOXYGEN
    1.86 @@ -681,6 +700,7 @@
    1.87      /// The value type of the edge weights
    1.88      typedef typename WeightMap::Value Value;
    1.89  
    1.90 +    /// The type of the matching map
    1.91      typedef typename Graph::template NodeMap<typename Graph::Arc>
    1.92      MatchingMap;
    1.93  
    1.94 @@ -1829,7 +1849,7 @@
    1.95      /// This function returns the weight of the found matching.
    1.96      ///
    1.97      /// \pre Either run() or start() must be called before using this function.
    1.98 -    Value matchingValue() const {
    1.99 +    Value matchingWeight() const {
   1.100        Value sum = 0;
   1.101        for (NodeIt n(_graph); n != INVALID; ++n) {
   1.102          if ((*_matching)[n] != INVALID) {
   1.103 @@ -1875,6 +1895,14 @@
   1.104        return (*_matching)[node];
   1.105      }
   1.106  
   1.107 +    /// \brief Return a const reference to the matching map.
   1.108 +    ///
   1.109 +    /// This function returns a const reference to a node map that stores
   1.110 +    /// the matching arc (or edge) incident to each node.
   1.111 +    const MatchingMap& matchingMap() const {
   1.112 +      return *_matching;
   1.113 +    }
   1.114 +
   1.115      /// \brief Return the mate of the given node.
   1.116      ///
   1.117      /// This function returns the mate of the given node in the found 
   1.118 @@ -2050,7 +2078,7 @@
   1.119    /// If the value type is integer, then the dual solution is multiplied
   1.120    /// by \ref MaxWeightedMatching::dualScale "4".
   1.121    ///
   1.122 -  /// \tparam GR The graph type the algorithm runs on.
   1.123 +  /// \tparam GR The undirected graph type the algorithm runs on.
   1.124    /// \tparam WM The type edge weight map. The default type is 
   1.125    /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
   1.126  #ifdef DOXYGEN
   1.127 @@ -2076,6 +2104,7 @@
   1.128      static const int dualScale =
   1.129        std::numeric_limits<Value>::is_integer ? 4 : 1;
   1.130  
   1.131 +    /// The type of the matching map
   1.132      typedef typename Graph::template NodeMap<typename Graph::Arc>
   1.133      MatchingMap;
   1.134  
   1.135 @@ -3038,7 +3067,7 @@
   1.136      /// This function returns the weight of the found matching.
   1.137      ///
   1.138      /// \pre Either run() or start() must be called before using this function.
   1.139 -    Value matchingValue() const {
   1.140 +    Value matchingWeight() const {
   1.141        Value sum = 0;
   1.142        for (NodeIt n(_graph); n != INVALID; ++n) {
   1.143          if ((*_matching)[n] != INVALID) {
   1.144 @@ -3069,6 +3098,14 @@
   1.145        return (*_matching)[node];
   1.146      }
   1.147  
   1.148 +    /// \brief Return a const reference to the matching map.
   1.149 +    ///
   1.150 +    /// This function returns a const reference to a node map that stores
   1.151 +    /// the matching arc (or edge) incident to each node.
   1.152 +    const MatchingMap& matchingMap() const {
   1.153 +      return *_matching;
   1.154 +    }
   1.155 +
   1.156      /// \brief Return the mate of the given node.
   1.157      ///
   1.158      /// This function returns the mate of the given node in the found 
     2.1 --- a/test/max_matching_test.cc	Wed Apr 15 12:01:14 2009 +0200
     2.2 +++ b/test/max_matching_test.cc	Fri Apr 17 09:54:14 2009 +0200
     2.3 @@ -138,13 +138,17 @@
     2.4    const_mat_test.matchingSize();
     2.5    const_mat_test.matching(e);
     2.6    const_mat_test.matching(n);
     2.7 +  const MaxMatching<Graph>::MatchingMap& mmap =
     2.8 +    const_mat_test.matchingMap();
     2.9 +  e = mmap[n];
    2.10    const_mat_test.mate(n);
    2.11  
    2.12    MaxMatching<Graph>::Status stat = 
    2.13 -    const_mat_test.decomposition(n);
    2.14 +    const_mat_test.status(n);
    2.15 +  const MaxMatching<Graph>::StatusMap& smap =
    2.16 +    const_mat_test.statusMap();
    2.17 +  stat = smap[n];
    2.18    const_mat_test.barrier(n);
    2.19 -  
    2.20 -  ignore_unused_variable_warning(stat);
    2.21  }
    2.22  
    2.23  void checkMaxWeightedMatchingCompile()
    2.24 @@ -167,10 +171,13 @@
    2.25    mat_test.start();
    2.26    mat_test.run();
    2.27    
    2.28 -  const_mat_test.matchingValue();
    2.29 +  const_mat_test.matchingWeight();
    2.30    const_mat_test.matchingSize();
    2.31    const_mat_test.matching(e);
    2.32    const_mat_test.matching(n);
    2.33 +  const MaxWeightedMatching<Graph>::MatchingMap& mmap =
    2.34 +    const_mat_test.matchingMap();
    2.35 +  e = mmap[n];
    2.36    const_mat_test.mate(n);
    2.37    
    2.38    int k = 0;
    2.39 @@ -201,9 +208,12 @@
    2.40    mat_test.start();
    2.41    mat_test.run();
    2.42    
    2.43 -  const_mat_test.matchingValue();
    2.44 +  const_mat_test.matchingWeight();
    2.45    const_mat_test.matching(e);
    2.46    const_mat_test.matching(n);
    2.47 +  const MaxWeightedPerfectMatching<Graph>::MatchingMap& mmap =
    2.48 +    const_mat_test.matchingMap();
    2.49 +  e = mmap[n];
    2.50    const_mat_test.mate(n);
    2.51    
    2.52    int k = 0;
    2.53 @@ -224,9 +234,9 @@
    2.54    int barrier_num = 0;
    2.55  
    2.56    for (NodeIt n(graph); n != INVALID; ++n) {
    2.57 -    check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN ||
    2.58 +    check(mm.status(n) == MaxMatching<SmartGraph>::EVEN ||
    2.59            mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition");
    2.60 -    if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) {
    2.61 +    if (mm.status(n) == MaxMatching<SmartGraph>::ODD) {
    2.62        ++barrier_num;
    2.63      } else {
    2.64        comp.insert(n);
    2.65 @@ -239,16 +249,16 @@
    2.66        check(e == mm.matching(graph.v(e)), "Wrong matching");
    2.67        ++num;
    2.68      }
    2.69 -    check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
    2.70 -          mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
    2.71 +    check(mm.status(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
    2.72 +          mm.status(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
    2.73            "Wrong Gallai-Edmonds decomposition");
    2.74  
    2.75 -    check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
    2.76 -          mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
    2.77 +    check(mm.status(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
    2.78 +          mm.status(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
    2.79            "Wrong Gallai-Edmonds decomposition");
    2.80  
    2.81 -    if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
    2.82 -        mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
    2.83 +    if (mm.status(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
    2.84 +        mm.status(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
    2.85        comp.join(graph.u(e), graph.v(e));
    2.86      }
    2.87    }
    2.88 @@ -256,7 +266,7 @@
    2.89    std::set<int> comp_root;
    2.90    int odd_comp_num = 0;
    2.91    for (NodeIt n(graph); n != INVALID; ++n) {
    2.92 -    if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) {
    2.93 +    if (mm.status(n) != MaxMatching<SmartGraph>::ODD) {
    2.94        int root = comp.find(n);
    2.95        if (comp_root.find(root) == comp_root.end()) {
    2.96          comp_root.insert(root);