如何使用Python NetworkX查找有向图中的最长10条路径？

Question

有没有办法在使用NetworkX创建的有向图（去除自环）中找到前10个最长的路径？

目前我尝试过的方法是（cone 是带自环的有向图）：

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

注意：在我使用的术语中，“最长路径”是指通过最多节点的路径（与标准定义不同，我们考虑边权重的定义）。

- vineeshvs

---

寻找最长的路径（恰好穿过每个节点一次）是一个NP难题。你对期望（复杂度，...）有什么想法？你考虑过多大的图形？ - Anthony Labarre

@AnthonyLabarre 最终目标是将图中最长的10条路径（大约）分成三个部分，并获取这些节点中的信号。最终的图将拥有100多个节点（但至少可以预期有1000个节点）。 - vineeshvs

@AnthonyLabarre 即使我们通过拓扑排序节点来删除循环，它仍然是NP难题吗？ - vineeshvs

不，如果您有一个DAG（有向无环图），那么问题就变成了多项式。这是您的情况吗（您使用dag_longest_path的代码片段似乎是这样）？请注意，如果图形具有循环，则无法对顶点进行拓扑排序，因此我不确定您打算如何删除循环（这意味着可能性很大，但有几种方法可以做到这一点）。 - Anthony Labarre

我将使用DAG并探索消除循环的方法。（我将把Verilog中的HDL描述转换为图形。在筛选消除循环的方法时也会考虑这一点）。感谢AnthonyLabarre教授。 - vineeshvs

Answer 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以获取图中的所有路径。例如，您可以在这里或这里看到一些想法。

关于第二个选项（使用最长路径边缘消除找到第二长的路径），这里有一个演示如何找到第二长路径的代码：

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级删除的边的图中的第二长路径...）。

- Shir

---

我已經實現了方法1並在Python中使用了Timsort（https://www.geeksforgeeks.org/timsort/）。對於我的任務有效。謝謝@Shir。 - vineeshvs