let graphe == int list vect;;

let rec list_iter f l = match l with
 [] -> ()
 | t::q -> f t ; list_iter f q;;

type sommet = C | I | T;;

let parcours_profondeur graphe x =
   let etats = make_vect (vect_length graphe) false in
    let rec parcours x =
        if not etats.(x)
        then begin
            etats.(x) <- true;
            list_iter parcours graphe.(x)
        end
    in parcours x;;

let parcours_profondeur graphe f x0 =
    let etats = make_vect (vect_length graphe) I in
    etats.(x0) <- C;
    let a_visiter = stack__new () in
    stack__push x0 a_visiter;
    while stack__length a_visiter > 0 do
        let x = stack__pop a_visiter in
        let rec decouvre_voisins l =
            match l with
            [] -> ()
            | y::q -> if etats.(y) = I
                        then begin
                                etats.(y) <- C;
                                stack__push y a_visiter
                        end; decouvre_voisins q
        in f x; etats.(x) <- T; decouvre_voisins graphe.(x)
    done;;

let parcours_largeur graphe f x0 =
    let etats = make_vect (vect_length graphe) I in
    etats.(x0) <- C;
    let a_visiter = queue__new () in
    queue__add x0 a_visiter;
    while queue__length a_visiter > 0 do
        let x = queue__take a_visiter in
        let rec decouvre_voisins l =
            match l with
            [] -> ()
            | y::q -> if etats.(y) = I
                        then begin
                                etats.(y) <- C;
                                queue__add y a_visiter
                        end; decouvre_voisins q
        in f x; etats.(x) <- T; decouvre_voisins graphe.(x)
    done;;


let graphe_grille n =
    let n2= n * n in
    let g = make_vect n2 [] in
    let sommet (i,j) = i + n * j in
    for i = 0 to n-1 do
        for j = 0 to n-1 do
            let l = ref [] in
            if j > 0
            then l := sommet (i,j-1)::!l;
            if i > 0
            then l := sommet (i-1,j)::!l;
            if j < n-1
            then l := sommet (i,j+1)::!l;
            if i < n-1
            then l := sommet (i+1,j)::!l;
            g.(sommet (i,j)) <- !l
        done;
    done;
    g;;

#open "graphics";;
let _ =
    open_graph " 500x500";
    let g = graphe_grille 500 in
    parcours_aleatoire g
        (fun n -> plot (n mod 500) (n / 500))
        (250+500*250);;

let rec extrait l i = match l with
    [] -> failwith "list vide"
    | t::q -> if i = 0 then (t, q)
        else let x, l2 = extrait q (i-1) in
            x, t::l2;;

let parcours_aleatoire graphe f x0 =
    let etats = make_vect (vect_length graphe) I in
    etats.(x0) <- C;
    let a_visiter = ref [x0] in
    let retire () = let i = random__int (list_length !a_visiter) in
        let x, l = extrait !a_visiter i in
        a_visiter := l;
        x
    in
    while list_length !a_visiter > 0 do
        let x = retire () in
        let rec decouvre_voisins l =
            match l with
            [] -> ()
            | y::q -> if etats.(y) = I
                        then begin
                                etats.(y) <- C;
                                a_visiter := y :: !a_visiter
                        end; decouvre_voisins q
        in f x; etats.(x) <- T; decouvre_voisins graphe.(x)
    done;;