SHARE
TWEET

Untitled

a guest Nov 9th, 2019 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def read_graph():
  2.     j = 1
  3.     all_edges = {}
  4.     d = {}
  5.     with open('graph_input.txt', 'r') as input_graph:
  6.         for line in input_graph:
  7.             from re import split
  8.             edges = split('\)\,\(', line)
  9.             max = 0
  10.             for i in range(len(edges)):
  11.                 if i != 0:
  12.                     if max < int(edges[i][0]):
  13.                         max = int(edges[i][0])
  14.                     if max < int(edges[i][2]):
  15.                         max = int(edges[i][2])
  16.                 else:
  17.                     if max < int(edges[i][1]):
  18.                         max = int(edges[i][1])
  19.                     if max < int(edges[i][3]):
  20.                         max = int(edges[i][3])
  21.             mas = [0] * max
  22.             old = [0] * max
  23.             for i in range(len(edges)):
  24.                 if i == 0:
  25.                     edges[i] = edges[i][1:]
  26.                 elif i == len(edges) - 1:
  27.                     edges[i] = edges[i][:len(edges[i]) - 1]
  28.                 try:
  29.                     splitted_edge = edges[i].split(',')
  30.                     edge = (splitted_edge[0], splitted_edge[1], int(splitted_edge[2]))
  31.                     if len(edge) != 3 or edge[2] <= 0:
  32.                         print('Строка {} в описании графа: введены неправильные параметры'.format(str(j)))
  33.                         exit()
  34.                 except:
  35.                     print('Строка {} в описании графа: введены неправильные параметры'.format(str(j)))
  36.                     exit()
  37.                 if edge[0] not in all_edges:
  38.                     all_edges[edge[0]] = []
  39.                     d[edge[0]] = [1, 0]
  40.                 else:
  41.                     d[edge[0]][0] += 1
  42.                 for item in all_edges[edge[0]]:
  43.                     if item[1] == edge[1]:
  44.                         print(
  45.                             'Строка {} в описании графа: введены неправильные параметры, дуга в такую вершину уже существует'.format(
  46.                                 str(j)))
  47.                         exit()
  48.                 if old[int(edge[1]) - 1] + 1 != edge[2]:
  49.                     print('Строка {}: введены неправильные параметры'.format(str(j)))
  50.                     exit()
  51.                 mas[int(edge[0]) - 1] += 1
  52.                 old[int(edge[1]) - 1] = edge[2]
  53.                 all_edges[edge[0]].append([mas[int(edge[0]) - 1], edge[1]])
  54.                 if edge[1] not in all_edges:
  55.                     all_edges[edge[1]] = []
  56.                     d[edge[1]] = [0, 1]
  57.                 else:
  58.                     d[edge[1]][1] += 1
  59.             j += 1
  60.     return all_edges, d
  61.  
  62.  
  63. def read_operations(all_edges):
  64.     operations = {}
  65.     available_operations = ['+', '*', 'exp']
  66.     j = 1
  67.     with open('vertex_operations.txt', 'r') as input_operations:
  68.         for line in input_operations:
  69.             line = line[:(len(line) - 1)]
  70.             pos = line.find(':')
  71.             if pos == -1:
  72.                 print('Строка {} в описании операций: введены неправильные параметры, неправильныйформат'.format(str(j)))
  73.                 exit()
  74.             vertex = str(line[:pos])
  75.             if vertex not in all_edges:
  76.                 print('Строка {} в описании операций: введены неправильные параметры, такой вершины нет'.format(str(j)))
  77.                 exit()
  78.             operation = str(line[(pos + 1):])
  79.             try:
  80.                 if operation not in available_operations:
  81.                     operations[vertex] = int(operation)
  82.                 else:
  83.                     operations[vertex] = operation
  84.             except:
  85.                 print('Строка {} в описании операций: введены неправильные параметры'.format(str(j)))
  86.                 exit()
  87.             j += 1
  88.     return operations
  89.  
  90.  
  91. def transform_graph(all_edges):
  92.     transformed_graph = {}
  93.     for vertex in all_edges.keys():
  94.         transformed_graph[vertex] = []
  95.         all_edges[vertex].sort(key=lambda x: x[0])
  96.         for i in range(len(all_edges[vertex])):
  97.             if i == 0:
  98.                 if all_edges[vertex][i][0] != 1:
  99.                     print('Введены неправильные параметры, первый порядковый номер дуги должен быть равен 1')
  100.                     exit()
  101.                 transformed_graph[vertex].append(all_edges[vertex][i][1])
  102.             else:
  103.                 if all_edges[vertex][i][0] - all_edges[vertex][i - 1][0] != 1:
  104.                     print('Введены неправильные параметры, разница между порядковыми номерам дуг должна равняться 1')
  105.                     exit()
  106.                 transformed_graph[vertex].append(all_edges[vertex][i][1])
  107.     return transformed_graph
  108.  
  109.  
  110. def dfs_check(v, graph, visited, parts):
  111.     visited[v] = True
  112.     dfs_graph = {v: []}
  113.     for vertex in graph[v]:
  114.         if vertex not in visited:
  115.             dfs_graph[v].append(dfs_check(vertex, graph, visited, parts))
  116.         else:
  117.             if vertex not in parts:
  118.                 print('Найден цикл между вершинами {} и {}'.format(str(v), str(vertex)))
  119.                 exit()
  120.             else:
  121.                 dfs_graph[v].append({vertex: parts[vertex]})
  122.     parts[v] = dfs_graph[v]
  123.     return dfs_graph
  124.  
  125.  
  126. def check_cycle(graph, d):
  127.     started_vertex = []
  128.     for vertex in d:
  129.         if d[vertex][1] == 0:
  130.             started_vertex.append(vertex)
  131.     parts = {}
  132.     visited = {}
  133.     for vertex in started_vertex:
  134.         dfs_check(vertex, graph, visited, parts)
  135.  
  136.  
  137. def reverse_graph(graph):
  138.     reversed_graph = {}
  139.     for u in sorted(graph.keys()):
  140.         for v in graph[u]:
  141.             if u not in reversed_graph:
  142.                 reversed_graph[u] = []
  143.             if v not in reversed_graph:
  144.                 reversed_graph[v] = []
  145.             reversed_graph[v].append(u)
  146.     return reversed_graph
  147.  
  148.  
  149. def correct_operations(graph, operations):
  150.     for v in graph.keys():
  151.         try:
  152.             if type(operations[v]) == int:
  153.                 if len(graph[v]) == 0:
  154.                     continue
  155.                 raise Exception
  156.             elif operations[v] == '+' or operations[v] == '*':
  157.                 if len(graph[v]) >= 2:
  158.                     continue
  159.                 raise Exception
  160.             elif operations[v] == 'exp':
  161.                 if len(graph[v]) == 1:
  162.                     continue
  163.                 raise Exception
  164.         except:
  165.             print('Такой операции не существует, или несоответствие операции вершине')
  166.             exit()
  167.  
  168.  
  169. def dfs_function(v, graph, operations, visited, function_graph, expressions, values):
  170.     visited[v] = True
  171.     new_function_graph = {v: str(v)}
  172.     new_values = {v: -1}
  173.     new_expressions = {v: str(operations[v])}
  174.     if type(operations[v]) == int:
  175.         new_values[v] = operations[v]
  176.     elif operations[v] == '+':
  177.         new_values[v] = 0
  178.     elif operations[v] == '*' or operations[v] == 'exp':
  179.         new_values[v] = 1
  180.     if not len(graph[v]):
  181.         function_graph[v] = new_function_graph[v]
  182.         values[v] = new_values[v]
  183.         expressions[v] = new_expressions[v]
  184.         return function_graph, values, expressions
  185.     new_function_graph[v] += '('
  186.     new_expressions[v] += '('
  187.     for vertex in graph[v]:
  188.         if vertex not in visited:
  189.             f, val, e = dfs_function(vertex, graph, operations, visited, function_graph, expressions, values)
  190.             new_function_graph[v] += str(f[vertex]) + ','
  191.             new_expressions[v] += str(e[vertex]) + ','
  192.             if operations[v] == '+':
  193.                 new_values[v] += val[vertex]
  194.             elif operations[v] == '*':
  195.                 new_values[v] *= val[vertex]
  196.             elif operations[v] == 'exp':
  197.                 from math import exp
  198.                 new_values[v] = exp(val[vertex])
  199.         else:
  200.             new_function_graph[v] += function_graph[vertex] + ','
  201.             new_expressions[v] += expressions[vertex] + ','
  202.             if operations[v] == '+':
  203.                 new_values[v] += values[vertex]
  204.             elif operations[v] == '*':
  205.                 new_values[v] *= values[vertex]
  206.             elif operations[v] == 'exp':
  207.                 from math import exp
  208.                 new_values[v] = exp(values[vertex])
  209.     function_graph[v] = new_function_graph[v] + ')'
  210.     values[v] = new_values[v]
  211.     expressions[v] = new_expressions[v] + ')'
  212.     return function_graph, values, expressions
  213.  
  214.  
  215. def construct_graph(graph, started_vertex, operations):
  216.     constructed_graph = {}
  217.     constructed_exp = {}
  218.     visited = {}
  219.     function_graph = {}
  220.     expressions = {}
  221.     values = {}
  222.     for v in started_vertex:
  223.         dfs_function(v, graph, operations, visited, function_graph, expressions, values)
  224.         returned_str = function_graph[v]
  225.         for i in range(len(returned_str)):
  226.             if i + 1 < len(returned_str) and returned_str[i] == ',' and returned_str[i + 1] == ')':
  227.                 returned_str = returned_str[:i] + returned_str[i + 1:]
  228.         constructed_graph[v] = returned_str
  229.         returned_expression = expressions[v]
  230.         for i in range(len(returned_expression)):
  231.             if i + 1 < len(returned_expression) and returned_expression[i] == ',' and returned_expression[i + 1] == ')':
  232.                 returned_expression = returned_expression[:i] + returned_expression[i + 1:]
  233.         constructed_exp[v] = returned_expression
  234.     return constructed_graph, values, constructed_exp
  235.  
  236.  
  237. def write_to_txt(constructed_graph, values, expressions, started_vertex):
  238.     with open('graph_function.txt', 'w', encoding='utf-8') as graph_function:
  239.         function = ",".join(constructed_graph[item] for item in constructed_graph)
  240.         graph_function.write(function + '\n')
  241.         for v in started_vertex:
  242.             graph_function.write(
  243.                 'Значение в вершине {}: {} = {} = {}\n'.format(v, str(constructed_graph[v]), str(expressions[v]),
  244.                                                                str(values[v])))
  245.  
  246.  
  247. if __name__ == '__main__':
  248.     all_edges, d = read_graph()
  249.     operations = read_operations(all_edges)
  250.     graph = transform_graph(all_edges)
  251.     check_cycle(graph, d)
  252.     started_vertex = []
  253.     for v in graph:
  254.         if not len(graph[v]):
  255.             started_vertex.append(v)
  256.     reversed_graph = reverse_graph(graph)
  257.     correct_operations(reversed_graph, operations)
  258.     constructed_graph, values, expressions = construct_graph(reversed_graph, started_vertex, operations)
  259.     write_to_txt(constructed_graph, values, expressions, started_vertex)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top