Skip to content

Instantly share code, notes, and snippets.

@yfarjoun
Forked from abhin4v/maximal_cliques.py
Created August 21, 2018 03:12
Show Gist options
  • Save yfarjoun/a943bb3b2b18bc4ab7bb6689adbfa76b to your computer and use it in GitHub Desktop.
Save yfarjoun/a943bb3b2b18bc4ab7bb6689adbfa76b 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment