lemon/max_matching.h
changeset 593 7ac52d6a268e
parent 590 b61354458b59
     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