Algorithmes de couplages parfaits et de mariages stables

Introduction

On a tous déjà connu ce moment où l’on rencontre un autre groupe. Pour favoriser les intéractions, on décide de faire des paires. Mais chacun a ses affinités, certains ne veulent pas être avec certains autres, ou ont des préférences de manière générale. Il faut donc former les paires de la manière la plus juste possible. C’est à cela que sert l’algorithme du mariage stable, il permet de créer des paires ou couples stables, en tenant compte des préférences. C'est un cas particulier ou une variante de l'algorithme des couplages parfaits.

Mariages Stable

Le problème

On a 2 groupes avec le même nombre d'individus par groupe. Chaque individu de chaque groupe note chaque individu de l'autre groupe par ordre de préférence. Le but: faire des couples en fonction des préférences pour que les couples soient stables.

Avec stable qui voudrait dire que si quelqu’un préfère un autre à son partenaire ce dernier ne le préfère pas en retour.

Algorithme en pseudo code

Entrée:

• GRP_1 avec n individus
• GRP_2 avec n individus

Tant que tout element dans GRP_1 n'est pas dans un couple:
    X <- individu sans couple dans GRP_1
    Pour i allant de 1 à n :
        Y <- le i-ème individu dans la liste de préférences de X
        Si Y n'est pas encore en couples:
            Mettre en couple X avec Y
            Sortir de la boucle pour X
        
        Sinon:
	    Z <- individu en couple avec Y
            Si Y préfère X à Z:
		        Enlève de couple Z et Y
		        Mettre en couple X avec Y
                Sortir de la boucle
        Fin Sinon
        Fin Si
   Fin Pour
Fin Tant que

Couplages Parfaits

Le problème

Dans un graphe biparti quelconque, le but est de trouver un couplage parfait c'est à dire un couplage où chaque sommet de chaque groupe est couplé à un sommet de l'autre groupe.

Pour cela, on va utiliser des chemins augmentants pour ajouter un couple à chaque fois, jusqu'à ce que le couplage soit parfait, en partant du principe qu'un tel couplage existe.

Algorithme en pseudo code

Entrée:

• Graphe biparti G, où GRP_1 et GRP_2 sont les deux groupes de n sommets.

Fonction CouplageParfait(G):
    C <- Créer Couplage Vide()
    Tant que nombre des couplage dans C est différent de n:
        S <- sommet_sans_couple(GRP_1)
        P <- créer chemin vide()
        mettre tout les sommets comme non visité()
        ajoute couplage (C, Trouve_Chemin_Augmentant (G,C, P, S))
    Fin tant que
    renvoie C

Fonction Trouve_Chemin_Augmentant (G,C,P,S):
    Mettre dans sommet visité(S)
    Pour chaque voisin T, de S dans G :
        Si T n'est pas visité et peut former un chemin augmentant et T non sommet visité:
            Ajouter T à P 
            Marquer T comme visité
            Si T est en couple avec un autre sommet Z dans C:
                Si Trouve_Chemin_Augmentant(G, C, P, Z):
                    Retourner P
            Sinon:
                Retourner P
    
    Retourner P

Implémentation

Mariages Stable Classique

Contexte

On a deux groupes de n individus, et chaque individu d’un groupe trie tous les individus de l’autre groupe.

Exemple en C

#include <stdio.h>
#include <stdlib.h>

typedef struct _noeuds 
{
    char nom[50];
    struct _noeuds* voisin;
    struct _noeuds** liste_pref;
}noeuds;

typedef struct 
{
    noeuds** grp1;
    noeuds** grp2;
    int len;
} liste_noeuds;

noeuds* get_noeuds_sans_voisins(liste_noeuds lst )
{
    noeuds* voisin = 0;
    int i = 0;
    while(i < lst.len && voisin == 0)
    {
        if( lst.grp1[i]->voisin == 0)
        {
            voisin = lst.grp1[i];
        }
        i++;
    }
    return voisin;
}

int get_ordre_pref(noeuds* noeud, noeuds* voisin)
{
    int i = 0;
    int trouvee = 0;
    while (! trouvee)
    {
        if (noeud->liste_pref[i] == voisin)
        {
            trouvee = 1;
        }
        else{
            i++;
        }
    }
    return i;
}

void create_couple(liste_noeuds lst)
{
    noeuds* noeud = get_noeuds_sans_voisins( lst);
    while( noeud != 0)
    {
        int i = 0;
        while( noeud->voisin == 0)
        {
            noeuds* voisin_pref = noeud->liste_pref[i];

            for (int i = 0; i < lst.len; i++)
            {
                printf("%s avec %s\n", lst.grp1[i]->nom, lst.grp1[i]->voisin->nom);
            }

            printf("\n");
            
            if(voisin_pref->voisin == 0)
            {
                voisin_pref->voisin = noeud;
                noeud->voisin = voisin_pref;
            }
            else
            {
                if (get_ordre_pref(voisin_pref,noeud)<get_ordre_pref(voisin_pref, voisin_pref->voisin) && 1)
                {
==Mariages Stable adapté pour Parcoursup==
                    noeud->voisin = voisin_pref;
                    voisin_pref->voisin->voisin = 0;
                    voisin_pref->voisin = noeud;
                }
                else
                {
                    i++;
                }
                
            }
        }
        noeud = get_noeuds_sans_voisins(lst);
    }
}

int main()
{
    liste_noeuds lst;
    lst.grp1 = malloc(4*sizeof(noeuds));
    lst.grp2 = malloc(4*sizeof(noeuds));
    lst.len = 4;

    noeuds** pref_A = malloc(4*sizeof(noeuds*));
    noeuds A = {"A", 0, pref_A};
    lst.grp1[0]= &A;

    noeuds** pref_B = malloc(4*sizeof(noeuds*));
    noeuds B = {"B", 0, pref_B};
    lst.grp1[1]= &B;

    noeuds** pref_C = malloc(4*sizeof(noeuds*));
    noeuds C = {"C", 0, pref_C};
    lst.grp1[2] = &C;

    noeuds** pref_D= malloc(4*sizeof(noeuds*));
    noeuds D = {"D", 0, pref_D};
    lst.grp1[3] = &D;

    noeuds** pref_E= malloc(4*sizeof(noeuds*));
    noeuds E = {"E", 0, pref_E};
    lst.grp2[0] = &E;

    noeuds** pref_F= malloc(4*sizeof(noeuds*));
    noeuds F = {"F", 0, pref_F};
    lst.grp2[1] = &F;

    noeuds** pref_I= malloc(4*sizeof(noeuds*));
    noeuds I = {"I", 0, pref_I};
    lst.grp2[2] = &I;

    noeuds** pref_H= malloc(4*sizeof(noeuds*));
    noeuds H = {"H", 0, pref_H};
    lst.grp2[3] = &H;

    pref_A[0] = &E;
    pref_A[1] = &F;
    pref_A[2] = &H;
    pref_A[3] = &I;

    pref_B[0] = &H;
    pref_B[1] = &F;
    pref_B[2] = &I;
    pref_B[3] = &E;

    pref_C[0] = &I;
    pref_C[1] = &H;
    pref_C[2] = &E;
    pref_C[3] = &F;

    pref_D[0] = &E;
    pref_D[1] = &I;
    pref_D[2] = &H;
    pref_D[3] = &F;

    pref_E[0] = &B;
    pref_E[1] = &C;
    pref_E[2] = &A;
    pref_E[3] = &D;

    pref_F[0] = &B;
    pref_F[1] = &A;
    pref_F[2] = &D;
    pref_F[3] = &C;

    pref_H[0] = &C;
    pref_H[1] = &A;
    pref_H[2] = &B;
    pref_H[3] = &D;

    pref_I[0] = &A;
    pref_I[1] = &B;
    pref_I[2] = &D;
    pref_I[3] = &C;


    create_couple(lst);
    printf("%s avec %s\n", A.nom, A.voisin->nom);
    printf("%s avec %s\n", B.nom, B.voisin->nom);
    printf("%s avec %s\n", C.nom, C.voisin->nom);
    printf("%s avec %s\n", D.nom, D.voisin->nom);

    free(lst.grp1);
    free(lst.grp2);
    
    free(pref_A);    
    free(pref_B);
    free(pref_C);
    free(pref_D);
    free(pref_E);
    free(pref_F);
    free(pref_H);
    free(pref_I);
}

