在有向图中找到包含指定节点的所有长度为 n 的循环的最快方法

Question

我有一个大型有向图，其中包含约 250 个节点和约 750 个加权边。我正在寻找一种方法来查找包含指定节点的所有长度为 n 的循环。例如，如果我想要在方向图 DG 中包含节点 A 的所有长度 n 的循环，我会这样做：

import networkx as nx
DG = nx.DiGraph() # assume this is a large graph
cycles = nx.simple_cycles(DG)
n = 4
node = 'A'
relevant_cycles = []
for cycle in cycles:
    if len(cycle) == n and node in cycle:
        relevant_cycles.append(cycle)

但是，对于我正在处理的大图来说，这非常慢。这个问题有更好的解决办法吗？

Answer 1

对于那些感兴趣的人，我改编了 Joel 的回答以创建一种更有效的方法来做到这一点。

def findPaths(G,u,n):
    if n==0:
        return [[u]]
    paths = [[u]+path for neighbor in G.neighbors(u) for path in findPaths(G,neighbor,n-1)]
    return paths

def find_cycles(G,u,n):
    paths = findPaths(DG,u,n)
    return [tuple(path) for path in paths if (path[-1] == u) and sum(x ==u for x in path) == 2]

cycles = find_cycles(DG,'A',4) # example usage

在有向图中找到包含指定节点的所有长度为 n 的循环的最快方法

Fastest way to find all cycles of length n containing a specified node in a directional graph

python

graph-theory

directed-graph

networkx