ЛР / ЛР1 / ПиАГМ ЛР1

Список использованных источников

1)Методические указания по практической работе 1,

«Представление графов в ЭВМ» – СПб: ГУАП, 2022

31

ПРИЛОЖЕНИЕ A. Код программы

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))]

#создание списка ребер графа

#находим по матрице смежности № и веса вершин детей, родителей и соседей

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])

32

, *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):

#добавление идентификаторов и меток к вершинам for i in range(len(g.vs)):

g.vs[i]["id"]= i g.vs[i]["label"]= peaks[i]

#получаем список ребер и их веса

,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 - ответ, образует ли заданная последовательность вершин

33

цепь; 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

34

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)):

35

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:

36

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

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)

37

последовательность вершин образует цепь.')

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)

последовательность вершин образует цепь.')

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))

38

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)

39

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,)),

peaks = ['Pavel I', 'Aleksandr I', 'Nikolai I', 'Aleksandr II', 'Aleksandr III', 'Nikolai II', 'Petr III', 'Ekaterina II']

40