Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def read_graph():
- j = 1
- all_edges = {}
- d = {}
- with open('graph_input.txt', 'r') as input_graph:
- for line in input_graph:
- from re import split
- edges = split('\)\,\(', line)
- max = 0
- for i in range(len(edges)):
- if i != 0:
- if max < int(edges[i][0]):
- max = int(edges[i][0])
- if max < int(edges[i][2]):
- max = int(edges[i][2])
- else:
- if max < int(edges[i][1]):
- max = int(edges[i][1])
- if max < int(edges[i][3]):
- max = int(edges[i][3])
- mas = [0] * max
- old = [0] * max
- for i in range(len(edges)):
- if i == 0:
- edges[i] = edges[i][1:]
- elif i == len(edges) - 1:
- edges[i] = edges[i][:len(edges[i]) - 1]
- try:
- splitted_edge = edges[i].split(',')
- edge = (splitted_edge[0], splitted_edge[1], int(splitted_edge[2]))
- if len(edge) != 3 or edge[2] <= 0:
- print('Строка {} в описании графа: введены неправильные параметры'.format(str(j)))
- exit()
- except:
- print('Строка {} в описании графа: введены неправильные параметры'.format(str(j)))
- exit()
- if edge[0] not in all_edges:
- all_edges[edge[0]] = []
- d[edge[0]] = [1, 0]
- else:
- d[edge[0]][0] += 1
- for item in all_edges[edge[0]]:
- if item[1] == edge[1]:
- print(
- 'Строка {} в описании графа: введены неправильные параметры, дуга в такую вершину уже существует'.format(
- str(j)))
- exit()
- if old[int(edge[1]) - 1] + 1 != edge[2]:
- print('Строка {}: введены неправильные параметры'.format(str(j)))
- exit()
- mas[int(edge[0]) - 1] += 1
- old[int(edge[1]) - 1] = edge[2]
- all_edges[edge[0]].append([mas[int(edge[0]) - 1], edge[1]])
- if edge[1] not in all_edges:
- all_edges[edge[1]] = []
- d[edge[1]] = [0, 1]
- else:
- d[edge[1]][1] += 1
- j += 1
- return all_edges, d
- def read_operations(all_edges):
- operations = {}
- available_operations = ['+', '*', 'exp']
- j = 1
- with open('vertex_operations.txt', 'r') as input_operations:
- for line in input_operations:
- line = line[:(len(line) - 1)]
- pos = line.find(':')
- if pos == -1:
- print('Строка {} в описании операций: введены неправильные параметры, неправильныйформат'.format(str(j)))
- exit()
- vertex = str(line[:pos])
- if vertex not in all_edges:
- print('Строка {} в описании операций: введены неправильные параметры, такой вершины нет'.format(str(j)))
- exit()
- operation = str(line[(pos + 1):])
- try:
- if operation not in available_operations:
- operations[vertex] = int(operation)
- else:
- operations[vertex] = operation
- except:
- print('Строка {} в описании операций: введены неправильные параметры'.format(str(j)))
- exit()
- j += 1
- return operations
- def transform_graph(all_edges):
- transformed_graph = {}
- for vertex in all_edges.keys():
- transformed_graph[vertex] = []
- all_edges[vertex].sort(key=lambda x: x[0])
- for i in range(len(all_edges[vertex])):
- if i == 0:
- if all_edges[vertex][i][0] != 1:
- print('Введены неправильные параметры, первый порядковый номер дуги должен быть равен 1')
- exit()
- transformed_graph[vertex].append(all_edges[vertex][i][1])
- else:
- if all_edges[vertex][i][0] - all_edges[vertex][i - 1][0] != 1:
- print('Введены неправильные параметры, разница между порядковыми номерам дуг должна равняться 1')
- exit()
- transformed_graph[vertex].append(all_edges[vertex][i][1])
- return transformed_graph
- def dfs_check(v, graph, visited, parts):
- visited[v] = True
- dfs_graph = {v: []}
- for vertex in graph[v]:
- if vertex not in visited:
- dfs_graph[v].append(dfs_check(vertex, graph, visited, parts))
- else:
- if vertex not in parts:
- print('Найден цикл между вершинами {} и {}'.format(str(v), str(vertex)))
- exit()
- else:
- dfs_graph[v].append({vertex: parts[vertex]})
- parts[v] = dfs_graph[v]
- return dfs_graph
- def check_cycle(graph, d):
- started_vertex = []
- for vertex in d:
- if d[vertex][1] == 0:
- started_vertex.append(vertex)
- parts = {}
- visited = {}
- for vertex in started_vertex:
- dfs_check(vertex, graph, visited, parts)
- def reverse_graph(graph):
- reversed_graph = {}
- for u in sorted(graph.keys()):
- for v in graph[u]:
- if u not in reversed_graph:
- reversed_graph[u] = []
- if v not in reversed_graph:
- reversed_graph[v] = []
- reversed_graph[v].append(u)
- return reversed_graph
- def correct_operations(graph, operations):
- for v in graph.keys():
- try:
- if type(operations[v]) == int:
- if len(graph[v]) == 0:
- continue
- raise Exception
- elif operations[v] == '+' or operations[v] == '*':
- if len(graph[v]) >= 2:
- continue
- raise Exception
- elif operations[v] == 'exp':
- if len(graph[v]) == 1:
- continue
- raise Exception
- except:
- print('Такой операции не существует, или несоответствие операции вершине')
- exit()
- def dfs_function(v, graph, operations, visited, function_graph, expressions, values):
- visited[v] = True
- new_function_graph = {v: str(v)}
- new_values = {v: -1}
- new_expressions = {v: str(operations[v])}
- if type(operations[v]) == int:
- new_values[v] = operations[v]
- elif operations[v] == '+':
- new_values[v] = 0
- elif operations[v] == '*' or operations[v] == 'exp':
- new_values[v] = 1
- if not len(graph[v]):
- function_graph[v] = new_function_graph[v]
- values[v] = new_values[v]
- expressions[v] = new_expressions[v]
- return function_graph, values, expressions
- new_function_graph[v] += '('
- new_expressions[v] += '('
- for vertex in graph[v]:
- if vertex not in visited:
- f, val, e = dfs_function(vertex, graph, operations, visited, function_graph, expressions, values)
- new_function_graph[v] += str(f[vertex]) + ','
- new_expressions[v] += str(e[vertex]) + ','
- if operations[v] == '+':
- new_values[v] += val[vertex]
- elif operations[v] == '*':
- new_values[v] *= val[vertex]
- elif operations[v] == 'exp':
- from math import exp
- new_values[v] = exp(val[vertex])
- else:
- new_function_graph[v] += function_graph[vertex] + ','
- new_expressions[v] += expressions[vertex] + ','
- if operations[v] == '+':
- new_values[v] += values[vertex]
- elif operations[v] == '*':
- new_values[v] *= values[vertex]
- elif operations[v] == 'exp':
- from math import exp
- new_values[v] = exp(values[vertex])
- function_graph[v] = new_function_graph[v] + ')'
- values[v] = new_values[v]
- expressions[v] = new_expressions[v] + ')'
- return function_graph, values, expressions
- def construct_graph(graph, started_vertex, operations):
- constructed_graph = {}
- constructed_exp = {}
- visited = {}
- function_graph = {}
- expressions = {}
- values = {}
- for v in started_vertex:
- dfs_function(v, graph, operations, visited, function_graph, expressions, values)
- returned_str = function_graph[v]
- for i in range(len(returned_str)):
- if i + 1 < len(returned_str) and returned_str[i] == ',' and returned_str[i + 1] == ')':
- returned_str = returned_str[:i] + returned_str[i + 1:]
- constructed_graph[v] = returned_str
- returned_expression = expressions[v]
- for i in range(len(returned_expression)):
- if i + 1 < len(returned_expression) and returned_expression[i] == ',' and returned_expression[i + 1] == ')':
- returned_expression = returned_expression[:i] + returned_expression[i + 1:]
- constructed_exp[v] = returned_expression
- return constructed_graph, values, constructed_exp
- def write_to_txt(constructed_graph, values, expressions, started_vertex):
- with open('graph_function.txt', 'w', encoding='utf-8') as graph_function:
- function = ",".join(constructed_graph[item] for item in constructed_graph)
- graph_function.write(function + '\n')
- for v in started_vertex:
- graph_function.write(
- 'Значение в вершине {}: {} = {} = {}\n'.format(v, str(constructed_graph[v]), str(expressions[v]),
- str(values[v])))
- if __name__ == '__main__':
- all_edges, d = read_graph()
- operations = read_operations(all_edges)
- graph = transform_graph(all_edges)
- check_cycle(graph, d)
- started_vertex = []
- for v in graph:
- if not len(graph[v]):
- started_vertex.append(v)
- reversed_graph = reverse_graph(graph)
- correct_operations(reversed_graph, operations)
- constructed_graph, values, expressions = construct_graph(reversed_graph, started_vertex, operations)
- write_to_txt(constructed_graph, values, expressions, started_vertex)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement