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);