CODEWITHSUNDEEP
pythonalgorithmgraph
user15565200
user15565200

Reputation:

How to find all the cliques in a graph (dictionary) in python?

import networkx as nx 

def get_clique(graph):
  G = nx.Graph(graph)
  all_cliques = list(nx.algorithms.clique.find_cliques(G))
  return max(all_cliques, key=len)

Is there another method to do this question instead of using networkx?

Upvotes: 1

Views: 448

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65506

It's not too hard to implement Bron--Kerbosch straight from the pseudocode.

import collections


def cliques_recursive(neighbors, r, p, x):
    if not p and not x:
        yield r
    else:
        for v in min((p - neighbors[u] for u in p | x), key=len):
            yield from cliques_recursive(
                neighbors, r | {v}, p & neighbors[v], x & neighbors[v]
            )
            p.remove(v)
            x.add(v)


def cliques(graph):
    neighbors = collections.defaultdict(set)
    for v, n_v in graph.items():
        for u in n_v:
            if u != v:
                neighbors[u].add(v)
                neighbors[v].add(u)
    yield from cliques_recursive(neighbors, set(), set(neighbors), set())


graph = {
    0: [9],
    1: [2, 3, 6],
    2: [1, 4],
    3: [2, 6],
    4: [5],
    5: [0, 3, 4],
    6: [1, 5, 7, 9],
    7: [8],
    8: [0, 9],
    9: [5, 6],
    10: [0, 8, 9],
}
for clique in cliques(graph):
    print(clique)

Upvotes: 2

TUI lover
TUI lover

Reputation: 552

There are methods to do that, but they are very likely to be inefficient in comparison. Finding all cliques is in general NP-complete.

Upvotes: 0

Related Questions