ЛР / ЛР1 / graph_LR1

import igraph as ig
import pandas as pd
import sys
import time


# проверка ввода матрицы смежност
def adjacency_matrix_check(adj_mat):
if len(adj_mat)**2 != sum([len(row) for row in adj_mat]):
return 'Ошибка: !Кол-во строк и столбцов матрицы смежности не равно!'
return True

# построение СПИСОКА РЕБЕР по матрице смежности
def get_list_edges_by_adjacency_matrix(adj_mat, peaks = [], view = True):
test = adjacency_matrix_check(adj_mat)
if test != True: return test
# проверка матрицы смежности
if not peaks:
peaks = [str(i) for i in range(len(adj_mat))]
# создание списка ребер графа
list_edges = []
for row in range(len(adj_mat)):
for col in range(len(adj_mat[row])):
if adj_mat[row][col] != 0:
if view: list_edges.append((((row ,peaks[row]), (col ,peaks[col])), adj_mat[row][col]))
else: list_edges.append(str(peaks[row]) + ' -> ' + str(peaks[col]) + ': ' + str(adj_mat[row][col])) # другое передставление ребер
return list_edges


# представление графа в виде МАССИВА ЗАПИСЕЙ
def get_array_of_graph_information(adj_mat, peaks):
info = []
for row in range(len(adj_mat)):
# находим по матрице смежности № и веса вершин детей, родителей и соседей
children = [(i, adj_mat[row][i]) for i in range(len(adj_mat[row])) if adj_mat[row][i] != 0]
parents = [(i, adj_mat[i][row]) for i in range(len(adj_mat)) if adj_mat[i][row] != 0]
neighbours = tuple(set(children + parents))
# находим необходимые значения по полученным спискам вершин
info.append([row
, peaks[row]
, *tuple(len(i) for i in [children, parents, neighbours])
, *tuple(tuple([j[0] for j in i]) for i in [children, parents, neighbours])
, *tuple(tuple([j[1] for j in i]) for i in [children, parents, neighbours])
])
col_name = ['№ вершины', 'Подпись вершины', 'Кол-во детей', 'Кол-во родителей'
, 'Кол-во соседей', '№ вершин детей', '№ вершин родителей'
, '№ вершин соседей', 'Веса исходящих', 'Веса входящих', 'Веса инцидентных ребер']
g_info = pd.DataFrame(info, columns=col_name)
return g_info


# Рисует график по МАТРИЦЕ СМЕЖНОСТИ
def view_graph(adj_mat, peaks, curved_value = False):
g = ig.Graph(directed=True) # создание ориентированного графа
g.add_vertices(len(peaks)) # добавление вершин графа

# добавление идентификаторов и меток к вершинам
for i in range(len(g.vs)):
g.vs[i]["id"]= i
g.vs[i]["label"]= peaks[i]

# получаем список ребер и их веса
list_edges = get_list_edges_by_adjacency_matrix(adj_mat, peaks)
# задаем ребра
g.add_edges([(edge[0][0][0], edge[0][1][0]) for edge in list_edges])
# задаем веса ребер
weights = [edge[1] for edge in list_edges]
g.es['label'] = weights
g.es['edge_width'] = weights

g.es["curved"] = curved_value

ig.plot(g, bbox = (350,350) # построение графика
, margin = 30
, vertex_label_size = 10
, vertex_size = 55
, vertex_color = 'white')
return 1


# Запрос номера вопроса
def get_question_number():
while 1:
question = input('''\nНайти:
1 - всех соседей заданной вершины графа;
2 - ответ, образует ли заданная последовательность вершин цепь;
3 - номера вершин, сумма весов инцидентных ребер которых больше заданной величины;
4 - количество ребер в графе;
Q - Выход.

Введите номер: ''')
if question.isdigit():
question = int(question)
if question in range(1,5): return question
else: print('\n!Указан не существующй номер вопроса! Повторите ввод.')
elif question.upper() == 'Q':
return -1
else: print('\n!Команда не найдена! Повторите ввод.')

# запрос и проверка корректности ввода вершины для поиска
def get_peaks_for_search(peaks):
peaks_up = [i.upper() for i in peaks]
while 1:
top = input('\nЗадайте вершину для поиска соседей:\n\t- из списка: ('+', '.join(str(i) for i in peaks)
+ ')\n\t- по номеру: от 0 до ' + str(len(peaks)-1)
+ '\n\t- Q для выхода' + '\nВведите вершину: ').upper()
if top in peaks_up:
top = peaks_up.index(top)
break
if top.isdigit():
top = int(top)
if top in range(len(peaks)):
break
else: print('\n!Вершины с указанным номером не существует! Повторите ввод.')
elif top == 'Q':
return -1
else: print('\n!Вершины с указанным названием не существует! Повторите ввод.')
return top

