The blossom algorithm is an algorithm in graph theory for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. Given a general graph G = (V, E), the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and |M| is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph.
Through this project, we aim to implement the blossom algorithm and visualize the steps leading to the maximum matching by using a graphical interface. The user creates the graph on screen by virtue of mouse inputs and obtains the maximum matching for the given input graph. The interface also allows the user to control the steps which show the implementation of the algorithm.
The environment in which the code is to be executed, must have the MinGW (gcc) compiler installed and the OpenGL API set up. Here is a comprehensive tutorial on how to do the same in the Windows environment.
Compile the C++ file with the following headers in the terminal
g++ graph.cpp -lGL -lGLU -lglut -o x.outExecute the compiled binary file
./x.outIn the window that pops up, create a graph by placing vertices with left-mouse clicks. We draw edges between vertices by clicking on one vertex of the edge and connecting it with the other vertex as shown in the demo below. Once the graph has been formed, right-click the mouse to terminate the input stage and initiate the Blossom algorithm.
Now head over to the terminal and press the Enter key to see how the algorithm proceeds step-by-step till the maximum matching is obtained. Once we obtain the maximum matching, the program shall ask us to press the Enter key thrice to terminate the program.
The graph represents matched edges in 🔴 red color and unmatched edges in ⚫ black color. The table below lists the various colors used with the vertices to denote actions:
| Color | Description |
|---|---|
| 🔴 | The active vertex which is being studied |
| 🟢 | The vertex for which we are finding the augmenting path |
| 🔵 | The vertex whose children are being explored |
| 🟡 | The vertex belonging to a blossom |
| 🟠 | The vertex is the father of the active vertex |
| ⚪ | A regular vertex which is none of the above |
Note: To have an in-depth understanding of how the code works line-by-line, refer to this report we have prepared.
Language used: C++
Libraries & APIs used: OpenGL, GLUT
This polynomial time algorithm is used in several applications including the assignment problem, the marriage problem, and the Hamiltonian cycle and path problems (i.e., Traveling Salesman Problem).
Throughout the course of this project, we were mentored by Prof. Dr. Chandan Giri. We are really grateful to sir for his active cooperation and support. Here are some resources which were really helpful to us.