open Graph.Pack.Digraph

(* function checks if element exists already in stack *)
let exists stack element =
  try
    Stack.iter (fun x-> if x = element then raise Exit;) stack;
    false;
  with
      Exit -> true
    | _ -> false

type composante =
    None
  | Some of int
;;

let string_of_composante x = match x with
    None -> "none"
  | Some(l) -> string_of_int l
;;


(* tarjan function *)
let tarjan g =
  let nb_of_vertex = nb_vertex g in
  let cfc = Array.create nb_of_vertex None in
  let nv = Array.create nb_of_vertex true in
  let ind = Array.create nb_of_vertex 0 in
  let ind_rec = Array.create nb_of_vertex 0 in
  let icfc = ref 1 in
  let i = ref 1 in
  let p = Stack.create () in

  let rec descente s_ =
    let s = V.label s_ in
    Stack.push s p ;    (* we store numbers only in stack *)
    nv.(s) <- false ;   (* NV[s] <- faux *)
    ind.(s) <- !i ;     (* ind[s] <- i *)
    ind_rec.(s) <- !i ; (* ind_rac[s] <- i *)
    i := !i + 1 ;       (* i <- i +1 *)

  (* for all succeseurs *)
    iter_succ
      (fun x_ ->
      let x=(V.label x_) in
      if nv.(x) then
    begin

      descente x_;
      ind_rec.(s) <- (min ind_rec.(s) ind_rec.(x));
    end
      else

      if (exists p x) then
    ind_rec.(s) <- (min ind_rec.(s) ind.(x) );
)


      (* the graph - 2nd argument *)
      g

      (* the vertex - 3rd argument *)
      s_;

    if ind_rec.(s) = ind.(s) then
      let z = ref (Stack.pop p) in
      cfc.(!z) <- Some(!icfc);
      while !z != s do
    z := Stack.pop p;
    cfc.(!z) <- Some(!icfc);
      done;
      icfc := !icfc+1
      ;
  in

  (* for all vertex if nv[x] then (descente x g) *)
  iter_vertex
    (fun x_ ->
      ( let x=(V.label x_) in
    if nv.(x) then
      descente x_;
      )
    )
    g;

  (* return cfc *)
  cfc
;;

let g = Rand.graph ~v:8 ~e:12 ();;
let k = tarjan g;;

let i = ref 0 in
while !i < 8 do
  print_endline ( (string_of_int !i)^ " " ^(string_of_composante k.(!i)));
  i:= !i+1;
done;
display_with_gv g;