(* --- type des listes --- *)

(* opérations de base *)

type 'a liste = 
    Nil
  | Cons of 'a * 'a liste
;;

let tete(l) = match l with
    Nil -> failwith "bottom"
  | Cons(x,r) -> x
;;

let reste(l) = match l with
    Nil -> failwith "bottom"
  | Cons(x,r) -> r
;;

let estNil(l) = match l with
    Nil -> true
  | Cons(x,l) -> false
;;

(* autres opérations *)

let rec estElt(x,l) = (not (estNil(l))) && ((tete(l)=x) || (estElt(x,reste(l))))
;;   

let rec concat(l1,l2) = 
  if estNil(l1) then l2 else Cons(tete(l1),concat(reste(l1),l2))
;;


(* type des graphes *)

type 'a graph = 
    GraphNouv 
  | AdjSommet of 'a graph * 'a
  | AdjArc of 'a graph * 'a * 'a
;;


(* le graphe en exemple *)

let ex = 
  AdjArc(AdjArc(AdjArc(AdjArc(AdjArc(AdjArc(AdjArc(AdjArc(
    AdjSommet(AdjSommet(AdjSommet(AdjSommet(AdjSommet(
     GraphNouv,5),4),3),2),1),1,3),3,2),3,4),4,3),4,5),2,3),2,5),5,1)
;;


let rec sommets g = 
(* liste des sommets *)
match g with
    GraphNouv 
    -> Nil
  | AdjSommet (g,x)
    -> Cons(x,(sommets g))
  | AdjArc (g,x,y) 
    -> sommets g
;;
 
let rec succ (g,x) =
(*  liste des successeurs d'un sommet x *)
  match g with
     GraphNouv
     -> Nil
   | AdjSommet (g,y) 
     -> succ (g,x)
   | AdjArc (g,y,z) 
     -> if y=x 
        then Cons(z,(succ (g,x))) 
        else succ (g,x)
;; 

(* parcours d'une graphe en profondeur (en partant d'un sommet x)
   en utilisant 2 listes l1 et l2 :
   l1 = liste des sommets restant à visiter
   l2 = liste des sommets déjà visités
 *)

let rec parcours_prof_aux (g,x,l1,l2) = 
   if estNil(l1) 
   then l2
   else let y = tete(l1) in
     if estElt(y,l2) 
     then parcours_prof_aux (g,x,reste(l1),l2)
     else parcours_prof_aux (g,x,reste(l1),
          parcours_prof_aux (g,y,succ (g,y),concat(l2,Cons(y,Nil))))
;;

let parcours_prof (g,x) = 
    parcours_prof_aux (g,x,succ (g,x),Cons(x,Nil))
;;

(* exemple *)
parcours_prof (ex,1);;