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