Algorithmes de couplages parfaits et de mariages stables

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche

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

Variante de l'algorithme

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);
}

Mariages Stable adapté pour Parcoursup

Contexte

Le groupe de gauche contient n individus et le groupe de droite m individus.

Le groupe de gauche représente les élèves, et celui de droite les formations. Les formations vont être attribuées aux élèves. L’inverse peut produire le même résultat ou un résultat différent, le groupe qui reçoit l’attribution est en général avantagé en moyenne en termes de rang de préférence dans leurs couples, les élèves peuvent formuler au plus m voeux, et réciproquement, les formations peuvent trier au plus n élèves et n peut être différent de m, donc il n’y a pas forcément autant de formations que d’élèves et inversement.

Exemple en C

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

uint32_t seed;

typedef struct _eleves eleves;
typedef struct _formation formation;
typedef struct _elvs_places elvs_places;

struct _formation
{
    int nom;

    elvs_places* places;
    int nb_places;
    int nb_places_prises;

    eleves** prefs;
    int nb_eleves_pref;
};
struct _eleves
{
    int nom;

    formation* etablissement;

    formation** voeux;
    int nb_voeux;
};

struct _elvs_places
{
    eleves* elvs;
    int classement;
};

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;
    }
}

int est_formation_complete(formation* form)
{
    return !(form->nb_places_prises < form->nb_places);
}

int get_max_tas_bin(elvs_places* tas_bin)
{
    return tas_bin[0].classement;
}

int get_indice_pref_elvs(formation* form, eleves* elvs)
{
    for (int i = 0; i < form->nb_eleves_pref; i++)
    {
        if(form->prefs[i] == elvs)
        {
            return i;
        }
    }
    return form->nb_eleves_pref;
}

eleves* get_eleves_sans_formation(eleves** lst_elvs, int nb_elvs)
{
    for (int i = 0; i < nb_elvs; i++)
    {
        if (lst_elvs[i]->etablissement==0)
        {
            for (int y = 0; y < lst_elvs[i]->nb_voeux; y++)
            {
                if( ! est_formation_complete(lst_elvs[i]->voeux[y]))
                {
                    return lst_elvs[i];
                }
                else if(get_max_tas_bin(lst_elvs[i]->voeux[y]->places) > get_indice_pref_elvs(lst_elvs[i]->voeux[y], lst_elvs[i]))
                {
                    return lst_elvs[i];
                }
            }
        }
    }
    return 0;
    
}

void insere_elt_dans_form_non_pleine(formation* form, elvs_places elvs_pl)
{
    int indice = form->nb_places_prises;
    elvs_places* places = form->places;  
    places[indice] = elvs_pl;
    while(indice>0){
        int indice_suiv = ( indice - 1 ) / 2;
        if(places[indice].classement>places[indice_suiv].classement)
        {
            elvs_places temps = places[indice_suiv];
            places[indice_suiv] = places[indice];
            places[indice] = temps;
        }
        indice = indice_suiv;
    }
    form->nb_places_prises++;
}

void insere_elt_dans_form_plein(formation* form, elvs_places elvs_pl)
{
    elvs_places* places = form->places;
    places[0] = elvs_pl;
    int indice = 0;
    int suivant_g = 1;
    int suivant_d = 2;
    while( suivant_g < form->nb_places)
    {
        if(suivant_d < form->nb_places)
        {
            if(places[suivant_g].classement > places[suivant_d].classement)
            {
                if(places[indice].classement < places[suivant_g].classement)
                {
                    elvs_places temps = places[indice];
                    places[indice] = places[suivant_g];
                    places[suivant_g] = temps;
                    indice = suivant_g;   
                }
                else if(places[indice].classement < places[suivant_d].classement)
                {
                    elvs_places temps = places[indice];
                    places[indice] = places[suivant_d];
                    places[suivant_d] = temps;
                    indice = suivant_d;  
                }
                else
                {
                    return;
                }
            }
            else{ 
                if(places[indice].classement < places[suivant_d].classement)
                {
                    elvs_places temps = places[indice];
                    places[indice] = places[suivant_d];
                    places[suivant_d] = temps;
                    indice = suivant_d;  
                }
                else if(places[indice].classement < places[suivant_g].classement)
                {
                    elvs_places temps = places[indice];
                    places[indice] = places[suivant_g];
                    places[suivant_g] = temps;
                    indice = suivant_g;   
                }
                else
                {
                    return;
                }
            }
        }
        else if(places[indice].classement < places[suivant_g].classement)
        {
            elvs_places temps = places[indice];
            places[indice] = places[suivant_g];
            places[suivant_g] = temps;
            indice = suivant_g;
        }
        else
        {
            return;
        }
        
        suivant_g = indice*2+1;
        suivant_d = indice*2+2;
    }
}

void attribue_formation(eleves** lst_elvs, int nb_elvs)
{
    eleves* elvs = get_eleves_sans_formation(lst_elvs, nb_elvs);
    while( elvs!=0 )
    {
        int i = 0;
        while (i < elvs->nb_voeux && elvs->etablissement==0)
        {
            if(est_formation_complete(elvs->voeux[i]))
            {
                int i_elvs_pref = get_indice_pref_elvs(elvs->voeux[i], elvs);
                int i_plus_ptite_pref = get_max_tas_bin(elvs->voeux[i]->places);
                if(i_elvs_pref < i_plus_ptite_pref)
                {
                    eleves* elvs_a_remplacer = elvs->voeux[i]->prefs[i_plus_ptite_pref];

                    elvs_a_remplacer->etablissement = 0;
                    elvs->etablissement = elvs->voeux[i];
                    insere_elt_dans_form_plein(elvs->voeux[i], (elvs_places){ .elvs = elvs, .classement = get_indice_pref_elvs(elvs->voeux[i],elvs)});
                }
            }
            else
            {
                elvs->etablissement = elvs->voeux[i];
                insere_elt_dans_form_non_pleine(elvs->voeux[i], (elvs_places){ .elvs = elvs, .classement = get_indice_pref_elvs(elvs->voeux[i],elvs)});
            }
            i++;
        }
        elvs = get_eleves_sans_formation(lst_elvs, nb_elvs);
    }
}


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;
}

