# Changeset 2058:0b1fc1566fdb in lemon-0.x for lemon/bipartite_matching.h

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

Refinements in bipartite matching algorithms

File:
1 edited

### Legend:

Unmodified
 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(); } }