Voisins communs

let voisins_communs m i j =
  let n = Array.length m in
  let c = ref 0 in
  for k = 0 to n - 1 do
    if m.(i).(k) && m.(j).(k) then c := !c + 1
  done;
  !c

On compte les sommets k adjacents simultanément à i et à j. La matrice rend ce test direct ($\Theta (1)$ par sommet), d'où un coût $\Theta (n)$. (En listes, il faudrait croiser deux listes, plus laborieux.)