abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
MinCostAssignment< BPGR , CM > Class Template Reference

Minimum cost assignment in bipartite graphs. More...

#include <lemon/bipartite_matching.h>

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

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

Detailed Description

template< typename BPGR , typename CM = typename BPGR::template EdgeMap< int > >
class lemon::MinCostAssignment< BPGR , CM >

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
BPGRThe bipartite graph type the algorithm runs on.
CMThe type of the cost map, whose values must be of a signed arithmetic type.

Constructor & Destructor Documentation

◆ MinCostAssignment()

template< typename BPGR , typename CM = typename BPGR::template EdgeMap< int > >
MinCostAssignment ( const BpGraph & graph,
const CostMap & cost )
inline

Constructor.

Parameters
graphThe bipartite graph the algorithm runs on.
costThe costs of the edges.

Member Function Documentation

◆ run()

template< typename BPGR , typename CM = typename BPGR::template EdgeMap< int > >
bool run ( )
inline

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.