首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >了解Networkx find_cliques()函数

问了解Networkx find_cliques()函数
EN

Stack Overflow用户
提问于 2019-04-20 06:49:29
回答 1查看 315关注 0票数 0

我目前正在尝试开发一种在图中寻找团的算法,幸运的是,我从Networkx找到了一个函数的文档,该函数就是这样做的。不幸的是,变量名有点简洁,我很难理解代码的每一部分都做了些什么。

以下是find_cliques的代码:

代码语言:javascript
复制
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

它只工作了5分钟,但我只是想了解这里发生了什么,我似乎找不到任何在线资源来解释它。

EN

回答 1

Stack Overflow用户

发布于 2019-04-20 18:51:50

find_cliques方法的documentation列出了此算法的三个引用。你可能想看看它们,或者看看wikipedia。

一些变量:

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

u=具有最多邻居的节点,这些邻居不属于其他集团。

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

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/55768644

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档