Рассчитайте самый длинный путь между двумя узлами NetworkX

Question

Я пытаюсь сделать мангольд с помощью Networkx. Все узлы в сети являются «задачами», которые необходимо выполнить для завершения проекта. С Networkx легко рассчитать общее время проекта. Но для создания манжеты Ганта мне нужно самое позднее начало каждого узла.

NetworkX включает одну функцию (dag_longest_path_length), но она рассчитывает на самый длинный путь во всей сети. Другая функция (astar_path_length) приводит к кратчайшему пути между источником и узлом, но не доступна ни одна функция, которая дает самый длинный путь или самое позднее начало в моем случае. (если узел в качестве двух предшественников выберет самый быстрый маршрут, но на самом деле ему также приходится ждать второго, прежде чем он сможет запуститься.

Я думал об одном варианте. Оценить предыдущие присоединенные узлы и выбрать самый длинный путь. Неформально мне это не удалось.

start_time=[]
time=0
DD=nx.DiGraph()
for i in range(df.shape[0]):
        DD.add_edge(str(df.at[i,'blockT'])+'_'+df.at[i,'Task'], str(df.at[i,'blockS'])+'_'+df.at[i,'Succ'], weight=df.at[i,'duration'])


fig, ax = plt.subplots()  
labels=[]  
for i in range(df.shape[0]):
        labels.append(str(df.at[i,'blockT'])+'_'+df.at[i,'Task'])
        print(nx.astar_path_length(DD, '0_START', str(df.at[i,'blockT'])+'_'+df.at[i,'Task'])  ) 

ax.broken_barh([(nx.astar_path_length(DD, '0_START', str(df.at[i,'blockT'])+'_'+df.at[i,'Task']), heuristic=None, weight='weight'),df.at[i,'duration'] )],(i-0.4,0.8), facecolors='blue' )

Answer 1

Похоже, вы используете DAG.

Ваша проблема встречается довольно редко, поэтому в networkx для нее нет встроенной функции. Вы должны сделать это вручную:

max(nx.all_simple_paths(DAG, source, target), key=lambda x: len(x))

Вот полный код тестирования:

import networkx as nx
import random
from itertools import groupby

# Create random DAG
G = nx.gnp_random_graph(50,0.3,directed=True)
DAG = nx.DiGraph([(u,v) for (u,v) in G.edges() if u<v])

# Get the longest path from node 1 to node 10
max(nx.all_simple_paths(DAG, 1, 10), key=lambda x: len(x))