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 Value totalCost() const

Return the cost of the matching.

inline bool matching( const Edge & edge ) const

Return true if the given edge is in the matching.

inline 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.

inline const MatchingMap & matchingMap() const

Return a const reference to the matching map.

inline Value potential( const Node & n ) const

Return the potential of the given node, i.e., the dual solution [see the description of the class].

Public Types

typedef BPGR BpGraph

The bipartite graph type of the algorithm.

typedef CM CostMap

The type of the cost map.

typedef CostMap::Value Value

The type of the costs.

typedef BpGraph::template NodeMap< typename BpGraph::Edge > MatchingMap

The type of the matching map.

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:

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.