void attribue_voeux_random(eleves** lst_elvs, int nb_evls, formation** lst_form, int nb_form)
{
    formation** lst_cp_forms = (formation **) cree_cp_lst((void **)lst_form, nb_form);
    for (int i = 0; i < nb_evls; i++)
    {
        
        shuffle( (void**) lst_cp_forms, nb_form);
    
        for (int j = 0; j < lst_elvs[i]->nb_voeux; j++)
        {
            lst_elvs[i]->voeux[j] = lst_cp_forms[j];
        }
    }
    free(lst_cp_forms);
}

void set_elvs_pref_random(eleves** lst_elvs, int nb_evls, formation** lst_form, int nb_form)
{
    eleves** lst_cp_elvs = (eleves**) cree_cp_lst( (void**) lst_elvs, nb_evls);
    for (int i = 0; i < nb_form; i++)
    {
        shuffle( (void**) lst_cp_elvs, nb_evls);

        for (int y = 0; y < nb_evls; y++)
        {
            lst_form[i]->prefs[y] = lst_cp_elvs[y];
        }
    }
    free(lst_cp_elvs);
}

eleves** cree_elvs(int nb_elvs, int nb_voeux)
{
    eleves** lst_elvs = malloc(nb_elvs*sizeof(eleves*));
    for (int i = 0; i < nb_elvs; i++)
    {
        lst_elvs[i] = malloc(sizeof(eleves));
        lst_elvs[i]->nom = i+1;
        lst_elvs[i]->etablissement = NULL;
        lst_elvs[i]->voeux = calloc(nb_voeux, sizeof(formation*));
        lst_elvs[i]->nb_voeux = nb_voeux;
    }
    return lst_elvs;
}

formation** cree_forms(int nb_forms,int nb_places, int nb_elvs)
{
    formation** lst_forms = malloc(nb_forms*sizeof(formation*));
    for (int i = 0; i < nb_forms; i++)
    {
        lst_forms[i] = malloc(sizeof(formation));
        lst_forms[i]->nom = i+1;
        lst_forms[i]->places = malloc(nb_places*sizeof(elvs_places));
        for (int y = 0; y < nb_places; y++)
        {
            lst_forms[i]->places[y].elvs = NULL;
        }
        
        lst_forms[i]->nb_places = nb_places;
        lst_forms[i]->nb_places_prises = 0;
        lst_forms[i]->prefs = malloc(nb_elvs*sizeof(eleves*));
        lst_forms[i]->nb_eleves_pref = nb_elvs;
    }
    return lst_forms;
    
}

void affichage(eleves** lst_elvs, int nb_elvs, formation** lst_forms, int nb_forms)
{
    for (int i = 0; i < nb_elvs; i++)
    {
        if(lst_elvs[i]->etablissement==NULL)
        {
            printf("evls%d : Pas de formation attribue\n", lst_elvs[i]->nom);
        }
        else
        {
            printf("evls%d : form%d\n", lst_elvs[i]->nom, lst_elvs[i]->etablissement->nom);
        }
        for (int y = 0; y < lst_elvs[i]->nb_voeux; y++)
        {
            if(lst_elvs[i]->voeux[y]==0)
            {
                printf("\t- voeux non attribue\n");
            }
            else
            {
                printf("\t- form%d", lst_elvs[i]->voeux[y]->nom);
            }
        }
        printf("\n");
    }
    printf("\n");
    for (int i = 0; i < nb_forms; i++)
    {
        printf("form%d :  (%d elvs %d)\n", i+1, lst_forms[i]->nb_places_prises, lst_forms[i]->nb_places);

        for (int y = 0; y < lst_forms[i]->nb_places; y++)
        {
            if( lst_forms[i]->places[y].elvs==NULL)
            {
                printf("\t- Place libre");
            }
            else{
                printf("\t-elvs%d", lst_forms[i]->places[y].elvs->nom);
            }
        }
        printf("\n");
        for (int y = 0; y < lst_forms[i]->nb_eleves_pref; y++)
        {
            printf("  - elvs%d",lst_forms[i]->prefs[y]->nom);
        }
        printf("\n");
    }
}

int main()
{
    seed = time(NULL);

    int nb_elvs = 1000;
    int nb_voeux = 8;

    int nb_forms = 13;
    int nb_places = 40;

    eleves** lst_elvs = cree_elvs(nb_elvs, nb_voeux);
    formation** lst_forms = cree_forms(nb_forms, nb_places, nb_elvs);

    attribue_voeux_random(lst_elvs, nb_elvs, lst_forms, nb_forms);
    set_elvs_pref_random(lst_elvs, nb_elvs, lst_forms, nb_forms);
    attribue_formation(lst_elvs, nb_elvs);
    
    affichage(lst_elvs, nb_elvs, lst_forms, nb_forms);

    for (int i = 0; i < nb_elvs; i++) {
        free(lst_elvs[i]->voeux);
        free(lst_elvs[i]);
    }
    free(lst_elvs);

    for (int i = 0; i < nb_forms; i++) {
        free(lst_forms[i]->places);
        free(lst_forms[i]->prefs);
        free(lst_forms[i]);
    }
    free(lst_forms);

    return 0;
}

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;
}
Récupérée de « http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=Algorithmes_de_couplages_parfaits_et_de_mariages_stables&oldid=15970 »