{{ message }}

Instantly share code, notes, and snippets.

# abhin4v/maximal_cliques.py

Last active Jan 29, 2020
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 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)?