Maximum Matchings

This application demonstrates an algorithm for finding maximum matchings in bipartite graphs. The general procedure used begins with finding any maximal matching greedily, then expanding the matching using augmenting paths via almost augmenting paths. For a detailed explanation of the concepts involved, see Maximum_Matchings.pdf. The user can choose the bipartite graph in various ways or add edges randomly. There is then a series of selection options for demonstrating the algorithm. This project was created using Python along with the pygame and livewires packages.

Structure
  • The user may navigate through the various pages to choose the bipartite graph examined.
  • There are options to choose the sizes of the branches as well as which edges appear. Alternatively, edges can be chosen for the user randomly.
  • There are then options for attempting to find a maximum matching manually, as well as for immediately displaying a maximum matching. In addition, the user may watch the application of the algorithm continuously or with steps.
Design
To navigate throughout the pages of the program, there are buttons which can be hovered over. To push the buttons you must push the space bar while hovered over, rather than clicking.

The application begins with a page for selecting the left branch size.
Left branch selection view
This is followed by a similar page for selecting the right branch size.
Right branch selection view
The user may then elect to choose edges manually or to allow the program to randomly select edges, adding any individual edge using a pseudo-random number generator with probability 40%. Below is a view for making edge selections manually.
Edge selection view
The user is then taken to a page for selecting the type of operation to apply.
Operations options view
Upon selecting the manual matching option, the user is allowed to select edges of the graph to try to find a maximum matching. Congratulations are given upon succeeding.
Manual matching view
After selecting the automatic matching option, a maximum matching is immediately displayed.
Automatically generated maximum matching displayed
If the user selects the option to watch the algorithm, the steps of the algorithm will be displayed with changes occurring every few seconds (with a pause button available). The first image below is a still of the initial greedy matching generation and the second image below is a still of the identification of an augmenting path to increase the size of the matching.
Greedy matching search view
Identification of an augmenting path
The fourth option also displays the steps of the algorithm but with buttons to follow the steps.
Running The Application
You will need to have Python installed, as well as the pygame and livewires libraries. The version of livewires used for this project was taken from this download (which also contains downloads for Python and pygame), under "Book related software". To download Python only, visit this page.

To download, clone the repository using this terminal command:
git clone https://github.com/wbchristerson/perfect-matchings.git

Alternatively, follow the instructions below to download to a hard drive:
  • Navigate to this page.
  • Click the green "Clone or download" button towards the right then choose "Download ZIP".
  • Find the folder perfect-matchings-master in your Downloads folder or wherever it was placed on your device.
  • Right click and choose "Extract All" then extract.
  • From within the directory generated through extraction (named perfect-matchings-master, unless you changed the file name), double click on the batch file main.bat. A window will open on screen, beginning the program.
If you encounter errors involving pygame or livewires, make sure that those packages are installed in lib/site-packages from the level of the directory containing this project.