# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1239954854 -7200
# Node ID 7ac52d6a268e196069ae0bbff57b2e7c45b50219
# Parent  b61354458b5982d2f29892f8f33b9b71bdb2d1ac
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.

diff -r b61354458b59 -r 7ac52d6a268e lemon/max_matching.h
--- a/lemon/max_matching.h	Wed Apr 15 12:01:14 2009 +0200
+++ b/lemon/max_matching.h	Fri Apr 17 09:54:14 2009 +0200
@@ -40,7 +40,7 @@
   /// \brief Maximum cardinality matching in general graphs
   ///
   /// This class implements Edmonds' alternating forest matching algorithm
-  /// for finding a maximum cardinality matching in a general graph. 
+  /// for finding a maximum cardinality matching in a general undirected graph.
   /// It can be started from an arbitrary initial matching 
   /// (the default is the empty one).
   ///
@@ -53,16 +53,17 @@
   /// a perfect matching. The number of the factor-critical components
   /// minus the number of barrier nodes is a lower bound on the
   /// unmatched nodes, and the matching is optimal if and only if this bound is
-  /// tight. This decomposition can be obtained by calling \c
-  /// decomposition() after running the algorithm.
+  /// tight. This decomposition can be obtained using \ref status() or
+  /// \ref statusMap() after running the algorithm.
   ///
-  /// \tparam GR The graph type the algorithm runs on.
+  /// \tparam GR The undirected graph type the algorithm runs on.
   template <typename GR>
   class MaxMatching {
   public:
 
     /// The graph type of the algorithm
     typedef GR Graph;
+    /// The type of the matching map
     typedef typename Graph::template NodeMap<typename Graph::Arc>
     MatchingMap;
 
@@ -84,6 +85,7 @@
       UNMATCHED = -2  ///< = -2.
     };
 
+    /// The type of the status map
     typedef typename Graph::template NodeMap<Status> StatusMap;
 
   private:
@@ -583,6 +585,14 @@
       return (*_matching)[n];
     }
 
+    /// \brief Return a const reference to the matching map.
+    ///
+    /// This function returns a const reference to a node map that stores
+    /// the matching arc (or edge) incident to each node.
+    const MatchingMap& matchingMap() const {
+      return *_matching;
+    }
+
     /// \brief Return the mate of the given node.
     ///
     /// This function returns the mate of the given node in the current 
@@ -605,10 +615,19 @@
     ///
     /// This function returns the \ref Status "status" of the given node
     /// in the Edmonds-Gallai decomposition.
