Click here to Skip to main content
12,885,163 members (33,357 online)
Click here to Skip to main content
Add your own
alternative version


8 bookmarked
Posted 18 May 2007

Bipartite Matching Problem in C#

, 18 May 2007 CPOL
Rate this:
Please Sign up or sign in to vote.
Solving the Bipartite Matching Problem in C#.


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.


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];
    if (p.X < mid)//on the left coordinates
        for (int k = 0; k < coordinatesLeft.Length; k++)
            if (p == coordinatesLeft[k])
                index = k;
        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))
                        found = true;
                ArrayList parentRow = new ArrayList();
                parentRow.Add("v" + j);
                parentRow.Add("u" + index);

                if (!found)//free node
                    updateMatching(parent, "v" + j);
                    //empty the list;


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Nabin Nepal
Nepal Nepal
No Biography provided

You may also be interested in...

Comments and Discussions

GeneralMy vote of 1 Pin
fereshte arjmand14-Apr-10 22:09
memberfereshte arjmand14-Apr-10 22:09 
Generali wana code in C language Pin
s198313-Feb-10 6:16
members198313-Feb-10 6:16 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170424.1 | Last Updated 18 May 2007
Article Copyright 2007 by Nabin Nepal
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid