let rec isAdjacent graphe sommet1 sommet2 = match graphe with
  | [] -> false
  | (a,b)::l -> if (((a=sommet1) && (b=sommet2)) || ((b=sommet1) && (a=sommet2))) then true else isAdjacent l sommet1 sommet2

let rec listeSommets graphe =
  let rec listeSommets2 graphe liste = match graphe with
    | [] -> liste
    | (sommet1,sommet2)::l when not (List.mem sommet1 liste) -> if not(List.mem sommet2 liste) then listeSommets2 l (sommet1::sommet2::liste)
                                                                            else listeSommets2 l (sommet1::liste)
    | (sommet1,sommet2)::l when not (List.mem sommet2 liste) -> if not(List.mem sommet1 liste) then listeSommets2 l (sommet1::sommet2::liste)
                                                                            else listeSommets2 l (sommet2::liste)
    | (_,_)::l -> listeSommets2 l liste

  in listeSommets2 graphe [];;


let listeVoisins graphe sommet =
  let rec listeVoisins2 graphe liste = match graphe with
    | [] -> liste
    | (a,b)::l when (a=sommet) -> listeVoisins2 l (List.sort_uniq compare (b::liste))
    | (a,b)::l when (b=sommet) -> listeVoisins2 l (List.sort_uniq compare (a::liste))
    | (_,_)::l -> listeVoisins2 l liste

  in listeVoisins2 graphe [];;


let rec plusPetiteCoulPossible couleur = function
  | [] -> couleur
  | coul::l -> if (couleur=coul) then plusPetiteCoulPossible (coul+1) l else plusPetiteCoulPossible couleur l;;


let rec insere elem liste = match liste with
  |  [] -> elem::[]
  |  tete::l -> if elem < tete then elem :: liste else tete :: insere elem l;;



let rec siVoisinsDejaColores listeCouleurBis couleur sommet graphe = match listeCouleurBis with
                                  | [] -> plusPetiteCoulPossible 1 couleur
                                  | (element,coul)::l -> if (isAdjacent graphe element sommet) then
                                                           siVoisinsDejaColores l (insere coul couleur) sommet graphe
                                                         else siVoisinsDejaColores l couleur sommet graphe;;

(* fonction aux *)
let exists_left list value = List.exists (fun (x, _) -> x = value) list;;



(* val gloutonSansH: (’a * ’a) list -> (’a * int) list * int * ’a list, pas d’heuristique : l’ordre de coloriage des sommets est indifférent *)

let gloutonSansH graphe =
  let rec gloutonSansH2 listeSommets listeCouleur nbCouleur listeCroissante = match listeSommets with
    | [] -> (listeCouleur, nbCouleur, listeCroissante)
    | sommet::listeSommets -> if (exists_left listeCouleur sommet)
                              then gloutonSansH2 listeSommets listeCouleur nbCouleur listeCroissante
                              else let couleurLocale = (siVoisinsDejaColores listeCouleur [] sommet graphe) in
                                (gloutonSansH2 listeSommets ((sommet,couleurLocale)::listeCouleur) (if nbCouleur<=couleurLocale then couleurLocale else (nbCouleur)) (listeCroissante@[sommet]))

  in gloutonSansH2 (listeSommets graphe) [] 0 [];;



(* val gloutonDeg: (’a * ’a) list -> (’a * int) list * int * ’a, listheuristique statique : les sommets sont colorés par ordre de degré décroissant *)



(* renvoie le degre du sommet *)
let degre graphe sommet = List.length (listeVoisins graphe sommet);;

(* insert l'element au bon endroit dans la liste *)

let sommetEnCoupleAvecDegre graphe sommet = (sommet,(degre graphe sommet));;


let rec insereDegre graphe elem liste = match liste with
  |  [] -> elem::liste
  |  element::l -> if ((degre graphe elem) > degre graphe element) then elem::liste else element::(insereDegre graphe elem l);;



(* pour chaque sommet, on calcul sont degre et on l'insert dans la liste *)

let tri_croissantDegresSommets graphe =
  let rec tri_croissantDegresSommets2 listeSommets liste = match listeSommets with
    | [] -> liste
    | element::l -> tri_croissantDegresSommets2 l (insereDegre graphe element liste)
  in tri_croissantDegresSommets2 (listeSommets graphe) [];;


let gloutonDeg graphe =
  let rec gloutonDeg2 listeSommets listeCouleur nbCouleur listeCroissante = match listeSommets with
    | [] -> (listeCouleur, nbCouleur, listeCroissante)
    | sommet::listeSommets -> if (exists_left listeCouleur sommet)
                              then gloutonDeg2 listeSommets listeCouleur nbCouleur listeCroissante
                              else let couleurLocale = (siVoisinsDejaColores listeCouleur [] sommet graphe) in
                                (gloutonDeg2 listeSommets ((sommet,couleurLocale)::listeCouleur) (if nbCouleur<=couleurLocale then couleurLocale else (nbCouleur)) (listeCroissante@[sommet]))

  in gloutonDeg2 (tri_croissantDegresSommets graphe) [] 0 [];;