# HG changeset patch # User Peter Kovacs # Date 2009-04-17 09:54:14 # 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 --git a/lemon/max_matching.h b/lemon/max_matching.h --- a/lemon/max_matching.h +++ b/lemon/max_matching.h @@ -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 class MaxMatching { public: /// The graph type of the algorithm typedef GR Graph; + /// The type of the matching map typedef typename Graph::template NodeMap MatchingMap; @@ -84,6 +85,7 @@ UNMATCHED = -2 ///< = -2. }; + /// The type of the status map typedef typename Graph::template NodeMap 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". #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 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". #ifdef DOXYGEN @@ -2076,6 +2104,7 @@ static const int dualScale = std::numeric_limits::is_integer ? 4 : 1; + /// The type of the matching map typedef typename Graph::template NodeMap 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 --git a/test/max_matching_test.cc b/test/max_matching_test.cc --- a/test/max_matching_test.cc +++ b/test/max_matching_test.cc @@ -138,13 +138,17 @@ const_mat_test.matchingSize(); const_mat_test.matching(e); const_mat_test.matching(n); + const MaxMatching::MatchingMap& mmap = + const_mat_test.matchingMap(); + e = mmap[n]; const_mat_test.mate(n); MaxMatching::Status stat = - const_mat_test.decomposition(n); + const_mat_test.status(n); + const MaxMatching::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::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::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::EVEN || + check(mm.status(n) == MaxMatching::EVEN || mm.matching(n) != INVALID, "Wrong Gallai-Edmonds decomposition"); - if (mm.decomposition(n) == MaxMatching::ODD) { + if (mm.status(n) == MaxMatching::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::EVEN || - mm.decomposition(graph.v(e)) != MaxMatching::MATCHED, + check(mm.status(graph.u(e)) != MaxMatching::EVEN || + mm.status(graph.v(e)) != MaxMatching::MATCHED, "Wrong Gallai-Edmonds decomposition"); - check(mm.decomposition(graph.v(e)) != MaxMatching::EVEN || - mm.decomposition(graph.u(e)) != MaxMatching::MATCHED, + check(mm.status(graph.v(e)) != MaxMatching::EVEN || + mm.status(graph.u(e)) != MaxMatching::MATCHED, "Wrong Gallai-Edmonds decomposition"); - if (mm.decomposition(graph.u(e)) != MaxMatching::ODD && - mm.decomposition(graph.v(e)) != MaxMatching::ODD) { + if (mm.status(graph.u(e)) != MaxMatching::ODD && + mm.status(graph.v(e)) != MaxMatching::ODD) { comp.join(graph.u(e), graph.v(e)); } } @@ -256,7 +266,7 @@ std::set comp_root; int odd_comp_num = 0; for (NodeIt n(graph); n != INVALID; ++n) { - if (mm.decomposition(n) != MaxMatching::ODD) { + if (mm.status(n) != MaxMatching::ODD) { int root = comp.find(n); if (comp_root.find(root) == comp_root.end()) { comp_root.insert(root);