Coulages Parfaits

Contexte

On peut avoir un graph biparti quelconque dans ce programme.

Exemple en C

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

uint32_t seed;

struct _noeud
{
    int name;
    struct _noeud** voisin;
    struct _noeud* couple;
    int nb_voisin;
} ;
typedef struct _noeud noeuds;

typedef struct
{
    noeuds** gauche;
    int nb_noeuds_gauche;

    noeuds** droite;
    int nb_noeuds_droite;
} g_biparti;

struct _list_ch {
    noeuds* noeud;
    struct _list_ch* suivant;
};
typedef struct _list_ch lst_ch;

typedef struct{
    noeuds* prec;
    noeuds* noeud;
    int est_traite;
} precedent;

uint32_t alea(int inf, int sup)
{

    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;

    return inf + (seed % (sup - inf + 1));
}

void shuffle(void **array, int size)
{
    for (int i = size - 1; i > 0; i--) 
    {
        int j = alea(0, size-1);

        void * temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

void** cree_cp_lst(void** lst, int nb)
{
    void** lst_cp = malloc(nb*sizeof(void*));
    for (int i = 0; i < nb; i++)
    {
        lst_cp[i] = lst[i];
    }
    return lst_cp;
}

g_biparti creer_graph_bi_parti(int nb_noeuds_gauche, int nb_noeuds_droite)
{
    g_biparti graph;
    graph.gauche = malloc(sizeof(noeuds*)*nb_noeuds_gauche);
    graph.nb_noeuds_gauche = nb_noeuds_gauche;
    graph.droite = malloc(sizeof(noeuds*)*nb_noeuds_droite);
    graph.nb_noeuds_droite = nb_noeuds_droite;

    int i;
    for(i=0;i<nb_noeuds_gauche;i++)
    {
        graph.gauche[i] = malloc(sizeof(noeuds));
        graph.gauche[i]->name = i;
        graph.gauche[i]->nb_voisin = 0;
        graph.gauche[i]->voisin = NULL;
        graph.gauche[i]->couple = NULL;
    }
    for(int y=0;y<nb_noeuds_droite;y++)
    {
        graph.droite[y] = malloc(sizeof(noeuds));
        graph.droite[y]->name = y+i;
        graph.droite[y]->nb_voisin = 0;
        graph.droite[y]->voisin = NULL;
        graph.droite[y]->couple = NULL;
    }
    return graph;
}

void donne_voisin_alea(g_biparti graph)
{
    noeuds** noeud_d = (noeuds**) cree_cp_lst((void**) graph.droite, graph.nb_noeuds_droite);
    int* nb_voisin_noeud_d = calloc(graph.nb_noeuds_droite, sizeof(int));

    for (int i = 0; i < graph.nb_noeuds_gauche; i++)
    {
        noeuds* noeud = graph.gauche[i];

        shuffle((void**) noeud_d, graph.nb_noeuds_droite);

        noeud->nb_voisin = alea(0, graph.nb_noeuds_droite);
        noeud->voisin = malloc(sizeof(noeuds*) * noeud->nb_voisin);

        for (int y = 0; y < noeud->nb_voisin; y++)
        {
            noeuds* v = noeud_d[y];
            noeud->voisin[y] = v;

            int index = v->name - graph.nb_noeuds_gauche;
            nb_voisin_noeud_d[index]++;
        }
    }

    for (int i = 0; i < graph.nb_noeuds_droite; i++)
    {
        graph.droite[i]->voisin = malloc(sizeof(noeuds*) * nb_voisin_noeud_d[i]);
        graph.droite[i]->nb_voisin = 0;
    }

    for (int i = 0; i < graph.nb_noeuds_gauche; i++)
    {
        noeuds* noeud = graph.gauche[i];
        for (int y = 0; y < noeud->nb_voisin; y++)
        {
            noeuds* droit = noeud->voisin[y];
            droit->voisin[droit->nb_voisin] = noeud;
            droit->nb_voisin++;
        }
    }

    free(noeud_d);
    free(nb_voisin_noeud_d);
}



void affichage(g_biparti graph)
{
    printf("Gauche:\n");
    for(int i = 0; i < graph.nb_noeuds_gauche; i++)
    {
        noeuds* noeud = graph.gauche[i];
        printf("noeud_g%d - couple: ", noeud->name);
        if (noeud->couple)
        {
            printf("noeud_d%d\n", noeud->couple->name);
        }
        else
        {
            printf("aucun\n");
        }
        if (noeud->nb_voisin == 0) {
            printf("\tsans voisin");
        }
        for (int y = 0; y < noeud->nb_voisin; y++)
        {
            printf("\tnoeud_d%d", noeud->voisin[y]->name);
        }
        printf("\n");
    }

    printf("\nDroite:\n");
    for(int i = 0; i < graph.nb_noeuds_droite; i++)
    {
        noeuds* noeud = graph.droite[i];
        printf("noeud_d%d - couple: ", noeud->name);
        if (noeud->couple)
        {
            printf("noeud_g%d\n", noeud->couple->name);
        }
        else
        {
            printf("aucun\n");
        }

        if (noeud->nb_voisin == 0) {
            printf("\tsans voisin");
        }
        for (int y = 0; y < noeud->nb_voisin; y++)
        {
            printf("\tnoeud_g%d", noeud->voisin[y]->name);
        }
        printf("\n");
    }
}

int attribue_cpl_naif(g_biparti graph)
{
    int nb_cpl = 0;
    for (int i=0; i<graph.nb_noeuds_gauche; i++)
    {
        noeuds* noeud = graph.gauche[i];
        for (int y=0; y<noeud->nb_voisin; y++) {
            if (noeud->voisin[y]->couple==NULL) {
                noeud->couple = noeud->voisin[y];
                noeud->couple->couple = noeud;
                nb_cpl++;
                break;
            }
        }
    }
    return nb_cpl;
}

noeuds* get_noeuds_sans_couple(noeuds** lst_noeuds, int nb_noeuds)
{
    for (int i = 0; i<nb_noeuds; i++) {
        if (lst_noeuds[i]->couple==NULL && lst_noeuds[i]->nb_voisin>0) {
            return lst_noeuds[i];
        }
    }
    return NULL;
}


int est_dans_lst_ch(lst_ch* lst_chaine, noeuds* noeud)
{
    while(lst_chaine != NULL )
    {
        if(lst_chaine->noeud == noeud)
        {
            return 1;
        }
        lst_chaine = lst_chaine->suivant;
    }
    return 0;
}

int est_deja_traite(precedent** precedents, int taille, noeuds* noeud) {
    for (int i = 0; i < taille; ++i) {
        if (precedents[i] != NULL && precedents[i]->noeud == noeud) {
            return 1;
        }
    }
    return 0;
}

void ajoute_lst_ch(lst_ch** a_faire, noeuds* noeud) {
    lst_ch* new_node = malloc(sizeof(lst_ch));
    new_node->noeud = noeud;
    new_node->suivant = *a_faire;
    *a_faire = new_node;
}

void liberer_lst_ch(lst_ch* liste) {
    while (liste) {
        lst_ch* tmp = liste;
        liste = liste->suivant;
        free(tmp);
    }
}

void chemin_augmentant_from_empty_node(g_biparti graph, lst_ch* a_faire, precedent** precedents) {
    noeuds* courant = a_faire->noeud;
    noeuds* prec = NULL;

    while (courant != NULL) {
        int i;
        for (i = 0; i < graph.nb_noeuds_droite + graph.nb_noeuds_gauche; i++) {
            if (precedents[i] && precedents[i]->noeud == courant) {
                break;
            }
        }

        prec = precedents[i]->prec;

        if (prec != NULL) {
            prec->couple = courant;
            courant->couple = prec;
        }

        courant = prec;
    }
}


int trouve_chemin_augmentant(g_biparti graph, lst_ch** a_faire, precedent** precedents) {
    while (*a_faire != NULL) {
        lst_ch* current = *a_faire;
        noeuds* noeud = current->noeud;
        *a_faire = current->suivant;
        free(current);

        for (int i = 0; i < noeud->nb_voisin; i++) {
            noeuds* voisin = noeud->voisin[i];

            if (!est_deja_traite(precedents, graph.nb_noeuds_gauche + graph.nb_noeuds_droite, voisin)) {
                precedent* new_prec = malloc(sizeof(precedent));
                new_prec->prec = noeud;
                new_prec->noeud = voisin;
                new_prec->est_traite = 0;

                for (int j = 0; j < graph.nb_noeuds_gauche + graph.nb_noeuds_droite; ++j) {
                    if (precedents[j] == NULL) {
                        precedents[j] = new_prec;
                        break;
                    }
                }

                if (voisin->couple == NULL) {
                    lst_ch temp;
                    temp.noeud = voisin;
                    temp.suivant = NULL;

                    chemin_augmentant_from_empty_node(graph, &temp, precedents);
                    return 1;
                } else {
                    ajoute_lst_ch(a_faire, voisin->couple);

                    precedent* new_prec_couple = malloc(sizeof(precedent));
                    new_prec_couple->prec = voisin;
                    new_prec_couple->noeud = voisin->couple;
                    new_prec_couple->est_traite = 0;

                    for (int j = 0; j < graph.nb_noeuds_gauche + graph.nb_noeuds_droite; ++j) {
                        if (precedents[j] == NULL) {
                            precedents[j] = new_prec_couple;
                            break;
                        }
                    }
                }
            }
        }
    }

    return 0;
}


int attribue_le_plus_de_couple(g_biparti graph)
{
    int nb_cpl = attribue_cpl_naif(graph);
    int ancient_nb_cpl;
    do
    {
        noeuds* noeud = get_noeuds_sans_couple(graph.gauche, graph.nb_noeuds_gauche);
        if(noeud==NULL) return nb_cpl;
        ancient_nb_cpl = nb_cpl;

    } while (ancient_nb_cpl < nb_cpl);
    return nb_cpl;
}

int max_matching(g_biparti graph) {
    int taille = graph.nb_noeuds_gauche + graph.nb_noeuds_droite;
    int nb_couples = 0;

    precedent** precedents = malloc(taille * sizeof(precedent*));
    for (int i = 0; i < taille; i++) {
        precedents[i] = NULL;
    }

    int match_trouve;

    do {
        for (int i = 0; i < taille; i++) {
            if (precedents[i] != NULL) {
                free(precedents[i]);
                precedents[i] = NULL;
            }
        }

        lst_ch* a_faire = NULL;

        for (int i = 0; i < graph.nb_noeuds_gauche; i++) {
            if (graph.gauche[i]->couple == NULL) {
                ajoute_lst_ch(&a_faire, graph.gauche[i]);

                precedent* p = malloc(sizeof(precedent));
                p->noeud = graph.gauche[i];
                p->prec = NULL;
                p->est_traite = 0;

                for (int j = 0; j < taille; ++j) {
                    if (precedents[j] == NULL) {
                        precedents[j] = p;
                        break;
                    }
                }
            }
        }

        match_trouve = trouve_chemin_augmentant(graph, &a_faire, precedents);

        if (match_trouve) {
            nb_couples++;
        }

        liberer_lst_ch(a_faire);
    } while (match_trouve);

    for (int i = 0; i < taille; ++i) {
        if (precedents[i]) {
            free(precedents[i]);
        }
    }
    free(precedents);

    return nb_couples;
}

void free_graph(g_biparti graph) {
    for (int i = 0; i < graph.nb_noeuds_gauche; i++) {
        free(graph.gauche[i]->voisin);
        free(graph.gauche[i]);
    }
    for (int i = 0; i < graph.nb_noeuds_droite; i++) {
        free(graph.droite[i]->voisin);
        free(graph.droite[i]);
    }
    free(graph.gauche);
    free(graph.droite);
}

int main()
{
    seed = time(NULL);
    
    int nb_noeuds_gauche = 5;
    int nb_noeuds_droite = 5;

    g_biparti graph = creer_graph_bi_parti(nb_noeuds_gauche, nb_noeuds_droite);
    donne_voisin_alea(graph);

    attribue_le_plus_de_couple(graph);
    max_matching(graph);
    affichage(graph);
    free_graph(graph);
    return 0;
}