![]() |
abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
|
Minimum cost assignment in bipartite graphs. More...
#include <lemon/bipartite_matching.h>
Public Member Functions | |
| MinCostAssignment (const BpGraph &graph, const CostMap &cost) | |
| Constructor. | |
| bool | run () |
| Run the algorithm. | |
Query Functions | |
The results of the algorithm, after run() has returned | |
| Value | totalCost () const |
| Return the cost of the matching. | |
| bool | matching (const Edge &edge) const |
Return true if the given edge is in the matching. | |
| Edge | matching (const Node &n) const |
Return the matching edge incident to the given node, or INVALID if the node is not covered by the matching. | |
| const MatchingMap & | matchingMap () const |
| Return a const reference to the matching map. | |
| Value | potential (const Node &n) const |
| Return the potential of the given node, i.e., the dual solution [see the description of the class]. | |
This class finds a matching of minimum cost among those that cover every red node of a bipartite graph, possibly not complete and with any number of blue nodes, if one exists. It implements the method of successive shortest augmenting paths: each red node is matched in turn along a shortest path of the residual graph, found by Dijkstra's algorithm on the costs reduced by node potentials, which the method keeps nonnegative; it takes \(O( n_r\ , (n + m \log m) )\) time, i.e., \(O( n_r\ , (n + m \log n) )\) on a graph without parallel edges, where \(n_r\) is the number of red nodes.
The potentials are the dual solution: for every edge \(e\) between the red node \(r\) and the blue node \(b\), \(c(e) \geq \pi(b) - \pi(r)\), with equality on the matching, and the blue nodes left unmatched have the same potential, the largest of the blue nodes [see potential()].
| BPGR | The bipartite graph type the algorithm runs on. |
| CM | The type of the cost map, whose values must be of a signed arithmetic type. |
|
inline |
Constructor.
| graph | The bipartite graph the algorithm runs on. |
| cost | The costs of the edges. |
|
inline |
This function finds a minimum cost matching that covers every red node.
true if such a matching exists; if it does not, the matching is left as the methods had grown it, and the potentials have no meaning.