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

(* tarjan function *)

let tarjan g =
  let nb_of_vertex = nb_vertex g in
  let cfc = Array.create nb_of_vertex 0 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 ;
    ind.(s) <- !i ;
    ind_rec.(s) <- !i ;
    i := !i + 1 ;

  (* for all succeseurs *)
    iter_succ (fun x_ ->
      (
    let x=(V.label x_) in
    if nv.(x) then
      (
        descente x_;
        ind_rec.(s) <- (min ind_rec.(s) ind_rec.(x));
      )
    else
      if (exists p x) then
        ind_rec.(s) <- (min ind_rec.(s) ind.(x) );
      )) g s_;

    if ind_rec.(s) = ind.(s) then
      let z = ref (Stack.pop p) in
      while !z != s do
    cfc.(!z) <- !icfc;
    z := Stack.pop p;
      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);
      )
    )
    g;

  (* return cfc *)
  cfc
;;

let g = Rand.graph ~v:10 ~e:20 ();;
let _ = tarjan g;;