我目前正在尝试制作一种算法来查找图中的派系,幸运的是,我从 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
它工作得很好,但我只是想了解这里发生了什么,我似乎无法在网上找到任何解释它的资源。