# запрос списка вершин графа
def get_peaks_for_chain(peaks):
while 1:
chain_peaks = input('\nЗадайте список вершин (по номерам от 0 до ' + str(len(peaks)-1)
+ ' через пробел) для проверки, образует ли заданная последовательность вершин цепь.'
+ '\n\t- Q для выхода' + '\nВведите вершины: ').split()
if all(map(lambda x: x.isdigit(), chain_peaks)):
chain_peaks = list(map(int, chain_peaks))
if set(chain_peaks).issubset(range(len(peaks))):
break
elif chain_peaks[0].upper() == 'Q':
return -1
print('\n!Указаны не существующие номера вершин! Повторите ввод.')
return chain_peaks

# запрос и проверка корректности ввода вершины для поиска
def get_value_for_search():
while 1:
value = input('\nЗадайте значение для сравнения: ').upper()
if value.isdigit():
return int(value)
elif value == 'Q':
return -1
else: print('\n!Введено неверное значение! Повторите ввод.')


# возвращает соседей указанной вершины по заданной МАТРИЦЕ СМЕЖНОСТИ
def get_neighbours_by_adj_mat(adj_mat, peaks, top):
children = [(i, peaks[i]) for i in range(len(adj_mat)) if adj_mat[top][i] != 0]
parents = [(i, peaks[i]) for i in range(len(adj_mat)) if adj_mat[i][top] != 0]
return tuple(set(children + parents))

# возвращает соседей указанной вершины по заданному СПИСОКУ РЕБЕР
def get_neighbours_by_l_edg(top, l_edg):
return tuple(set(i[0][1] if i[0][0][0] == top else i[0][0] for i in l_edg if i[0][0][0] == top or i[0][1][0] == top))

# возвращает соседей указанной вершины по заданному МАССИВУ ЗАПИСЕЙ
def get_neighbours_by_graph_info(top, g_info, peaks):
return tuple((i, peaks[i]) for i in g_info['№ вершин соседей'][top])


# проверка вершин на цепь в передставлении графа МАТРИЦА СМЕЖНОСТИ
def get_chain_answer_by_adj_mat(adj, peaks_num):
if len(peaks_num) == 1: return True
for i in range(1, len(peaks_num)):
if adj[peaks_num[i-1]][peaks_num[i]] == 0: return False
return True

# проверка вершин на цепь в передставлении графа СПИСОК РЕБЕР
def get_chain_answer_by_l_edg(l_edg, peaks_num):
if len(peaks_num) == 1: return True
temp_l_edg = [[j[0][1][0] for j in l_edg if j[0][0][0] == i] for i in peaks_num]
for i in range(1, len(peaks_num)):
if peaks_num[i] not in temp_l_edg[i-1]: return False
return True

# проверка вершин на цепь в МАССИВ ЗАПИСЕЙ
def get_chain_answer_by_graph_info(g_info, peaks_num):
if len(peaks_num) == 1: return True
for i in range(1, len(peaks_num)):
if peaks_num[i] not in g_info['№ вершин детей'][peaks_num[i-1]]: return False
return True


# номера вершин, сумма весов инцидентных ребер которых больше заданной величины в передставлении графа МАТРИЦА СМЕЖНОСТИ
def get_peaks_weight_more_value_by_adj_mat(adj_mat, value):
return [i for i in range(len(adj_mat)) if sum([col for col in adj_mat[i]]+[row[i] for row in adj_mat]) > value]

# номера вершин, сумма весов инцидентных ребер которых больше заданной величины в передставлении графа СПИСОК РЕБЕР
def get_peaks_weight_more_value_by_l_edg(peaks, l_edg, value):
return [i for i in range(len(peaks)) if sum([j[1] for j in l_edg if j[0][0][0] == i or j[0][1][0] == i]) > value]

# номера вершин, сумма весов инцидентных ребер которых больше заданной величины в передставлении графа МАССИВ ЗАПИСЕЙ
def get_peaks_weight_more_value_by_graph_info(peaks, g_info, value):
return [i for i in range(len(peaks)) if sum(g_info['Веса инцидентных ребер'][i]) > value]


# определение кол-ва ребер в передставлении графа МАТРИЦА СМЕЖНОСТИ
def get_edge_count_by_adj_mat(adj_mat):
return sum([sum([1 for j in i if j != 0]) for i in adj_mat])

# определение кол-ва ребер в передставлении графа СПИСОК РЕБЕР
def get_edge_count_by_l_edg(l_edg):
return len(l_edg)

# определение кол-ва ребер в передставлении графа МАССИВ ЗАПИСЕЙ
def get_edge_count_by_graph_info(g_info):
return g_info['Кол-во детей'].sum()


# поиск в МАТРИЦЕ СМЕЖНОСТИ
def search_in_views_by_adj_mat(adj_mat, peaks):

while 1:
question = get_question_number()

match question:
case 1: # 1 - всех соседей заданной вершины графа;
top = get_peaks_for_search(peaks)
if top == -1: continue
print('\nСоседи вершины №', top, '(', peaks[top], '):', get_neighbours_by_adj_mat(adj_mat, peaks, top))

case 2: # 2 - ответ, образует ли заданная последовательность вершин цепь;
peaks_num = get_peaks_for_chain(peaks)
if peaks_num == -1: continue

chain_answer = get_chain_answer_by_adj_mat(adj_mat, peaks_num)
if chain_answer: print('\nЗаданная последовательность вершин образует цепь.')
else: print('\nЗаданная последовательность вершин не образует цепь.')

case 3: # 3 - номера вершин, сумма весов инцидентных ребер которых больше заданной величины;
value = get_value_for_search()
if value == -1: continue
print('\nНомера вершин, сумма весов инцедентных ребер, которых больше', value, ':', *get_peaks_weight_more_value_by_adj_mat(adj_mat, value))

case 4: # 4 - количество ребер в графе;
print('\nВ графе', get_edge_count_by_adj_mat(adj_mat), 'ребер.')

case -1:
return -1
return -2

# поиск в СПИСОК РЕБЕР
def search_in_views_by_list_edges(l_edg, peaks):
while 1:
question = get_question_number()

match question:
case 1: # 1 - всех соседей заданной вершины графа;
top = get_peaks_for_search(peaks)
if top == -1: continue
print('\nСоседи вершины №', top, '(', peaks[top], '):', get_neighbours_by_l_edg(top, l_edg))

case 2: # 2 - ответ, образует ли заданная последовательность вершин цепь;
peaks_num = get_peaks_for_chain(peaks)
if peaks_num == -1: continue
chain_answer = get_chain_answer_by_l_edg(l_edg, peaks_num)
if chain_answer: print('\nЗаданная последовательность вершин образует цепь.')
else: print('\nЗаданная последовательность вершин не образует цепь.')

case 3: # 3 - номера вершин, сумма весов инцидентных ребер которых больше заданной величины;
value = get_value_for_search()
if value == -1: continue
print('\nНомера вершин, сумма весов инцедентных ребер, которых больше'
, value, ':', *get_peaks_weight_more_value_by_l_edg(peaks, l_edg, value))

case 4: # 4 - количество ребер в графе;
print('\nВ графе', get_edge_count_by_l_edg(l_edg), 'ребер.')

case -1:
return -1
return -2

# поиск в МАССИВ ЗАПИСЕЙ
def search_in_views_by_graph_mat(g_info, peaks):
while 1:
question = get_question_number()

match question:
case 1: # 1 - всех соседей заданной вершины графа;
top = get_peaks_for_search(peaks)
if top == -1: continue
print('\nСоседи вершины №', top, '(', peaks[top], '):', get_neighbours_by_graph_info(top, g_info, peaks))

case 2: # 2 - ответ, образует ли заданная последовательность вершин цепь;
peaks_num = get_peaks_for_chain(peaks)
if peaks_num == -1: continue
chain_answer = get_chain_answer_by_graph_info(g_info, peaks_num)
if chain_answer: print('\nЗаданная последовательность вершин образует цепь.')
else: print('\nЗаданная последовательность вершин не образует цепь.')

case 3: # 3 - номера вершин, сумма весов инцидентных ребер которых больше заданной величины;
value = get_value_for_search()
if value == -1: continue
print('\nНомера вершин, сумма весов инцедентных ребер, которых больше', value
, ':', *get_peaks_weight_more_value_by_graph_info(peaks, g_info, value))

case 4: # 4 - количество ребер в графе;
print('\nВ графе', get_edge_count_by_graph_info(g_info), 'ребер.')

case -1:
return -1
return -2

# поиск в разных представлениях графа
def search_in_views(adj_mat, peaks, l_edg = [], g_info = []):
while 1:
num = input('''\n
Выберете представление для поиска:
1 - матрица смежности;
2 - список ребер;
3 - массив записей;
Q - Выход.
Введите номер: ''')

match num.upper():
case '1':
print('', pd.DataFrame(adj_mat, columns=peaks, index=peaks), sep='\n')
search_in_views_by_adj_mat(adj_mat, peaks)

case '2':
if l_edg == [] or isinstance(l_edg[0], str): l_edg = get_list_edges_by_adjacency_matrix(adj_mat, peaks)
print('', *l_edg, sep='\n')
search_in_views_by_list_edges(l_edg, peaks)

