Introduction
This project implements the Bipartite Matching Problem in C# .NET. It intends to find out the maximum match between two sets of coordinates in a bipartite graph.
Background
Readers of this article require some understanding of Bipartite graphs. A Bipartite graph is one in which nodes of the graph are divided into two groups where there are no edges between the same group.
Using the code
The project contains a button "FindMatching
" and a drawing panel inside a form. The user draws a bipartite graph on the panel, and finally clicks the button "FindMatching" which displays the maximum match between two sets of coordinates in the bipartite graph
private int n1, n2;
private Point[] coordinatesLeft,coordinatesRight;
private bool[,] graph;
public static Point P1;
public static Point P2;
public static Point P3;
public Color drawColor = Color.Black;
public bool mouseDown = false;
private int mid = -1;
private Point temp;
private ArrayList matching, parent;
private bool matchingDone = false;
while (list.Count > 0)
{
Point p = list[0];
list.Remove(p);
if (p.X < mid)
{
for (int k = 0; k < coordinatesLeft.Length; k++)
{
if (p == coordinatesLeft[k])
{
index = k;
break;
}
}
visited.Add("u" + index);
for (int j = 0; j < n2; j++)
{
bool found = false;
if (graph[index,j] == true && !visited.Contains("v" + j))
{
for (int k = 0; k < matching.Count; k++)
{
ArrayList row = (ArrayList)matching[k];
if (row[1].Equals("v" + j))
{
list.Add(coordinatesRight[j]);
found = true;
}
}
ArrayList parentRow = new ArrayList();
parentRow.Add("v" + j);
parentRow.Add("u" + index);
parent.Add(parentRow);
if (!found)
{
updateMatching(parent, "v" + j);
list.Clear();
break;
}
}
}
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.