Aller au contenu

Algorithme de Kruskal, union-find

Ce TP accompagne le chapitre Algorithmique avancée des graphes et utilise la structure du chapitre Union-Find.

Union-Find

On va définir un type

struct union_find {
    int *parent;
    int *rank;
    int nelements;
};
typedef struct union_find union_find;

Question 1. Écrire des fonctions de prototypes :

union_find uf_makesets(int n);
int uf_find(union_find uf, int x);
void uf_union(union_find uf, int x, int y);
void uf_free(union_find uf);

Ces fonctions vont réaliser les opérations vues en classe. Pour makesets on va réaliser des makeset des éléments de 0 à n-1 d'un coup en créant la valeur de type union_find (et notamment en allouant la mémoire). uf_free va alors libérer toute la mémoire allouée dans une telle structure.

Corrigé 
union_find uf_makesets(int n)
{
    union_find uf;
    uf.parent = malloc(sizeof(int) * n);
    uf.rank = malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
    {
        uf.parent[i] = i;
        uf.rank[i] = 0;
    }
    uf.nelements = n;
    return uf;
}

int uf_find(union_find uf, int x)
{
    if (uf.parent[x] != x)
        uf.parent[x] = uf_find(uf, uf.parent[x]);
    return uf.parent[x];
}

void uf_union(union_find uf, int x, int y)
{
    int rx = uf_find(uf, x);
    int ry = uf_find(uf, y);
    assert(rx != ry);

    if (uf.rank[rx] > uf.rank[ry])
        uf.parent[ry] = rx;
    else {
        uf.parent[rx] = ry;
        if (uf.rank[rx] == uf.rank[ry])
            uf.rank[ry] = uf.rank[ry] + 1;
    }
}

void uf_free(union_find uf)
{
    free(uf.parent);
    free(uf.rank);
}

Ici, on a choisi d'interdire l'union de deux éléments déjà dans le même ensemble avec un assert : c'est à l'appelant de tester uf_find(uf, x) != uf_find(uf, y) au préalable. Le chapitre Union-Find fait le choix inverse de rendre cet appel inoffensif. Il faut inclure stdlib.h et assert.h.

Question 2. Écrire des jeux de tests pour ces fonctions. Avec des assert par exemple.

Question 3. On veut comparer les différentes optimisations de cette structure de données. Pour cela, on rajoute deux nouveaux paramètres booléens compress et weighted qui vont indiquer respectivement si on effectue de la compression de chemin ou si on utilise les rangs pour équilibrer lors des unions. Reprendre les fonctions précédentes pour qu'elles tiennent compte de ces paramètres. On pourra remplacer le prototype de makesets pour initialiser les valeurs : union_find uf_makesets(int n, bool compress, bool weighted);

Corrigé

On ajoute les deux booléens à la structure (et on inclut stdbool.h) :

struct union_find {
    int *parent;
    int *rank;
    int nelements;
    bool compress;
    bool weighted;
};
typedef struct union_find union_find;

union_find uf_makesets(int n, bool compress, bool weighted)
{
    union_find uf;
    uf.compress = compress;
    uf.weighted = weighted;
    uf.parent = malloc(sizeof(int) * n);
    uf.rank = malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
    {
        uf.parent[i] = i;
        uf.rank[i] = 0;
    }
    uf.nelements = n;
    return uf;
}

int uf_find(union_find uf, int x)
{
    if (uf.compress) {
        if (uf.parent[x] != x)
            uf.parent[x] = uf_find(uf, uf.parent[x]);
        return uf.parent[x];
    } else {
        while(uf.parent[x] != x)
            x = uf.parent[x];
        return x;
    }
}

void uf_union(union_find uf, int x, int y)
{
    int rx = uf_find(uf, x);
    int ry = uf_find(uf, y);
    assert(rx != ry);

    if (!uf.weighted || uf.rank[rx] > uf.rank[ry])
        uf.parent[ry] = rx;
    else {
        uf.parent[rx] = ry;
        if (uf.rank[rx] == uf.rank[ry])
            uf.rank[ry] = uf.rank[ry] + 1;
    }
}

uf_free est inchangée.

Question 4. Écrire une fonction

int *random_tests(int n, int m);

qui génère un jeu de test aléatoire de m unions pour n valeurs. Ce jeu de test sera représenté par un tableau t de 2m entiers indiquant qu'on souhaite effectuer des unions entre t[2*i] et t[2*i+1]. On ne demande pas que les unions soient valides ici.