-    Status decomposition(const Node& n) const {
+    Status status(const Node& n) const {
       return (*_status)[n];
     }
 
+    /// \brief Return a const reference to the status map, which stores
+    /// the Edmonds-Gallai decomposition.
+    ///
+    /// This function returns a const reference to a node map that stores the
+    /// \ref Status "status" of each node in the Edmonds-Gallai decomposition.
+    const StatusMap& statusMap() const {
+      return *_status;
+    }
+
     /// \brief Return \c true if the given node is in the barrier.
     ///
     /// This function returns \c true if the given node is in the barrier.
@@ -662,7 +681,7 @@
   /// If the value type is integer, then the dual solution is multiplied
   /// by \ref MaxWeightedMatching::dualScale "4".
   ///
-  /// \tparam GR The graph type the algorithm runs on.
+  /// \tparam GR The undirected graph type the algorithm runs on.
   /// \tparam WM The type edge weight map. The default type is 
   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 #ifdef DOXYGEN
@@ -681,6 +700,7 @@
     /// The value type of the edge weights
     typedef typename WeightMap::Value Value;
 
+    /// The type of the matching map
     typedef typename Graph::template NodeMap<typename Graph::Arc>
     MatchingMap;
 
@@ -1829,7 +1849,7 @@
     /// This function returns the weight of the found matching.
     ///
     /// \pre Either run() or start() must be called before using this function.
-    Value matchingValue() const {
+    Value matchingWeight() const {
       Value sum = 0;
       for (NodeIt n(_graph); n != INVALID; ++n) {
         if ((*_matching)[n] != INVALID) {
@@ -1875,6 +1895,14 @@
       return (*_matching)[node];
     }
 
+    /// \brief Return a const reference to the matching map.
+    ///
+    /// This function returns a const reference to a node map that stores
+    /// the matching arc (or edge) incident to each node.
+    const MatchingMap& matchingMap() const {
+      return *_matching;
+    }
+
     /// \brief Return the mate of the given node.
     ///
     /// This function returns the mate of the given node in the found 
@@ -2050,7 +2078,7 @@
   /// If the value type is integer, then the dual solution is multiplied
   /// by \ref MaxWeightedMatching::dualScale "4".
   ///
-  /// \tparam GR The graph type the algorithm runs on.
+  /// \tparam GR The undirected graph type the algorithm runs on.
   /// \tparam WM The type edge weight map. The default type is 
   /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
 #ifdef DOXYGEN
@@ -2076,6 +2104,7 @@
     static const int dualScale =
       std::numeric_limits<Value>::is_integer ? 4 : 1;
 
+    /// The type of the matching map
     typedef typename Graph::template NodeMap<typename Graph::Arc>
     MatchingMap;
 
@@ -3038,7 +3067,7 @@
     /// This function returns the weight of the found matching.
     ///
     /// \pre Either run() or start() must be called before using this function.
-    Value matchingValue() const {
+    Value matchingWeight() const {
       Value sum = 0;
       for (NodeIt n(_graph); n != INVALID; ++n) {
         if ((*_matching)[n] != INVALID) {
@@ -3069,6 +3098,14 @@
       return (*_matching)[node];
     }
 
+    /// \brief Return a const reference to the matching map.
+    ///
+    /// This function returns a const reference to a node map that stores
+    /// the matching arc (or edge) incident to each node.
+    const MatchingMap& matchingMap() const {
+      return *_matching;
+    }
+
     /// \brief Return the mate of the given node.
     ///
     /// This function returns the mate of the given node in the found 
diff -r b61354458b59 -r 7ac52d6a268e test/max_matching_test.cc
--- a/test/max_matching_test.cc	Wed Apr 15 12:01:14 2009 +0200
+++ b/test/max_matching_test.cc	Fri Apr 17 09:54:14 2009 +0200
@@ -138,13 +138,17 @@
   const_mat_test.matchingSize();
   const_mat_test.matching(e);
   const_mat_test.matching(n);
+  const MaxMatching<Graph>::MatchingMap& mmap =
+    const_mat_test.matchingMap();
+  e = mmap[n];
   const_mat_test.mate(n);
 
   MaxMatching<Graph>::Status stat = 
-    const_mat_test.decomposition(n);
+    const_mat_test.status(n);
+  const MaxMatching<Graph>::StatusMap& smap =
+    const_mat_test.statusMap();
+  stat = smap[n];
   const_mat_test.barrier(n);
-  
-  ignore_unused_variable_warning(stat);
 }
 
 void checkMaxWeightedMatchingCompile()
@@ -167,10 +171,13 @@
   mat_test.start();
   mat_test.run();
   
-  const_mat_test.matchingValue();
+  const_mat_test.matchingWeight();
   const_mat_test.matchingSize();
   const_mat_test.matching(e);
   const_mat_test.matching(n);
+  const MaxWeightedMatching<Graph>::MatchingMap& mmap =
+    const_mat_test.matchingMap();
+  e = mmap[n];
   const_mat_test.mate(n);
   
   int k = 0;
@@ -201,9 +208,12 @@
   mat_test.start();
   mat_test.run();
   
-  const_mat_test.matchingValue();
+  const_mat_test.matchingWeight();
   const_mat_test.matching(e);
   const_mat_test.matching(n);
+  const MaxWeightedPerfectMatching<Graph>::MatchingMap& mmap =
+    const_mat_test.matchingMap();
+  e = mmap[n];
   const_mat_test.mate(n);
   
   int k = 0;
@@ -224,9 +234,9 @@
   int barrier_num = 0;
 
   for (NodeIt n(graph); n != INVALID; ++n) {
-    check(mm.decomposition(n) == MaxMatching<SmartGraph>::EVEN ||
+    check(mm.status(n) == MaxMatching<SmartGraph>::EVEN ||
           mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition");
-    if (mm.decomposition(n) == MaxMatching<SmartGraph>::ODD) {
+    if (mm.status(n) == MaxMatching<SmartGraph>::ODD) {
       ++barrier_num;
     } else {
       comp.insert(n);
@@ -239,16 +249,16 @@
       check(e == mm.matching(graph.v(e)), "Wrong matching");
       ++num;
     }
-    check(mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
-          mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
+    check(mm.status(graph.u(e)) != MaxMatching<SmartGraph>::EVEN ||
+          mm.status(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,
           "Wrong Gallai-Edmonds decomposition");
 
-    check(mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
-          mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
+    check(mm.status(graph.v(e)) != MaxMatching<SmartGraph>::EVEN ||
+          mm.status(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,
           "Wrong Gallai-Edmonds decomposition");
 
-    if (mm.decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
-        mm.decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
+    if (mm.status(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&
+        mm.status(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {
       comp.join(graph.u(e), graph.v(e));
     }
   }
@@ -256,7 +266,7 @@
   std::set<int> comp_root;
   int odd_comp_num = 0;
   for (NodeIt n(graph); n != INVALID; ++n) {
-    if (mm.decomposition(n) != MaxMatching<SmartGraph>::ODD) {
+    if (mm.status(n) != MaxMatching<SmartGraph>::ODD) {
       int root = comp.find(n);
       if (comp_root.find(root) == comp_root.end()) {
         comp_root.insert(root);