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.
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
.
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.
Optional, not tested
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.
You may submit your answer on Moodle in either Python or Java.
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 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
.
The tester will use its own copy of Matcher
from
uk.ac.cam.cl.tester.Algorithms
, and it will also have
access to LabelledGraph
and MaxFlow
from Tick 3.