1.1 --- a/lemon/bipartite_matching.h Fri Apr 14 23:55:36 2006 +0000
1.2 +++ b/lemon/bipartite_matching.h Tue Apr 18 07:01:55 2006 +0000
1.3 @@ -328,7 +328,7 @@
1.4 ///
1.5 /// It just initalize the algorithm and then start it.
1.6 void run() {
1.7 - init();
1.8 + greedyInit();
1.9 start();
1.10 }
1.11
1.12 @@ -349,7 +349,7 @@
1.13 /// problem what is proof of the optimality of the matching.
1.14 /// \return The size of the cover set.
1.15 template <typename CoverMap>
1.16 - int coverSet(CoverMap& covering) {
1.17 + int coverSet(CoverMap& covering) const {
1.18
1.19 typename Graph::template ANodeMap<bool> areached(*graph, false);
1.20 typename Graph::template BNodeMap<bool> breached(*graph, false);
1.21 @@ -403,7 +403,7 @@
1.22 /// value mapped to the other uedges.
1.23 /// \return The number of the matching edges.
1.24 template <typename MatchingMap>
1.25 - int quickMatching(MatchingMap& matching) {
1.26 + int quickMatching(MatchingMap& matching) const {
1.27 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.28 if (anode_matching[it] != INVALID) {
1.29 matching[anode_matching[it]] = true;
1.30 @@ -417,7 +417,7 @@
1.31 /// Set true all matching uedge in the map and the others to false.
1.32 /// \return The number of the matching edges.
1.33 template <typename MatchingMap>
1.34 - int matching(MatchingMap& matching) {
1.35 + int matching(MatchingMap& matching) const {
1.36 for (UEdgeIt it(*graph); it != INVALID; ++it) {
1.37 matching[it] = it == anode_matching[graph->aNode(it)];
1.38 }
1.39 @@ -428,7 +428,7 @@
1.40 /// \brief Return true if the given uedge is in the matching.
1.41 ///
1.42 /// It returns true if the given uedge is in the matching.
1.43 - bool matchingEdge(const UEdge& edge) {
1.44 + bool matchingEdge(const UEdge& edge) const {
1.45 return anode_matching[graph->aNode(edge)] == edge;
1.46 }
1.47
1.48 @@ -436,7 +436,7 @@
1.49 ///
1.50 /// Returns the matching edge from the node. If there is not such
1.51 /// edge it gives back \c INVALID.
1.52 - UEdge matchingEdge(const Node& node) {
1.53 + UEdge matchingEdge(const Node& node) const {
1.54 if (graph->aNode(node)) {
1.55 return anode_matching[node];
1.56 } else {
1.57 @@ -463,6 +463,26 @@
1.58
1.59 };
1.60
1.61 + /// \ingroup matching
1.62 + ///
1.63 + /// \brief Maximum cardinality bipartite matching
1.64 + ///
1.65 + /// This function calculates the maximum cardinality matching
1.66 + /// in a bipartite graph. It gives back the matching in an undirected
1.67 + /// edge map.
1.68 + ///
1.69 + /// \param graph The bipartite graph.
1.70 + /// \retval matching The undirected edge map which will be set to
1.71 + /// the matching.
1.72 + /// \return The size of the matching.
1.73 + template <typename BpUGraph, typename MatchingMap>
1.74 + int maxBipartiteMatching(const BpUGraph& graph, MatchingMap& matching) {
1.75 + MaxBipartiteMatching<BpUGraph> bpmatching(graph);
1.76 + bpmatching.run();
1.77 + bpmatching.matching(matching);
1.78 + return bpmatching.matchingSize();
1.79 + }
1.80 +
1.81 /// \brief Default traits class for weighted bipartite matching algoritms.
1.82 ///
1.83 /// Default traits class for weighted bipartite matching algoritms.
1.84 @@ -701,8 +721,8 @@
1.85 bnode_matching[it] = INVALID;
1.86 bnode_potential[it] = 0;
1.87 for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) {
1.88 - if (-(*weight)[jt] <= bnode_potential[it]) {
1.89 - bnode_potential[it] = -(*weight)[jt];
1.90 + if ((*weight)[jt] > bnode_potential[it]) {
1.91 + bnode_potential[it] = (*weight)[jt];
1.92 }
1.93 }
1.94 }
1.95 @@ -753,8 +773,8 @@
1.96 for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
1.97 if (jt == anode_matching[anode]) continue;
1.98 Node bnode = graph->bNode(jt);
1.99 - Value bvalue = avalue + anode_potential[anode] -
1.100 - bnode_potential[bnode] - (*weight)[jt];
1.101 + Value bvalue = avalue - (*weight)[jt] +
1.102 + anode_potential[anode] + bnode_potential[bnode];
1.103 if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) {
1.104 bdist[bnode] = bvalue;
1.105 bpred[bnode] = jt;
1.106 @@ -778,8 +798,8 @@
1.107 }
1.108 } else {
1.109 if (bestNode == INVALID ||
1.110 - - bvalue - bnode_potential[bnode] > bestValue) {
1.111 - bestValue = - bvalue - bnode_potential[bnode];
1.112 + bnode_potential[bnode] - bvalue > bestValue) {
1.113 + bestValue = bnode_potential[bnode] - bvalue;
1.114 bestNode = bnode;
1.115 }
1.116 }
1.117 @@ -795,9 +815,9 @@
1.118
1.119 for (BNodeIt it(*graph); it != INVALID; ++it) {
1.120 if (bpred[it] != INVALID) {
1.121 - bnode_potential[it] += bdist[it];
1.122 + bnode_potential[it] -= bdist[it];
1.123 } else {
1.124 - bnode_potential[it] += bdistMax;
1.125 + bnode_potential[it] -= bdistMax;
1.126 }
1.127 }
1.128 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.129 @@ -864,12 +884,12 @@
1.130
1.131 /// \brief Gives back the potential in the NodeMap
1.132 ///
1.133 - /// Gives back the potential in the NodeMap. The potential
1.134 - /// is feasible if \f$ \pi(a) - \pi(b) - w(ab) = 0 \f$ for
1.135 - /// each matching edges and \f$ \pi(a) - \pi(b) - w(ab) \ge 0 \f$
1.136 - /// for each edges.
1.137 + /// Gives back the potential in the NodeMap. The matching is optimal
1.138 + /// with the current number of edges if \f$ \pi(a) + \pi(b) - w(ab) = 0 \f$
1.139 + /// for each matching edges and \f$ \pi(a) + \pi(b) - w(ab) \ge 0 \f$
1.140 + /// for each edges.
1.141 template <typename PotentialMap>
1.142 - void potential(PotentialMap& potential) {
1.143 + void potential(PotentialMap& potential) const {
1.144 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.145 potential[it] = anode_potential[it];
1.146 }
1.147 @@ -884,7 +904,7 @@
1.148 /// value mapped to the other uedges.
1.149 /// \return The number of the matching edges.
1.150 template <typename MatchingMap>
1.151 - int quickMatching(MatchingMap& matching) {
1.152 + int quickMatching(MatchingMap& matching) const {
1.153 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.154 if (anode_matching[it] != INVALID) {
1.155 matching[anode_matching[it]] = true;
1.156 @@ -898,7 +918,7 @@
1.157 /// Set true all matching uedge in the map and the others to false.
1.158 /// \return The number of the matching edges.
1.159 template <typename MatchingMap>
1.160 - int matching(MatchingMap& matching) {
1.161 + int matching(MatchingMap& matching) const {
1.162 for (UEdgeIt it(*graph); it != INVALID; ++it) {
1.163 matching[it] = it == anode_matching[graph->aNode(it)];
1.164 }
1.165 @@ -909,7 +929,7 @@
1.166 /// \brief Return true if the given uedge is in the matching.
1.167 ///
1.168 /// It returns true if the given uedge is in the matching.
1.169 - bool matchingEdge(const UEdge& edge) {
1.170 + bool matchingEdge(const UEdge& edge) const {
1.171 return anode_matching[graph->aNode(edge)] == edge;
1.172 }
1.173
1.174 @@ -917,7 +937,7 @@
1.175 ///
1.176 /// Returns the matching edge from the node. If there is not such
1.177 /// edge it gives back \c INVALID.
1.178 - UEdge matchingEdge(const Node& node) {
1.179 + UEdge matchingEdge(const Node& node) const {
1.180 if (graph->aNode(node)) {
1.181 return anode_matching[node];
1.182 } else {
1.183 @@ -982,6 +1002,55 @@
1.184
1.185 };
1.186
1.187 + /// \ingroup matching
1.188 + ///
1.189 + /// \brief Maximum weighted bipartite matching
1.190 + ///
1.191 + /// This function calculates the maximum weighted matching
1.192 + /// in a bipartite graph. It gives back the matching in an undirected
1.193 + /// edge map.
1.194 + ///
1.195 + /// \param graph The bipartite graph.
1.196 + /// \param weight The undirected edge map which contains the weights.
1.197 + /// \retval matching The undirected edge map which will be set to
1.198 + /// the matching.
1.199 + /// \return The value of the matching.
1.200 + template <typename BpUGraph, typename WeightMap, typename MatchingMap>
1.201 + typename WeightMap::Value
1.202 + maxWeightedBipartiteMatching(const BpUGraph& graph, const WeightMap& weight,
1.203 + MatchingMap& matching) {
1.204 + MaxWeightedBipartiteMatching<BpUGraph, WeightMap>
1.205 + bpmatching(graph, weight);
1.206 + bpmatching.run();
1.207 + bpmatching.matching(matching);
1.208 + return bpmatching.matchingValue();
1.209 + }
1.210 +
1.211 + /// \ingroup matching
1.212 + ///
1.213 + /// \brief Maximum weighted maximum cardinality bipartite matching
1.214 + ///
1.215 + /// This function calculates the maximum weighted of the maximum cardinality
1.216 + /// matchings of a bipartite graph. It gives back the matching in an
1.217 + /// undirected edge map.
1.218 + ///
1.219 + /// \param graph The bipartite graph.
1.220 + /// \param weight The undirected edge map which contains the weights.
1.221 + /// \retval matching The undirected edge map which will be set to
1.222 + /// the matching.
1.223 + /// \return The value of the matching.
1.224 + template <typename BpUGraph, typename WeightMap, typename MatchingMap>
1.225 + typename WeightMap::Value
1.226 + maxWeightedMaxBipartiteMatching(const BpUGraph& graph,
1.227 + const WeightMap& weight,
1.228 + MatchingMap& matching) {
1.229 + MaxWeightedBipartiteMatching<BpUGraph, WeightMap>
1.230 + bpmatching(graph, weight);
1.231 + bpmatching.run(true);
1.232 + bpmatching.matching(matching);
1.233 + return bpmatching.matchingValue();
1.234 + }
1.235 +
1.236 /// \brief Default traits class for minimum cost bipartite matching
1.237 /// algoritms.
1.238 ///
1.239 @@ -1360,12 +1429,12 @@
1.240
1.241 /// \brief Gives back the potential in the NodeMap
1.242 ///
1.243 - /// Gives back the potential in the NodeMap. The potential
1.244 - /// is feasible if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for
1.245 + /// Gives back the potential in the NodeMap. The potential is optimal with
1.246 + /// the current number of edges if \f$ \pi(a) - \pi(b) + w(ab) = 0 \f$ for
1.247 /// each matching edges and \f$ \pi(a) - \pi(b) + w(ab) \ge 0 \f$
1.248 /// for each edges.
1.249 template <typename PotentialMap>
1.250 - void potential(PotentialMap& potential) {
1.251 + void potential(PotentialMap& potential) const {
1.252 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.253 potential[it] = anode_potential[it];
1.254 }
1.255 @@ -1380,7 +1449,7 @@
1.256 /// value mapped to the other uedges.
1.257 /// \return The number of the matching edges.
1.258 template <typename MatchingMap>
1.259 - int quickMatching(MatchingMap& matching) {
1.260 + int quickMatching(MatchingMap& matching) const {
1.261 for (ANodeIt it(*graph); it != INVALID; ++it) {
1.262 if (anode_matching[it] != INVALID) {
1.263 matching[anode_matching[it]] = true;
1.264 @@ -1394,7 +1463,7 @@
1.265 /// Set true all matching uedge in the map and the others to false.
1.266 /// \return The number of the matching edges.
1.267 template <typename MatchingMap>
1.268 - int matching(MatchingMap& matching) {
1.269 + int matching(MatchingMap& matching) const {
1.270 for (UEdgeIt it(*graph); it != INVALID; ++it) {
1.271 matching[it] = it == anode_matching[graph->aNode(it)];
1.272 }
1.273 @@ -1405,7 +1474,7 @@
1.274 /// \brief Return true if the given uedge is in the matching.
1.275 ///
1.276 /// It returns true if the given uedge is in the matching.
1.277 - bool matchingEdge(const UEdge& edge) {
1.278 + bool matchingEdge(const UEdge& edge) const {
1.279 return anode_matching[graph->aNode(edge)] == edge;
1.280 }
1.281
1.282 @@ -1413,7 +1482,7 @@
1.283 ///
1.284 /// Returns the matching edge from the node. If there is not such
1.285 /// edge it gives back \c INVALID.
1.286 - UEdge matchingEdge(const Node& node) {
1.287 + UEdge matchingEdge(const Node& node) const {
1.288 if (graph->aNode(node)) {
1.289 return anode_matching[node];
1.290 } else {
1.291 @@ -1478,6 +1547,31 @@
1.292
1.293 };
1.294
1.295 + /// \ingroup matching
1.296 + ///
1.297 + /// \brief Minimum cost maximum cardinality bipartite matching
1.298 + ///
1.299 + /// This function calculates the minimum cost matching of the maximum
1.300 + /// cardinality matchings of a bipartite graph. It gives back the matching
1.301 + /// in an undirected edge map.
1.302 + ///
1.303 + /// \param graph The bipartite graph.
1.304 + /// \param cost The undirected edge map which contains the costs.
1.305 + /// \retval matching The undirected edge map which will be set to
1.306 + /// the matching.
1.307 + /// \return The cost of the matching.
1.308 + template <typename BpUGraph, typename CostMap, typename MatchingMap>
1.309 + typename CostMap::Value
1.310 + minCostMaxBipartiteMatching(const BpUGraph& graph,
1.311 + const CostMap& cost,
1.312 + MatchingMap& matching) {
1.313 + MinCostMaxBipartiteMatching<BpUGraph, CostMap>
1.314 + bpmatching(graph, cost);
1.315 + bpmatching.run();
1.316 + bpmatching.matching(matching);
1.317 + return bpmatching.matchingCost();
1.318 + }
1.319 +
1.320 }
1.321
1.322 #endif
2.1 --- a/test/bipartite_matching_test.cc Fri Apr 14 23:55:36 2006 +0000
2.2 +++ b/test/bipartite_matching_test.cc Tue Apr 18 07:01:55 2006 +0000
2.3 @@ -23,8 +23,8 @@
2.4 Graph graph;
2.5 vector<Node> aNodes;
2.6 vector<Node> bNodes;
2.7 - int n = argc > 1 ? atoi(argv[1]) : 100;
2.8 - int m = argc > 2 ? atoi(argv[2]) : 100;
2.9 + int n = argc > 1 ? atoi(argv[1]) : 10;
2.10 + int m = argc > 2 ? atoi(argv[2]) : 10;
2.11 int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m));
2.12 int c = argc > 4 ? atoi(argv[4]) : 100;
2.13
2.14 @@ -33,6 +33,7 @@
2.15 int max_cardinality;
2.16 int max_weight;
2.17 int max_cardinality_max_weight;
2.18 + int min_cost_matching;
2.19
2.20 for (int i = 0; i < n; ++i) {
2.21 Node node = graph.addANode();
2.22 @@ -74,6 +75,21 @@
2.23 }
2.24
2.25 {
2.26 + Graph::UEdgeMap<bool> mm(graph);
2.27 +
2.28 + check(max_cardinality == maxBipartiteMatching(graph, mm),
2.29 + "WRONG MATCHING");
2.30 +
2.31 + for (ANodeIt it(graph); it != INVALID; ++it) {
2.32 + int num = 0;
2.33 + for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
2.34 + if (mm[jt]) ++num;
2.35 + }
2.36 + check(num <= 1, "INVALID PRIMAL");
2.37 + }
2.38 + }
2.39 +
2.40 + {
2.41 MaxBipartiteMatching<Graph> bpmatch(graph);
2.42
2.43 bpmatch.greedyInit();
2.44 @@ -137,10 +153,10 @@
2.45
2.46 for (UEdgeIt it(graph); it != INVALID; ++it) {
2.47 if (mm[it]) {
2.48 - check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
2.49 + check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
2.50 "INVALID DUAL");
2.51 } else {
2.52 - check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
2.53 + check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
2.54 "INVALID DUAL");
2.55 }
2.56 }
2.57 @@ -159,6 +175,21 @@
2.58 }
2.59
2.60 {
2.61 + Graph::UEdgeMap<bool> mm(graph);
2.62 +
2.63 + check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm),
2.64 + "WRONG MATCHING");
2.65 +
2.66 + for (ANodeIt it(graph); it != INVALID; ++it) {
2.67 + int num = 0;
2.68 + for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
2.69 + if (mm[jt]) ++num;
2.70 + }
2.71 + check(num <= 1, "INVALID PRIMAL");
2.72 + }
2.73 + }
2.74 +
2.75 + {
2.76 MaxWeightedBipartiteMatching<Graph> bpmatch(graph, weight);
2.77
2.78 bpmatch.run();
2.79 @@ -171,10 +202,10 @@
2.80
2.81 for (UEdgeIt it(graph); it != INVALID; ++it) {
2.82 if (mm[it]) {
2.83 - check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
2.84 + check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
2.85 "INVALID DUAL");
2.86 } else {
2.87 - check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
2.88 + check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
2.89 "INVALID DUAL");
2.90 }
2.91 }
2.92 @@ -202,10 +233,10 @@
2.93
2.94 for (UEdgeIt it(graph); it != INVALID; ++it) {
2.95 if (mm[it]) {
2.96 - check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0,
2.97 + check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0,
2.98 "INVALID DUAL");
2.99 } else {
2.100 - check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0,
2.101 + check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0,
2.102 "INVALID DUAL");
2.103 }
2.104 }
2.105 @@ -223,9 +254,25 @@
2.106 }
2.107
2.108 {
2.109 - Graph::UEdgeMap<int> cost(graph);
2.110 + Graph::UEdgeMap<bool> mm(graph);
2.111
2.112 - cost = subMap(constMap<UEdge>(c), weight);
2.113 + check(max_cardinality_max_weight ==
2.114 + maxWeightedMaxBipartiteMatching(graph, weight, mm),
2.115 + "WRONG MATCHING");
2.116 +
2.117 + for (ANodeIt it(graph); it != INVALID; ++it) {
2.118 + int num = 0;
2.119 + for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
2.120 + if (mm[jt]) ++num;
2.121 + }
2.122 + check(num <= 1, "INVALID PRIMAL");
2.123 + }
2.124 + }
2.125 +
2.126 + Graph::UEdgeMap<int> cost(graph);
2.127 + cost = subMap(constMap<UEdge>(c), weight);
2.128 +
2.129 + {
2.130
2.131 MinCostMaxBipartiteMatching<Graph> bpmatch(graph, cost);
2.132
2.133 @@ -255,11 +302,28 @@
2.134 check(num <= 1, "INVALID PRIMAL");
2.135 }
2.136
2.137 + min_cost_matching = bpmatch.matchingCost();
2.138 check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE");
2.139 check(max_cardinality * c - max_cardinality_max_weight
2.140 == bpmatch.matchingCost(), "WRONG SIZE");
2.141
2.142 }
2.143
2.144 + {
2.145 + Graph::UEdgeMap<bool> mm(graph);
2.146 +
2.147 + check(min_cost_matching ==
2.148 + minCostMaxBipartiteMatching(graph, cost, mm),
2.149 + "WRONG MATCHING");
2.150 +
2.151 + for (ANodeIt it(graph); it != INVALID; ++it) {
2.152 + int num = 0;
2.153 + for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) {
2.154 + if (mm[jt]) ++num;
2.155 + }
2.156 + check(num <= 1, "INVALID PRIMAL");
2.157 + }
2.158 + }
2.159 +
2.160 return 0;
2.161 }