Repository files navigation

Theblossom algorithm is an algorithm in graph theory for constructing maximum matchings on graphs.The algorithm was developed byJack 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 theMinGW (gcc) compiler installed and theOpenGL 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.out

Execute the compiled binary file

  ./x.out

In 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 theEnter 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 theEnter 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:

Note: To have an in-depth understanding of how the code works line-by-line, refer to thisreport we have prepared.

Language used: C++

Libraries & APIs used: OpenGL, GLUT

This polynomial time algorithm is used in several applications including theassignment problem, themarriage problem, and theHamiltonian cycle and path problems (i.e.,Traveling Salesman Problem).

• @suddhabratoghosh

• @bikramjitsaha

• @rahulsharma

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.

• Blossom algorithm
• Edmonds's Blossom Algorithm - Maximum matchings in general graphs
• CS494 Lecture Notes - Edmonds' General Matching Algorithm