let average_distance graph vertex =
let rec add_successors distance visited vertices =
let succs = ref [] in
let (n, sum) =
List.fold_left (fun (old_n, old_sum) v ->
if not (VS.mem v !visited) then
begin
visited := VS.add v !visited;
succs := (G.succ graph v)::!succs;
(old_n + 1, old_sum + distance)
end
else
(old_n, old_sum)
) (0, 0) vertices
in
let sf = List.flatten !succs in
if sf <> [] then
let (n', sum') = add_successors (distance + 1) visited sf in
(n + n', sum + sum')
else
(n, sum)
in
let visited = ref (VS.singleton vertex) in
let (n, sum) = add_successors 1 visited (G.succ graph vertex)
in
if sum = 0 then 0.0 else float_of_int sum /. float_of_int n