Maximum Weighted Matching
Finds a matching in an undirected edge-weighted graph that maximizes the sum of matched edge weights.
Complexity: O(n3) for maximum_weighted_matching; exponential in m for brute force
Defined in: <boost/graph/maximum_weighted_matching.hpp>
Example
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/maximum_weighted_matching.hpp>
#include <iostream>
#include <vector>
using namespace boost;
// This algorithm hard-codes its weight source to the interior `edge_weight_t`
// tag (see boost/graph/maximum_weighted_matching.hpp). Bundled properties are
// not supported here; the tag-based form below is required.
using Graph = adjacency_list<vecS, vecS, undirectedS, no_property,
property<edge_weight_t, int>>;
using Vertex = graph_traits<Graph>::vertex_descriptor;
int main() {
Graph g(5);
add_edge(0, 1, {3}, g);
add_edge(1, 2, {1}, g);
add_edge(2, 3, {4}, g);
add_edge(3, 4, {2}, g);
add_edge(0, 4, {5}, g);
std::vector<Vertex> mate(num_vertices(g));
maximum_weighted_matching(g, &mate[0]);
std::cout << "Matched edges:\n";
int total = 0;
for (Vertex v = 0; v < num_vertices(g); ++v) {
if (mate[v] != graph_traits<Graph>::null_vertex() && v < mate[v]) {
auto w = get(edge_weight, g, edge(v, mate[v], g).first);
std::cout << " " << v << " -- " << mate[v] << " (w=" << w << ")\n";
total += w;
}
}
std::cout << "Total weight: " << total << "\n";
}Matched edges:
0 -- 4 (w=5)
2 -- 3 (w=4)
Total weight: 9(1) maximum_weighted_matching (default maps)
template <typename Graph, typename MateMap>
void maximum_weighted_matching(
const Graph& g,
MateMap mate);| Direction | Parameter | Description |
|---|---|---|
IN |
|
An undirected graph. The graph type must be a model of Vertex and Edge List Graph and Incidence Graph. The graph may not contain parallel edges. |
OUT |
|
Must be a model of
ReadWritePropertyMap,
mapping vertices to vertices. For any vertex v in the graph,
|
(2) maximum_weighted_matching (with vertex index map)
template <typename Graph, typename MateMap,
typename VertexIndexMap>
void maximum_weighted_matching(
const Graph& g,
MateMap mate,
VertexIndexMap vm);| Direction | Parameter | Description |
|---|---|---|
IN |
|
An undirected graph. The graph type must be a model of Vertex and Edge List Graph and Incidence Graph. The graph may not contain parallel edges. |
OUT |
|
Must be a model of
ReadWritePropertyMap,
mapping vertices to vertices. For any vertex v in the graph,
|
IN |
|
Must be a model of
ReadablePropertyMap,
mapping vertices to integer indices in the range |
(3) maximum_weighted_matching (with vertex index map and edge weight map)
template <typename Graph, typename MateMap,
typename VertexIndexMap, typename EdgeWeightMap>
void maximum_weighted_matching(
const Graph& g,
MateMap mate,
VertexIndexMap vm,
EdgeWeightMap weights);| Direction | Parameter | Description |
|---|---|---|
IN |
|
An undirected graph. The graph type must be a model of Vertex and Edge List Graph and Incidence Graph. The graph may not contain parallel edges. |
OUT |
|
Must be a model of
ReadWritePropertyMap,
mapping vertices to vertices. For any vertex v in the graph,
|
IN |
|
Must be a model of
ReadablePropertyMap,
mapping vertices to integer indices in the range |
IN |
|
Must be a model of ReadablePropertyMap, mapping edges to weights. Edge weights must be integers or floating point values. |
(4) brute_force_maximum_weighted_matching (default maps)
template <typename Graph, typename MateMap>
void brute_force_maximum_weighted_matching(
const Graph& g,
MateMap mate);| Direction | Parameter | Description |
|---|---|---|
IN |
|
An undirected graph. The graph type must be a model of Vertex and Edge List Graph and Incidence Graph. The graph may not contain parallel edges. |
OUT |
|
Must be a model of
ReadWritePropertyMap,
mapping vertices to vertices. For any vertex v in the graph,
|
(5) brute_force_maximum_weighted_matching (with vertex index map)
template <typename Graph, typename MateMap,
typename VertexIndexMap>
void brute_force_maximum_weighted_matching(
const Graph& g,
MateMap mate,
VertexIndexMap vm);| Direction | Parameter | Description |
|---|---|---|
IN |
|
An undirected graph. The graph type must be a model of Vertex and Edge List Graph and Incidence Graph. The graph may not contain parallel edges. |
OUT |
|
Must be a model of
ReadWritePropertyMap,
mapping vertices to vertices. For any vertex v in the graph,
|
IN |
|
Must be a model of
ReadablePropertyMap,
mapping vertices to integer indices in the range |
Description
Before you continue, it is recommended to read about maximal cardinality matching first. A maximum weighted matching of an edge-weighted graph is a matching for which the sum of the weights of the edges is maximum. Two different matchings (edges in the matching are colored blue) in the same graph are illustrated below. The matching on the left is a maximum cardinality matching of size 8 and a maximal weighted matching of weight sum 30, meaning that it has maximum size over all matchings in the graph and its weight sum can’t be increased by adding edges. The matching on the right is a maximum weighted matching of size 7 and weight sum 38, meaning that it has maximum weight sum over all matchings in the graph.
|
|
Both maximum_weighted_matching and
brute_force_maximum_weighted_matching find a
maximum weighted matching in any undirected graph. The matching is returned in a
MateMap, which is a
ReadWritePropertyMap
that maps vertices to vertices. In the mapping returned, each vertex is
either mapped to the vertex it’s matched to, or to
graph_traits<Graph>::null_vertex() if it doesn’t participate in the matching.
If the VertexIndexMap is not explicitly specified, it is obtained from the internal vertex property
of the graph by calling get(vertex_index, g).
If the EdgeWeightMap is not explicitly specified, it is obtained from the internal edge property
of the graph by calling get(edge_weight, g).
Algorithm Description
The maximum weighted matching problem was solved by Edmonds in
[68].
Subsequently, Gabow [69] and
Lawler [16] developed methods
to reduce the run time from O(V4) to O(V3).
The implementation of maximum_weighted_matching follows a description
of the O(V3) algorithm by Galil [71].
The best known time complexity for maximum weighted matching in general
graphs is O(VE + V2 log V) by Gabow
[70], but it relies on an efficient
algorithm for the nearest common ancestor problem on trees, which Boost
does not currently provide.
Starting from an empty matching, the algorithm repeatedly augments the matching until no further improvement is possible. Alternating trees and blossoms are used to find an augmenting path, in a way that is similar to maximum cardinality matching. A linear programming technique is used to ensure that the selected augmenting path has maximum weight. This involves assigning dual variables to vertices and blossoms, and computing slack values for edges.
The outline of the algorithm is as follows:
-
Start with an empty matching and initialize dual variables to half of the maximum edge weight.
-
(Labeling) Root a tree at each non-matched vertex, and proceed to construct alternating trees by labeling, using only edges with zero slack value. If an augmenting path is found, go to step 2. If a blossom is formed, go to step 3. Otherwise, go to step 4.
-
(Augmentation) Find the augmenting path, tracing the path through shrunken blossoms. Augment the matching. Deconstruct and unlabel the alternating trees traversed by the augmenting path. Go to step 1.
-
(Blossoming) Identify the blossoms in the alternating cycle and shrink these into a newly formed blossom. Return to step 1.
-
(Updating dual variables) Adjust the dual variables based on the primal-dual method. If this enables further growth of the alternating trees, return to step 1. Otherwise, halt the algorithm; the matching has maximum weight.
The implementation deviates from the description in [71] on a few points:
-
After augmenting the matching, [71] expands all blossoms with zero dual. This is correct but potentially unnecessary; some of the expanded blossoms will be recreated during the next stage. The implementation holds off on the expansion of such blossoms. In any scenario where a blossom must be expanded to make progress, label T will be assigned to it. At that point, the blossom will be expanded through a zero-delta dual step. The additional cost is O(V) per expanded blossom, and the total number of blossom expansions is O(V2), therefore this does not change the overall time complexity of the algorithm.
-
The algorithm records a minimum-slack edge ek,l for every pair of blossoms Bk, Bl. Storing these edges in a 2-dimensional array would increase the space complexity to O(V2); an unfortunate cost for large sparse graphs. The implementation of
maximum_weighted_matchingavoids this by maintaining, for each blossom Bk, a listBk.best_edge_setthat contains the non-empty elements of ek,l, plus edges between Bk and Bl discovered after shrinking Bk. The combined length of these lists is O(E), since any edge is contained in at most two lists. The algorithm only ever examines ek,l during the process of merging Bk into a larger blossom. In that case, it sequentially examines ek,l for all l, taking time O(V). The implementation handles this by examining every element ofBk.best_edge_set, taking time O(V) plus a constant time per newly discovered edge. This does not change the overall time complexity of the algorithm. -
After augmenting, [71] removes all labels and alternating trees. This keeps the algorithm simple, but it causes many trees and labels to be rediscovered at the beginning of the new stage. To avoid such redundant work,
maximum_weighted_matchingremoves labels only from the two alternating trees that are touched by the augmenting path. All other labels and trees are reused in the next stage. Erasing labels from a subset of the graph requires updating the data structures that track minimum-slack edges. This involves examining all edges that either touch a blossom which loses its label or touch a vertex which depended on a lost label. These steps take O(V + E) per stage, adding up to O(V3) in total. Although this strategy does not improve the worst-case time complexity of the algorithm, it achieves a significant speedup in benchmarks on random graphs.
If edge weights are integers, the algorithm uses only integer computations. This is achieved by internally multiplying edge weights by 2, which ensures that all dual variables are also integers.
A brute-force implementation
brute_force_maximum_weighted_matching is also
provided. This algorithm simply searches all possible matchings and
selects one with the maximum weight sum.