home

fail everything

Gale Shapley Source Code

If the title doesn’t ring any bells than stop reading now. Basically, I needed to implement the gale shapely algorithm for a uni assessment but whilst looking around for an implementation I could only find one in python here . The pseudo code for the algorithm from the wiki found here is this:

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = m's highest ranked such woman who he has not proposed to yet
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
           (m, w) become engaged
           m' becomes free
         else
           (m', w) remain engaged
    }
}

Here is the algorithm implemented in AS3, there is a difference in the else if part where the “else some pair already exists” from the pseudo code is assumed in the AS3. Also, the last else from the pseudo code is missing since it is redundant.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public function galeShapely():void
{
    var tempMan:Person = null;
    var tempWoman:Person = null;
    while(manArray.length > 0)
    {
        tempMan = manArray[0];
        tempWoman = womanArray[tempMan.getNextPreferance() - 1];
        if (tempWoman.getMatchedTo() == null)
        {
            tempWoman.setMatchedTo(manArray.shift());
        }
        else if (tempWoman.isBetterPreferance(tempMan.getIndex()))
        {
            manArray.push(tempWoman.getMatchedTo());
            tempWoman.setMatchedTo(manArray.shift());
        }
    }
}

Download the full source here

3 Responses

  1. Pingback: Is there a fast, open-source implementation of the Gale-Shapley algorithm? - Quora

  2. csr

    at line 6, do you mean:
    while(manArray.length > 0)

    December 14, 2011 at 3:07 am

  3. Roman Kovalik

    Wow, must have happen when I was trying to get the syntax highlighting to work, fixed now. Thanks for pointing it out.

    December 14, 2011 at 8:04 pm

Leave a Reply

Your email address will not be published. Required fields are marked *

*


8 × = forty eight

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>