We are trying to implement the algorithm (very roughly) described in the pages 6 and 7 in the 1987 article "Three Fast Algorithms for Four Problems in Stable Marriage" by Dan Gusfield, available here.
However, there's something wrong in our code, and we can't find the source of the problem. In theory, breakmarriage should never fail and exit, since we already know the marriages that must be broken - but it does fail. The unexpected failure of breakmarriage causes the access to random places in the memory, causing the program to crash. Also, some instances find the correct number of rotations, but there are more rotations with no predecessors than expected.
Here's the code for the data structures and for procedures:
#include <stdlib.h>
struct ResultsList {
struct ResultsListElement* first;
struct ResultsListElement* last;
};
struct ResultsListElement {
char* value; //il matching
struct ResultsListElement* next;
};
struct RotationList { //list_el
char man;
char woman;
struct RotationList* next;
};
struct RotationNode {
struct RotationList* rotation;
int index;
int missing_predecessors;
struct SuccessorsList* successors;
};
struct SuccessorsList {
struct RotationNode* value;
struct SuccessorsList* next;
};
struct RotationsList { //free_rotations_list
struct RotationsListElement* first;
struct RotationsListElement* last;
};
struct RotationsListElement { //free_rotations_list
struct RotationNode* value;
struct RotationsListElement* next;
};
void appendResultsList(struct ResultsList* list, char* result){
struct ResultsListElement *new = malloc(sizeof (struct ResultsListElement));
new->value = result;
new->next = NULL;
if (list->first==NULL){
list->first = new;
list->last=new;
}else{
list->last->next = new;
list->last = new;
}
}
void appendRotationsList(struct RotationsList* list, struct RotationNode* rotation_node){
struct RotationsListElement *new = malloc(sizeof (struct RotationsListElement));
new->value = rotation_node;
new->next = NULL;
if (list->first==NULL){
list->first = new;
list->last=new;
}else{
list->last->next = new;
list->last = new;
}
}
#include <stdlib.h>
#include "..\data_structures\data_structures.h"
#define false 0
#define true 1
char* gale_shapley(int, int*, int*);
int accept_proposal(int*, int, int, int, int);
struct RotationsList* find_all_rotations(int*, int*, int, char*);
void breakmarriage(char*, int, int, int*, int*, int*, int*, struct RotationsList*, struct RotationNode**, int*, int*, int);
void pause_breakmarriage(int*, char*, char*, char*, struct RotationsList*, int, int, struct RotationNode**, int*, int*);
void recursive_search(char*, int, struct RotationsListElement*, struct ResultsList*);
char* gale_shapley(int n, int* men_preferences, int* women_preferences) {
int women_partners[n], men_free[n];
for (int i = 0; i < n; i++) {
women_partners[i] = -1;
men_free[i] = true;
}
while (true) {
int m = -1;
for (int i = 0; i < n; i++) {
if (men_free[i]){
m = i;
break;
}
}
if (m == -1) {
break;
}
for (int i = 0; i < n && men_free[m]; i++) {
int w = men_preferences[m * n + i];
if (women_partners[w] == -1) {
women_partners[w] = m;
men_free[m] = false;
} else {
int m1 = women_partners[w];
if (accept_proposal(women_preferences, n, w, m, m1)) {
women_partners[w] = m;
men_free[m] = false;
men_free[m1] = true;
}
}
}
}
char* matching = (char*)malloc(n * sizeof(char));
for (char i = 0; i < n; i++) {
matching[women_partners[i]] = i;
}
return matching;
}
int accept_proposal(int* women_preferences, int n, int w, int m, int m1) {
for (int i = 0; i < n; i++) {
if (women_preferences[w * n + i] == m) {
return true;
}
if (women_preferences[w * n + i] == m1) {
return false;
}
}
return 0;
}
struct RotationsList* find_all_rotations(int* men_preferences, int* women_preferences, int n, char* top_matching) {
struct RotationsList* free_rotations_list = (struct RotationsList*) malloc(sizeof (struct RotationsList));
free_rotations_list->first=NULL;
free_rotations_list->last=NULL;
struct RotationNode** last_to_have_modified = (struct RotationNode**)malloc(sizeof (struct RotationNode) * n); //vettore di puntatori all'ultimo nodo che ha modificato l'uomo
char* m_i = (char*) malloc(sizeof (char) * n);
char* inverted_bottom_matching = gale_shapley(n, women_preferences, men_preferences);
char* bottom_matching = (char*)malloc(sizeof (char) * n);
for(int i=0;i<n;i++){
bottom_matching[inverted_bottom_matching[i]]=i;
}
int* marking = (int*) malloc(sizeof (int) * n); //-1 unmarked, n marked ma non associata, altri sono la donna precedente
int rotation_index = 0; //per indicizzare le rotationi su already_added_predecessors
int* already_added_predecessors = (int*) malloc(sizeof (int) * (n*n)); //per ridurre il numero di archi nel grafo delle rotazioni
for (int j = 0; j < n; j++) {
m_i[j] = top_matching[j];
marking[j] = -1;
last_to_have_modified[j] = NULL;
}
int* men_preferences_indexes = (int*) malloc(sizeof (int) * n);
for (int j = 0; j < n*n; j++) {
already_added_predecessors[j] = false;
}
//escludiamo le preferenze sicuramente non presenti in un matrimonio stabile
for (int j = 0; j < n; j++) {
int k = 0;
while (men_preferences[j * n + k] != m_i[j]) {
k++;
}
men_preferences_indexes[j] = k+1;//scartiamo quelle attuali, teniamo solo quelle diverse
}
int old_m = 0;
while (true) {
//STEP 1
int m = -1;
//troviamo il primo uomo diverso tra m_i e bottom_matching
for (int j = old_m; j < n; j++) {
if (m_i[j] != bottom_matching[j]) {
m = j;
old_m = j;
break;
}
}
if (m < 0) { //m_i == bottom_matching
break;
}
//STEP 2
char w = m_i[m];
marking[w] = n;
breakmarriage(m_i, m, n, men_preferences, men_preferences_indexes, women_preferences, marking, free_rotations_list,
last_to_have_modified, &rotation_index, already_added_predecessors, w);
}
free(last_to_have_modified);
free(m_i);
free(marking);
free(already_added_predecessors);
free(men_preferences_indexes);
free(inverted_bottom_matching);
free(bottom_matching);
return free_rotations_list;
}
void breakmarriage(char* M, int m, int n, int* men_preferences, int* men_preferences_indexes, int* women_preferences, int* marking,
struct RotationsList* free_rotations_list, struct RotationNode** last_to_have_modified, int* rotation_index,
int* already_added_predecessors, int first_woman) {
int i = 0;
while (men_preferences[m * n + i] != M[m]) {//serve?
i++;
}
men_preferences_indexes[m] = i + 1;
int former_wife = M[m]; //il w dell'articolo, donna con cui l'uomo è accoppiato e si deve separare
char* reversed_M = (char*)malloc(sizeof (char) * n);
char* old_reversed_M = (char*)malloc(sizeof (char) * n);
for (i = 0; i < n; i++) {
reversed_M[M[i]] = i;
old_reversed_M[M[i]] = i;
}
int w, m1, breakmarriage_fail, k, old_marking;
int previous_woman = first_woman;
while(true) {
breakmarriage_fail = true;
//itero sulle preferenze di m
//m diventa m' dell'articolo all'interno del ciclo
for (i = men_preferences_indexes[m]; i < n; i++) {
w = men_preferences[m * n + i]; //il w dell'articolo
//prendo m1 (attuale compagno di w) e lo confronto con m
m1 = reversed_M[w];
//se w preferisce m a m1, sciolgo (w, m1) e creo (w, m)
if (marking[w] < 0 && accept_proposal(women_preferences, n, w, m, m1)) { //step 2a
k = men_preferences_indexes[m]; //aggiorniamo indice
while (men_preferences[k] != w) {
k++;
}
men_preferences_indexes[m] = k+1;
reversed_M[w] = m;
marking[w] = previous_woman;
previous_woman = w;
m = m1; //nuovo uomo non accoppiato
breakmarriage_fail = false;
break;
} else if (accept_proposal(women_preferences, n, w, m, old_reversed_M[w])) { //step 2b
breakmarriage_fail = false;
old_marking = marking[w];
reversed_M[w] = m;
pause_breakmarriage(marking, M, reversed_M, old_reversed_M, free_rotations_list, w, previous_woman,
last_to_have_modified, rotation_index, already_added_predecessors);
reversed_M[w] = m1;
if (former_wife == w) { //3c: w = w'
reversed_M[w] = m;
free(reversed_M);
free(old_reversed_M);
return; //al passo 1
} else {
if (!accept_proposal(women_preferences, n, w, m, m1)) {
marking[w] = old_marking;
previous_woman = w;
continue;//al passo 2
} else {
reversed_M[w] = m;
m = m1;//m1 è quello giusto o dovrebbe essere un altro??
break;
}
}
}
}
if (breakmarriage_fail) { //non abbiamo trovato un accoppiamento stabile per m
free(reversed_M);
free(old_reversed_M);
return;
}
}
}
void pause_breakmarriage(int* marking, char* M, char* reversed_M, char* old_reversed_M, struct RotationsList* free_rotations_list, int w,
int previous_woman, struct RotationNode** last_to_have_modified, int* rotation_index, int* already_added_predecessors) {
int no_predecessors = true;
struct RotationList* prev_list_el = NULL;
int w2 = w;
int go_on = true;
struct RotationNode* rotation_node = (struct RotationNode*)malloc(sizeof (struct RotationNode));
rotation_node->missing_predecessors = 0;
rotation_node->index = *rotation_index;
rotation_node->successors=NULL;
*rotation_index += 1;
struct RotationsList* predecessors_list = (struct RotationsList*)malloc(sizeof (struct RotationsList)); //i predecessori del nodo che stiamo creando, per poter resettare already_added_predecessors
predecessors_list->first = NULL;
predecessors_list->last=NULL;
struct RotationList* list_el = NULL;
struct SuccessorsList* new_successor;
while(w2 != w || go_on) {
go_on = false;
//costruire lista della rotazione dalla coda alla testa
list_el = (struct RotationList*)malloc(sizeof (struct RotationList));
list_el->man = old_reversed_M[w2];
list_el->woman = w2;
list_el->next = prev_list_el;
prev_list_el = list_el;
//aggiorniamo predecessori e last_to_have_modified
if (last_to_have_modified[old_reversed_M[w2]] != NULL && !already_added_predecessors[last_to_have_modified[old_reversed_M[w2]]->index]) {
new_successor = (struct SuccessorsList*)malloc(sizeof (struct SuccessorsList));
new_successor->value = rotation_node;
//aggiungiamo la rotazione solo una volta ad ogni predecessore
new_successor->next = last_to_have_modified[old_reversed_M[w2]]->successors;
last_to_have_modified[old_reversed_M[w2]]->successors = new_successor;
no_predecessors = false;
rotation_node->missing_predecessors += 1;
already_added_predecessors[last_to_have_modified[old_reversed_M[w2]]->index] = true;
appendRotationsList(predecessors_list, last_to_have_modified[old_reversed_M[w2]]);
}
last_to_have_modified[old_reversed_M[w2]] = rotation_node;
//aggiorniamo old_reversed_M (i = i+1)
old_reversed_M[w2] = reversed_M[w2];
//aggiorna M
M[old_reversed_M[w2]] = w2;
//resettare marking
marking[w2] = -1;
//update previous_woman
w2 = previous_woman;
previous_woman = marking[w2];
}
rotation_node->rotation = prev_list_el;
if (no_predecessors) {
appendRotationsList(free_rotations_list, rotation_node);
}
//ripristiniamo already_added_predecessors, deallocando lo spazio
struct RotationsListElement* rot_list_el = predecessors_list->first;
struct RotationsListElement * temp;
while (rot_list_el != NULL) {
already_added_predecessors[rot_list_el->value->index] = false;
temp = rot_list_el;
rot_list_el = rot_list_el->next;
free(temp);
}
free(predecessors_list);
return;
}
Notice that many of the parameters have the only purpose to make the code more efficient.
An example of an input that causes problems is the following, but it shouldn't be difficult to find more examples by trying random (valid) inputs.
2 0 1
0 1 2
1 0 2
2 0 1
0 1 2
1 2 0
We managed to get it to work. There were a few errors in the logic of the implementation and a matrix was being accessed like a vector.
Also, the way we were trying to find all the predecessors of the rotations can't work. We implemented the algorithm to build the graph that is presented later in the same paper - with some corrections since the algorithm in the paper has an error.
If you want to see the code, you can find it in this repository. As I'm writing it, it's still WIP, but the algorithm itself should be correct.