Блог

 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)

 

Есть ли другой способ ответить на этот вопрос вместо использования networkx?

Не так уж сложно реализовать Bron-Kerbosch прямо из псевдокода.

 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 amp; neighbors[v], x amp; 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)
 

Для этого существуют методы, но они, скорее всего, окажутся неэффективными по сравнению с ними. Поиск всех клик в общем случае является NP-полным.