# HG changeset patch # User deba # Date 1187702541 0 # Node ID 19651a04d056aa342b9ef0c976b209d9d8b2eb04 # Parent 7a096a6bf53ad27fdfa447f4988ec78ee3f3866c Query functions: aMatching and bMatching Modified algorithm function interfaces ANodeMap matching map BNodeMap barrier map Consistency between augmenting path and push-relabel algorithm diff -r 7a096a6bf53a -r 19651a04d056 lemon/bipartite_matching.h --- a/lemon/bipartite_matching.h Sat Aug 11 16:34:41 2007 +0000 +++ b/lemon/bipartite_matching.h Tue Aug 21 13:22:21 2007 +0000 @@ -359,7 +359,7 @@ int quickMatching(MatchingMap& mm) const { for (ANodeIt it(*graph); it != INVALID; ++it) { if (anode_matching[it] != INVALID) { - mm[anode_matching[it]] = true; + mm.set(anode_matching[it], true); } } return matching_size; @@ -372,11 +372,36 @@ template int matching(MatchingMap& mm) const { for (UEdgeIt it(*graph); it != INVALID; ++it) { - mm[it] = it == anode_matching[graph->aNode(it)]; + mm.set(it, it == anode_matching[graph->aNode(it)]); } return matching_size; } + ///Gives back the matching in an ANodeMap. + + ///Gives back the matching in an ANodeMap. The parameter should + ///be a write ANodeMap of UEdge values. + ///\return The number of the matching edges. + template + int aMatching(MatchingMap& mm) const { + for (ANodeIt it(*graph); it != INVALID; ++it) { + mm.set(it, anode_matching[it]); + } + return matching_size; + } + + ///Gives back the matching in a BNodeMap. + + ///Gives back the matching in a BNodeMap. The parameter should + ///be a write BNodeMap of UEdge values. + ///\return The number of the matching edges. + template + int bMatching(MatchingMap& mm) const { + for (BNodeIt it(*graph); it != INVALID; ++it) { + mm.set(it, bnode_matching[it]); + } + return matching_size; + } /// \brief Return true if the given uedge is in the matching. /// @@ -445,13 +470,13 @@ int size = 0; for (ANodeIt it(*graph); it != INVALID; ++it) { - covering[it] = !areached[it] && anode_matching[it] != INVALID; + covering.set(it, !areached[it] && anode_matching[it] != INVALID); if (!areached[it] && anode_matching[it] != INVALID) { ++size; } } for (BNodeIt it(*graph); it != INVALID; ++it) { - covering[it] = breached[it]; + covering.set(it, breached[it]); if (breached[it]) { ++size; } @@ -499,7 +524,7 @@ } for (ANodeIt it(*graph); it != INVALID; ++it) { - barrier[it] = areached[it] || anode_matching[it] == INVALID; + barrier.set(it, areached[it] || anode_matching[it] == INVALID); } } @@ -543,7 +568,7 @@ } for (BNodeIt it(*graph); it != INVALID; ++it) { - barrier[it] = !breached[it]; + barrier.set(it, !breached[it]); } } @@ -568,14 +593,55 @@ /// edge map. /// /// \param graph The bipartite graph. - /// \retval matching The undirected edge map which will be set to - /// the matching. + /// \return The size of the matching. + template + int maxBipartiteMatching(const BpUGraph& graph) { + MaxBipartiteMatching bpmatching(graph); + bpmatching.run(); + return bpmatching.matchingSize(); + } + + /// \ingroup matching + /// + /// \brief Maximum cardinality bipartite matching + /// + /// This function calculates the maximum cardinality matching + /// in a bipartite graph. It gives back the matching in an undirected + /// edge map. + /// + /// \param graph The bipartite graph. + /// \retval matching The ANodeMap of UEdges which will be set to covered + /// matching undirected edge. /// \return The size of the matching. template int maxBipartiteMatching(const BpUGraph& graph, MatchingMap& matching) { MaxBipartiteMatching bpmatching(graph); bpmatching.run(); - bpmatching.matching(matching); + bpmatching.aMatching(matching); + return bpmatching.matchingSize(); + } + + /// \ingroup matching + /// + /// \brief Maximum cardinality bipartite matching + /// + /// This function calculates the maximum cardinality matching + /// in a bipartite graph. It gives back the matching in an undirected + /// edge map. + /// + /// \param graph The bipartite graph. + /// \retval matching The ANodeMap of UEdges which will be set to covered + /// matching undirected edge. + /// \retval barrier The BNodeMap of bools which will be set to a barrier + /// of the BNode-set. + /// \return The size of the matching. + template + int maxBipartiteMatching(const BpUGraph& graph, + MatchingMap& matching, BarrierMap& barrier) { + MaxBipartiteMatching bpmatching(graph); + bpmatching.run(); + bpmatching.aMatching(matching); + bpmatching.bBarrier(barrier); return bpmatching.matchingSize(); } @@ -987,10 +1053,10 @@ template void potential(PotentialMap& pt) const { for (ANodeIt it(*graph); it != INVALID; ++it) { - pt[it] = anode_potential[it]; + pt.set(it, anode_potential[it]); } for (BNodeIt it(*graph); it != INVALID; ++it) { - pt[it] = bnode_potential[it]; + pt.set(it, bnode_potential[it]); } } @@ -1003,7 +1069,7 @@ int quickMatching(MatchingMap& mm) const { for (ANodeIt it(*graph); it != INVALID; ++it) { if (anode_matching[it] != INVALID) { - mm[anode_matching[it]] = true; + mm.set(anode_matching[it], true); } } return matching_size; @@ -1016,7 +1082,33 @@ template int matching(MatchingMap& mm) const { for (UEdgeIt it(*graph); it != INVALID; ++it) { - mm[it] = it == anode_matching[graph->aNode(it)]; + mm.set(it, it == anode_matching[graph->aNode(it)]); + } + return matching_size; + } + + ///Gives back the matching in an ANodeMap. + + ///Gives back the matching in an ANodeMap. The parameter should + ///be a write ANodeMap of UEdge values. + ///\return The number of the matching edges. + template + int aMatching(MatchingMap& mm) const { + for (ANodeIt it(*graph); it != INVALID; ++it) { + mm.set(it, anode_matching[it]); + } + return matching_size; + } + + ///Gives back the matching in a BNodeMap. + + ///Gives back the matching in a BNodeMap. The parameter should + ///be a write BNodeMap of UEdge values. + ///\return The number of the matching edges. + template + int bMatching(MatchingMap& mm) const { + for (BNodeIt it(*graph); it != INVALID; ++it) { + mm.set(it, bnode_matching[it]); } return matching_size; } @@ -1533,17 +1625,17 @@ /// \brief Gives back the potential in the NodeMap /// - /// Gives back the potential in the NodeMap. The potential is optimal with - /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for - /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$ - /// for each edges. + /// Gives back the potential in the NodeMap. The matching is optimal + /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$ + /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$ + /// for each edges. template void potential(PotentialMap& pt) const { for (ANodeIt it(*graph); it != INVALID; ++it) { - pt[it] = anode_potential[it]; + pt.set(it, anode_potential[it]); } for (BNodeIt it(*graph); it != INVALID; ++it) { - pt[it] = bnode_potential[it]; + pt.set(it, bnode_potential[it]); } } @@ -1556,7 +1648,7 @@ int quickMatching(MatchingMap& mm) const { for (ANodeIt it(*graph); it != INVALID; ++it) { if (anode_matching[it] != INVALID) { - mm[anode_matching[it]] = true; + mm.set(anode_matching[it], true); } } return matching_size; @@ -1569,11 +1661,36 @@ template int matching(MatchingMap& mm) const { for (UEdgeIt it(*graph); it != INVALID; ++it) { - mm[it] = it == anode_matching[graph->aNode(it)]; + mm.set(it, it == anode_matching[graph->aNode(it)]); } return matching_size; } + /// \brief Gives back the matching in an ANodeMap. + /// + /// Gives back the matching in an ANodeMap. The parameter should + /// be a write ANodeMap of UEdge values. + /// \return The number of the matching edges. + template + int aMatching(MatchingMap& mm) const { + for (ANodeIt it(*graph); it != INVALID; ++it) { + mm.set(it, anode_matching[it]); + } + return matching_size; + } + + /// \brief Gives back the matching in a BNodeMap. + /// + /// Gives back the matching in a BNodeMap. The parameter should + /// be a write BNodeMap of UEdge values. + /// \return The number of the matching edges. + template + int bMatching(MatchingMap& mm) const { + for (BNodeIt it(*graph); it != INVALID; ++it) { + mm.set(it, bnode_matching[it]); + } + return matching_size; + } /// \brief Return true if the given uedge is in the matching. /// @@ -1655,9 +1772,9 @@ /// /// \brief Minimum cost maximum cardinality bipartite matching /// - /// This function calculates the minimum cost matching of the maximum - /// cardinality matchings of a bipartite graph. It gives back the matching - /// in an undirected edge map. + /// This function calculates the maximum cardinality matching with + /// minimum cost of a bipartite graph. It gives back the matching in + /// an undirected edge map. /// /// \param graph The bipartite graph. /// \param cost The undirected edge map which contains the costs. diff -r 7a096a6bf53a -r 19651a04d056 lemon/pr_bipartite_matching.h --- a/lemon/pr_bipartite_matching.h Sat Aug 11 16:34:41 2007 +0000 +++ b/lemon/pr_bipartite_matching.h Tue Aug 21 13:22:21 2007 +0000 @@ -315,11 +315,11 @@ /// either run() or start() must be called. ///@{ - /// \brief Set true all matching uedge in the map. - /// - /// Set true all matching uedge in the map. It does not change the - /// value mapped to the other uedges. - /// \return The number of the matching edges. + ///Set true all matching uedge in the map. + + ///Set true all matching uedge in the map. It does not change the + ///value mapped to the other uedges. + ///\return The number of the matching edges. template int quickMatching(MatchingMap& mm) const { for (ANodeIt n(_g);n!=INVALID;++n) { @@ -328,7 +328,7 @@ return _matching_size; } - ///\brief Set true all matching uedge in the map and the others to false. + ///Set true all matching uedge in the map and the others to false. ///Set true all matching uedge in the map and the others to false. ///\return The number of the matching edges. @@ -340,6 +340,36 @@ return _matching_size; } + ///Gives back the matching in an ANodeMap. + + ///Gives back the matching in an ANodeMap. The parameter should + ///be a write ANodeMap of UEdge values. + ///\return The number of the matching edges. + template + int aMatching(MatchingMap& mm) const { + for (ANodeIt n(_g);n!=INVALID;++n) { + mm.set(n,_matching[n]); + } + return _matching_size; + } + + ///Gives back the matching in a BNodeMap. + + ///Gives back the matching in a BNodeMap. The parameter should + ///be a write BNodeMap of UEdge values. + ///\return The number of the matching edges. + template + int bMatching(MatchingMap& mm) const { + for (BNodeIt n(_g);n!=INVALID;++n) { + mm.set(n,INVALID); + } + for (ANodeIt n(_g);n!=INVALID;++n) { + if (_matching[n]!=INVALID) + mm.set(_g.bNode(_matching[n]),_matching[n]); + } + return _matching_size; + } + ///Returns true if the given uedge is in the matching. @@ -457,8 +487,10 @@ ///This function finds a maximum cardinality matching ///in a bipartite graph \c g. ///\param g An undirected bipartite graph. - ///\retval matching A write UEdgeMap of value type \c bool. - /// The found edges will be returned in this map. + ///\retval matching A write ANodeMap of value type \c UEdge. + /// The found edges will be returned in this map, + /// i.e. for an \c ANode \c n the edge matching[n] is the one + /// that covers the node \c n. ///\return The cardinality of the maximum matching. /// ///\note The the implementation is based @@ -468,7 +500,7 @@ { PrBipartiteMatching bpm(g); bpm.run(); - bpm.matching(matching); + bpm.aMatching(matching); return bpm.matchingSize(); } @@ -478,8 +510,10 @@ ///This function finds a maximum cardinality matching ///in a bipartite graph \c g. ///\param g An undirected bipartite graph. - ///\retval matching A write UEdgeMap of value type \c bool. - /// The found edges will be returned in this map. + ///\retval matching A write ANodeMap of value type \c UEdge. + /// The found edges will be returned in this map, + /// i.e. for an \c ANode \c n the edge matching[n] is the one + /// that covers the node \c n. ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set /// exactly once for each BNode. The nodes with \c true value represent /// a barrier \e B, i.e. the cardinality of \e B minus the number of its @@ -494,7 +528,7 @@ { PrBipartiteMatching bpm(g); bpm.run(); - bpm.matching(matching); + bpm.aMatching(matching); bpm.bBarrier(barrier); return bpm.matchingSize(); } @@ -521,8 +555,10 @@ ///\ingroup matching ///This function finds a perfect matching in a bipartite graph \c g. ///\param g An undirected bipartite graph. - ///\retval matching A write UEdgeMap of value type \c bool. - /// The found edges will be returned in this map. + ///\retval matching A write ANodeMap of value type \c UEdge. + /// The found edges will be returned in this map, + /// i.e. for an \c ANode \c n the edge matching[n] is the one + /// that covers the node \c n. /// The values are unchanged if the graph /// has no perfect matching. ///\return \c true iff \c g has a perfect matching. @@ -533,8 +569,8 @@ bool prPerfectBipartiteMatching(const Graph &g,MT &matching) { PrBipartiteMatching bpm(g); - bool ret = bpm.runPerfect(); - if (ret) bpm.matching(matching); + bool ret = bpm.checkedRunPerfect(); + if (ret) bpm.aMatching(matching); return ret; } @@ -543,8 +579,10 @@ ///\ingroup matching ///This function finds a perfect matching in a bipartite graph \c g. ///\param g An undirected bipartite graph. - ///\retval matching A readwrite UEdgeMap of value type \c bool. - /// The found edges will be returned in this map. + ///\retval matching A write ANodeMap of value type \c UEdge. + /// The found edges will be returned in this map, + /// i.e. for an \c ANode \c n the edge matching[n] is the one + /// that covers the node \c n. /// The values are unchanged if the graph /// has no perfect matching. ///\retval barrier A \c bool WriteMap on the BNodes. The map will only @@ -557,12 +595,12 @@ ///\note The the implementation is based ///on the push-relabel principle. template - int prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier) + bool prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier) { PrBipartiteMatching bpm(g); - bool ret=bpm.runPerfect(); + bool ret=bpm.checkedRunPerfect(); if(ret) - bpm.matching(matching); + bpm.aMatching(matching); else bpm.bBarrier(barrier); return ret; diff -r 7a096a6bf53a -r 19651a04d056 test/bipartite_matching_test.cc --- a/test/bipartite_matching_test.cc Sat Aug 11 16:34:41 2007 +0000 +++ b/test/bipartite_matching_test.cc Tue Aug 21 13:22:21 2007 +0000 @@ -136,15 +136,32 @@ } { - Graph::UEdgeMap mm(graph); + Graph::ANodeMap mm(graph); check(max_cardinality == maxBipartiteMatching(graph, mm), "WRONG MATCHING"); - for (ANodeIt it(graph); it != INVALID; ++it) { + for (BNodeIt it(graph); it != INVALID; ++it) { int num = 0; + for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { - if (mm[jt]) ++num; + if (mm[graph.aNode(jt)] == jt) ++num; + } + check(num <= 1, "INVALID PRIMAL"); + } + } + + { + Graph::ANodeMap mm(graph); + + check(max_cardinality == prBipartiteMatching(graph, mm), + "WRONG MATCHING"); + + for (BNodeIt it(graph); it != INVALID; ++it) { + int num = 0; + + for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { + if (mm[graph.aNode(jt)] == jt) ++num; } check(num <= 1, "INVALID PRIMAL"); }