TP — Graphes 101

Travaux pratiques · MP2I · 2021-2022 · OCaml

Cours : Implémentation des graphes

Dans ce TP, on va voir les bases de la manipulation des graphes. L'objectif est de réaliser des fonctions qu'on pourra réutiliser dans d'autres TPs. Vous pouvez faire le TP avec des fichiers .ml comme le TP18 ou directement sur Jupyter pour bénéficier des jeux de tests.

La partie bonus finale sera réalisable avec graphics, donc il faudra faire une transition à ce moment-là.

Pour simplifier, on ne va considérer dans un premier temps que des graphes \(G = ([|0; n-1|], A)\).

Matrice d'adjacence

Ainsi, on pourra considérer la matrice d'adjacence mat : bool array array telle que mat.(i).(j) soit égal à true si et seulement si \((i, j) \in A\).

On utilise make_matrix puis on remplit les arêtes une à une :

type mat_adj = bool array array

Question 1

let mat_vide n : mat_adj =
    (* Renvoie la matrice d'adjacence du graphe vide sans arêtes *)

Corrigé

let mat_vide n : mat_adj =
    Array.make_matrix n n false

Question 2

let mat_ajout_arete (m:mat_adj) x y : unit =
    (* Ajoute une arete x -> y *)

Corrigé

let mat_ajout_arete (m:mat_adj) x y : unit =
    m.(x).(y) <- true

Comme ce n'est pas forcément très pratique de définir des graphes ainsi, on va commencer par réaliser une fonction init_matrix qui permettra d'appliquer une fonction int -> int -> 'a pour définir une matrice à la manière de Array.init.

Question 3

let init_matrix n p f =

Corrigé

let init_matrix n p f =
    Array.init n (fun i -> Array.init p (f i))

Question 4

La fonction suivante renvoie la matrice d'adjacence pour \(A = \{(0, 1), (1, 2), \dots, (n-2, n-1), (n-1, 0)\}\).

let mat_cycle n =

Corrigé

let mat_cycle n =
    init_matrix n n (fun i j -> (i+1) mod n = j)

Question 6

Pour les fonctions suivantes, on demande d'extraire les voisins entrants et sortants sous forme d'une liste. On pourra utiliser une fonction auxiliaire récursive ou une référence sur une liste pour simuler une pile.

let mat_voisins_entrants m x =
let mat_voisins_sortants m x =
let mat_degre_entrant m x =
let mat_degre_sortant m x =

Corrigé

let mat_voisins_entrants m x =
    let v = ref [] in
    let n = Array.length m in
    for y = 0 to n-1 do
        if m.(y).(x) then v := y :: !v
    done;
    !v

let mat_voisins_sortants m x =
    let v = ref [] in
    let n = Array.length m in
    for y = 0 to n-1 do
        if m.(x).(y) then v := y :: !v
    done;
    !v

let mat_degre_entrant m x =
    List.length (mat_voisins_entrants m x)

let mat_degre_sortant m x =
    List.length (mat_voisins_sortants m x)

Graphes par matrice d'adjacence

Pour représenter un graphe, on va utiliser un tableau 'a array pour les sommets et utiliser l'indice d'un élément pour accéder à la matrice d'adjacence.

Ainsi le graphe A -> B <-> C sera représenté par le tableau [|"A";"B";"C"|] et la matrice \(\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}\). Notons qu'on aurait pu permuter les éléments de \(S\) et la matrice associée sera également permutée : [|"C";"A";"B"|] et \(\begin{pmatrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}\).

On va devoir ainsi gérer la cohérence entre le tableau des sommets et la matrice d'adjacence le long des transformations.

On en déduit le type suivant. On va supposer que chaque sommet est identifié uniquement par sa valeur. Ainsi, dans l'exemple précédent "A" a un unique indice pour l'identifier. On remarque que le fait que les champs ne soient pas mutables signifie qu'il faudra créer un nouveau graphe pour changer l'ensemble de sommets.

type 'a graphem = { som : 'a array; mat : bool array array }

Question 7

let graphem_vide () : 'a graphem =
    (* renvoie un graphe sans sommet ni arêtes *)

