NetworkX系列教程(10)-算法之三:关键路径问题

小书匠Graph图论

重头戏部分来了,写到这里我感觉得仔细认真点了,可能在NetworkX中,实现某些算法就一句话的事,但是这个算法是做什么的,用在什么地方,原理是怎么样的,不清除,所以,我决定先把图论中常用算法弄个明白在写这部分.

图论常用算法看我的博客:

下面我将使用NetworkX实现上面的算法,建议不清楚的部分打开两篇博客对照理解.

我将图论的经典问题及常用算法的总结写在下面两篇博客中:

图论---问题篇

 图论---算法篇

目录:

* 11.3关键路径算法(CPA)

注意:如果代码出现找不库,请返回第一个教程,把库文件导入.

11.3关键路径算法(CPA)

以下代码从这里复制,由于版本问题,将代码中的:nx.topological_sort(self, reverse=True)改为list(reversed(list(nx.topological_sort(self))))

import networkx as nx
import matplotlib.pyplot as plt
from matplotlib.font_manager import *
#定义自定义字体，文件名从1.b查看系统中文字体中来
myfont = FontProperties(fname='/usr/share/fonts/truetype/wqy/wqy-zenhei.ttc')
#解决负号'-'显示为方块的问题
matplotlib.rcParams['axes.unicode_minus']=False
class CPM(nx.DiGraph):
def __init__(self):
super().__init__()
self._dirty = True
self._critical_path_length = -1
self._criticalPath = None
def add_node(self, *args, **kwargs):
self._dirty = True
super().add_node(*args, **kwargs)
def add_nodes_from(self, *args, **kwargs):
self._dirty = True
super().add_nodes_from(*args, **kwargs)
def add_edge(self, *args): # , **kwargs):
self._dirty = True
super().add_edge(*args) # , **kwargs)
def add_edges_from(self, *args, **kwargs):
self._dirty = True
super().add_edges_from(*args, **kwargs)
def remove_node(self, *args, **kwargs):
self._dirty = True
super().remove_node(*args, **kwargs)
def remove_nodes_from(self, *args, **kwargs):
self._dirty = True
super().remove_nodes_from(*args, **kwargs)
def remove_edge(self, *args): # , **kwargs):
self._dirty = True
super().remove_edge(*args) # , **kwargs)
def remove_edges_from(self, *args, **kwargs):
self._dirty = True
super().remove_edges_from(*args, **kwargs)
#根据前向拓扑排序算弧的最早发生时间
def _forward(self):
for n in nx.topological_sort(self):
es = max([self.node[j]['EF'] for j in self.predecessors(n)], default=0)
self.add_node(n, ES=es, EF=es + self.node[n]['duration'])
#根据前向拓扑排序算弧的最迟发生时间
def _backward(self):
#for n in nx.topological_sort(self, reverse=True):
for n in list(reversed(list(nx.topological_sort(self)))):
lf = min([self.node[j]['LS'] for j in self.successors(n)], default=self._critical_path_length)
self.add_node(n, LS=lf - self.node[n]['duration'], LF=lf)
#最早发生时间=最迟发生时间,则判断该节点为关键路径上的关键活动
def _compute_critical_path(self):
graph = set()
for n in self:
if self.node[n]['EF'] == self.node[n]['LF']:
graph.add(n)
self._criticalPath = self.subgraph(graph)
@property
def critical_path_length(self):
if self._dirty:
self._update()
return self._critical_path_length
@property
def critical_path(self):
if self._dirty:
self._update()
return sorted(self._criticalPath, key=lambda x: self.node[x]['ES'])
def _update(self):
self._forward()
self._critical_path_length = max(nx.get_node_attributes(self, 'EF').values())
self._backward()
self._compute_critical_path()
self._dirty = False
if __name__ == "__main__":
#构建graph
G = CPM()
G.add_node('A', duration=5)
G.add_node('B', duration=2)
G.add_node('C', duration=4)
G.add_node('D', duration=4)
G.add_node('E', duration=3)
G.add_node('F', duration=7)
G.add_node('G', duration=4)
G.add_edges_from([
('A', 'B'),
('A', 'C'),
('C','D'),
('C','E'),
('C','G'),
('B','D'),
('D','F'),
('E','F'),
('G','F'),
])
#显示graph
nx.draw_spring(G,with_labels=True)
plt.title('AOE网络',fontproperties=myfont)
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()
print('关键活动为:')
print(G.critical_path_length, G.critical_path)
G.add_node('D', duration=2)
print('\n修改D活动持续时间4为2后的关键活动为:')
print(G.critical_path_length, G.critical_path)

关键路径示例(该图非黑色线为手工绘制,数字手工添加)

从graph中可以知道,有两条关键路径,分别是:A->C->G->F和A->C->D->F,长度都是20.

输出:

关键活动为: 20 ['A', 'C', 'D', 'G', 'F']

修改D活动持续时间4为2后的关键活动为: 20 ['A', 'C', 'G', 'F']

关键活动为: ['A', 'C', 'D', 'G', 'F'],可以构成两条边.D活动持续时间4为2后,关键路径变化.

巴特西

NetworkX系列教程(10)-算法之三:关键路径问题

11.3关键路径算法(CPA)

最新文章

热门文章