我目前正在尝试开发一种在图中寻找团的算法,幸运的是,我从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它只工作了5分钟,但我只是想了解这里发生了什么,我似乎找不到任何在线资源来解释它。
发布于 2019-04-20 18:51:50
find_cliques方法的documentation列出了此算法的三个引用。你可能想看看它们,或者看看wikipedia。
一些变量:
adj=字典将每个节点的邻居存储为一个集合
u=具有最多邻居的节点,这些邻居不属于其他集团。
ext_u = u的所有邻居,这些邻居不是另一个集团的成员
https://stackoverflow.com/questions/55768644
复制相似问题