Bipartite Matching

Github Classroom

You can clone the starter files for this lab at this GitHub Classroom link. Be sure to open the assignment in VSCode and setup up your virtual environment following these instructions.

Objective

In this lab, you will implement bipartite graph matching algorithms in the context of assigning HTAs to courses based on their preferences. First, you’ll implement a method to translate our input graph into a directed graph which allows us to find augmenting paths. Then, you’ll implement the find_path method to yield these paths. Next, you’ll implement a method to improve a given partial matching by using an augmenting path. Finally, you’ll put these to construct an algorithm that iteratively constructs a maximum matching, maximizing the total number of HTAs who are assigned to courses.

Introduction

Imagine that you are the Brown CS Department, and need to assign HTAs to courses. Each HTA candidate has a list of courses which they are qualified for, and each course can take one HTA. Your goal is to create an assignment that matches as many HTAs to courses as possible.

This problem can be modeled through a bipartite graph (i.e. a graph with two subsets of nodes where there are no edges between nodes in the same subset) where:

Your task is to implement a matching algorithm to solve this problem efficiently

Setup

We’ll provide you with starter code to represent the Graph, following the style presented in lecture. You’ll need to implement various parts of the matching algorithm throughout the lab.

Step 1: Translating to a directed graph

As in lecture, we want to translate our input graph, given a partial matching, into a directed graph “g_arrow” which has the same nodes and edges which we can use to find augmenting paths in. It will be helpful to refer to the March 12th lecture notes to understand the exact specifications of this transformation.

Recall the clever trick we used in lecture of adding extra nodes to make finding augmenting paths easier. We have implemented this part for you.

Task: Finish implementing “make_directed_graph” in matching.py

TA Checkpoint: Ensure that you are passing the make_directed_graph test in test_matching.py

Step 2: Finding Augmenting Paths

Now, given a partial matching and a newly constructed directed graph, an augmenting path is a path that alternates between unmatched and matched edges and starts and ends at unmatched nodes. Ultimately, these paths will be used to improve the partial matching.

Consider the following simple graph, with a partial matching indicated by the edges in red. What is the augmenting path in this graph?

Task: Implement the find_path function, which should take in our newly constructed graph and a start and end node (which two do we choose?) and return an augmenting path, as a list of darts.

Question: How can we use these augmenting paths to adjust and improve our matching?

Step 3: Using an Augmenting Path to Improve a Matching

Consider this simple graph from above, with a partial matching of size 2 again indicated by the red edges. What is the augmenting path in this graph, and how can we use it to improve the matching?

Hint: finding an augmenting path should always allow you to increase the size of your matching by exactly 1.

Task: Implement the “augment_matching” helper function, which takes in a partial matching and an augmenting path, and returns an improved matching.

Question: What can we say about a given matching if there are no possible augmenting paths remaining in the graph?

Step 4: Putting it Together to Find a Maximum Matching

Now, we are finally ready to optimally assign our HTAs to courses.

Task: Implement the “find_maximum_matching” function as follows:

Final TA Checkpoint: Ensure that you are passing all of the tests in “test_matching.py”

Be prepared to answer the question: Why does this algorithm ensure a maximum matching?

If you have any feedback, you can fill out this anonymous Google Form!