Solving the Stable Marriage problem in Erlang

Whilst talk­ing with an ex-col­league, a ques­tion came up on how to imple­ment the Sta­ble Mar­riage prob­lem using a mes­sage pass­ing approach. Nat­u­ral­ly, I want­ed to answer that ques­tion with Erlang!

Let’s first dis­sect the prob­lem and decide what process­es we need and how they need to inter­act with one anoth­er.

The sta­ble mar­riage prob­lem is com­mon­ly stat­ed as:

Giv­en n men and n women, where each per­son has ranked all mem­bers of the oppo­site sex with a unique num­ber between 1 and n in order of pref­er­ence, mar­ry the men and women togeth­er such that there are no two peo­ple of oppo­site sex who would both rather have each oth­er than their cur­rent part­ners. If there are no such peo­ple, all the mar­riages are “sta­ble”. (It is assumed that the par­tic­i­pants are bina­ry gen­dered and that mar­riages are not same-sex).

From the prob­lem descrip­tion, we can see that we need:

  • a mod­ule for man
  • a mod­ule for woman
  • a mod­ule for orches­trat­ing the exper­i­ment

In terms of inter­ac­tion between the dif­fer­ent mod­ules, I imag­ined some­thing along the line of the fol­low­ing:

image

The pro­pos­al com­mu­ni­ca­tion needs to be syn­chro­nous* as the man can­not pro­ceed until he gets an answer for his pro­pos­al. But all oth­er com­mu­ni­ca­tions can be asyn­chro­nous.

(* remem­ber, a syn­chro­nous call in OTP-sense is not the same as a syn­chro­nous call in Java/C# where the call­ing thread is blocked.

In this case the com­mu­ni­ca­tion still hap­pens via asyn­chro­nous mes­sage pass­ing, but the call­ing process asyn­chro­nous­ly waits for a reply before mov­ing on)

From here, the imple­men­ta­tion itself is pret­ty straight for­ward.

And using the test data from Roset­ta Code, you can have a mod­ule that sets up the test, which I’ve called stable_marriage here.

Com­pile and run the code gives the fol­low­ing out­put:

image

You can get the full source code for this solu­tion on github.

Enjoy!

Links

Repo for solu­tion

Roset­ta Code test data