Понимание функции Networkx find_cliques () - PullRequest
Новая
       72

Понимание функции Networkx find_cliques ()

0 голосов
/ 20 апреля 2019

В настоящее время я пытаюсь создать алгоритм для нахождения клика в графе, и, к счастью, я нашел документацию от Networkx для функции, которая делает именно это. К сожалению, имена переменных немного лаконичны, и мне трудно понять, что делает каждая часть кода.

Вот код для find_cliques: 

def find_cliques(G):
    if len(G) == 0:
        return

    adj = {u: {v for v in G[u] if v != u} for u in G}
    Q = [None]

    subg = set(G)
    cand = set(G)
    u = max(subg, key=lambda u: len(cand & adj[u]))
    ext_u = cand - adj[u]
    stack = []

    try:
        while True:
            if ext_u:
                q = ext_u.pop()
                cand.remove(q)
                Q[-1] = q
                adj_q = adj[q]
                subg_q = subg & adj_q
                if not subg_q:
                    yield Q[:]
                else:
                    cand_q = cand & adj_q
                    if cand_q:
                        stack.append((subg, cand, ext_u))
                        Q.append(None)
                        subg = subg_q
                        cand = cand_q
                        u = max(subg, key=lambda u: len(cand & adj[u]))
                        ext_u = cand - adj[u]
            else:
                Q.pop()
                subg, cand, ext_u = stack.pop()
    except IndexError:
        pass

Это работает просто тьфу, но я просто хочу понять, что здесь происходит, и я не могу найти какие-либо ресурсы в Интернете, объясняющие это.

1 Ответ

1 голос
/ 20 апреля 2019

Документация метода find_cliques содержит три ссылки на этот алгоритм.Вы можете захотеть взглянуть на них или взглянуть на wikipedia .

Некоторые переменные:

adj = словарь, хранящий для каждого узла соседние узлы в виде набора

u = узел с наибольшим числом соседей, которые не принадлежат другой клике.

ext_u = все соседи u, которые не являются членами другой клики

...