如何使用Python NetworkX在Digraph中找到最长的10条路径?

问题描述 投票:3回答:1

有没有办法在使用NetworkX制作的Digraph中找到前10条长路径(删除了自循环)?

到目前为止我尝试过的,(锥形是带有自循环的有向图)

cone.remove_edges_from(cone.selfloop_edges())    
print nx.dag_longest_path(cone)

注意:在我使用的术语中,最长路径表示通过最大节点数的路径(与我们考虑边缘权重的标准定义不同)

python networkx
1个回答
1
投票

我可以想到两种态度:

  1. 查找图表中的所有路径,按长度排序并选择最长的10个路径
  2. 找到最长的路径,然后每次删除其中的一条边,并在剩余的图中找到最长的路径。如果对所有边进行此操作,并从所有尝试中获取最长路径,则应在原始图中获得第二长图。 (将其扩展到10可能不是很有效,但它应该工作)

对于第一个想法(找到所有路径,然后选择最长的) - 这是一个天真的示例代码。这不是你能获得的最佳效率,而只是一个例子 -

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来获取图中的所有路径。你可以看一些想法herehere例如。

关于第二个选项(使用消除最长路径边缘找到第二个最长路径),这里有一个代码,演示如何找到第二个最长路径:

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级的消除边缘......)。

© www.soinside.com 2019 - 2024. All rights reserved.