12,240,803 members (59,225 online)
alternative version

18.8K views
8 bookmarked
Posted

# Bipartite Matching Problem in C#

, 18 May 2007 CPOL
 Rate this:
Solving the Bipartite Matching Problem in C#.

## 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;
}
}
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))
{
found = true;
}
}
ArrayList parentRow = new ArrayList();

if (!found)//free node
{
updateMatching(parent, "v" + j);
//empty the list;
list.Clear();
break;
}
}
}```

## Share

 Engineer Nepal
No Biography provided

## You may also be interested in...

 First Prev Next
 My vote of 1 fereshte arjmand14-Apr-10 23:09 fereshte arjmand 14-Apr-10 23:09
 i wana code in C language s198313-Feb-10 7:16 s1983 13-Feb-10 7:16
 Last Visit: 31-Dec-99 19:00     Last Update: 28-Apr-16 20:30 Refresh 1