Как найти 10 самых длинных путей в Digraph с Python NetworkX?

Question

Есть ли способ найти 10 лучших длинных путей в Digraph (с удаленными петлями), созданными с использованием NetworkX?

Что я пробовал до сих пор, ( cone орграф с самоконтролями)

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

Примечание. В использованной мной терминологии самый длинный путь означает путь, который проходит через максимальное количество узлов (в отличие от стандартного определения, в котором мыучитывать вес ребра)

Answer 1

Я могу думать о двух отношениях:

1. Найти все пути на графике, отсортировать по длине и взять 10 самых длинных
2. Найдите самый длинный путь, затем каждый раз удаляйте в нем одно ребро и найдите самый длинный путь в оставшемся графе. Если вы делаете это со всеми ребрами и выбираете самый длинный путь из всех попыток, вы должны получить 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, чтобы получить все пути на графике. Вы можете увидеть некоторые идеи здесь или здесь например.

Что касается второго варианта (найти второй самый длинный путь, используя исключение самых длинных краев пути), вот код, который демонстрирует, как найти 2-й самый длинный путь:

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 ...).