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