有没有办法在使用NetworkX制作的Digraph中找到前10条长路径(删除了自循环)?
到目前为止我尝试过的,(锥形是带有自循环的有向图)
cone.remove_edges_from(cone.selfloop_edges())
print nx.dag_longest_path(cone)
注意:在我使用的术语中,最长路径表示通过最大节点数的路径(与我们考虑边缘权重的标准定义不同)
我可以想到两种态度:
对于第一个想法(找到所有路径,然后选择最长的) - 这是一个天真的示例代码。这不是你能获得的最佳效率,而只是一个例子 -
import itertools
import networkx as nx
all_paths=[]
for (x,y) in itertools.combinations(DAG.nodes,2):
for path in nx.all_simple_paths(DAG,x,y):
all_paths.append(path)
all_paths.sort(key=len,reverse=True)
print all_paths[:10]
如果您想要一个更高效的解决方案,您应该使用DFS来获取图中的所有路径。你可以看一些想法here或here例如。
关于第二个选项(使用消除最长路径边缘找到第二个最长路径),这里有一个代码,演示如何找到第二个最长路径:
longest_path = nx.dag_longest_path(DG)
print "longest path = " + longest_path
second_longest_paths = []
for i in range(len(longest_path) - 1):
edge = (longest_path[i], longest_path[i + 1])
DG.remove_edges_from([edge])
second_longest_paths.append(nx.dag_longest_path(DG))
DG.add_edges_from([edge])
second_longest_paths.sort(reverse=True, key=len)
print "second longest path = " + str(second_longest_paths[0])
但我认为将其扩展到10条最长的路径可能有点棘手(可能涉及我们刚刚完成的过程的递归,找到图中第二条最长的路径,其中第2级的消除边缘......)。