Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Finds all maximal cliques in a graph using the Bron-Kerbosch algorithm
# Finds all maximal cliques in a graph using the Bron-Kerbosch algorithm. The input graph here is
# in the adjacency list format, a dict with vertexes as keys and lists of their neighbors as values.
# https://en.wikipedia.org/wiki/Bron-Kerbosch_algorithm
from collections import defaultdict
def find_cliques(graph):
p = set(graph.keys())
r = set()
x = set()
cliques = []
for v in degeneracy_ordering(graph):
neighs = graph[v]
find_cliques_pivot(graph, r.union([v]), p.intersection(neighs), x.intersection(neighs), cliques)
p.remove(v)
x.add(v)
return sorted(cliques, lambda x: len(x))
def find_cliques_pivot(graph, r, p, x, cliques):
if len(p) == 0 and len(x) == 0:
cliques.append(r)
else:
u = iter(p.union(x)).next()
for v in p.difference(graph[u]):
neighs = graph[v]
find_cliques_pivot(graph, r.union([v]), p.intersection(neighs), x.intersection(neighs), cliques)
p.remove(v)
x.add(v)
def degeneracy_ordering(graph):
ordering = []
ordering_set = set()
degrees = defaultdict(lambda : 0)
degen = defaultdict(list)
max_deg = -1
for v in graph:
deg = len(graph[v])
degen[deg].append(v)
degrees[v] = deg
if deg > max_deg:
max_deg = deg
while True:
i = 0
while i <= max_deg:
if len(degen[i]) != 0:
break
i += 1
else:
break
v = degen[i].pop()
ordering.append(v)
ordering_set.add(v)
for w in graph[v]:
if w not in ordering_set:
deg = degrees[w]
degen[deg].remove(w)
if deg > 0:
degrees[w] -= 1
degen[deg - 1].append(w)
ordering.reverse()
return ordering
@ColonelJ

This comment has been minimized.

Copy link

ColonelJ commented Jan 29, 2020

I don't understand why you take the reverse of the ordering, surely the degeneracy ordering should start with the vertex of minimum degree (to match what is shown on the Wikipedia page)?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.