Skip to content

Instantly share code, notes, and snippets.

@abhin4v
Last active October 7, 2021 16:46
Show Gist options
  • Save abhin4v/8304062 to your computer and use it in GitHub Desktop.
Save abhin4v/8304062 to your computer and use it in GitHub Desktop.
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
Copy link

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