case '3':
if g_info == []: g_info = get_array_of_graph_information(adj_mat, peaks)
print('\n', g_info)
search_in_views_by_graph_mat(g_info, peaks)

case 'Q':
break
case _:
print('\n!Команда не найдена! Повторите ввод.')
return -2


# узнать размер представлений графа
def view_objects_size(adja_mat, l_edg, g_info):
info = '\nРазмер представлений:\n\t- матрица смежности: ' + str(sys.getsizeof(adja_mat)) +\
' байт;\n\t- список ребер: ' + str(sys.getsizeof(l_edg)) +\
' байт;\n\t- массив записей: ' + str(sys.getsizeof(g_info)) + ' байт.'
print(info)
return info


# тест времени работы функций пункта 4
def func_time_test(adj_mat, l_edg, g_info, peaks):
view = ('в представлении графа матрица смежности'
, 'в представлении графа список ребер'
, 'в представлении графа массив записей')
fun_name = ('поиска соседей'
, 'проверки последовательности вершин на образование цепи'
, 'поиска вершин, сумма инцедентных ребер которых больше заданного числа'
, 'определения кол-ва ребер')
fun = (
(get_neighbours_by_adj_mat, (adj_mat, peaks, 6)),
(get_neighbours_by_l_edg, (6, l_edg)),
(get_neighbours_by_graph_info, (6, g_info, peaks)),

(get_chain_answer_by_adj_mat, (adj_mat, (5, 6, 7, 0, 1))),
(get_chain_answer_by_l_edg, (l_edg, (5, 6, 7, 0, 1))),
(get_chain_answer_by_graph_info, (g_info, (5, 6, 7, 0, 1))),

(get_peaks_weight_more_value_by_adj_mat, (adj_mat, 16)),
(get_peaks_weight_more_value_by_l_edg, (peaks, l_edg, 16)),
(get_peaks_weight_more_value_by_graph_info, (peaks, g_info, 16)),

(get_edge_count_by_adj_mat, (adj_mat,)),
(get_edge_count_by_l_edg, (l_edg,)),
(get_edge_count_by_graph_info, (g_info,)),
)

for f in range(len(fun)):
print('\nФункция', fun[f][0].__name__, fun_name[f // 3], view[f % 3])
start_time = time.time()
for iter in range(10**6): fun[f][0](*fun[f][1])
end_time = (time.time() - start_time)
print('\tВремя выполнения функции 10^6 раз:' , round(end_time, 3), 'секунд')
print('\tСреднее время одного выполнения функции:' , round(end_time / 10**6, 8), 'секунд')


# Меню вызова подпрограмм
def menu():
# 0 1 2 3 4 5 6 7
peaks = ['Pavel I', 'Aleksandr I', 'Nikolai I', 'Aleksandr II', 'Aleksandr III', 'Nikolai II', 'Petr III', 'Ekaterina II']
adjacency_matrix = [[0, 6, 6, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 7, 0, 0, 0, 0],
[0, 0, 0, 0, 8, 0, 2, 0],
[0, 0, 0, 0, 0, 9, 0, 0],
[0, 0, 0, 0, 0, 0, 2, 0],
[34, 0, 0, 0, 4, 0, 0, 4],
[5, 0, 0, 0, 0, 5, 0, 0]]
list_edges = get_list_edges_by_adjacency_matrix(adjacency_matrix, peaks)
graph_info = get_array_of_graph_information(adjacency_matrix, peaks)

while 1:
num = input('''
Выберете необходимое действие:
1 - построения списка ребер;
2 - визуализировать заданный граф;
3 - представить граф в виде массива записей;
4 - поиск в представлениях (матрица смежности, список ребер, массив записей);
5 - вывести размер объектов содержащего продставления графа (матрица смежности, список ребер, массив записей);
6 - тест скорости работы подпрограмм пункта 4;
Q - Выход.
Введите номер: ''')
# N - Задать свою матрицу смежности (строкой вида "[[1, ..., 2], ... [3, ..., 4]] ['Название вершины 1', ..., 'Название вершины N']")

match num.upper():
case '1':
print('', *get_list_edges_by_adjacency_matrix(adjacency_matrix, peaks, False), sep='\n')
case '2':
view_graph(adjacency_matrix, peaks)
case '3':
print(graph_info)
case '4':
search_in_views(adjacency_matrix, peaks, list_edges, graph_info)
case '5':
view_objects_size(adjacency_matrix, list_edges, graph_info)
case '6':
func_time_test(adjacency_matrix, list_edges, graph_info, peaks)

# case 'N':
# peaks = input('Задайте список вершин в виде ["Название вершины 1", ..., "Название вершины N"]')
# adjacency_matrix = input()

case 'Q':
break
case _:
print('\n!Команда не найдена! Повторите ввод.')


if __name__ == "__main__": menu()