Algorithmes de couplages parfaits et de mariages stables
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
L’algorithme de base décrit plus haut présente un cas idyllique, chaque individu trie les membres de l’autre groupe. Mais on peut facilement imaginer un cas où tous les individus ne classent pas toutes les invidus de l'autre groupe. Pour résoudre ce problème, il suffit de modifier la condition de la boucle principale et de vérifier que chaque individu sans couple peut encore former un couple parmi ses choix restants.
Pour cela, on peut dérouler l’algorithme du mariage stable en s’assurant que pour chaque individu classé, s’il pourrait être en couple avec quelqu’un qu’il a classé. Cette variante n’est pas la plus optimisée, car elle implique le déroulement d'une deuxième exécution de l'algorithme pour cette vérification, Cependant, c’est probablement la manière la plus simple à implémenter si l’on souhaite adapter un algorithme de mariage stable de base. C’est d’ailleurs celle que j’ai utilisée dans l’exemple Parcoursup ci-dessus.
Il faudra aussi bien penser pour
X <- individu sans couple dans GRP_1
à vérifier que cet individu peut effectivement être mis en couple en plus de ne pas être déjà dans un couple.
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.
Définitions et conditions
Dans un graphe biparti, un couplage est dit parfait si chaque sommet de l'ensemble gauche ou droit du graphe biparti est en couple avec un sommet de l'autre ensemble, respectivement droit ou gauche.
Pour qu’un graphe biparti admette un couplage parfait, il doit respecter la condition suivante ( Théorème de Hall ) :
- Pour tout sous-ensemble (S,A) de l’ensemble gauche ou droit du graphe biparti, avec S l'enssemble de sommet et A l'enssemble des arrêtes, (le nombre d’arêtes est supérieur au nombre de sommets, sachant que pour rappel, le graphe biparti implique qu’aucun de ces sommets de ce sous-ensemble ne peut être relié entre eux).
Bien sûr, s’il n’y a pas la condition de couplage parfait, on peut quand même utiliser le principe de chemin augmentant pour avoir un nombre de couplages optimal dans le graphe.
Algorithme en pseudo code
Fonction Couplage_Maximal(Graphe):
Couplage ← vide
Répéter :
Sommet ← sommet non couplé dans la partie gauche
Chemin ← Trouver_Chemin_Augmentant(Graphe, Couplage, Sommet)
Si Chemin existe :
Inverser le couplage le long du chemin
Sinon :
Sortir de la boucle
Retourner Couplage
Fonction Trouver_Chemin_Augmentant(Graphe, Couplage, Sommet):
Si Sommet déjà visité :
Retourner Aucun
Marquer Sommet comme visité
Pour chaque Voisin du Sommet :
Si Voisin est libre OU si on peut étendre via son partenaire :
Retourner Chemin menant à Voisin
Retourner Aucun
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 trient les n élèves, mais elles ont chacune un nombre de place prédéfinie, 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;
}