NetworkX наиболее эффективный способ найти самый длинный путь в DAG в начальной вершине без ошибок

Question

Начиная с определенной вершины, как найти самый длинный путь относительно этой вершины? Я просматривал все и не могу найти решение этой проблемы, которая действительно работает для всех возможных случаев DAG. Исходный код в NetworkX был бы предпочтительнее, но обычный питон тоже хорош. Мне действительно любопытно, почему я не могу найти подходящий рабочий пример, я понимаю, что это проблема типа NP, но я хотел бы знать, как это сделать.

Answer 1

Во-первых, я бы проверял, подключен ли этот график. Если это так, то самым длинным путем является путь по всем узлам. Если нет, это означает, что эта вершина содержится в связанной компоненте. Затем я бы использовал connected_component_subgraphs, чтобы найти самый большой компонент, в котором находится эта вершина. После этого самый длинный путь - это путь по всем узлам этого самого большого компонента.

Конечно, это работает только в том случае, если вы не разрешаете циклы на своем пути.

import networkx as nx 
G = nx.DiGraph() 
G.add_edges_from([(0,1),(0,4),(4,5),(4,6),(5,6),(6,1),(0,2),(2,3),(1,2)]) 
for path in nx.all_simple_paths(G, source=0, target=3): 
    print(path) 

Результат:

[0, 1, 2, 3] 
[0, 2, 3] 
[0, 4, 5, 6, 1, 2, 3] 
[0, 4, 6, 1, 2, 3] 

Третий является то, что вам нравится.