Algorithms Tick 3*: bipartite matching

In this tick you will implement two versions of a matching algorithm for a bipartite graph, both based on the Ford–Fulkerson algorithm. A bipartite graph is one in which the vertices are split into two sets, Left and Right, and all edges have one end in Left and the other in Right. A matching is a selection of some or all of the graphs edges, such that no vertex (either left or right) is connected to more than one edge.

Task 1: maximum size matchings

A maximum size matching (also called a maximum matching) is a matching with as many edges as possible. An algorithm to find one, using the Ford–Fulkerson algorithm, is described in lecture notes. Your first task is to implement this algorithm.

You will be given an \(m\times n\) matrix weights, such that weight[i][j]>0 if there is an edge between left-hand vertex \(i\in\{0,\dots,m-1\}\) and right-hand vertex \(j\in\{0,\dots,n-1\}\), and weight[i][j]==0 if there is no edge. Your code should return an array of length \(m\) representing the matching, call it res, where res[i]==j means that left hand vertex \(i\) matches with right hand vertex \(j\), and res[i]==-1 means that left hand vertex \(i\) is not matched.

Note that your algorithm for this task should only pay attention to whether or not weights[i][j] is non-zero. It should treat weights[i][j]==1 exactly the same as weights[i][j]=1000.

Task 2: weighted matchings

The weight of a matching is the sum of its edge weights, and in many applications it is useful to be able to find high-weight matchings. In this task, you will still use the Ford–Fulkerson algorithm, but you will implement a heuristic method to look for a maximum matching that prefers edges with high weight.

First, implement a version of breadth first search that finds all shortest paths from the source to the sink. Next, from among these shortest paths, pick the one that has maximum reward, where the reward of a ‘forward’ edge from left-vertex \(i\) to right-vertex \(j\) is weights[i][j] and the reward of a ‘backwards’ edge from right-vertex \(j\) to left-vertex \(i\) is - weights[i][j].

For example, given \[ \text{weights} = \begin{pmatrix}10&4&5\\6&8&3\\5&4&0\end{pmatrix} \] your code should in its first pass pick the edge with weight 10, in its second pass it should add the edge with weight 8, and in its third pass it should discard the edge with weight 10 and pick instead the two edges with weight 5.

Task 3: optimization (optional)

Optional, not necessary for earning the star

Your algorithm from Task 2 will stop as soon as it has found a maximum matching, even though there may be other maximum size matchings of higher weight.

To seek a higher weight matching, we could define a new graph with appropriate edge weights, look for a negative-weight cycle in this new graph, and use such a cycle to improve the weight of the matching. Implement an algorithm to achieve this, by adapting Bellman–Ford to discover such a cycle.

Submission (Python)

Submission filename: matching.py (The Moodle tester lets you upload more than one file, and you may if you wish include your maxflow.py from Tick 3.)

Please submit a source file matching.py that implements two functions:

max_matching(weights)
greedy_matching(weights)

Here weights is a matrix, which might not be square. The number of left-hand vertices is len(weights) and the number of right-hand vertices is len(weights[0]). Your functions should both return a list, with one entry for each left-hand vertex. You can use either -1 or None to indicate “this vertex is not matched”.

Submission (Java)

Submission filenames: MaximumMatcher.java and GreedyMatcher.java (The Moodle tester lets you upload an extra file, and you may wish to include your MaxFlowFinder.java from Tick 3.)

Please submit two classes, MaximumMatcher for task 1 and GreedyMatcher for task 2. Each of these should implement the interface uk.ac.cam.cl.tester.Algorithms.Matcher, defined as follows:

package uk.ac.cam.cl.tester.Algorithms;

public interface Matcher {
    int[] getMatching(int[][] weights);
}

The weights matrix might not be square. The number of left-hand vertices is weights.length, and the number of right-hand vertices is weights[0].length.