Rappel : on peut utiliser rand() % A pour générer une valeur aléatoire entière entre 0 et A-1.

Corrigé 
int *random_tests(int n, int m)
{
    int *fusions = malloc(sizeof(int) * 2 * m);

    for(int i = 0; i < 2*m; i++)
    {
        fusions[i] = rand() % n;
    }

    return fusions;
}

Question 5. Écrire une fonction

void apply_tests(union_find uf, int *tests, int m);

qui va appliquer les tests qu'on vient de générer sur un union_find qui aura été initialisé par le bon appel à uf_makesets.

Attention ici il faudra faire attention à ne faire l'union que si elle est valide, c'est-à-dire uniquement lorsqu'elle fusionne deux arbres de la forêt.

Corrigé 
void apply_tests(union_find uf, int *tests, int m)
{
    for(int i = 0; i < m; i++)
    {
        int x = tests[2*i];
        int y = tests[2*i+1];

        if (uf_find(uf, x) != uf_find(uf, y))
            uf_union(uf, x, y);
    }
}

Il est possible de mesurer des temps simplement en C à l'aide de la fonction clock_t clock(); définie dans time.h.

Cette fonction renvoie le temps processeur consommé par le programme, exprimé en tops d'horloge ; une constante CLOCKS_PER_SEC permet alors d'en déduire un nombre de secondes ainsi :

clock_t start = clock();
// tâche à mesurer en temps
clock_t end = clock();
// le nombre flottant de secondes écoulées
double elapsed = ((double)(end-start)/CLOCKS_PER_SEC);

Question 6. En déduire des tracés de comparaison du coût moyen en fonction de n pour 2n unions. On comparera avec/sans l'union pondérée et la compression de chemins (quatre choix donc). Attention, il sera sûrement impossible de mesurer le temps pris par la version sans optimisation pour de grandes valeurs de n.

Remarque

Pour tracer des courbes, on peut utiliser gnuplot ou faire un export vers Python avec matplotlib. On peut même faire un export en CSV dans la console et copier-coller dans un tableur.

La partie suivante présente rapidement gnuplot.

Remarque

À titre indicatif, pour \(n = 20\,000\) et \(2n\) unions aléatoires, on a mesuré environ 0,6 s sans optimisation contre moins de 0,01 s dès qu'une des deux optimisations est activée. Sans optimisation, la hauteur des arbres peut devenir linéaire et chaque find coûte alors \(O(n)\).

Gnuplot en bref

Si on a un fichier data.dat avec des valeurs séparées en colonnes par des tabulations ('\t'). Par exemple :

0   0   0
1   1   1
2   4   8
3   9   27
4   16  64

on peut procéder ainsi pour afficher un tracé avec gnuplot :

$ gnuplot
gnuplot> plot "data.dat"

Par défaut, il va tracer la deuxième colonne en fonction de la première.

Pour tracer la colonne j en fonction de la colonne i :

gnuplot> plot "data.dat" using i:j

On peut demander de tracer des lignes avec :

gnuplot> plot "data.dat" using i:j with linespoint

Tout ou presque peut être abrégé donc la commande précédente peut s'écrire :

gnuplot> p "data.dat" u i:j w lp

Pour tracer plusieurs courbes, on peut mettre les descriptions à la suite :

gnuplot> p "data.dat" u 1:2 w lp, "data.dat" u 1:3 w lp

On peut aussi utiliser des boucles pour faire ça :

gnuplot> p for [col=2:3] "data.dat" using 1:col w lp

Pour écrire un fichier, on peut préciser un terminal de sortie, par exemple en png, avec :

gnuplot> set terminal pngcairo size 500,500
gnuplot> set output "fichier.png"

Arbre couvrant de poids minimal

On considère un graphe de points du plan dont les arêtes sont données dans un tableau :

struct edge {
    int u;
    int v;
};
typedef struct edge edge;

struct vertex {
    double x;
    double y;
};
typedef struct vertex vertex;

struct graph {
    vertex *vertices;
    int nvertices;
    edge *edges;
    int nedges;
};
typedef struct graph graph;

Ainsi, l'arête e relie les sommets d'indice e.u et e.v. Un sommet v correspond au point du plan (v.x, v.y).

Question 7. Écrire une fonction

double w(graph *g, edge *e);

qui renvoie la distance euclidienne entre les deux sommets donnés par une arête.

Attention pour avoir sqrt il faudra math.h et lier avec -lm.

