We give functions for computing maximum and minimum weighted matchings in bipartite graphs. All functions provide a proof of optimality of their answer in the form of a potential function pot (all functions below are also available without the parameter pot). See the LEDA book for a discussion of potential functions.
The functions in this section are template functions. The template parameter
NT can be instantiated with any number type. In order to use the template
version of the function the appropriate .t-file
must be included.
#include <LEDA/templates/mwb_matching.t>
The pre-instantiated versions have the same function
names except for the suffix _T
. Preinstatiations are available for the
number types int and double.
In order to use them either
#include <LEDA/mwb_matching.h>
or
#include <LEDA/graph_alg.h>
has to be included (the latter file includes the former).
Special care should be taken when using the functions with a number type NT that can incur rounding error, e.g., the type double. The functions are only guaranteed to perform correctly if all arithmetic performed is without rounding error. This is the case if all numerical values in the input are integers (albeit stored as a number of type NT) and if none of the intermediate results exceeds the maximal integer representable by the number type (252 in the case of doubles). All intermediate results are sums and differences of input values, in particular, the algorithms do not use divisions and multiplications.
The algorithms have the following arithmetic demands. Let C be the maximal absolute value of any edge cost and let k = min(| A|,| B|).
All intermediate values are bounded by 3C in the case of maximum weight matchings, by 7C + 14kC in the case of the assignment algorithm, and by 3(C + 1 + 2kC) in the case of maximum weight matchings of maximum cardinality.
list<edge> | MAX_WEIGHT_BIPARTITE_MATCHING_T(graph& G, edge_array<NT> c, node_array<NT>& pot) | |
computes a matching of maximal cost and a potential function pot
that is tight with respect to M. The running time of the algorithm is
O(n*(m + nlogn)).
Precondition: G must be bipartite.
|
||
list<edge> | MAX_WEIGHT_BIPARTITE_MATCHING_T(graph& G, list<node> A, list<node> B, edge_array<NT> c, node_array<NT>& pot) | |
As above. It is assumed that the partition (A, B) witnesses that G
is bipartite and that all edges of G are directed from A to B. If A and
B have different sizes then is is advisable that A is the smaller set; in
general, this leads to smaller running time.
|
||
void | CHECK_MWBM_T(graph G, edge_array<NT> c, list<edge> M, node_array<NT> pot) | |
checks that pot is a tight feasible
potential function with respect to
M and that M is a matching. Tightness of pot implies that M is a
maximum weighted matching.
|
||
list<edge> | MAX_WEIGHT_ASSIGNMENT_T(graph& G, edge_array<NT> c, node_array<NT>& pot) | |
computes a perfect
matching of maximal cost and a potential function pot
that is tight with respect to M. The running time of the algorithm is
O(n*(m + nlogn)). If G contains no perfect matching
the empty set of edges is returned.
Precondition: G must be bipartite.
|
||
list<edge> | MAX_WEIGHT_ASSIGNMENT_T(graph& G, list<node> A, list<node> B, edge_array<NT> c, node_array<NT>& pot) | |
As above. It is assumed that the partition (A, B) witnesses that G
is bipartite and that all edges of G are directed from A to B.
|
||
void | CHECK_MAX_WEIGHT_ASSIGNMENT_T(graph G, edge_array<NT> c, list<edge> M, node_array<NT> pot) | |
checks that pot is a tight feasible
potential function with respect to
M and that M is a perfect matching. Tightness of pot implies that M is a
maximum cost assignment.
|
||
list<edge> | MIN_WEIGHT_ASSIGNMENT_T(graph& G, edge_array<NT> c, node_array<NT>& pot) | |
computes a perfect
matching of minimal cost and a potential function pot
that is tight with respect to M. The running time of the algorithm is
O(n*(m + nlogn)). If G contains no perfect matching
the empty set of edges is returned.
Precondition: G must be bipartite.
|
||
list<edge> | MIN_WEIGHT_ASSIGNMENT_T(graph& G, list<node> A, list<node> B, edge_array<NT> c, node_array<NT>& pot) | |
As above. It is assumed that the partition (A, B) witnesses that G
is bipartite and that all edges of G are directed from A to B.
|
||
void | CHECK_MIN_WEIGHT_ASSIGNMENT_T(graph G, edge_array<NT> c, list<edge> M, node_array<NT> pot) | |
checks that pot is a tight feasible
potential function with respect to
M and that M is a perfect matching. Tightness of pot implies that M is a
minimum cost assignment.
|
||
list<edge> | MWMCB_MATCHING_T(graph& G, list<node> A, list<node> B, edge_array<NT> c, node_array<NT>& pot) | |
Returns a maximum weight matching among the matching of
maximum cardinality.
The potential function pot is tight with respect to a modified
cost function which increases the cost of every edge by
L = 1 + 2kC
where C is the maximum absolute value of any weight and
k = min(| A|,| B|).
It is assumed that the partition (A, B) witnesses that G
is bipartite and that all edges of G are directed from A to B. If A and
B have different sizes, it is advisable that A is the smaller set; in
general, this leads to smaller running time.
|