0

我目前正在尝试制作一种算法来查找图中的派系,幸运的是,我从 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

它工作得很好,但我只是想了解这里发生了什么,我似乎无法在网上找到任何解释它的资源。

4

1 回答 1

1

该方法的文档列出了find_cliques该算法的三个参考资料。您可能想查看它们或查看wikipedia

一些变量:

adj= 字典为每个节点存储邻居作为一个集合

u=不属于其他集团的邻居数量最多的节点。

ext_u= u 的所有邻居,它们不是另一个集团的成员

于 2019-04-20T10:51:50.040 回答