Bipartite Matching Problem in C#

• Download source code - 20.7 KB

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

//Variables required
private int n1, n2;//number of coordinates on left and right
private Point[] coordinatesLeft,coordinatesRight;//array of coordinates
private bool[,] graph;//if there is an edge, it is set to true
public static Point P1;//three points required for tackling with mousemove
public static Point P2;
public static Point P3;
public Color drawColor = Color.Black;
public bool mouseDown = false;//required for mouse drag
private int mid = -1;//separates two sets of coordinates
private Point temp;//to check if the point already exists
//matching contains the current list of matching coordinates
private ArrayList matching, parent;
private bool matchingDone = false;
// to paint once its done

//findMatching method
while (list.Count > 0)
//implements BFS, until the queue is empty
{
    Point p = list[0];
    list.Remove(p);
    if (p.X < mid)//on the left coordinates
    {
        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)//free node
                {
                    updateMatching(parent, "v" + j);
                    //empty the list;
                    list.Clear();
                    break;
                }
            }
        }