Représentations de graphes

Graphe utilisé pour les exemples ci-dessous :

Remarque : les fonctions add_edge et is_edge ci-dessous marchent aussi sur un graphe orienté.

Matrice d’adjacence

let g_mat = [|
    [|0; 0; 0; 0; 0; 0; 1|];
    [|0; 0; 1; 1; 1; 0; 0|];
    [|0; 1; 0; 0; 1; 1; 0|];
    [|0; 1; 0; 0; 1; 0; 0|];
    [|0; 0; 1; 1; 0; 0; 0|];
    [|0; 0; 1; 0; 1; 0; 0|];
    [|1; 0; 0; 0; 0; 0; 0|];
|]

val g_mat : int array array =
  [|[|0; 0; 0; 0; 0; 0; 1|]; [|0; 0; 1; 1; 1; 0; 0|];
    [|0; 1; 0; 0; 1; 1; 0|]; [|0; 1; 0; 0; 1; 0; 0|];
    [|0; 0; 1; 1; 0; 0; 0|]; [|0; 0; 1; 0; 1; 0; 0|];
    [|1; 0; 0; 0; 0; 0; 0|]|]

let add_edge g u v = (* ajoute l'arête (u, v) dans un graphe g représenté par matrice d'adjacence *)
    g.(u).(v) <- 1

val add_edge : int array array -> int -> int -> unit = <fun>

let is_edge g u v = (* teste si g contient l'arête (u, v) *)
    g.(u).(v) = 1

let () = assert (is_edge g_mat 4 2 && not (is_edge g_mat 2 0))

val is_edge : int array array -> int -> int -> bool = <fun>

Liste d’adjacence

let g_list = [|[6]; [2; 3; 4]; [1; 4; 5]; [1; 4]; [1; 2; 3; 5]; [4; 2]; [0]|]

val g_list : int list array =
  [|[6]; [2; 3; 4]; [1; 4; 5]; [1; 4]; [1; 2; 3; 5]; [4; 2]; [0]|]

let add_edge g u v = (* ajoute l'arête (u, v) dans un graphe g représenté par liste d'adjacence *)
    g.(u) <- v::g.(u)

val add_edge : 'a list array -> int -> 'a -> unit = <fun>

let is_edge g u v = (* teste si g contient l'arête (u, v) *)
    List.mem v g.(u);;

let () = assert (is_edge g_list 4 2 && not (is_edge g_list 2 0))

val is_edge : 'a list array -> int -> 'a -> bool = <fun>

Dictionnaire d’adjacence

Ici, on utilise un dictionnaire (par table de hachage) pour représenter le graphe. Chaque élément de la table de hachage sera un ensemble, obtenu avec le module Set (utilisant un arbre binaire de recherche équilibré).

module S = Set.Make(Int) (* structure d'ensemble d'entiers *)

module S :
  sig
    type elt = Int.t
    type t = Set.Make(Int).t
    val empty : t
    val is_empty : t -> bool
    val mem : elt -> t -> bool
    val add : elt -> t -> t
    val singleton : elt -> t
    val remove : elt -> t -> t
    val union : t -> t -> t
    val inter : t -> t -> t
    val disjoint : t -> t -> bool
    val diff : t -> t -> t
    val compare : t -> t -> int
    val equal : t -> t -> bool
    val subset : t -> t -> bool
    val iter : (elt -> unit) -> t -> unit
    val map : (elt -> elt) -> t -> t
    val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
    val for_all : (elt -> bool) -> t -> bool
    val exists : (elt -> bool) -> t -> bool
    val filter : (elt -> bool) -> t -> t
    val filter_map : (elt -> elt option) -> t -> t
    val partition : (elt -> bool) -> t -> t * t
    val cardinal : t -> int
    val elements : t -> elt list
    val min_elt : t -> elt
    val min_elt_opt : t -> elt option
    val max_elt : t -> elt
    val max_elt_opt : t -> elt option
    val choose : t -> elt
    val choose_opt : t -> elt option
    val split : elt -> t -> t * bool * t
    val find : elt -> t -> elt
    val find_opt : elt -> t -> elt option
    val find_first : (elt -> bool) -> t -> elt
    val find_first_opt : (elt -> bool) -> t -> elt option
    val find_last : (elt -> bool) -> t -> elt
    val find_last_opt : (elt -> bool) -> t -> elt option
    val of_list : elt list -> t
    val to_seq_from : elt -> t -> elt Seq.t
    val to_seq : t -> elt Seq.t
    val to_rev_seq : t -> elt Seq.t
    val add_seq : elt Seq.t -> t -> t
    val of_seq : elt Seq.t -> t
  end

let g_dict = Hashtbl.create 42;;
let () = for i = 0 to Array.length g_list - 1 do
    Hashtbl.add g_dict i (S.of_list g_list.(i))
done

val g_dict : ('_weak1, '_weak2) Hashtbl.t = <abstr>

Hashtbl.create 42 permet de créer une table de hachage avec un tableau de taille initiale 42. Lorsqu’on ajoute des associations à la table de hachage, la taille du tableau peut augmenter (pour éviter un trop grand nombre de collisions).

let is_edge g u v = (* teste si g contient l'arête (u, v) *)
    Hashtbl.find g u 
    |> S.mem v

let () = assert (is_edge g_dict 3 1 && not (is_edge g_dict 2 0))

val is_edge : ('a, S.t) Hashtbl.t -> 'a -> S.elt -> bool = <fun>

let add_edge g u v = (* ajoute l'arête (u, v) à g *)
    let s = Hashtbl.find g u in
    Hashtbl.add g u (S.add v s)

val add_edge : ('a, S.t) Hashtbl.t -> 'a -> S.elt -> unit = <fun>

Plus d’informations sur les tables de hachage.

Module

Type de module pour un graphe :

module type Graph = sig
    type vertex
    type t
    val empty : int -> t
    val n : t -> int
    val is_edge : vertex -> vertex -> t -> bool
    val add_edge : vertex -> vertex -> t -> unit
    val del_edge : vertex -> vertex -> t -> unit
end

module type Graph =
  sig
    type vertex
    type t
    val empty : int -> t
    val n : t -> int
    val is_edge : vertex -> vertex -> t -> bool
    val add_edge : vertex -> vertex -> t -> unit
    val del_edge : vertex -> vertex -> t -> unit
  end

module MatrixGraph : (Graph with type vertex := int) = struct
    type vertex = int
    type t = vertex array array
    let empty n = Array.make_matrix n n 0
    let n = Array.length
    let is_edge i j m = m.(i).(j) <> 0
    let add_edge i j m = m.(i).(j) <- 1
    let del_edge i j m = m.(i).(j) <- 0
end

module MatrixGraph :
  sig
    type t
    val empty : int -> t
    val n : t -> int
    val is_edge : int -> int -> t -> bool
    val add_edge : int -> int -> t -> unit
    val del_edge : int -> int -> t -> unit
  end

Exemple d’utilisation :

let g = MatrixGraph.empty 4;; (* graphe à 4 sommets *)
let () = MatrixGraph.add_edge 0 1 g;; (* ajout d'une arête entre les sommets *)
MatrixGraph.is_edge 0 3 g;; (* false *)
let () = MatrixGraph.add_edge 0 3 g;;
MatrixGraph.is_edge 0 3 g;; (* true *)

val g : MatrixGraph.t = <abstr>

- : bool = false

- : bool = true