## Wednesday, January 15, 2014

### The "empty chairs" bipartite matching algorithm

Today while browsing the TC forums I had a blast from the past. There was a time in which I didn't know what max flow or bipartite matching is, so I had to learn it. The process was difficult and long. While trying to understand max flow though, I did get some knowledge about solving bipartite matching without max flow. Or rather by a very simplified recursive logic that does max flow.

The good thing about the recursive logic is that it has a real life metaphor that makes it easy to remember and it is also very easy to implement. I am reposting this from an old topcoder forums post I wrote a long time ago. I thought it is good to have it in a more visible place:

Well, I have a logic for bipartite matching that makes an easy to remember and implement algorithm, not to mention it is fast:

This is as best as I could explain it:

int personInChair[m]; //personInChair[m] Points to the person that's currently on  chair i
bool foundChair[n]; //foundChair[i] is 1 if and only if the guy has already sit on a chair.

bool canSit[n][m]; //canSit[i][j] is true if and only if person i can sit on chair j.

bool findChair(int x)
// Person x will try and find a new chair...
{
return false;   //preventing infinite recursion and things like that

for (int j=0; j<m; j++)
if(canSit[x][j])
{
int otherGuy = personInChair[j];
if ( otherGuy == -1)
{
//the sit is empty, just sit on it!
personInChair[j] = x;
foundChair[x] = true;
return true;
}
else
{
//kindly ask the other guy if he can move to another chair:
if ( findChair(otherGuy) )
{
//he was able to move.
personInChair[j] = x;
foundChair[x]=true;
return true;
}

}
}
return false; //No chairs available right now.
}

int maximumChairs() //this will return the maximum number of people
// that sit on a chair.
{
int sum=0;
fill(personInChair,personInChair+m, -1); //nobody has sit yet.
fill(foundChair,foundChair+n, false);    //
while(true)
{
bool somethingChanged = false;
for (int i=0; i<n; i++) //Everybody should try to find a chair.
if(! foundChair[i] )
{
if(findChair[i])
{
somethingChanged=true;
sum++;
}
}

if(!somethingChanged)
break;

}

return sum;
}


I think that when I came up with that algorithm it was based on code I've seen from red coders. The chair metaphor makes it easy to remember. I wonder if this algorithm has a name / original author or if it is something that merely materialized in programming competitions out of need.

Anyway, it is not that fast. It is O(n^3) :)