let graphem_isoles (s:'a array) : 'a graphem =
    (* Renvoie un graphe sans arêtes de sommets s *)

let graphem_dim (g:'a graphem) : int * int =
    (* Renvoie le couple (n,p) où n est le nombre de sommets
    et p le nombre d'arêtes *)

Corrigé

let graphem_vide () : 'a graphem =
    { som = [||]; mat = [||] }

let graphem_isoles (s:'a array) : 'a graphem =
    { som = s; mat = mat_vide (Array.length s) }

let graphem_dim (g:'a graphem) : int * int =
    let n = Array.length g.som in
    let p = ref 0 in
    for i = 0 to n-1 do
        for j = 0 to n-1 do
            if g.mat.(i).(j) then incr p
        done
    done;
    n, !p

assert (graphem_dim g_ex = (5, 9) );
"OK"

Question 8

La représentation n'étant pas très lisible, on aimerait pouvoir afficher les graphes sous la forme suivante :

Sommets: A B C D E
Aretes: A -> B, A -> C, A -> D, B -> C, C -> A, C -> E, D -> E, E -> C, E -> D,

On rappelle qu'avec Jupyter il faut un printf finissant par \n%! pour s'assurer de l'affichage.

let graphem_print g =
    (* Affiche un char graphem sous le format précédent *)

Corrigé

let graphem_print g =
    let n, _ = graphem_dim g in
    Printf.printf "Sommets: ";
    for i = 0 to n-1 do
        Printf.printf "%c " g.som.(i)
    done;
    Printf.printf "\nAretes: ";
    for i = 0 to n-1 do
        for j = 0 to n-1 do
            if g.mat.(i).(j)
            then Printf.printf "%c -> %c, " g.som.(i) g.som.(j)
        done
    done;
    Printf.printf "\n%!"

graphem_print g_ex

Sommets: A B C D E
Aretes: A -> B, A -> C, A -> D, B -> C, C -> A, C -> E, D -> E, E -> C, E -> D,

À partir de maintenant, on va travailler sur les sommets puis en déduire leurs indices, on supposera que toutes les fonctions sont appelées avec des sommets valides.

Question 9

exception Trouve of int

let graphem_indice (g:'a graphem) (x:'a) : int =
    (* Renvoie l'indice de x dans le graphe *)

Corrigé

exception Trouve of int

let graphem_indice (g:'a graphem) (x:'a) : int =
    try
        for i = 0 to Array.length g.som - 1 do
            if g.som.(i) = x
            then raise (Trouve i)
        done;
        raise Not_found
    with Trouve i -> i

assert (graphem_indice g_ex 'C' = 2);
"OK"

Question 10

let graphem_test_arete (g:'a graphem) (x:'a) (y:'a) : bool =
    (* Test si le graphe contient une arete x -> y *)

let graphem_ajoute_arete (g:'a graphem) (x:'a) (y:'a) : unit =
    (* Ajoute une arete x -> y *)

let graphem_suppr_arete (g:'a graphem) (x:'a) (y:'a) : unit =
    (* Supprime une arete x -> y *)

Corrigé

let graphem_test_arete (g:'a graphem) (x:'a) (y:'a) : bool =
    let i = graphem_indice g x in
    let j = graphem_indice g y in
    g.mat.(i).(j)

let graphem_ajoute_arete (g:'a graphem) (x:'a) (y:'a) : unit =
    let i = graphem_indice g x in
    let j = graphem_indice g y in
    g.mat.(i).(j) <- true

let graphem_suppr_arete (g:'a graphem) (x:'a) (y:'a) : unit =
    let i = graphem_indice g x in
    let j = graphem_indice g y in
    g.mat.(i).(j) <- false

Pour les fonctions suivantes, on pourra utiliser toutes les fonctions disponibles dans le module Array : https://ocaml.org/api/Array.html. Notamment Array.append.

Question 11

let graphem_ajoute_sommet (g:'a graphem) (x:'a) : 'a graphem =
    (* Ajoute un nouveau sommet au graphe a la fin du tableau,
       il faudra changer la matrice *)

Corrigé

let graphem_ajoute_sommet (g:'a graphem) (x:'a) : 'a graphem =
    let n, _ = graphem_dim g in
    let som = Array.append g.som [|x|] in
    let mat = Array.append g.mat [| Array.make (n+1) false |] in
    for i = 0 to n-1 do
        mat.(i) <- Array.append mat.(i) [|false|]
    done;
    { som = som; mat = mat }

let g = graphem_ajoute_sommet g_ex 'F' in
assert (g = {som = [|'A'; 'B'; 'C'; 'D'; 'E'; 'F'|];
 mat =
  [|[|false; true; true; true; false; false|];
     [|false; false; true; false; false; false|];
     [|true; false; false; false; true; false|];
     [|false; false; false; false; true; false|];
     [|false; false; true; true; false; false|];
     [|false; false; false; false; false; false|]|]} );
"OK"

Listes d'adjacence

On va maintenant représenter les arêtes par un ladj : int list array où ladj.(i) donne la liste des indices des voisins sortants du sommet d'indice \(i\).

On va reprendre les fonctions précédentes.

type liste_adj = int list array

Question 14

let ladj_vide n =
let ladj_ajout_arete l x y =
let ladj_cycle n =
let ladj_complet n =

Corrigé

let ladj_vide n =
    Array.make n []

let ladj_ajout_arete l x y =
    l.(x) <- y :: l.(x)

let ladj_cycle n =
    Array.init n (fun i -> [(i+1) mod n])

let ladj_complet n =
    let rec aux i j =
        if i < 0
        then []
        else if i <> j then i :: aux (i-1) j else aux (i-1) j
    in
    Array.init n (fun i -> aux (n-1) i)

let ladj_voisins_sortants l x = l.(x)

let l = [| [1;2;3]; [2]; [0;4]; [4]; [2;3] |] in
let l2 = ladj_voisins_entrants l 4 in
assert (l2 = [2;3] || l2 = [3;2]);
"OK"

let ladj_degre_sortant l x = List.length l.(x)

Question 16

let ladj_degre_entrant l x =

Corrigé

let ladj_degre_entrant l x =
    List.length (ladj_voisins_entrants l x)

Question 17

let mat_to_ladj m =
    (* Convertit une matrice d'adjacence en liste d'adjacence *)

Corrigé

let mat_to_ladj m =
    let n = Array.length m in
    let l = ladj_vide n in
    for i = 0 to n-1 do
        for j = 0 to n-1 do
            if m.(i).(j)
            then l.(i) <- j :: l.(i)
        done
    done;
    l

Question 18

let ladj_to_mat l =
    (* Convertit une liste d'adjacence en matrice d'adjacence *)

Corrigé

let ladj_to_mat l =
    let n = Array.length l in
    let m = mat_vide n in
    for i = 0 to n-1 do
        List.iter (fun j -> m.(i).(j) <- true) l.(i)
    done;
    m

Graphe par liste d'adjacence

type 'a graphel = { soml : 'a array; ladj : int list array }

On va maintenant reprendre toutes les fonctions précédentes. Attention sans faire de conversions brutales depuis et vers les matrices d'adjacence.

Question 19

let graphel_vide () =
let graphel_isoles s =
let graphel_dim g =

Corrigé

let graphel_vide () =
    { soml = [||]; ladj = [||]}

let graphel_isoles s =
    { soml = s; ladj = ladj_vide (Array.length s) }

let graphel_dim g =
    let n = Array.length g.soml in
    let p = Array.fold_left (+) 0 (Array.map List.length g.ladj) in
    n, p

assert (graphel_dim g_ex_l = (5, 9) );
"OK"

graphel_print g_ex_l

Sommets: A B C D E
Aretes: A -> B, A -> C, A -> D, B -> C, C -> A, C -> E, D -> E, E -> C, E -> D,

Question 21

exception Trouve of int

let graphel_indice (g:'a graphel) (x:'a) : int =
    (* Renvoie l'indice de x dans le graphe *)

Corrigé

exception Trouve of int

let graphel_indice (g:'a graphel) (x:'a) : int =
    try
        for i = 0 to Array.length g.soml - 1 do
            if g.soml.(i) = x
            then raise (Trouve i)
        done;
        raise Not_found
    with Trouve i -> i

assert (graphel_indice g_ex_l 'C' = 2);
"OK"

Question 23

let graphel_ajoute_sommet (g:'a graphel) (x:'a) : 'a graphel =
    (* Ajoute un nouveau sommet au graphe a la fin du tableau *)

Corrigé

let graphel_ajoute_sommet (g:'a graphel) (x:'a) : 'a graphel =
    let soml = Array.append g.soml [|x|] in
    let ladj = Array.append g.ladj [| [] |] in
    { soml = soml; ladj = ladj }

Question 24

let rec suppr_adj l i =
    (* supprime le sommet i de la liste d'adjacence en décalant
    à j-1 les indices j > i *)

Corrigé

let rec suppr_adj l i =
    match l with
    | [] -> []
    | t::q when t = i -> suppr_adj q i
    | t::q when t < i -> t :: suppr_adj q i
    | t::q -> (t-1) :: suppr_adj q i

assert (suppr_adj [1;2;3;4;5] 3 = [1;2;3;4]);
assert (suppr_adj [1;3;5] 3 = [1;4]);
"OK"

graphel_suppr_sommet g_ex_l 'C'
(* doit valoir :
{soml = [|'A'; 'B'; 'D'; 'E'|]; ladj = [|[1; 2]; []; [3]; [2]|]}
*)