Changeset 593:7ac52d6a268e in lemon-1.2 for lemon

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.

File:

• lemon/max_matching.h (modified) (14 diffs)

lemon/max_matching.h

@@ -41 +41 @@
   ///
   /// 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).
@@ -54 +54 @@
   /// 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 {
@@ -64 +64 @@
     /// The graph type of the algorithm
     typedef GR Graph;
+    /// The type of the matching map
     typedef typename Graph::template NodeMap<typename Graph::Arc>
     MatchingMap;
@@ -85 +86 @@
     };
 
+    /// The type of the status map
     typedef typename Graph::template NodeMap<Status> StatusMap;
 
@@ -584 +586 @@
     }
 
+    /// \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.
     ///
@@ -606 +616 @@
     /// 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;
     }
 
@@ -663 +682 @@
   /// 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>".
@@ -682 +701 @@
     typedef typename WeightMap::Value Value;
 
+    /// The type of the matching map
     typedef typename Graph::template NodeMap<typename Graph::Arc>
     MatchingMap;
@@ -1830 +1850 @@
     ///
     /// \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) {
@@ -1874 +1894 @@
     Arc matching(const Node& node) const {
       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;
     }
 
@@ -2051 +2079 @@
   /// 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>".
@@ -2077 +2105 @@
       std::numeric_limits<Value>::is_integer ? 4 : 1;
 
+    /// The type of the matching map
     typedef typename Graph::template NodeMap<typename Graph::Arc>
     MatchingMap;
@@ -3039 +3068 @@
     ///
     /// \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) {
@@ -3068 +3097 @@
     Arc matching(const Node& node) const {
       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;
     }