Click here to Skip to main content
Click here to Skip to main content

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#.

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;
                }
            }
        }

License

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

Share

About the Author

Nabin Nepal
Engineer
Nepal Nepal
No Biography provided

Comments and Discussions

 
GeneralMy vote of 1 Pinmemberfereshte arjmand14-Apr-10 23:09 
Generali wana code in C language Pinmembers198313-Feb-10 7:16 

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

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

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