计算两个节点 NetworkX 之间的最长路径 [英] Calculate the longest path between two nodes NetworkX

问题描述

我正在尝试使用 Networkx 制作甘特图.网络中的所有节点都是完成项目需要执行的任务".使用 Networkx 可以轻松计算项目的总时间.但是制作甘特图我需要每个节点的最新启动.

I'm trying to make a Gantt chard using Networkx. All the nodes in the network are "tasks" that need to be performed to complete the project. With Networkx it is easy to calculate the total time of the project. But the make the Gantt chard I need the latest start of each node.

NetworkX 包含一个函数(dag_longest_path_length)，但这会计算整个网络中的最长路径.另一个函数(astar_path_length)导致源和节点之间的最短路径，但没有提供最长路径的函数，或者在我的情况下最晚开始.(如果一个节点作为两个前驱，它会走最快的路线，但实际上它也必须等待第二个才能开始.

NetworkX includes one function(dag_longest_path_length) but this calculates to longest path in the whole network. Another function(astar_path_length) results in the shortest path between a source and node, but no function is availed which gives the longest path, or latest start in my case. (if a node as two predecessors it will take the fastest route, but in reality it also has to wait on the second before it can start.

我正在考虑一种选择.评估先前连接的节点并选择最长的路径.非正式的我没有成功.

I was thinking of one option. To evaluate the previous attached nodes and selecting the longest path. Unformal I did not succeeded.

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

推荐答案

这是我使用的一些代码.我同意它真的应该成为 NetworkX 的一部分，因为它对我来说经常出现.graph 必须是 DiGraph.s 是源节点，dist 是一个 dict 键，节点以 s 的加权距离作为值.

Here is some code that I use. I agree is really should be part of NetworkX because it comes up pretty often for me. graph must be a DiGraph. s is the source node and dist is a dict keyed by nodes with weighted distances to s as values.

    def single_source_longest_dag_path_length(graph, s):
        assert(graph.in_degree(s) == 0)
        dist = dict.fromkeys(graph.nodes, -float('inf'))
        dist[s] = 0
        topo_order = nx.topological_sort(graph)
        for n in topo_order:
            for s in graph.successors(n):
                if dist[s] < dist[n] + graph.edges[n,s]['weight']:
                    dist[s] = dist[n] + graph.edges[n,s]['weight']
        return dist

这篇关于计算两个节点 NetworkX 之间的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！