MinCostAssignment
Declared in lemon/bipartite_matching.h, in the group Matching Algorithms; the same class on the Doxygen site.
-
template< typename BPGR , typename CM = typename BPGR::template EdgeMap< int > >
class MinCostAssignment Minimum cost assignment in bipartite graphs.
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()].
- Template Parameters:
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.
Query Functions
The results of the algorithm, after run() has returned
true.-
inline bool matching( const Edge & edge ) const
Return
trueif the given edge is in the matching.
-
inline Edge matching( const Node & n ) const
Return the matching edge incident to the given node, or
INVALIDif the node is not covered by the matching.
-
inline const MatchingMap & matchingMap() const
Return a const reference to the matching map.
Public Types
Public Functions
-
inline MinCostAssignment( const BpGraph & graph , const CostMap & cost )
Constructor.
- Parameters:
graph – The bipartite graph the algorithm runs on.
cost – The costs of the edges.
-
inline bool run()
Run the algorithm.
This function finds a minimum cost matching that covers every red node.
- Returns:
trueif such a matching exists; if it does not, the matching is left as the methods had grown it, and the potentials have no meaning.