Graphes

type Arete = {a : int; b : int };;
type Graphe = {n : int; A : Arete list};;

let Gexl = {n = 5; A = [{a = 0; b = 4}; {a = 4; b = 3}; {a = 0; b = 3}; {a = 1; b = 3}; {a = 0; b = 3}; { a = 3; b = 0}]};;

let rec afficherListe liste = match liste with
    | [] -> ();
    | t::q -> print_int t; afficherListe q;;

(* Complexité : |O(liste)|*)
let rec insere liste valeur = match liste with
    | [] -> [valeur];
    | t::q -> if t = valeur then liste else (
                     if t < valeur then t::(insere q valeur)
                     else valeur :: (t::q)
                     );;

let maListe = [1;2;3;5;6];;
let maListe = insere maListe 4;;
afficherListe maListe;;

let voisins graphe sommet =
    let rec sommetsAux liste element = match liste with
        | [] -> []
        | t::q -> if t.a == element then (insere (sommetsAux q element) t.b)
                     else (
                        if t.b == element then (insere (sommetsAux q element) t.a)
                        else (sommetsAux q element)
                        )
        in sommetsAux graphe.A sommet;;

afficherListe (voisins Gexl 3);;

let rec trouverLePremierTrouDansLaListe liste = match liste with
    | [] -> 0;
    | [t] -> t + 1;
    | t::q -> if t < hd(q) - 1 then t + 1
                 else trouverLePremierTrouDansLaListe q;;

let rec getColor liste vec = match liste with
    | []   -> [];
    (*| t::q -> vec.(t) :: getColor q vec;;*)
    | t::q -> insere (getColor q vec) (vec.(t));;

let coloration graphe =
    let couleurs = make_vect graphe.n (0) in
    for i = 0 to graphe.n - 1 do
        let listeDeCouleurs = getColor (voisins graphe i) couleurs in
        couleurs.(i) <- trouverLePremierTrouDansLaListe listeDeCouleurs;
    done;
    couleurs;;

let test = coloration Gexl;;

let coloration graphe = let rec trouverLePremierTrouDansLaListe liste = match liste with | [] -> 0; | [t] -> t + 1; | t::q -> if t < hd(q) - 1 then t + 1 else trouverLePremierTrouDansLaListe q in let rec getColor liste vec = match liste with | []   -> []; | t::q -> vec.(t) :: (getColor q vec); in let couleurs = make_vect graphe.n (0) in for i = 0 to graphe.n - 1 do let listeDeCouleurs = getColor (voisins graphe i) couleurs in couleurs.(i) <- trouverLePremierTrouDansLaListe listeDeCouleurs; done; couleurs;;