#input
Table = #table#
#check name of Activities
for row in Table:
if (' ' in row[0]) or (not row[0]):
show('Name of Activities cannot contain blank space.')
assert()
#check duration if it is real number
for row in Table:
if row[2] not in RR:
show('Please enter number for Duration.')
assert()
#show input before everything
firstshowntable = [['Activity','Predecessors','Duration']] + Table
show('')
show(table(firstshowntable , frame = true, header_row = true))
#split predeccessors string in Table before constructing class
for row in Table:
if not row[1].strip():
row[1] = []
else:
row[1] = row[1].split(' ')
import copy
import matplotlib.pyplot as plt
class Project:
#class constructor by input table
def __init__(self,Table):
"""
input table : each row array in form [name : [predecessors], duration]
class elements:
node_predeccessor: dict in form {Activities node : predeccessors} (with start and end nodes)
node_successor: dict in form {Activities node : successors} (with start and end nodes)
node_duration: dict in form {Activities node : duration}
sort_nodes: topological sorted activities node
activity_node_data: dict in form {Activities node :{'ES':,'EF':,'LS':,'LF':,'TF':}}
"""
#create activities start and end
Table1 = copy.deepcopy(Table)
for row in Table1:
if not row[1]:
row[1] = ['St']
endpredes = []
for r1 in Table1:
inpredes = false
for r2 in Table1:
if r1[0] in r2[1]:
inpredes = true
if not inpredes:
endpredes += [r1[0]]
Table1 = [['St',[],0]] + Table1 + [['End',endpredes,0]]
#transfer node predeccessors to class element
self.node_predeccessor = {row[0] : row[1] for row in Table1}
#find sucessors of each activity
self.node_successor = {row[0] : [] for row in Table1}
for r1 in Table1:
for r2 in Table1:
if r1[0] in r2[1]:
self.node_successor[r1[0]] += [r2[0]]
#transfer node activities duration
self.node_duration = {}
for row in Table1:
self.node_duration[row[0]] = row[2]
#initialize sort_nodes (to be construct by class function later)
self.sort_nodes = []
#initialize activity_node_data and result_table (to be calculated later by class function)
self.activity_node_data = {row[0] :{'ES':0,'EF':0,'LS':0,'LF':0,'TF':0} for row in Table1}
#end of constructor
# topological sort node
# A recursive function used by topologicalSort
def topologicalSortUtil(self,v,visited,stack):
# Mark the current node as visited.
visited[v] = True
# Recur for all the vertices adjacent to this vertex
for i in self.node_successor[v]:
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
# Push current node to stack which stores result
stack.insert(0,v)
# The function to do Topological Sort. It uses recursive
# topologicalSortUtil()
def topologicalSort(self):
# Mark all the vertices as not visited
visited = {k:False for k in self.node_successor.keys()}
stack =[]
# Call the recursive helper function to store Topological
# Sort starting from all vertices one by one
for i in self.node_successor.keys():
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
# assigin stack to sort_nodes
self.sort_nodes = stack
#end of topological sort
#compute node data forwardly (must run topological sort before)
def forward_pass(self):
#get node order topologically
node_order = copy.deepcopy(self.sort_nodes)
#compute 'ES', 'EF' forwardly
for act_node in node_order[1:]:
maxf = -math.inf
for node in self.node_predeccessor[act_node]:
if maxf < self.activity_node_data[node]['EF']:
maxf = self.activity_node_data[node]['EF']
self.activity_node_data[act_node]['ES'] = maxf
self.activity_node_data[act_node]['EF'] = maxf + self.node_duration[act_node]
#end of forward pass
#backward pass (must run forward_pass before)
# compute 'LS', 'LF' and 'TF'
def backward_pass(self):
#get reverse node order topologically
node_order = copy.deepcopy(self.sort_nodes)
reverse_order = node_order[::-1]
#assign 'LS' and 'LF' to node 'End'
self.activity_node_data['End']['LS'] = self.activity_node_data['End']['EF']
self.activity_node_data['End']['LF'] = self.activity_node_data['End']['EF']
#compute 'LS', 'LF' backwardly
for act_node in reverse_order[1:]:
mins = math.inf
for node in self.node_successor[act_node]:
if mins > self.activity_node_data[node]['LS']:
mins = self.activity_node_data[node]['LS']
self.activity_node_data[act_node]['LF'] = mins
self.activity_node_data[act_node]['LS'] = mins - self.node_duration[act_node]
#backward compute finished 'ES', 'EF', 'LS' and 'LF' are calculated
#compute 'TF' for each node
for act_node in node_order:
self.activity_node_data[act_node]['TF'] = self.activity_node_data[act_node]['LF'] - self.activity_node_data[act_node]['ES'] - self.node_duration[act_node]
#end of backward pass
#display result table and gantt chart
def display_result(self):
#make result table from node data
resulttable = [['Activity','ES(Earliest Start)','EF(Earliest Finish)','LS(latest Start)','LF(Latest Finish)','TF(Total Float)']]
for act , attrib in self.activity_node_data.items():
resulttable += [[act, attrib['ES'], attrib['EF'], attrib['LS'], attrib['LF'], attrib['TF']]]
#get finish time for later gantt chart
finish_time = resulttable[len(resulttable)-1][4]
# remove 'start' and 'end' activity row
resulttable1 = copy.deepcopy(resulttable)
resulttable1.remove(resulttable1[1])
resulttable1 = resulttable1[:-1]
show('')
show('')
show('')
show('The ES,EF,LS,LF and TF(total float) of the activities are calculated as follows:')
show(table(resulttable1))
#identify critical activities
critical_activity_string = ''
for i in range(len(resulttable1)):
if resulttable1[i][5] == 0:
critical_activity_string += resulttable1[i][0] + ','
critical_activity_string = critical_activity_string[:-1]
show(critical_activity_string + ' are critical activities.')
#gantt chart
#copy resulttable1 and remove head row for chart data graph
resulttable2 = copy.deepcopy(resulttable1)
resulttable2 = resulttable2[1:]
#indexs of critical
critical_index = []
for i in range(len(resulttable2)):
if resulttable2[i][5] == 0:
critical_index += [i]
#create gantt chart
fig, ax = plt.subplots()
for i in range(len(resulttable2)):
if resulttable2[i][5] > 0:
ax.broken_barh(\
[(resulttable2[i][1] , resulttable2[i][2] -resulttable2[i][1]), (resulttable2[i][2], resulttable2[i][4] - resulttable2[i][2])],\
(len(resulttable2)-i-0.25, 0.5), facecolors=('blue', 'lightblue')\
)
else:
ax.broken_barh([(resulttable2[i][1] , resulttable2[i][2] -resulttable2[i][1])], (len(resulttable2)-i-0.25, 0.5),\
facecolors=('orange')\
)
ax.set_title('Gantt Chart')
ax.set_ylim(0, len(resulttable2)+1)
ax.set_xlim(0, 1.1*finish_time)
ax.set_xlabel('Time Since Start')
ax.set_yticks([len(resulttable2)-i for i in range(len(resulttable2))])
ax.set_yticklabels([row[0] for row in resulttable2])
ax.grid(True)
#may act arrows between bars in the future
#for i in range(len(critical_index)-1):
#ax.arrow(resulttable2[critical_index[i]][4], len(resulttable2) - critical_index[i], 0, critical_index[i] - critical_index[i+1] +0.5, head_width=0.2, head_length=0.1, color = 'red')
plt.show()
#main
P = Project(Table)
P.topologicalSort()
P.forward_pass()
P.backward_pass()
P.display_result()