If you want to improve the speed of Bron-Kerbosch, you should look into using a "pivot" (see e.g. ftp://ftp-sop.inria.fr/geometrica/fcazals/papers/ncliques.pdf). Here's my (purely functional) implementation, using a simple functional set data structure IntSet:
let fold_maximal_cliques f g accu =
let rec extend clique cands nots accu =
(* returns the accumulator ACCU plus all maximal cliques C that
are supersets of CLIQUE, disjoint from NOTS, and subset of CANDS
union CLIQUE. *)
if IntSet.is_empty cands
then
if IntSet.is_empty nots
then f accu clique
else accu
else
let pivot, _ =
IntSet.fold
(fun (pivot, pivot_score) u ->
let score =
IntSet.intersection_size (Graph.neighbors g u) cands
in
if score > pivot_score
then (u, score)
else (pivot, pivot_score))
(IntSet.union cands nots)
(-1, -1) in
let _, _, accu =
IntSet.fold
(fun ((cands, nots, accu) as state) u ->
if Graph.is_connected g u pivot
then state
else
let cands = IntSet.delete cands u in
let clique' = IntSet.add clique u in
let u_neighbors = Graph.neighbors g u in
let cands' = IntSet.intersection cands u_neighbors in
let nots' = IntSet.intersection nots u_neighbors in
let accu = extend clique' cands' nots' accu in
let nots = IntSet.add nots u in
(cands, nots, accu))
cands
(cands, nots, accu)
in
accu
in
extend IntSet.empty (Graph.vertices g) IntSet.empty accu
;;
Pivot
If you want to improve the speed of Bron-Kerbosch, you should look into using a "pivot" (see e.g. ftp://ftp-sop.inria.fr/geometrica/fcazals/papers/ncliques.pdf). Here's my (purely functional) implementation, using a simple functional set data structure IntSet:
let rec extend clique cands nots accu =
(* returns the accumulator ACCU plus all maximal cliques C that
are supersets of CLIQUE, disjoint from NOTS, and subset of CANDS
union CLIQUE. *)
if IntSet.is_empty cands
then
if IntSet.is_empty nots
then f accu clique
else accu
else
let pivot, _ =
IntSet.fold
(fun (pivot, pivot_score) u ->
let score =
IntSet.intersection_size (Graph.neighbors g u) cands
in
if score > pivot_score
then (u, score)
else (pivot, pivot_score))
(IntSet.union cands nots)
(-1, -1) in
let _, _, accu =
IntSet.fold
(fun ((cands, nots, accu) as state) u ->
if Graph.is_connected g u pivot
then state
else
let cands = IntSet.delete cands u in
let clique' = IntSet.add clique u in
let u_neighbors = Graph.neighbors g u in
let cands' = IntSet.intersection cands u_neighbors in
let nots' = IntSet.intersection nots u_neighbors in
let accu = extend clique' cands' nots' accu in
let nots = IntSet.add nots u in
(cands, nots, accu))
cands
(cands, nots, accu)
in
accu
in
extend IntSet.empty (Graph.vertices g) IntSet.empty accu
;;