我目前正在尝试制作一个用于在图表中查找派系的算法,幸运的是我从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
它只是fie,但我只是想了解这里发生的事情,我似乎无法找到任何在线解释它的资源。
documentation方法的find_cliques
列出了该算法的三个参考。你可能想看看它们,或者你看看wikipedia。
一些变量:
adj
=为每个节点存储邻居作为集合的字典
u
=邻居数量最多的节点,不属于其他集团。
ext_u
=你的所有邻居,不是另一个集团的成员