Aller au contenu

C20 Algorithmes des graphes

"If in physics there's something you don't understand, you can always hide behind the uncharted depths of nature. You can always blame God. You didn't make it so complex yourself. But if your program doesn't work, there is no one to hide behind. You cannot hide behind an obstinate nature. If it doesn't work, you've messed up."
E. Djikstra
(Interview télévisée)

Cours

Support de cours chapitre 20

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.

Travaux dirigés

Fiche de TD20

Travaux pratiques

Note

On rappelle les structures de données utilisés en OCaml pour représenter les graphes :

  • par matrice d'adjacence : 

    type graphe = {
ordre : int; 
madj : int array array};;

  • par liste d'adjacence : 

    type graphe = {
ordre : int;
ladj : int list array};;

â–Ş Exercice 1 : Nombre de chemins de longueurs k

On rappelle que les puissances de la matrice d'adjacence d'un graphe donnent le nombres de chemins de longueurs \(k\) entre deux sommets de ce graphe. Plus formellement, en notant \(M\) la matrice d'adjacence d'un graphe \(G\), le coefficient \(M_{ij}^k\) de la puissance \(k-\)ième de \(M\) est le nombre de chemins du sommet \(i\) vers le sommet \(j\) (voir l'exercice 9 de la fiche de TD du chapitre 17).

  1. Ecrire une fonction mult int array array -> int array array -> int array array qui prend en entrée deux matrices et calcule leur produit.

  2. Ecrire une fonction  expr: int array array -> int -> int array array qui prend en entrée une matrice \(M\) et un entier \(k\) et renvoie \(M^k\) en utilisant l'algorithme d'exponentiation rapide.

  3. On considère le graphe suivant :

    graph LR
A(("0"))
B(("1"))
C(("2"))
D(("3"))
E(("4"))
F(("5"))
G(("6"))
H(("7"))
A --> B
A --> C
B --> D
C --> F
C --> G
E --> G
E --> A
D --> F
G --> F
B --> C
F --> E
F --> H
H --> F
D --> C
    DĂ©terminer le nombre de chemins de longueur 42 entre le sommet 6 et le sommet 7.
    Vérifier votre réponse :

â–Ş Exercice 2 : Parcours en largeur d'un graphe

  1. Visualiser l'algorithme de parcours en largeur d'un graphe (site de l'université de San Francisco). On rappelle que dans ce parcours, on explore le graphe en "cercles concentriques" centrés sur le sommet de départ. Afin de s'assurer de la bonne compréhension de l'algorithme, on pourra prévoir le parcours puis lancer la visualisation afin de vérifier.

  2. Ecrire en OCaml une fonction bfs: graphe int -> int array qui prend en argument un graphe et un sommet de départ et renvoie un tableau de d'entiers donnant la distance minimale en nombre d'arêtes entre le sommet de départ et les sommets du graphe.

    Note

    Dans le cours, on avait utilisé la valeur -1 pour indiquer l'absence de chemin. Une autre possibilité est d'utiliser un type option c'est en OCaml une façon élégante d'indiquer l'absence de valeur ici, le tableau de distance peut contenir un entier ou alors None pour indiquer qu'aucun chemin n'a été trouvé. c'est-à-dire qu'on utilise le type None | Some of int (voir la documentation).

  3. Vous pouvez télécharger ci-dessous un fichier texte représentant un graphe non orienté à 50 noeuds (et 100 arêtes). Chaque ligne est une arête sous la forme de deux entiers : sommet de départ et sommet d'arrivée. Ecrire une fonction lire_graphe string -> int -> int*int list qui prend en argument une chaine de caractère (le nom du fichier) ainsi qu'un entier n (le nombre de sommets) et renvoie un graphe d'ordre n en y créant chaque arête lue dans le fichier. Exemple (50 noeuds et 100 arêtes)

  4. Tester votre fonction de parcours en largeur sur ce graphe, un seul sommet se situe à la distance maximale. Multiplier le numéro de ce sommet par cette distance et tester votre résultat :

  5. Pour le moment, notre fonction renvoie le tableau de distance mais sans indiquer le chemin à suivre. Créer un tableau parent qui indique lorsqu'un sommet est parcouru le sommet d'où l'on vient.

  6. Utiliser ce tableau afin de pouvoir reconstruire un chemin depuis le sommet de départ 42 jusqu'à n'importe quel sommet du graphe. Un seul chemin de longueur 4 (la longueur minimale) permet de relier le sommet 42 au sommet 43. Quel est ce chemin ? Vous pouvez vérifier votre résultat en entrant les sommets de ce chemin séparé par des points virgules (inclure 42 comme premier sommet et 43 comme sommet final)

â–Ş Exercice 3 : Parcours en profondeur d'un graphe

  1. Visualiser l'algorithme de parcours en profondeur d'un graphe (site de l'université de San Francisco). On rappelle que dans ce parcours, on explore à chaque étape le premier voisin non encore exploré du sommet courant. Afin de s'assurer de la bonne compréhension de l'algorithme, on pourra prévoir le parcours puis lancer la visualisation afin de vérifier.

  2. Dans cet algorithme on doit disposer d'une structure de données permettant de savoir si un sommet a déjà été visité ou non. On proposer d'utiliser un tableau de booléens  visite (si le sommet i n'a pas été encore visité alors l'élément d'indice i de visite vaut false) et on rappelle que deux options sont envisageables :

    • utiliser la rĂ©cursivitĂ© de façon Ă  ce que les sommets en attente de traitement soient stockĂ©s dans la pile des appels rĂ©cursifs
    • utiliser explicitement une pile (module Stack de OCaml)

    Ecrire les implémentations du parcours en profondeur en OCaml avec ces deux méthodes en vous aidant éventuellement de ce qui a été fait en cours.

  3. Même question en C, il faudra dans le cas de l'utilisation explicite d'une pile en écrire une implémentation par liste chainée.

â–Ş Exercice 4 : Applications du parcours en profondeur

  1. Tri topologique

    1. Modifier le parcours en profondeur de l'exercice précédent afin de conserver l'ordre de visite des sommets. En déduire une fonction tri_topologique: graphe -> int list qui renvoie un tri topologique d'un graphe sans circuit donné en argument.

    2. Modifier la fonction précédente afin qu'elle lève une exception si on rencontre un circuit

    3. Tester sur le graphe suivant (sans circuit)

    graph LR
S0(("0"))
S1(("1"))
S2(("2"))
S3(("3"))
S4(("4"))
S5(("5"))
S6(("6"))
S7(("7"))
S8(("8"))
S7 --> S4
S4 --> S8
S5 --> S8
S5 --> S1
S8 --> S0
S6 --> S3
S1 --> S0
S4 --> S3
    1. Ajouter un arc de façon à former un circuit dans le graphe précédent et tester la détection de cycle

  2. Calcul des composantes connexes

    1. Utiliser l'algorithme de parcours en profondeur afin d'implémenter une fonction composantes_connexes: graphe -> int list list qui renvoie les composantes connexes sous forme de listes de sommets.

    2. Tester sur le graphe non orienté suivant :

    graph LR
S0(("0"))
S1(("1"))
S2(("2"))
S3(("3"))
S4(("4"))
S5(("5"))
S6(("6"))
S7(("7"))
S8(("8"))
S9(("9"))
S7 --- S4
S4 --- S8
S8 --- S7
S5 --- S1
S2 --- S3
S1 --- S2
S1 --- S3
S0 --- S6

â–Ş Exercice 5 : RĂ©solution de labyrinthe par un parcours en largeur

On considère un labyrinthe de dimensions données et fourni sous la forme d'un fichier ascii où les caractères . indiquent les cases où il est possible de se déplacer et les caractères @ indiquent un mur infranchissable. On donne les coordonnées d'une case en fournissant d'abord le numéro de ligne puis le numéro de colonne et la case située en haut et à gauche est de coordonnées (0,0). Dans l'exemple suivant, les dimensions sont de 10 sur 10 et les coordonnées de la case contenant un D sont (6,4) et celles de la case contenant un A sont (1,6):

@@@@@@@@@@
@....@A@.@
@.@@.@...@
@.@@.@@.@@
@.@...@..@
@......@.@
@@@@D....@
@..@...@.@
@.....@@.@
@@@@@@@@@@

Les seuls déplacements autorisés dans le labyrinthe sont droite, haut, gauche et bas. Le but de l'exercice est de déterminer, le nombre minimal de déplacements entre deux cases données (lorsqu'un chemin entre ces deux cases existe). Dans l'exemple précédent, le nombre minimal de déplacements pour aller de D vers A est 11 et on a fléché ci-dessus un chemin possible : 

@@@@@@@@@@
@....@A@.@
@.@@.@^<.@
@.@@.@@^@@
@.@...@^<@
@......@^@
@@@@x>>>^@
@..@...@.@
@.....@@.@
@@@@@@@@@@

Pour cela, l'idée est d'effectuer le parcours en largeur d'un graphe :

  • chaque sommet du graphe est un Ă©tat du labyrinthe indiquant les cases non encore visitĂ©es
  • un arc va d'un sommet \(s\) vers un sommet \(t\) lorsqu'il est possible Ă  partir de \(s\) d'atteindre une case non encore parcourue qui sera alors marquĂ©e comme tel dans \(t\).

Par exemple, sur le labyrinthe ci-dessus, en supposant qu'on se trouve initialement sur la case marquée d'un D, trois nouveaux états qu'on a indiqué en les marquants d'un 1 sont accessibles (en un déplacement):

@@@@@@@@@@
@....@A@.@
@.@@.@...@
@.@@.@@.@@
@.@...@..@
@...1..@.@
@@@@D1...@
@..@1..@.@
@.....@@.@
@@@@@@@@@@

A partir de ces nouveaux états, on peut accéder en deux déplacements aux cases indiquées ci-dessous avec un 2 : 

@@@@@@@@@@
@....@A@.@
@.@@.@...@
@.@@.@@.@@
@.@.2.@..@
@..212.@.@
@@@@D12..@
@..@12.@.@
@...2.@@.@
@@@@@@@@@@

On donnera les fichiers représentant un labyrinthe sous le format suivant :

  • La première ligne donne le nombre de lignes
  • La seconde ligne le nombre de colonnes
  • La troisième ligne contient les coordonnĂ©es du points de dĂ©part (deux entiers : la ligne et la colonne)
  • La quatrième ligne contient les coordonnĂ©es du point d'arrivĂ©e

Ainsi, le problème de trouver le plus court chemin depuis le point D jusqu'au point A donné dans le labyrinthe en exemple sera représenté par le fichier ascii suivant : 

10
10
6 4
1 6
@@@@@@@@@@
@....@.@.@
@.@@.@...@
@.@@.@@.@@
@.@...@..@
@......@.@
@@@@.....@
@..@...@.@
@.....@@.@
@@@@@@@@@@

  1. On décide dans la suite de représenter la carte de taille heightxwidth par un tableau linéarisée c'est à dire que le point de coordonnées l,c dans la carte sera à l'indice l*width+c dans un tableau à une dimension. Ecrire les fonction suivantes :

    • int get_index(int l, int c, int width) qui renvoie l'index dans le tableau linĂ©arisĂ© du point de coordonnĂ©es l,c
    • void get_lc(int index, int* l, int *c, int width) qui modifie *l et *c afin qu'ils contiennent la ligne et la colonne correspondantes Ă  l'index index dans le tableau linĂ©arisĂ©.
    Correction 
    int get_index(int l, int c, int width)
{
    return l * width + c;
}

void get_lc(int index, int *l, int *c, int width)
{
    *l = index / width;
    *c = index % width;
}

  2. Ecrire une fonction de signature int *read_map(char filename[], int* height, int* width, int* start, int* arrival) qui prend en entrée un nom de fichier filename, modifie les entiers height, width, start et arrival afin qu'ils contiennent le nombre de lignes du labyrinthe, le nombre de colonne, l'index dans le tableau linéarisé des points de départ et d'arrivée. Cette fonction renvoie un pointeur vers une matrice linéarisée d'entiers, dans lequel on représentant les cases vides par 0 et les murs par 1. Ces deux constantes peuvent êtres définies (par exemple avec une directive de précompiliation en début de programme de façon explicite : #define EMPTY 0 et #define WALL 1)

    Correction 
    int *read_map(char filename[], int *height, int *width, int *start, int *arrival)
{
    FILE *inputstream = fopen(filename, "r");
    int l, c;
    if (!inputstream)
    {
        printf("Fichier non trouvé !\n");
        exit(-1);
    }
    // Les dimensions sont sur les deux premieres lignes
    fscanf(inputstream, "%d", height);
    fscanf(inputstream, "%d", width);
    // Puis on lit les coordonnées du point de départ et d'arrivée
    fscanf(inputstream, "%d", &l);
    fscanf(inputstream, "%d", &c);
    *start = get_index(l, c, *width);
    fscanf(inputstream, "%d", &l);
    fscanf(inputstream, "%d", &c);
    *arrival = get_index(l, c, *width);
    int *map = malloc(sizeof(int) * *height * *width);
    char cc;
    fgetc(inputstream);
    for (int l = 0; l < *height; l++)
    {
        for (int c = 0; c < *width; c++)
        {
            cc = fgetc(inputstream);
            if (cc == '@')
            {
                map[get_index(l,c,*width)] = WALL;
            }
            else if (cc == '.')
            {
                map[get_index(l,c,*width)] = EMPTY;
            }
            else
            {
                printf("Caractère inconnu dans le fichier \n");
            }
        }
        fgetc(inputstream);
    }
    fclose(inputstream);
    return map;
}

  3. On doit maintenant écrire la structure de données de file dans laquelle seront enfiler les états successifs lors du parcours en largeur du graphe. Pour cela on propose le type structuré suivant :

        struct node_s
    {
        int num; //l'index de la case dans le tableau linéarisé
        int dist;//le nombre de déplacements pour l'atteindre
        struct node_s *next;//pointeur vers le noeud suivant
    };
    typedef struct node_s node;
    typedef node *lnode;
    struct queue_s
    {
        lnode start;
        lnode end;
    };
    typedef struct queue_s queue;

    C'est à dire qu'on représente une file d'attente par une liste chainée avec un pointeur sur le premier élément et un pointeur sur le dernier élément de la liste. Dans cette structure, il est bien important de comprendre que l'ajout d'un élément se fait après le pointeur de queue et que le retrait d'un élément se fait depuis le pointeur de tête.

    flowchart LR
subgraph "Pointeurs d'accès"
    direction RL
    T[Start]
    Q[End]
end
subgraph "Liste chainée"
    direction RL 
    A(("A")) 
    B(("B"))
    C(("C"))
    D(("D"))
    E(("E"))
    N["NULL"]
    A -->  B --> C--> D --> E --> N
end
T --> A
Q --> E

    Dans l'exemple ci-dessus, l'élément défilé serait A et on enfilerais un nouvel élément après E.

    Ecrire les fonctions suivantes qui permettront de manipuler cette structure de données :

    1. queue create() qui renvoie une file vide (les deux pointeurs start et end sont NULL).
    2. bool is_empty(queue q) qui renvoie true si la file est vide.
    3. insert(queue *q, int nodenum, int nodedist) qui enfile un nouveau nom dont on donne l'indice nodenum et la distance par rapport au point de départ nodedist
    4. node extract(queue *q) qui défile un noeud.
    5. void destroy(queue *q) qui défile tous les éléments et libère l'espace mémoire alloué.
    Correction 
    queue create()
{
    queue q = {.start = NULL, .end = NULL};
    return q;
}

bool is_empty(queue q)
{
    return q.start == NULL;
}

void insert(queue *q, int nodenum, int nodedist)
{
    // Ajout d'un noeud APRES le pointeur de fin
    node *new = malloc(sizeof(node));
    if (!new)
    {
        printf("Impossible d'allouer un espace mémoire suffisant \n");
        exit(-2);
    }
    new->num = nodenum;
    new->dist = nodedist;
    new->next = NULL;
    if (q->end)
    {
        q->end->next = new;
    }
    else
    {
        q->start = new;
    }
    q->end = new;
}

node extract(queue *q)
{
    // Retrait du noeud pointé par le pointeur de tête
    assert(q->start != NULL);
    node n;
    node *temp = q->start;
    n.num = q->start->num;
    n.dist = q->start->dist;
    q->start = q->start->next;
    if (!q->start)
    {
        q->end = NULL;
    }
    free(temp);
    return n;
}

void destroy(queue *q)
{
    node *temp;
    while (q->start)
    {
        temp = q->start;
        q->start = q->start->next;
        free(temp);
    }
}

  4. Maintenant que nous disposons de la structure de données adéquate il nous reste à appliquer l'algorithme de parcours en largeur afin de déterminer la longueur minimale d'un chemin liant le point de départ à celui d'arriver. On commencer par initialiser une file avec pour seul élément le point de départ (représenté par son index dans le tableau linéarisé) associée à une distance de 0. Puis tant que cette file vide n'est pas vide et que l'arrivée n'a pas été atteinte, on défile un noeud et on enfile les cases adjacentes non encore parcourues (qu'on pourra marquer dans la carte à l'aide d'une constante VISITED). Ecrire une fonction int solve(char* fname) qui prend en argument un nom de fichier contenant un labyrinthe (au format décrit en introduction) et renvoie la longueur d'un plus court chemin ou -1 si aucun chemin n'existe.

    Correction 
    queue create()
{
    queue q = {.start = NULL, .end = NULL};
    return q;
}

bool is_empty(queue q)
{
    return q.start == NULL;
}

void insert(queue *q, int nodenum, int nodedist)
{
    // Ajout d'un noeud APRES le pointeur de fin
    node *new = malloc(sizeof(node));
    if (!new)
    {
        printf("Impossible d'allouer un espace mémoire suffisant \n");
        exit(-2);
    }
    new->num = nodenum;
    new->dist = nodedist;
    new->next = NULL;
    if (q->end)
    {
        q->end->next = new;
    }
    else
    {
        q->start = new;
    }
    q->end = new;
}

node extract(queue *q)
{
    // Retrait du noeud pointé par le pointeur de tête
    assert(q->start != NULL);
    node n;
    node *temp = q->start;
    n.num = q->start->num;
    n.dist = q->start->dist;
    q->start = q->start->next;
    if (!q->start)
    {
        q->end = NULL;
    }
    free(temp);
    return n;
}

void destroy(queue *q)
{
    node *temp;
    while (q->start)
    {
        temp = q->start;
        q->start = q->start->next;
        free(temp);
    }
}

  5. On peut à présent tester notre programme en lui donnant en entrée un fichier contenant un problème de labyrinthe. Par exemple pour le labyrinthe donné en exemple : 

    10
10
6 4
1 6
@@@@@@@@@@
@....@.@.@
@.@@.@...@
@.@@.@@.@@
@.@...@..@
@......@.@
@@@@.....@
@..@...@.@
@.....@@.@
@@@@@@@@@@
    Le programme doit renvoyer 11. On propose ci-dessous un autre jeu de données avec un labyrinthe bien plus grands, il est extrait du site 2D Pathfinding Benchmark. Et vous pouvez le télécharger ci-dessous :
    Labyrinthe Et vous pouvez vérifier la réponse du programme :

  6. Pour le moment on dispose de la longueur minimale d'un chemin, mais pas du chemin lui-même. Afin de reconstruire le chemin parcouru, on propose d'enregistrer dans un tableau parent la case d'origine d'une case nouvellement atteinte. Ainsi à l'origine le point de départ n'a pas de parent, puis chaque case atteinte en un déplacement a pour parent la case de départ. Une fois la case d'arrivée atteinte, on remonte de proche en proche dans ce tableau afin de reconstruire le chemin parcouru. Ecrire une fonction de signature int* solve_path(char* fname) qui renvoie un pointeur vers le tableau des cases parcourues si un chemin est trouvé et un pointeur null sinon. On pourra retrouver la taille de ce tableau car un chemin se termine forcément sur la case d'arrivée.

Humour d'informaticien

goto