1.1 --- a/lemon/bipartite_matching.h Sat Aug 11 16:34:41 2007 +0000
1.2 +++ b/lemon/bipartite_matching.h Tue Aug 21 13:22:21 2007 +0000
1.3 @@ -359,7 +359,7 @@
1.4 int quickMatching(MatchingMap& mm) const {
1.5 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.6 if (anode_matching[it] != INVALID) {
1.7 - mm[anode_matching[it]] = true;
1.8 + mm.set(anode_matching[it], true);
1.9 }
1.10 }
1.11 return matching_size;
1.12 @@ -372,11 +372,36 @@
1.13 template <typename MatchingMap>
1.14 int matching(MatchingMap& mm) const {
1.15 for (UEdgeIt it(*graph); it != INVALID; ++it) {
1.16 - mm[it] = it == anode_matching[graph->aNode(it)];
1.17 + mm.set(it, it == anode_matching[graph->aNode(it)]);
1.18 }
1.19 return matching_size;
1.20 }
1.21
1.22 + ///Gives back the matching in an ANodeMap.
1.23 +
1.24 + ///Gives back the matching in an ANodeMap. The parameter should
1.25 + ///be a write ANodeMap of UEdge values.
1.26 + ///\return The number of the matching edges.
1.27 + template<class MatchingMap>
1.28 + int aMatching(MatchingMap& mm) const {
1.29 + for (ANodeIt it(*graph); it != INVALID; ++it) {
1.30 + mm.set(it, anode_matching[it]);
1.31 + }
1.32 + return matching_size;
1.33 + }
1.34 +
1.35 + ///Gives back the matching in a BNodeMap.
1.36 +
1.37 + ///Gives back the matching in a BNodeMap. The parameter should
1.38 + ///be a write BNodeMap of UEdge values.
1.39 + ///\return The number of the matching edges.
1.40 + template<class MatchingMap>
1.41 + int bMatching(MatchingMap& mm) const {
1.42 + for (BNodeIt it(*graph); it != INVALID; ++it) {
1.43 + mm.set(it, bnode_matching[it]);
1.44 + }
1.45 + return matching_size;
1.46 + }
1.47
1.48 /// \brief Return true if the given uedge is in the matching.
1.49 ///
1.50 @@ -445,13 +470,13 @@
1.51
1.52 int size = 0;
1.53 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.54 - covering[it] = !areached[it] && anode_matching[it] != INVALID;
1.55 + covering.set(it, !areached[it] && anode_matching[it] != INVALID);
1.56 if (!areached[it] && anode_matching[it] != INVALID) {
1.57 ++size;
1.58 }
1.59 }
1.60 for (BNodeIt it(*graph); it != INVALID; ++it) {
1.61 - covering[it] = breached[it];
1.62 + covering.set(it, breached[it]);
1.63 if (breached[it]) {
1.64 ++size;
1.65 }
1.66 @@ -499,7 +524,7 @@
1.67 }
1.68
1.69 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.70 - barrier[it] = areached[it] || anode_matching[it] == INVALID;
1.71 + barrier.set(it, areached[it] || anode_matching[it] == INVALID);
1.72 }
1.73 }
1.74
1.75 @@ -543,7 +568,7 @@
1.76 }
1.77
1.78 for (BNodeIt it(*graph); it != INVALID; ++it) {
1.79 - barrier[it] = !breached[it];
1.80 + barrier.set(it, !breached[it]);
1.81 }
1.82 }
1.83
1.84 @@ -568,14 +593,55 @@
1.85 /// edge map.
1.86 ///
1.87 /// \param graph The bipartite graph.
1.88 - /// \retval matching The undirected edge map which will be set to
1.89 - /// the matching.
1.90 + /// \return The size of the matching.
1.91 + template <typename BpUGraph>
1.92 + int maxBipartiteMatching(const BpUGraph& graph) {
1.93 + MaxBipartiteMatching<BpUGraph> bpmatching(graph);
1.94 + bpmatching.run();
1.95 + return bpmatching.matchingSize();
1.96 + }
1.97 +
1.98 + /// \ingroup matching
1.99 + ///
1.100 + /// \brief Maximum cardinality bipartite matching
1.101 + ///
1.102 + /// This function calculates the maximum cardinality matching
1.103 + /// in a bipartite graph. It gives back the matching in an undirected
1.104 + /// edge map.
1.105 + ///
1.106 + /// \param graph The bipartite graph.
1.107 + /// \retval matching The ANodeMap of UEdges which will be set to covered
1.108 + /// matching undirected edge.
1.109 /// \return The size of the matching.
1.110 template <typename BpUGraph, typename MatchingMap>
1.111 int maxBipartiteMatching(const BpUGraph& graph, MatchingMap& matching) {
1.112 MaxBipartiteMatching<BpUGraph> bpmatching(graph);
1.113 bpmatching.run();
1.114 - bpmatching.matching(matching);
1.115 + bpmatching.aMatching(matching);
1.116 + return bpmatching.matchingSize();
1.117 + }
1.118 +
1.119 + /// \ingroup matching
1.120 + ///
1.121 + /// \brief Maximum cardinality bipartite matching
1.122 + ///
1.123 + /// This function calculates the maximum cardinality matching
1.124 + /// in a bipartite graph. It gives back the matching in an undirected
1.125 + /// edge map.
1.126 + ///
1.127 + /// \param graph The bipartite graph.
1.128 + /// \retval matching The ANodeMap of UEdges which will be set to covered
1.129 + /// matching undirected edge.
1.130 + /// \retval barrier The BNodeMap of bools which will be set to a barrier
1.131 + /// of the BNode-set.
1.132 + /// \return The size of the matching.
1.133 + template <typename BpUGraph, typename MatchingMap, typename BarrierMap>
1.134 + int maxBipartiteMatching(const BpUGraph& graph,
1.135 + MatchingMap& matching, BarrierMap& barrier) {
1.136 + MaxBipartiteMatching<BpUGraph> bpmatching(graph);
1.137 + bpmatching.run();
1.138 + bpmatching.aMatching(matching);
1.139 + bpmatching.bBarrier(barrier);
1.140 return bpmatching.matchingSize();
1.141 }
1.142
1.143 @@ -987,10 +1053,10 @@
1.144 template <typename PotentialMap>
1.145 void potential(PotentialMap& pt) const {
1.146 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.147 - pt[it] = anode_potential[it];
1.148 + pt.set(it, anode_potential[it]);
1.149 }
1.150 for (BNodeIt it(*graph); it != INVALID; ++it) {
1.151 - pt[it] = bnode_potential[it];
1.152 + pt.set(it, bnode_potential[it]);
1.153 }
1.154 }
1.155
1.156 @@ -1003,7 +1069,7 @@
1.157 int quickMatching(MatchingMap& mm) const {
1.158 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.159 if (anode_matching[it] != INVALID) {
1.160 - mm[anode_matching[it]] = true;
1.161 + mm.set(anode_matching[it], true);
1.162 }
1.163 }
1.164 return matching_size;
1.165 @@ -1016,7 +1082,33 @@
1.166 template <typename MatchingMap>
1.167 int matching(MatchingMap& mm) const {
1.168 for (UEdgeIt it(*graph); it != INVALID; ++it) {
1.169 - mm[it] = it == anode_matching[graph->aNode(it)];
1.170 + mm.set(it, it == anode_matching[graph->aNode(it)]);
1.171 + }
1.172 + return matching_size;
1.173 + }
1.174 +
1.175 + ///Gives back the matching in an ANodeMap.
1.176 +
1.177 + ///Gives back the matching in an ANodeMap. The parameter should
1.178 + ///be a write ANodeMap of UEdge values.
1.179 + ///\return The number of the matching edges.
1.180 + template<class MatchingMap>
1.181 + int aMatching(MatchingMap& mm) const {
1.182 + for (ANodeIt it(*graph); it != INVALID; ++it) {
1.183 + mm.set(it, anode_matching[it]);
1.184 + }
1.185 + return matching_size;
1.186 + }
1.187 +
1.188 + ///Gives back the matching in a BNodeMap.
1.189 +
1.190 + ///Gives back the matching in a BNodeMap. The parameter should
1.191 + ///be a write BNodeMap of UEdge values.
1.192 + ///\return The number of the matching edges.
1.193 + template<class MatchingMap>
1.194 + int bMatching(MatchingMap& mm) const {
1.195 + for (BNodeIt it(*graph); it != INVALID; ++it) {
1.196 + mm.set(it, bnode_matching[it]);
1.197 }
1.198 return matching_size;
1.199 }
1.200 @@ -1533,17 +1625,17 @@
1.201
1.202 /// \brief Gives back the potential in the NodeMap
1.203 ///
1.204 - /// Gives back the potential in the NodeMap. The potential is optimal with
1.205 - /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for
1.206 - /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$
1.207 - /// for each edges.
1.208 + /// Gives back the potential in the NodeMap. The matching is optimal
1.209 + /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$
1.210 + /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$
1.211 + /// for each edges.
1.212 template <typename PotentialMap>
1.213 void potential(PotentialMap& pt) const {
1.214 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.215 - pt[it] = anode_potential[it];
1.216 + pt.set(it, anode_potential[it]);
1.217 }
1.218 for (BNodeIt it(*graph); it != INVALID; ++it) {
1.219 - pt[it] = bnode_potential[it];
1.220 + pt.set(it, bnode_potential[it]);
1.221 }
1.222 }
1.223
1.224 @@ -1556,7 +1648,7 @@
1.225 int quickMatching(MatchingMap& mm) const {
1.226 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.227 if (anode_matching[it] != INVALID) {
1.228 - mm[anode_matching[it]] = true;
1.229 + mm.set(anode_matching[it], true);
1.230 }
1.231 }
1.232 return matching_size;
1.233 @@ -1569,11 +1661,36 @@
1.234 template <typename MatchingMap>
1.235 int matching(MatchingMap& mm) const {
1.236 for (UEdgeIt it(*graph); it != INVALID; ++it) {
1.237 - mm[it] = it == anode_matching[graph->aNode(it)];
1.238 + mm.set(it, it == anode_matching[graph->aNode(it)]);
1.239 }
1.240 return matching_size;
1.241 }
1.242
1.243 + /// \brief Gives back the matching in an ANodeMap.
1.244 + ///
1.245 + /// Gives back the matching in an ANodeMap. The parameter should
1.246 + /// be a write ANodeMap of UEdge values.
1.247 + /// \return The number of the matching edges.
1.248 + template<class MatchingMap>
1.249 + int aMatching(MatchingMap& mm) const {
1.250 + for (ANodeIt it(*graph); it != INVALID; ++it) {
1.251 + mm.set(it, anode_matching[it]);
1.252 + }
1.253 + return matching_size;
1.254 + }
1.255 +
1.256 + /// \brief Gives back the matching in a BNodeMap.
1.257 + ///
1.258 + /// Gives back the matching in a BNodeMap. The parameter should
1.259 + /// be a write BNodeMap of UEdge values.
1.260 + /// \return The number of the matching edges.
1.261 + template<class MatchingMap>
1.262 + int bMatching(MatchingMap& mm) const {
1.263 + for (BNodeIt it(*graph); it != INVALID; ++it) {
1.264 + mm.set(it, bnode_matching[it]);
1.265 + }
1.266 + return matching_size;
1.267 + }
1.268
1.269 /// \brief Return true if the given uedge is in the matching.
1.270 ///
1.271 @@ -1655,9 +1772,9 @@
1.272 ///
1.273 /// \brief Minimum cost maximum cardinality bipartite matching
1.274 ///
1.275 - /// This function calculates the minimum cost matching of the maximum
1.276 - /// cardinality matchings of a bipartite graph. It gives back the matching
1.277 - /// in an undirected edge map.
1.278 + /// This function calculates the maximum cardinality matching with
1.279 + /// minimum cost of a bipartite graph. It gives back the matching in
1.280 + /// an undirected edge map.
1.281 ///
1.282 /// \param graph The bipartite graph.
1.283 /// \param cost The undirected edge map which contains the costs.
2.1 --- a/lemon/pr_bipartite_matching.h Sat Aug 11 16:34:41 2007 +0000
2.2 +++ b/lemon/pr_bipartite_matching.h Tue Aug 21 13:22:21 2007 +0000
2.3 @@ -315,11 +315,11 @@
2.4 /// either run() or start() must be called.
2.5 ///@{
2.6
2.7 - /// \brief Set true all matching uedge in the map.
2.8 - ///
2.9 - /// Set true all matching uedge in the map. It does not change the
2.10 - /// value mapped to the other uedges.
2.11 - /// \return The number of the matching edges.
2.12 + ///Set true all matching uedge in the map.
2.13 +
2.14 + ///Set true all matching uedge in the map. It does not change the
2.15 + ///value mapped to the other uedges.
2.16 + ///\return The number of the matching edges.
2.17 template <typename MatchingMap>
2.18 int quickMatching(MatchingMap& mm) const {
2.19 for (ANodeIt n(_g);n!=INVALID;++n) {
2.20 @@ -328,7 +328,7 @@
2.21 return _matching_size;
2.22 }
2.23
2.24 - ///\brief Set true all matching uedge in the map and the others to false.
2.25 + ///Set true all matching uedge in the map and the others to false.
2.26
2.27 ///Set true all matching uedge in the map and the others to false.
2.28 ///\return The number of the matching edges.
2.29 @@ -340,6 +340,36 @@
2.30 return _matching_size;
2.31 }
2.32
2.33 + ///Gives back the matching in an ANodeMap.
2.34 +
2.35 + ///Gives back the matching in an ANodeMap. The parameter should
2.36 + ///be a write ANodeMap of UEdge values.
2.37 + ///\return The number of the matching edges.
2.38 + template<class MatchingMap>
2.39 + int aMatching(MatchingMap& mm) const {
2.40 + for (ANodeIt n(_g);n!=INVALID;++n) {
2.41 + mm.set(n,_matching[n]);
2.42 + }
2.43 + return _matching_size;
2.44 + }
2.45 +
2.46 + ///Gives back the matching in a BNodeMap.
2.47 +
2.48 + ///Gives back the matching in a BNodeMap. The parameter should
2.49 + ///be a write BNodeMap of UEdge values.
2.50 + ///\return The number of the matching edges.
2.51 + template<class MatchingMap>
2.52 + int bMatching(MatchingMap& mm) const {
2.53 + for (BNodeIt n(_g);n!=INVALID;++n) {
2.54 + mm.set(n,INVALID);
2.55 + }
2.56 + for (ANodeIt n(_g);n!=INVALID;++n) {
2.57 + if (_matching[n]!=INVALID)
2.58 + mm.set(_g.bNode(_matching[n]),_matching[n]);
2.59 + }
2.60 + return _matching_size;
2.61 + }
2.62 +
2.63
2.64 ///Returns true if the given uedge is in the matching.
2.65
2.66 @@ -457,8 +487,10 @@
2.67 ///This function finds a maximum cardinality matching
2.68 ///in a bipartite graph \c g.
2.69 ///\param g An undirected bipartite graph.
2.70 - ///\retval matching A write UEdgeMap of value type \c bool.
2.71 - /// The found edges will be returned in this map.
2.72 + ///\retval matching A write ANodeMap of value type \c UEdge.
2.73 + /// The found edges will be returned in this map,
2.74 + /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
2.75 + /// that covers the node \c n.
2.76 ///\return The cardinality of the maximum matching.
2.77 ///
2.78 ///\note The the implementation is based
2.79 @@ -468,7 +500,7 @@
2.80 {
2.81 PrBipartiteMatching<Graph> bpm(g);
2.82 bpm.run();
2.83 - bpm.matching(matching);
2.84 + bpm.aMatching(matching);
2.85 return bpm.matchingSize();
2.86 }
2.87
2.88 @@ -478,8 +510,10 @@
2.89 ///This function finds a maximum cardinality matching
2.90 ///in a bipartite graph \c g.
2.91 ///\param g An undirected bipartite graph.
2.92 - ///\retval matching A write UEdgeMap of value type \c bool.
2.93 - /// The found edges will be returned in this map.
2.94 + ///\retval matching A write ANodeMap of value type \c UEdge.
2.95 + /// The found edges will be returned in this map,
2.96 + /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
2.97 + /// that covers the node \c n.
2.98 ///\retval barrier A \c bool WriteMap on the BNodes. The map will be set
2.99 /// exactly once for each BNode. The nodes with \c true value represent
2.100 /// a barrier \e B, i.e. the cardinality of \e B minus the number of its
2.101 @@ -494,7 +528,7 @@
2.102 {
2.103 PrBipartiteMatching<Graph> bpm(g);
2.104 bpm.run();
2.105 - bpm.matching(matching);
2.106 + bpm.aMatching(matching);
2.107 bpm.bBarrier(barrier);
2.108 return bpm.matchingSize();
2.109 }
2.110 @@ -521,8 +555,10 @@
2.111 ///\ingroup matching
2.112 ///This function finds a perfect matching in a bipartite graph \c g.
2.113 ///\param g An undirected bipartite graph.
2.114 - ///\retval matching A write UEdgeMap of value type \c bool.
2.115 - /// The found edges will be returned in this map.
2.116 + ///\retval matching A write ANodeMap of value type \c UEdge.
2.117 + /// The found edges will be returned in this map,
2.118 + /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
2.119 + /// that covers the node \c n.
2.120 /// The values are unchanged if the graph
2.121 /// has no perfect matching.
2.122 ///\return \c true iff \c g has a perfect matching.
2.123 @@ -533,8 +569,8 @@
2.124 bool prPerfectBipartiteMatching(const Graph &g,MT &matching)
2.125 {
2.126 PrBipartiteMatching<Graph> bpm(g);
2.127 - bool ret = bpm.runPerfect();
2.128 - if (ret) bpm.matching(matching);
2.129 + bool ret = bpm.checkedRunPerfect();
2.130 + if (ret) bpm.aMatching(matching);
2.131 return ret;
2.132 }
2.133
2.134 @@ -543,8 +579,10 @@
2.135 ///\ingroup matching
2.136 ///This function finds a perfect matching in a bipartite graph \c g.
2.137 ///\param g An undirected bipartite graph.
2.138 - ///\retval matching A readwrite UEdgeMap of value type \c bool.
2.139 - /// The found edges will be returned in this map.
2.140 + ///\retval matching A write ANodeMap of value type \c UEdge.
2.141 + /// The found edges will be returned in this map,
2.142 + /// i.e. for an \c ANode \c n the edge <tt>matching[n]</tt> is the one
2.143 + /// that covers the node \c n.
2.144 /// The values are unchanged if the graph
2.145 /// has no perfect matching.
2.146 ///\retval barrier A \c bool WriteMap on the BNodes. The map will only
2.147 @@ -557,12 +595,12 @@
2.148 ///\note The the implementation is based
2.149 ///on the push-relabel principle.
2.150 template<class Graph,class MT, class GT>
2.151 - int prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
2.152 + bool prPerfectBipartiteMatching(const Graph &g,MT &matching,GT &barrier)
2.153 {
2.154 PrBipartiteMatching<Graph> bpm(g);
2.155 - bool ret=bpm.runPerfect();
2.156 + bool ret=bpm.checkedRunPerfect();
2.157 if(ret)
2.158 - bpm.matching(matching);
2.159 + bpm.aMatching(matching);
2.160 else
2.161 bpm.bBarrier(barrier);
2.162 return ret;
3.1 --- a/test/bipartite_matching_test.cc Sat Aug 11 16:34:41 2007 +0000
3.2 +++ b/test/bipartite_matching_test.cc Tue Aug 21 13:22:21 2007 +0000
3.3 @@ -136,15 +136,32 @@
3.4 }
3.5
3.6 {
3.7 - Graph::UEdgeMap<bool> mm(graph);
3.8 + Graph::ANodeMap<UEdge> mm(graph);
3.9
3.10 check(max_cardinality == maxBipartiteMatching(graph, mm),
3.11 "WRONG MATCHING");
3.12
3.13 - for (ANodeIt it(graph); it != INVALID; ++it) {
3.14 + for (BNodeIt it(graph); it != INVALID; ++it) {
3.15 int num = 0;
3.16 +
3.17 for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
3.18 - if (mm[jt]) ++num;
3.19 + if (mm[graph.aNode(jt)] == jt) ++num;
3.20 + }
3.21 + check(num <= 1, "INVALID PRIMAL");
3.22 + }
3.23 + }
3.24 +
3.25 + {
3.26 + Graph::ANodeMap<UEdge> mm(graph);
3.27 +
3.28 + check(max_cardinality == prBipartiteMatching(graph, mm),
3.29 + "WRONG MATCHING");
3.30 +
3.31 + for (BNodeIt it(graph); it != INVALID; ++it) {
3.32 + int num = 0;
3.33 +
3.34 + for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
3.35 + if (mm[graph.aNode(jt)] == jt) ++num;
3.36 }
3.37 check(num <= 1, "INVALID PRIMAL");
3.38 }