Maximum Matchings
GitHub repository: https://github.com/wbchristerson/perfect-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.
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 filemain.bat
. A window will open on screen, beginning the program.
pygame
or livewires
, make sure that those packages are installed in lib/site-packages
from the level of the directory containing this project.