Finding maximal cliques (and independent sets) in an undirected graph. Bron–Kerbosch algorithm.

A small ocaml implementation of the Bron–Kerbosch algorithm to list all maximal cliques in an undirected graph. The description of the algorithm is on wikipedia. http://en.wikipedia.org/wiki/Bron–Kerbosch_algorithm . The example given is the same as in the wikipedia page.

open Graph

(*
The Bron–Kerbosch algorithm is an algorithm for finding maximal cliques in an undirected graph. 
http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

   BronKerbosch1(R,P,X):
       if P and X are both empty:
           report R as a maximal clique
       for each vertex v in P:
           BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
           P := P \ {v}
           X := X ⋃ {v}

   BronKerbosch2(R,P,X):
       if P and X are both empty:
           report R as a maximal clique
       choose a pivot vertex u in P ⋃ X
       for each vertex v in P \ N(u):
           BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
           P := P \ {v}
           X := X ⋃ {v}
*)

module V = struct
  type t = int
  let compare = compare
  let hash = Hashtbl.hash
  let equal = (=)
end

module UG = Persistent.Graph.Concrete(V)
module N = Oper.Neighbourhood(UG)
module S = N.Vertex_Set

let rec bronKerbosch1 gr r p x =
  let n v = N.set_from_vertex gr v in
  if (S.is_empty p) && (S.is_empty x) then [r]
  else
    let (_,_,mxc) =
      S.fold (fun v (p,x,acc) ->
        let r' = S.union r (S.singleton v) in
        let p' = S.inter p (n v) in
        let x' = S.inter x (n v) in
        (S.remove v p, S.add v x, (bronKerbosch1 gr r' p' x') @ acc)
      ) p (p,x,[])
    in mxc

let rec bronKerbosch2 gr r p x =
  let n v = N.set_from_vertex gr v in
  if (S.is_empty p) && (S.is_empty x) then [r]
  else
    let u = S.choose (S.union p x) in
    let (_,_,mxc) =
      S.fold (fun v (p,x,acc) ->
        let r' = S.union r (S.singleton v) in
        let p' = S.inter p (n v) in
        let x' = S.inter x (n v) in
        (S.remove v p, S.add v x,(bronKerbosch2 gr r' p' x') @ acc)
      ) (S.diff p (n u)) (p,x,[])
    in mxc

let main () =
  let vl = [1;2;3;4;5;6] in
  let gr = List.fold_left (fun g v -> UG.add_vertex g v) UG.empty vl in
  let el = [(6,4);(4,3);(4,5);(5,2);(3,2);(5,1);(2,1)] in
  let gr = List.fold_left (fun g (x,y) -> UG.add_edge g x y) gr el in
  let r = S.empty in
  let p = List.fold_right S.add vl S.empty in
  let x = S.empty in
  print_endline "bronKerbosch1";
  let mxl = bronKerbosch1 gr r p x in
  List.iter (fun s ->
    Printf.printf "%s\n" (String.concat "," (List.map string_of_int (S.elements s)))
  ) mxl
  ;
  print_endline "bronKerbosch2";
  let mxl = bronKerbosch2 gr r p x in
  List.iter (fun s ->
    Printf.printf "%s\n" (String.concat "," (List.map string_of_int (S.elements s)))
  ) mxl
;;

main () ;;

To test it :

$ocamlfind ocamlc -linkpkg -package ocamlgraph cliques.ml
$./a.out 
bronKerbosch1
4,6
4,5
3,4
2,3
1,2,5
bronKerbosch2
4,6
4,5
3,4
2,3
1,2,5

There is also a bit of code here. Even if it might be more efficient, it looks to me exceptionally complicated for such a simple algorithm…

Update - Maximal Independent Sets

Maybe is also worth mentioning the Maximal independent set problem that is the dual of the maximal clique problem. In other words, the list of all maximal independent set of a graph is nothing else that the list of maximal cliques of the complement of the input graph.

module O = Oper.Make(Builder.I(UG))

let max_independent_sets gr =
  let cgr = O.complement gr in
  let r = S.empty in
  let p = UG.fold_vertex S.add cgr S.empty in
  let x = S.empty in
  bronKerbosch2 cgr r p x