Advertisement
fevzi02

CР по теме Класс Сетевой график. Поиск критического пути

Nov 4th, 2022
1,643
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 7.59 KB | None | 0 0
  1. #Класс Графа
  2. class Graph:
  3.     #number_of_vertices - количество вершин графа; weight_of_all_arcs - словарь дуг и их вес
  4.     def __init__(self, number_of_vertices, weight_of_all_arcs):
  5.         self.number_of_vertices = number_of_vertices
  6.         self.weight_of_all_arcs = weight_of_all_arcs
  7.  
  8.     # дуги входящие в вершину - vert. Возвращает список ключей(дуг) которые входят в вершину vert
  9.     def _arcs_that_enter_the_vertex(self, vert):
  10.         val = list(self.weight_of_all_arcs.keys()) #список всех дуг
  11.         list_arcs = [] #список дуг входящие в вершину
  12.         for arc in val:
  13.             if arc[1] == vert:
  14.                 list_arcs.append(arc)
  15.         return list_arcs
  16.  
  17.     # дуги выходящие из вершины - vert. Возвращает список ключей(дуг) которые выходят из вершины vert
  18.     def _arcs_coming_out_of_a_vertex(self, vert):
  19.         val = list(self.weight_of_all_arcs.keys()) #список всех дуг
  20.         list_arcs = [] #список дуг выходящих из вершины
  21.         for arc in val:
  22.             if arc[0] == vert:
  23.                 list_arcs.append(arc)
  24.         return list_arcs
  25.  
  26.  
  27. #Класс Сетевой график. Поиск критического пути
  28. class Network_diagram():
  29.     def __init__(self, Graph):
  30.         self.Graph = Graph # наследуем класс Graph
  31.         self.temp_tp = [0 for i in range(self.Graph.number_of_vertices)] #раннее время наступления событий
  32.         self.temp_tn = [0 for i in range(self.Graph.number_of_vertices)] #позднее время наступления событий
  33.  
  34. #Вычисление ранего времени наступления событий
  35.     def _tp(self):
  36.         for vertic in range(self.Graph.number_of_vertices): # Прогонка по вершинам
  37.             # метод класса Graph который возвращает дуги входящие в вершину vertic
  38.             atetv = self.Graph._arcs_that_enter_the_vertex(vertic)
  39.             #если в вершину не входит дуга, тогда это начальная вершина время возникновения событий для которой будет = 0
  40.             if len(atetv) == 0:
  41.                 self.temp_tp[vertic] = 0
  42.             #если в вершину входит 1 дуга, тогда в хранение времени возникновения событий для вершин внесем вес этой дуги + вес вершины
  43.             elif len(atetv) == 1:
  44.                 self.temp_tp[vertic] = self.Graph.weight_of_all_arcs[atetv[0]] + self.temp_tp[atetv[0][0]] #нулевой индекс так как atetv является списком
  45.             else:
  46.                 self.maxTP(atetv)
  47.         return(self.temp_tp)
  48.  
  49.     def maxTP(self, atetv):
  50.         max = 0
  51.         for i in range(len(atetv)):
  52.             if max < self.temp_tp[atetv[i][0]] + self.Graph.weight_of_all_arcs[atetv[i]]:
  53.                 max = self.temp_tp[atetv[i][0]] + self.Graph.weight_of_all_arcs[atetv[i]]
  54.         self.temp_tp[atetv[i][1]] = max
  55.  
  56. #Вычисление позднего времени наступления событий
  57.     def _tn(self):
  58.         for vertic in range(self.Graph.number_of_vertices): # Прогонка по вершинам
  59.             v = self.Graph.number_of_vertices - (vertic + 1)
  60.             # метод класса Graph который возвращает дуги выходящие из вершины v
  61.             acooav = self.Graph._arcs_coming_out_of_a_vertex(v)
  62.             #если из вершины не выходит дуга, тогда это начальная вершина время возникновения событий для которой будет равно последнему TP
  63.             if len(acooav) == 0:
  64.                 self.temp_tn[v] = self.temp_tp[-1]
  65.             #если из вершины выходит 1 дуга, тогда в хранение времени возникновения событий для вершин внесем (вес вершины - вес этой дуги)
  66.             elif len(acooav) == 1:
  67.                 self.temp_tn[v] = self.temp_tn[acooav[0][1]] - self.Graph.weight_of_all_arcs[acooav[0]]
  68.             else:
  69.                 self.minTN(acooav)
  70.         return(self.temp_tn)
  71.  
  72.     def minTN(self, acooav):
  73.         min = None
  74.         for i in range(len(acooav)):
  75.             if min == None:
  76.                 min = self.temp_tn[acooav[i][1]] - self.Graph.weight_of_all_arcs[acooav[i]]
  77.             if min > self.temp_tn[acooav[i][1]] - self.Graph.weight_of_all_arcs[acooav[i]]:
  78.                 min = self.temp_tn[acooav[i][1]] - self.Graph.weight_of_all_arcs[acooav[i]]
  79.         self.temp_tn[acooav[i][0]] = min
  80.  
  81. #Резервы времени событий
  82.     def _event_time_reserves(self):
  83.         self.event_time_reserves = []
  84.         for i in range(self.Graph.number_of_vertices):
  85.             self.event_time_reserves.append(self.temp_tn[i] - self.temp_tp[i])
  86.         return self.event_time_reserves
  87.  
  88. #В критический путь не входят события
  89.     def _event_are_not_includes(self):
  90.         list_event = []
  91.         for etr in range(len(self.event_time_reserves)):
  92.             if self.event_time_reserves[etr] != 0 :
  93.                 list_event.append(etr)
  94.         return list_event
  95.  
  96. #Полные резервы времени работ
  97.     def _full_reserves_of_work_time(self):
  98.         self.full_reserves_of_work_time = {}
  99.         for arc in self.Graph.weight_of_all_arcs.keys():
  100.             self.full_reserves_of_work_time[arc] = (self.temp_tn[arc[1]] - self.temp_tp[arc[0]] - self.Graph.weight_of_all_arcs[arc])
  101.         return self.full_reserves_of_work_time
  102.  
  103. #Критический путь
  104.     def _critical_path(self):
  105.         self.critical_path = []
  106.         for frowt in self.full_reserves_of_work_time:
  107.             if self.full_reserves_of_work_time[frowt] == 0:
  108.                 self.critical_path.append(frowt[0])
  109.                 last = frowt[1]
  110.         self.critical_path.append(last)
  111.         return self.critical_path
  112. #-------------------------------------------------------------------------------
  113. #-------------------------------------------------------------------------------
  114. #-------------------------------------------------------------------------------
  115. #Примеры графов
  116. g = Graph( 9, { (0,1):4, (0,2):3, (0,3):5, (1,4):3,
  117.                 (2,4):6, (2,5):8, (3,4):2, (3,6):8,
  118.                 (4,5):6, (5,7):5, (6,7):3, (7,8):6
  119.               }
  120.          )
  121. g2 = Graph( 8, { (0,1):4, (1,2):3, (1,3):8, (2,4):10,
  122.                 (2,5):4, (3,4):12, (4,5):7, (4,6):4,
  123.                 (5,6):2, (6,7):3
  124.               }
  125.          )
  126. #-------------------------------------------------------------------------------
  127.  
  128. ND = Network_diagram(g2)
  129. print("раннее время наступления событий - ", ND._tp())
  130. print("позднее время наступления событий - ", ND._tn())
  131. print("Резервы времени событий - ", ND._event_time_reserves())
  132. print("В критический путь не входят события", ND._event_are_not_includes())
  133. print("Полные резервы времени работ",ND._full_reserves_of_work_time())
  134. print("Критический путь", ND._critical_path())
  135.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement