# Changeset 2058:0b1fc1566fdb in lemon-0.x

Ignore:
Timestamp:
04/18/06 09:01:55 (18 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2702
Message:

Refinements in bipartite matching algorithms

Files:
2 edited

Unmodified
Added
Removed
• ## lemon/bipartite_matching.h

 r2051 /// It just initalize the algorithm and then start it. void run() { init(); greedyInit(); start(); } /// \return The size of the cover set. template int coverSet(CoverMap& covering) { int coverSet(CoverMap& covering) const { typename Graph::template ANodeMap areached(*graph, false); /// \return The number of the matching edges. template int quickMatching(MatchingMap& matching) { int quickMatching(MatchingMap& matching) const { for (ANodeIt it(*graph); it != INVALID; ++it) { if (anode_matching[it] != INVALID) { /// \return The number of the matching edges. template int matching(MatchingMap& matching) { int matching(MatchingMap& matching) const { for (UEdgeIt it(*graph); it != INVALID; ++it) { matching[it] = it == anode_matching[graph->aNode(it)]; /// /// It returns true if the given uedge is in the matching. bool matchingEdge(const UEdge& edge) { bool matchingEdge(const UEdge& edge) const { return anode_matching[graph->aNode(edge)] == edge; } /// Returns the matching edge from the node. If there is not such /// edge it gives back \c INVALID. UEdge matchingEdge(const Node& node) { UEdge matchingEdge(const Node& node) const { if (graph->aNode(node)) { return anode_matching[node]; }; /// \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 undirected edge map which will be set to /// the matching. /// \return The size of the matching. template int maxBipartiteMatching(const BpUGraph& graph, MatchingMap& matching) { MaxBipartiteMatching bpmatching(graph); bpmatching.run(); bpmatching.matching(matching); return bpmatching.matchingSize(); } /// \brief Default traits class for weighted bipartite matching algoritms. bnode_potential[it] = 0; for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) { if (-(*weight)[jt] <= bnode_potential[it]) { bnode_potential[it] = -(*weight)[jt]; if ((*weight)[jt] > bnode_potential[it]) { bnode_potential[it] = (*weight)[jt]; } } if (jt == anode_matching[anode]) continue; Node bnode = graph->bNode(jt); Value bvalue = avalue + anode_potential[anode] - bnode_potential[bnode] - (*weight)[jt]; Value bvalue = avalue  - (*weight)[jt] + anode_potential[anode] + bnode_potential[bnode]; if (bpred[bnode] == INVALID || bvalue < bdist[bnode]) { bdist[bnode] = bvalue; } else { if (bestNode == INVALID || - bvalue - bnode_potential[bnode] > bestValue) { bestValue = - bvalue - bnode_potential[bnode]; bnode_potential[bnode] - bvalue > bestValue) { bestValue = bnode_potential[bnode] - bvalue; bestNode = bnode; } for (BNodeIt it(*graph); it != INVALID; ++it) { if (bpred[it] != INVALID) { bnode_potential[it] += bdist[it]; bnode_potential[it] -= bdist[it]; } else { bnode_potential[it] += bdistMax; bnode_potential[it] -= bdistMax; } } /// \brief Gives back the potential in the NodeMap /// /// Gives back the potential in the NodeMap. The potential /// is feasible 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& potential) { void potential(PotentialMap& potential) const { for (ANodeIt it(*graph); it != INVALID; ++it) { potential[it] = anode_potential[it]; /// \return The number of the matching edges. template int quickMatching(MatchingMap& matching) { int quickMatching(MatchingMap& matching) const { for (ANodeIt it(*graph); it != INVALID; ++it) { if (anode_matching[it] != INVALID) { /// \return The number of the matching edges. template int matching(MatchingMap& matching) { int matching(MatchingMap& matching) const { for (UEdgeIt it(*graph); it != INVALID; ++it) { matching[it] = it == anode_matching[graph->aNode(it)]; /// /// It returns true if the given uedge is in the matching. bool matchingEdge(const UEdge& edge) { bool matchingEdge(const UEdge& edge) const { return anode_matching[graph->aNode(edge)] == edge; } /// Returns the matching edge from the node. If there is not such /// edge it gives back \c INVALID. UEdge matchingEdge(const Node& node) { UEdge matchingEdge(const Node& node) const { if (graph->aNode(node)) { return anode_matching[node]; }; /// \ingroup matching /// /// \brief Maximum weighted bipartite matching /// /// This function calculates the maximum weighted matching /// in a bipartite graph. It gives back the matching in an undirected /// edge map. /// /// \param graph The bipartite graph. /// \param weight The undirected edge map which contains the weights. /// \retval matching The undirected edge map which will be set to /// the matching. /// \return The value of the matching. template typename WeightMap::Value maxWeightedBipartiteMatching(const BpUGraph& graph, const WeightMap& weight, MatchingMap& matching) { MaxWeightedBipartiteMatching bpmatching(graph, weight); bpmatching.run(); bpmatching.matching(matching); return bpmatching.matchingValue(); } /// \ingroup matching /// /// \brief Maximum weighted maximum cardinality bipartite matching /// /// This function calculates the maximum weighted of the maximum cardinality /// matchings of a bipartite graph. It gives back the matching in an /// undirected edge map. /// /// \param graph The bipartite graph. /// \param weight The undirected edge map which contains the weights. /// \retval matching The undirected edge map which will be set to /// the matching. /// \return The value of the matching. template typename WeightMap::Value maxWeightedMaxBipartiteMatching(const BpUGraph& graph, const WeightMap& weight, MatchingMap& matching) { MaxWeightedBipartiteMatching bpmatching(graph, weight); bpmatching.run(true); bpmatching.matching(matching); return bpmatching.matchingValue(); } /// \brief Default traits class for minimum cost bipartite matching /// \brief Gives back the potential in the NodeMap /// /// Gives back the potential in the NodeMap. The potential /// is feasible if \f$\pi(a) - \pi(b) + w(ab) = 0 \f$ for /// 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. template void potential(PotentialMap& potential) { void potential(PotentialMap& potential) const { for (ANodeIt it(*graph); it != INVALID; ++it) { potential[it] = anode_potential[it]; /// \return The number of the matching edges. template int quickMatching(MatchingMap& matching) { int quickMatching(MatchingMap& matching) const { for (ANodeIt it(*graph); it != INVALID; ++it) { if (anode_matching[it] != INVALID) { /// \return The number of the matching edges. template int matching(MatchingMap& matching) { int matching(MatchingMap& matching) const { for (UEdgeIt it(*graph); it != INVALID; ++it) { matching[it] = it == anode_matching[graph->aNode(it)]; /// /// It returns true if the given uedge is in the matching. bool matchingEdge(const UEdge& edge) { bool matchingEdge(const UEdge& edge) const { return anode_matching[graph->aNode(edge)] == edge; } /// Returns the matching edge from the node. If there is not such /// edge it gives back \c INVALID. UEdge matchingEdge(const Node& node) { UEdge matchingEdge(const Node& node) const { if (graph->aNode(node)) { return anode_matching[node]; }; /// \ingroup matching /// /// \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. /// /// \param graph The bipartite graph. /// \param cost The undirected edge map which contains the costs. /// \retval matching The undirected edge map which will be set to /// the matching. /// \return The cost of the matching. template typename CostMap::Value minCostMaxBipartiteMatching(const BpUGraph& graph, const CostMap& cost, MatchingMap& matching) { MinCostMaxBipartiteMatching bpmatching(graph, cost); bpmatching.run(); bpmatching.matching(matching); return bpmatching.matchingCost(); } }
• ## test/bipartite_matching_test.cc

 r2051 vector aNodes; vector bNodes; int n = argc > 1 ? atoi(argv[1]) : 100; int m = argc > 2 ? atoi(argv[2]) : 100; int n = argc > 1 ? atoi(argv[1]) : 10; int m = argc > 2 ? atoi(argv[2]) : 10; int e = argc > 3 ? atoi(argv[3]) : (int)((n+m) * log(n+m)); int c = argc > 4 ? atoi(argv[4]) : 100; int max_weight; int max_cardinality_max_weight; int min_cost_matching; for (int i = 0; i < n; ++i) { } max_cardinality = bpmatch.matchingSize(); } { Graph::UEdgeMap mm(graph); check(max_cardinality == maxBipartiteMatching(graph, mm), "WRONG MATCHING"); for (ANodeIt it(graph); it != INVALID; ++it) { int num = 0; for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { if (mm[jt]) ++num; } check(num <= 1, "INVALID PRIMAL"); } } for (UEdgeIt it(graph); it != INVALID; ++it) { if (mm[it]) { check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0, check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0, "INVALID DUAL"); } else { check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0, check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0, "INVALID DUAL"); } { Graph::UEdgeMap mm(graph); check(max_weight == maxWeightedBipartiteMatching(graph, weight, mm), "WRONG MATCHING"); for (ANodeIt it(graph); it != INVALID; ++it) { int num = 0; for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { if (mm[jt]) ++num; } check(num <= 1, "INVALID PRIMAL"); } } { MaxWeightedBipartiteMatching bpmatch(graph, weight); for (UEdgeIt it(graph); it != INVALID; ++it) { if (mm[it]) { check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0, check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0, "INVALID DUAL"); } else { check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0, check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0, "INVALID DUAL"); } for (UEdgeIt it(graph); it != INVALID; ++it) { if (mm[it]) { check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] == 0, check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] == 0, "INVALID DUAL"); } else { check(pm[graph.aNode(it)] - weight[it] - pm[graph.bNode(it)] >= 0, check(pm[graph.aNode(it)] + pm[graph.bNode(it)] - weight[it] >= 0, "INVALID DUAL"); } { Graph::UEdgeMap cost(graph); cost = subMap(constMap(c), weight); Graph::UEdgeMap mm(graph); check(max_cardinality_max_weight == maxWeightedMaxBipartiteMatching(graph, weight, mm), "WRONG MATCHING"); for (ANodeIt it(graph); it != INVALID; ++it) { int num = 0; for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { if (mm[jt]) ++num; } check(num <= 1, "INVALID PRIMAL"); } } Graph::UEdgeMap cost(graph); cost = subMap(constMap(c), weight); { MinCostMaxBipartiteMatching bpmatch(graph, cost); } min_cost_matching = bpmatch.matchingCost(); check(max_cardinality == bpmatch.matchingSize(), "WRONG SIZE"); check(max_cardinality * c - max_cardinality_max_weight } { Graph::UEdgeMap mm(graph); check(min_cost_matching == minCostMaxBipartiteMatching(graph, cost, mm), "WRONG MATCHING"); for (ANodeIt it(graph); it != INVALID; ++it) { int num = 0; for (IncEdgeIt jt(graph, it); jt != INVALID; ++jt) { if (mm[jt]) ++num; } check(num <= 1, "INVALID PRIMAL"); } } return 0; }
Note: See TracChangeset for help on using the changeset viewer.