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