Corrigé 
double w(graph *g, edge *e)
{
    vertex a = g->vertices[e->u];
    vertex b = g->vertices[e->v];
    return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

Question 8. Écrire une fonction

graph randomize(int n, int m, double w, double h);

qui crée un graphe aléatoirement avec n sommets (n ≥ 2) et m arêtes. Les sommets auront des coordonnées dans [0,w] x [0,h].

Note : pour N assez grand, on peut générer aléatoirement un double dans [0,w] ainsi : w * ((double)(rand() % (N+1)) / N)

Corrigé 
graph randomize(int n, int m, double w, double h)
{
    int N = 10000;
    graph g;

    g.nvertices = n;
    g.vertices = malloc(sizeof(vertex) * n);
    for(int i = 0; i < n; i++)
    {
        g.vertices[i].x = w * ((double)(rand() % (N+1)) / N);
        g.vertices[i].y = h * ((double)(rand() % (N+1)) / N);
    }
    g.nedges = m;
    g.edges = malloc(sizeof(edge) * m);
    for(int i = 0; i < m; i++)
    {
        int u = rand() % n;
        int v = rand() % (n-1);
        if (v == u) v = v + 1;
        g.edges[i].u = u;
        g.edges[i].v = v;
    }

    return g;
}

On évite ainsi les boucles \(u \smile u\) : si \(v = u\), alors \(u \le n-2\) et \(v + 1 \le n - 1\). Le paramètre w masque ici la fonction w de la question précédente, ce qui ne pose pas de problème puisqu'on ne l'utilise pas dans cette fonction. Le graphe obtenu peut contenir des arêtes multiples et n'est pas forcément connexe.

Question 9. Pour trier les arêtes on va utiliser qsort de stdlib.h. Cette fonction pose plusieurs problèmes :

  • il faut faire des conversions depuis void * explicitement ;
  • comme la fonction de comparaison ne prend pas de paramètre supplémentaire, on doit utiliser des variables globales.

On vous demande ainsi d'ajouter dans votre fichier :

graph *global_graph = NULL;
int compare_edges(const void *e1, const void *e2)
{
    double w1 = w(global_graph, (edge *)e1);
    double w2 = w(global_graph, (edge *)e2);
    if (w1 < w2)
        return -1;
    if (w1 > w2)
        return 1;
    return 0;
}

et pour trier les arêtes du graphe g, on pourra alors écrire :

global_graph = g;
qsort(g->edges, g->nedges, sizeof(edge), compare_edges);

Question 10. On sait qu'un arbre couvrant contient nvertices-1 arêtes, on va donc stocker un arbre couvrant comme un tableau d'entiers mst de cette longueur. mst[i] sera l'indice de la i-ème arête dans l'arbre.

Écrire ainsi une fonction

int *kruskal(graph *g);

qui renvoie le tableau mst en l'ayant alloué préalablement.

On s'assurera que le graphe est connexe en vérifiant que la structure union_find utilisée ne contient qu'un seul arbre.

Corrigé

On compte les arbres de la forêt en comptant les racines :

int uf_count_trees(union_find uf)
{
    int count = 0;
    for(int i = 0; i < uf.nelements; i++)
        if (uf.parent[i] == i)
            count++;
    return count;
}

int *kruskal(graph *g)
{
    global_graph = g;
    qsort(g->edges, g->nedges, sizeof(edge), compare_edges);

    int *mst = malloc(sizeof(int) * (g->nvertices - 1));
    union_find uf = uf_makesets(g->nvertices, true, true);
    int mst_size = 0;

    for (int i = 0; i < g->nedges; i++)
    {
        int ru = uf_find(uf, g->edges[i].u);
        int rv = uf_find(uf, g->edges[i].v);
        if (ru != rv)
        {
            uf_union(uf, ru, rv);
            mst[mst_size] = i;
            mst_size++;
        }
    }
    assert(uf_count_trees(uf) == 1);
    uf_free(uf);

    return mst;
}

Attention, les indices stockés dans mst sont ceux des arêtes après le tri : kruskal modifie l'ordre du tableau g->edges.

Remarque

Pour tester kruskal, on peut comparer, sur de nombreux petits graphes aléatoires connexes (4 à 6 sommets), le poids de l'arbre obtenu avec le minimum des poids des parties à \(n - 1\) arêtes qui forment un arbre, obtenu par énumération de toutes ces parties. C'est ainsi qu'ont été testés les corrigés de ce TP.

Question 11. Faire des essais de graphes aléatoires en affichant le graphe et par-dessus dans une autre couleur l'arbre couvrant de poids minimal obtenu.