(* --- type des piles --- *)

(* opérations de base *)

type 'a pile = 
    PileNouv 
  | Empiler of 'a * 'a pile
;;

let sommet(p) = match p with
    PileNouv -> failwith "bottom"
  | Empiler(x,p) -> x
;;

let depiler(p) = match p with
    PileNouv -> failwith "bottom"
  | Empiler(x,p) -> p
;;

let estPileNouv(p) = match p with
    PileNouv -> true
  | Empiler(x,p) -> false
;;

 
(*
   recherche d'un chemin du sommet x au sommet y
   (en utilisant une pile pour mémoriser le chemin) 
   chaque élément de la pile est un couple (x,l)
   d'un sommet x et d'une liste de successeurs de x
*)

let rec chemin_aux (g,(x,y),p) =
(* fonction auxilaire utilisant une pile *)
  if estPileNouv(p) 
  then failwith "bottom"
  else 
    let (x,s) = sommet(p) in
      match s with
        Nil
        -> (* on revient en arrière *)
           chemin_aux (g,(x,y),depiler(p))
      | Cons(z,zs)
        -> if z = y
           then p (* chemin trouvé *)
           else chemin_aux (g,(z,y),Empiler((z,succ (g,z)),p))
;;

let chemin (g,(x,y)) =
  (chemin_aux (g,(x,y),Empiler((x, succ (g,x)),PileNouv)))
;;


(* exemple *)

chemin (ex,(1,5));;