10182

The Blossom Algorithm for Weighted Graphs

This Demonstration shows the steps of Edmonds's famous blossom algorithm for finding the perfect matching of minimal weight in a complete weighted graph. The algorithm uses and modifies a dual solution—the labels on the vertices—and tries to find a perfect matching using only equality edges (edges whose weight equals the sum of the labels at its ends). The matching is augmented by the augmenting tree method, but when that fails, the labels are changed. When blossoms (odd cycles) are found, they are shrunk.
The numbers in the grid are the weights (or the reduced weights) but with inactive edges (edges within a blossom) excluded; red entries denote equality edges and blue denotes the current matching. The colors on the graph vertices at the bottom-left represent the blossom groupings, and the blue text above the grid shows the values of the labels : the set of current labels of (derived) vertices. The edges in the two graphs at the bottom show the current matching (blue), the current tree edges (green), and the current active equality edges (red). The table at the upper-left shows the vertices in the current derived graph, with the pseudo-nodes colored to match the cycles they represent. The pseudo-nodes are also shown via the arrows at the far right, which indicate the current pseudo-node that contains a given vertex.

DETAILS

The algorithm for finding a minimum weight matching is due to Jack Edmonds (1965; see [5]). It is noteworthy because at the time the problem was known to be solvable in polynomial time for bipartite graphs, but it was not clear that the general problem would yield as well. The unweighted case, where one seeks a matching of maximum size, is somewhat easier, and is described in [2].
Our implementation follows [1], but we consider only complete graphs and assume all weights are non-negative; this is fully general since false edges of large negative weight can always be added to make a graph complete. We give enough details for the reader to understand the output. For further details of some of the steps, see [1]. Open-source code that implements the algorithm in an efficient way is available at [3].
We assume the reader is familiar with the basics of matching theory in the bipartite case (see [4]); the main idea there is that of building an alternating-path tree and using the tree to augment the matching one edge at a time. For the weighted bipartite case, we use the idea of a feasible labeling of the vertices, where "feasible" means that for any edge , the sum of the labels is not greater than the edge's weight. The bipartite case makes use of the subgraph of equality edges: edges whose reduced weight (weight less the labels at the two ends) is 0. Both the unweighted and weighted bipartite case make use of alternating path trees; the key idea of Edmonds that allowed a general solution was to realize that when odd cycles arose during the tree construction, the cycle (called a blossom) could be shrunk to a single new vertex (called a pseudo-node), yielding a smaller derived graph on which the algorithm can be carried forward.
The weighted blossom algorithm uses the following datasets. The original vertex set (of size ) is denoted and we keep track of the following for the vertices and edges of the original graph:
, the list of pseudo-nodes that is absorbed into.
, the current pseudo-node for , the last entry in .
, the vertex matched to (0 if unmatched).
, the current weight of the edge .
Tree edges, a subset of the edges of ; the tree edge indicates that is the parent of .
Equality edges: edges such that and .
Let denote the derived graph, which consists of all vertices not currently in a blossom, together with all current pseudo-nodes, each of which represents a blossom. We use for the pseudo-nodes. Then for the derived graph with vertex set we keep track of the following:
, the parent of in the tree; if is not in the tree or is the root.
, the label of . In the Demonstration image the labels shown are the more relevant values .
gives the reduced weight of edge : .
A vertex in the tree is called odd or even depending on its distance to the root (the root is even). The subset of consisting of odd (resp., even) vertices is denoted (resp. ). And as the matching is constructed (and destroyed, since matching edges inside a blossom are deleted in Case 3), a vertex is called matched if there is a vertex such that and .
The algorithm loops through five cases until exiting via Case 1. Start with the initial labeling and the empty matching.
Case 1: Augment the matching. Do this if there is an equality edge with and being unmatched; the edge and the path from to the root in the tree are used to augment the matching. If there is an unmatched vertex in , then reset the tree to consist only of such a vertex. Otherwise expand all remaining pseudo-nodes in reverse order and return the final matching.
Case 2: Augment the tree with two new edges. Do this if Case 1 fails and there is an equality edge with , , not in the tree, and a matched vertex. Add the edges and where is chosen so that and ; is taken to be .
Case 3: Shrink a blossom and update the tree, weights, and matching. Do this if previous cases fail and there is an equality edge such that , and . Introduce a vertex for the new pseudo-node that is larger than any previously used, and set . When a blossom is shrunk, edges within the blossom are ignored: if they were in the matching or tree they are removed and even if they satisfy the equality edge condition, they are not considered equality edges. The weight updating step proceeds by for each original vertex lying in the cycle, even hereditarily, and each vertex not in the cycle.
Case 4: Expand an odd pseudo-node and update the tree, weights, and matching. Do this if previous cases fail and there is a pseudo-node for which . Delete from each list where . The weight update proceeds by for each original vertex lying, even hereditarily, in the cycle that represents and each vertex not in the cycle. This step is also used when the final expansion of blossoms is called upon in Case 1.
Case 5: Update the labels on vertices in that are in the current tree. Do this if none of the preceding cases hold. Compute as described in [1] and increase by for any and reduce by for any .
For the finer details of what is done in these cases, the author refers the reader to [1].
The complexity of the algorithm stems from two features: (1) blossoms can become vertices in subsequent blossoms, and (2) in Case 4 we can expand a pseudo-node out of order. Problem (1) requires keeping careful track of the current blossom for a given original vertex, and (2) requires updating many values in the stored data, since the expanded pseudo-node no longer exists.
To understand the output in the Demonstration, keep in mind that trees are represented two ways: the parent structure in describes the tree, but the edges come from vertices in such that is in the tree. Thus, for example, one can have tree edges and that are adjacent in the tree because the corresponding derived vertices and are the same. Also note that the derived graph is really a multigraph, since if, say, is 6 and the cycle 4, 5, 6 was just shrunk into the pseudo-node 7, then the edges , , and all exist in the derived graph, even though their ends (4, 5, 6) are all the same vertex in .
Snapshot 1 [seed 2, 6 vertices, step 12]: The derived graph at step 12 has four vertices (2, 3, 6, and the pseudo-node 7 representing {1, 4, 5}) and there are three equality edges, one of which is in the matching. The next step extends the tree from to , which allows the matching to be augmented to . This is now a perfect matching in the 4-vertex derived graph and the final blossom expansion adds to get the final minimal-weight matching in the original graph. Note that at the last step the label values are such that each matching edge is an equality edge. By a basic theorem [6, Thm. 5.5] this proves that the matching is minimal.
Snapshot 2 [seed 6, 12 vertices, step 36]: Here the derived graph's vertices are {2, 3, 7, 8, 16}, where 16 represents {1, 4, 5, 6, 9, 10, 11}. The tree is . The labels have just been changed and has just become an equality edge that creates a blossom because 1 is part of pseudo-node 16, thus closing the cycle via . So pseudo-node 17 gets introduced and the derived graph has only the two vertices 12 and 17. The minimal matching there is with weight 3 and the subsequent expansion of the remaining pseudo-nodes 17, 16, 15, and 14 leads to the final answer. Note that blossom 13 was eliminated earlier, at step 26. And at the final step the matching edges are not contained in the equality edges, though that does always hold true prior to the final expansion of pseudo-nodes.
Snapshot 3 [seed 6, 6 vertices, step 18]: In this example the minimum matching weight is 70 and the largest feasible labeling sum is 67, so a feasible labeling that proves the matching minimal does not exist. Note that the final matching is not a subset of equality edges. In this case there is no feasible labeling for which the equality edges contain the matching.
References
[1] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver, Combinatorial Optimization, New York: Wiley, 1998.
[2] M. Kusner and S. Wagon, "The Blossom Algorithm for Maximum Matching", Wolfram Demonstrations Project, 2011.
[3] Egerváry Research Group on Combinatorial Optimization. Lemon Graph Library. (2010) lemon.cs.elte.hu/trac/lemon.
[4] S. Wagon, "The Hungarian Maximum Matching Algorithm," Wolfram Demonstrations Project, 2010.
[5] Wikipedia. "Edmonds's Matching Algorithm." (Dec 13, 2011) en.wikipedia.org/wiki/Edmonds's_matching _algorithm.
[6] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, New York: Elsevier, 1976.

PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.