NAME

Graph::Matching - Maximum Matching in Graphs

SYNOPSIS

Computes maximum matchings in general weighted graphs.

A matching is a subset of edges in which no node occurs more than once. The cardinality of a matching is the number of matched edges. The weight of a matching is the sum of the weights of its edges.

Example:

    use Graph::Matching qw(max_weight_matching);
    my $graph = [ [ 1, 2, 14 ], [ 2, 3, 18 ] ];
    my %matching = max_weight_matching($graph);

FUNCTION

%m = max_weight_matching($graph [, $maxcardinality ])

Compute a maximum-weighted matching in the undirected, weighted graph $graph. If $maxcardinality is true, compute the maximum-cardinality matching with maximum weight among all maximum-cardinality matchings.

The graph $graph should be a reference to an array of edges. An edge is described by an arrayref [ $v, $w, $weight ], containing the two nodes and the weight of the edge. Edges are undirected (usable in both directions). A pair of nodes may have at most one edge between them.

The matching is returned as a hash %m, such that $m{$v} == $w if node $v is matched to node $w. Unmatched nodes will not occur as keys of %m.

This function takes time O(number_of_nodes ** 3).

If all edge weights are integers, the algorithm uses only integer computations. If floating point weights are used, the algorithm could return a slightly suboptimal matching due to numeric precision errors.

$graph = edges_from_Graph($g)

Extract a reference to an array of edges, suitable for passing to the max_weight_matching function, from an instance $g of the CPAN Graph module.

NOTES

The algorithm is taken from "Efficient Algorithms for Finding Maximum Matching in Graphs" by Zvi Galil, ACM Computing Surveys, 1986. It is based on the "blossom" method for finding augmenting paths and the "primal-dual" method for finding a matching of maximum weight, both methods invented by Jack Edmonds. Some ideas were taken from "Implementation of algorithms for maximum matching on non-bipartite graphs" by H.J. Gabow, Stanford Ph.D. thesis, 1973.