ГУАП
КАФЕДРА № 41
ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
ассистент |
|
|
|
М.Н. Шелест |
|
|
|
|
|
|
|
|
|
|
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №1
ПРЕДСТАВЛЕНИЕ ГРАФОВ В ЭВМ
по курсу: ПОСТРОЕНИЕ И АНАЛИЗ ГРАФОВЫХ МОДЕЛЕЙ
РАБОТУ ВЫПОЛНИЛ СТУДЕНТ ГР. №
подпись, дата |
|
инициалы, фамилия |
Санкт-Петербург 2022
Цель работы
Изучение представления графов в ЭВМ при помощи матрицы смежности, множества пар вершин и массива структур. Визуализация графов.
Индивидуальный вариант
Граф согласно индивидуальному варианту №10 в соответствии с рисунком 1.
Рисунок 1 – Граф индивидуального варианта
2
Ход работы
1)Матрица смежности в соответствии с рисунком 2.
Рисунок 2 – Матрица смежности
2) Ввели в ЭВМ матрицу смежности в явном виде. Код в соответствии с листингом 1. Листинг всей программы приведен в Приложении A. Код программы.
Листинг 1 – Матрица смежности в явном виде
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]]
3
3) Написали подпрограмму для построения списка ребер по заданной матрицы смежности. Код подпрограммы и вспомогательной подпрограммы для проверки введенной матрицы смежности в соответствии с листингами 2 – 3, списки использованных в подпрограммах переменных в соответствии с таблицами 1-2. Результат работы в соответствии с рисунком 3.
Таблица 1 – Список переменных подпрограммы из Листинга 2
Название |
Значение |
|
|
adj_mat |
Список значений матрицы смежности |
|
|
peaks |
Список названий вершин |
|
|
test |
Результат проверки матрицы смежности |
|
|
list_edges |
Список ребер графа |
|
|
row |
Итератор по строкам матрицы смежности |
|
|
col |
Итератор по значениям строки матрицы смежности |
|
|
Листинг 2 – Подпрограмма построения списка ребер
# построение списка ребер по матрице смежности
def list_edges_by_adjacency_matrix(adj_mat, peaks = []):
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: |
|
|
list_edges.append(((peaks[row],peaks[col]), |
|
adj_mat[row][col])) |
|
|
|
# list_edges.append([str(peaks[row]) + ' -> ' + |
|
str(peaks[col]) + ' = ' + str(adj_mat[row][col])]) |
# другое |
|
передставление |
ребер |
|
return list_edges |
|
4
Таблица 2 – Список переменных подпрограммы из Листинга 3
Название |
Значение |
adj_mat Список значений матрицы смежности
Листинг 3 – Подпрограмма проверка корректности ввода матрицы смежности
# проверка ввода матрицы смежност def adjacency_matrix_check(adj_mat):
if len(adj_mat)**2 != sum([len(row) for row in adj_mat]): return 'Ошибка: !Кол-во строк и столбцов матрицы
смежности не равно!' return True
Рисунок 3 – Результат работы подпрограммы построения списка ребер графа
5
4) Визуализировали заданный граф. Убедились в том, что он
совпадает с исходным графом. Код подпрограммы в соответствии с
листингом 4, |
список использованных переменных в соответствии с |
|
таблицей 3. Результат работы в соответствии с рисунком 4. |
||
Таблица 3 – Список переменных подпрограммы из Листинга 4 |
||
|
|
|
Название |
|
Значение |
|
|
|
adj_mat |
|
Список значений матрицы смежности |
|
|
|
peaks |
|
Список названий вершин |
|
|
|
g |
|
Объект igraph содержащий граф |
|
|
|
Листинг 4 – Подпрограмма построения графа
# Рисует график по матрице смежности |
|
def view_graph(adj_mat, peaks): |
|
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 = list_edges_by_adjacency_matrix(adj_mat, peaks)
# задаем ребра g.add_edges([(peaks.index(edge[0][0]),
peaks.index(edge[0][1])) 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"] = False
# построение графика ig.plot(g, bbox = (350,350)
,margin = 30
,vertex_label_size = 10
,vertex_size = 55
,vertex_color = 'white') return 1
6
Рисунок 4 – Результат работы подпрограммы построения графа
5) Написали подпрограмму, позволяющую представить граф в виде массива записей, основываясь на заданной матрице смежности. Каждой вершине графа соответствует запись. Вывели полученный массив записей в понятном пользователю виде таблица. Для создания таблицы записей использовали пакет pandas (в коде pd). Код подпрограммы в соответствии с листингом 5, список использованных переменных в соответствии с таблицей 4. Результат работы в соответствии с рисунком 4.
Таблица 4 – Список переменных подпрограммы из Листинга 5
Название |
Значение |
|
|
adj_mat |
Список значений матрицы смежности |
|
|
peaks |
Список названий вершин |
|
|
info |
Временный массив с информацией о графе |
|
|
row |
Итератор по номерам строк |
|
|
i, j |
Итератор для циклов |
|
|
children |
Список кортежей с номерами вершин и весами ребер детей |
|
конкретной вершины |
|
|
7
Название |
Значение |
|
|
parents |
Список кортежей с номерами вершин и весами ребер |
|
родителей конкретной вершины |
|
|
neighbours |
Список кортежей с номерами вершин и весами ребер соседней |
|
(инцидентных вершин) конкретной вершины |
|
|
col_name |
Список названий столбцов вершины |
|
|
g_info |
Датафрейм хранящий массив записей о графе |
|
|
Листинг 5 – Подпрограмма построения графа
# представление графа в виде массива записей
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) print(g_info)
return g_info
Рисунок 5 – Результат работы подпрограммы, представляющей граф в виде
8
массива записей
9
6)Для каждого из представлений (матрица смежности, список ребер,
массив записей) написали подпрограммы поиска и вывода на экран:
•всех соседей заданной вершины графа;
•ответа, образует ли заданная последовательность вершин цепь;
•номеров вершин, сумма весов инцидентных ребер которых больше заданной величины;
•количества ребер в графе.
Для каждой подпрограммы организовали диалог с пользователем
(запрос параметра – вывод результата). Данные для представления результатов выполнения данных подпрограмм подобрать самостоятельно.
Функция search_in_views для выбора представления графа для поиска.
Список использованных переменных в соответствии с таблицей 5, код в соответствии с листингом 6. Результат работы функций в соответствии с рисунком 6.
Таблица 5 – Список переменных подпрограммы из Листинга 6
Название |
Значение |
|
|
adj_mat |
Список значений матрицы смежности |
|
|
peaks |
Список названий вершин |
|
|
l_edg |
Список ребер графа |
|
|
g_info |
Массив записей графа |
|
|
num |
Номер вида представления графа |
|
|
10