-
Notifications
You must be signed in to change notification settings - Fork 0
/
AOE.py
134 lines (129 loc) · 6.53 KB
/
AOE.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 29 21:58:03 2020
@author: 孔令百
Name:AOE.py
Desctiption:该模块中主要是AOE网络计算的底层算法
"""
"""
类:AOE类
功能:求解AOE网络
"""
class AOE:
"""
函数：__init__(self,graph_head,graph_tail,circle_dict,line_dict)
功能：AOE类的构造函数
传入参数：AOE网络正向邻接表graph_head(字典),AOE网络逆邻接表graph_tail(字典),圆图形字典circle_dict(字典),连接线图形字典line_dict(字典)
传出参数：无
"""
def __init__(self,graph_head,graph_tail,circle_dict,line_dict):
self.gh=graph_head#AOE网络邻接表
self.gt=graph_tail#AOE网络逆邻接表
self.circle_dict=circle_dict#圆图形字典
self.line_dict=line_dict#连接线图形字典
self.order=list(self.gh.keys())#顶点的拓扑排序序列
self.critical_activity=[]#关键活动列表
self.critical_affair=[]#关键事件列表
self.Ve={}#事件Vi的最早可能开始时间,格式key=圆图形名称(字符串),value=时间(整数)
self.Vl={}#事件Vi的最迟允许开始时间,格式key=圆图形名称(字符串),value=时间(整数)
self.e={}#活动ai的最早可能开始时间,格式key=连接线图形名称(字符串),value=时间(整数)
self.l={}#活动ai的最迟允许开始时间,格式key=连接线图形名称(字符串),value=时间(整数)
self.route_list=[]#多种关键路径列表
self.activity_group=[]#多种关键活动列表
self.time=0
"""
函数：function(self)
功能：运行算法,求解Ve,Vl,e,l,critical_activity,critical_affair
传入参数：无
传出参数：关键活动self.critical_activity(列表),关键事件self.critical_affair(列表)
"""
def function(self):
#从Ve[0]=0开始
self.Ve[self.order[0]]=0
#以公式Ve[i]=max{Ve[j]+dur(<Vj,Vi>)}向前递推
for i in range(1,len(self.order)):
v=self.order[i]
m=max(self.gt[v],key=lambda x:self.Ve[x[0]]+x[1])
self.Ve[v]=self.Ve[m[0]]+m[1]
#从Vl[n-1]=Ve[n-1]开始
self.Vl[self.order[-1]]=self.Ve[self.order[-1]]
#全工程可以完成的最早时间就是Vl[n-1]
self.time=self.Ve[self.order[-1]]
#以公式Vl[i]=min{Vl[j]-dur(<Vi,Vj>)}反向递推
for i in range(len(self.order)-2,-1,-1):
v=self.order[i]
m=min(self.gh[v],key=lambda x:self.Vl[x[0]]-x[1])
self.Vl[v]=self.Vl[m[0]]-m[1]
#以Ve[k]=Vl[k]为判断条件寻找关键事件
for v in self.order:
if self.Ve[v]==self.Vl[v]:
self.critical_affair.append(v)
#计算e[k]和l[k]
#e[k]=Ve[i]
#l[k]=Vl[j]-dur(<Vi,Vj>)
for line,value in self.line_dict.items():
self.e[line]=self.Ve[value[1]]
self.l[line]=self.Vl[value[2]]-value[0]
#以e[k]=l[k]为判断条件寻找关键活动
for line in self.line_dict:
if self.e[line]==self.l[line]:
self.critical_activity.append(line)
return self.critical_activity,self.critical_affair
"""
函数：_route(self,cur,route)
功能：寻找全部的关键路径
传入参数：当前事件顶点cur(字符串),当前路径route(字符串)
传出参数：无
"""
def _route(self,cur,route):
#拷贝当前路径
new_route=route
#将当前事件加入到当前路径中
if new_route=="":
new_route=self.circle_dict[cur][0]
else:
new_route+='→'+self.circle_dict[cur][0]
#如果当前事件是AOE网络的汇点
if cur==self.order[-1]:
#加入当前路径到关键路径
self.route_list.append(new_route)
#检查当前事件的下一个关键事件
for out in self.circle_dict[cur][3]:
if out in self.critical_activity:
#递归地调用此函数
new=self.line_dict[out][2]
self._route(new,new_route)
"""
函数：critical(self)
功能：计算每一条关键路径和每一组关键活动
传入参数：无
传出参数：全部关键路径self.route_list(列表),各组关键事件self.activity_group(列表)
"""
def critical(self):
#从源点开始递归计算关键路径
self._route(self.order[0],"")
#将每一条关键路径中的关键事件分离出来,组成一组加入到关键事件列表中
for route in self.route_list:
step=route.split('→')
activity=""
if len(step)>=2:
activity='<'+step[0]+','+step[1]+'>'
for i in range(1,len(step)-1):
activity+=',<'+step[i]+','+step[i+1]+'>'
self.activity_group.append(activity)
return self.route_list,self.activity_group
"""
该模块的测试代码
"""
if __name__=="__main__":
gh={'c0': [('c1', 5), ('c2', 6)], 'c1': [('c3', 3)], 'c2': [('c3', 6), ('c4', 3)], 'c3': [('c4', 3), ('c6', 4), ('c5', 4)], 'c4': [('c6', 1), ('c7', 4)], 'c5': [('c9', 4)], 'c6': [('c8', 5)], 'c7': [('c8', 2)], 'c8': [('c9', 2)], 'c9': []}
gt={'c0': [], 'c1': [('c0', 5)], 'c2': [('c0', 6)], 'c3': [('c1', 3), ('c2', 6)], 'c4': [('c3', 3), ('c2', 3)], 'c5': [('c3', 4)], 'c6': [('c4', 1), ('c3', 4)], 'c7': [('c4', 4)], 'c8': [('c6', 5), ('c7', 2)], 'c9': [('c5', 4), ('c8', 2)]}
c={'c0': ['1', (103, 146), [], ['l0', 'l2']], 'c1': ['2', (218, 62), ['l0'], ['l1']], 'c2': ['3', (223, 244), ['l2'], ['l3', 'l5']], 'c3': ['4', (357, 62), ['l1', 'l3'], ['l4', 'l7', 'l8']], 'c4': ['5', (358, 242), ['l4', 'l5'], ['l6', 'l12']], 'c5': ['6', (545, 67), ['l8'], ['l9']], 'c6': ['7', (478, 146), ['l6', 'l7'], ['l10']], 'c7': ['8', (581, 258), ['l12'], ['l13']], 'c8': ['9', (670, 159), ['l10', 'l13'], ['l11']], 'c9': ['10', (848, 147), ['l9', 'l11'], []]}
l={'l0': [5, 'c0', 'c1'], 'l1': [3, 'c1', 'c3'], 'l2': [6, 'c0', 'c2'], 'l3': [6, 'c2', 'c3'], 'l4': [3, 'c3', 'c4'], 'l5': [3, 'c2', 'c4'], 'l6': [1, 'c4', 'c6'], 'l7': [4, 'c3', 'c6'], 'l8': [4, 'c3', 'c5'], 'l9': [4, 'c5', 'c9'], 'l10': [5, 'c6', 'c8'], 'l11': [2, 'c8', 'c9'], 'l12': [4, 'c4', 'c7'], 'l13': [2, 'c7', 'c8']}
aoe=AOE(gh,gt,c,l)
critical_activity,critical_affair=aoe.function()
routes,activity=aoe.critical()
print(critical_activity)
print(critical_affair)
print(routes)
print(activity)