let degree graph f =
let n = (G.nb_vertex graph) in
let m = ref 0 in
let h = Hashtbl.create 1031 in
let add h v =
(* we don't care about leaves *)
if v = 0 then () else
try Hashtbl.replace h v ((Hashtbl.find h v) + 1)
with Not_found -> Hashtbl.add h v 1
in
let total =
G.fold_vertex (fun v sum ->
let s = (List.length (f graph v)) in
if s > !m then m := s ;
add h s ;
sum + s
) graph 0
in
( (float_of_int total) /. (float_of_int n) , !m, h)