7) Написали подпрограмму, реализующую создание взвешенный графа правильной треугольной решетки в представлении матрицы смежности.
Функция get_adjacency_matrix_triangular_lattice_graph для создания графа правильной треугольной решетки в представлении матрицы смежности.
Список использованных переменных в соответствии с таблицей 5, код в соответствии с листингом 4. Результат работы функций в соответствии с рисунком 15, изображение, построенное с помощью функции view_graph в
соответствии с рисунком 16.
Таблица 5 – Список переменных подпрограммы из Листинга 4
Название |
Значение |
|
|
adj_mat |
Матрица смежности |
|
|
size |
Размер стороны графа (кол-во вершин в ней) |
|
|
v |
Итератор по номерам вершин |
|
|
row |
Номер строки |
|
|
col |
Номер столбца |
|
|
Листинг 4 – Подпрограмма создания графа правильной треугольной решетки в представлении матрицы смежности
def get_adjacency_matrix_triangular_lattice_graph(size): adj_mat = [[0] * size**2 for i in range(size**2)] for v in range(size**2):
row = v // size col = v % size
if col < size-1: # строки adj_mat[v][v+1] = adj_mat[v+1][v] = 1
if row < size-1: # столбцы adj_mat[v][v+size] = adj_mat[v+size][v] = 1
# диагонали
if (row % 2 == 0 and col % 2 == 0) or (row % 2 == 1 and col % 2 == 1):
if col > 0: adj_mat[v][v+size-1] = adj_mat[v+size-1][v] = 1
if col < size-1: adj_mat[v][v+size+1] = adj_mat[v+size+1][v] = 1
return pd.DataFrame(adj_mat)
11
Рисунок 15 – Результат работы функции
Рисунок 16 – Изображение созданного в функции графа
12
8) Построили график зависимости быстродействия (среднего времени выполнения) алгоритма Прима от количества узлов в графе (без учета времени создания графа).
Функции performance_test и plot_info для измерения быстродействия функции и построения графика по полученным значениям. Список использованных переменных в соответствии с таблицами 6-7, код в соответствии с листингом 5-6. Результат работы функций в соответствии с рисунком 17, график в соответствии с рисунком 18.
Таблица 6 – Список переменных подпрограммы из Листинга 5
Название |
Значение |
|
|
num |
Количество итераций цикла |
|
|
result |
Датафрейм результатов измерений |
|
|
size |
Размер матрицы |
|
|
adj_mat |
Матрица смежности |
|
|
start_time |
Время начала тета |
|
|
end_time |
Время выполнения алгоритма |
|
|
Листинг 5 – Подпрограмма замер быстродействия работы алгоритма
def performance_test(num, func_mat, func_alg):
result = pd.DataFrame([], columns=['size', 'time']) for size in range(1, num+1):
adj_mat = func_mat(size) start_time = time.time() func_alg(adj_mat)
end_time = (time.time() - start_time) result.loc[len(result)] = [size, end_time]
plot_info(result) return result
Таблица 7 – Список переменных подпрограммы из Листинга 6
Название |
Значение |
data Данные для построения графика
fig, ax, plt Объекты matplotlib необходимые для построения графика
13
Листинг 6 – Подпрограмма построения графика
def plot_info(data):
fig, ax = plt.subplots()
plt.title('График быстродействия алгоритма') ax.set_xlabel('Размер') ax.set_ylabel('Время выполнения')
ax.grid() ax.xaxis.set_major_locator(ticker.MultipleLocator(1)) plt.bar(data['size'], data['time']) plt.tight_layout()
plt.show()
Рисунок 17 – Результат работы функции performance_test
Рисунок 18 – Результат работы функции plot_info
14
Вывод
Выполнив лабораторную работу, мы реализовали и проверили на тестовом примере базовый алгоритм на графе. Сравнили быстродействие реализованного алгоритма на графах правильной треугольной решетки разного размера.
В работе для отображения графика использовали библиотеку IGraph с
помощью которой очень удобно создавать изображения графа. Так же использовали библиотеку Pandas для удобного хранения представлений графа.
Для выполнения проверки быстродействия алгоритма воспользовались стандартными библиотекой Time позволившей нам засечь время работы функции.
15
Список использованных источников
1) Методические указания по практической работе 2, «Базовые
алгоритмы на графах» – СПб: ГУАП, 2022
16
ПРИЛОЖЕНИЕ A. Код программы
import igraph as ig import pandas as pd
import matplotlib.pyplot as plt import matplotlib.ticker as ticker import random as rd
import math import time
# Рисует график по МАТРИЦЕ СМЕЖНОСТИ
def view_graph(adj_mat, peaks = [], curved_value = False): if not peaks: peaks = list(adj_mat)
g = ig.Graph() |
# создание ориентированного графа |
|
g.add_vertices(len(peaks)) |
# добавление вершин графа |
|
# добавление идентификаторов и меток к вершинам for i in range(len(g.vs)):
g.vs[i]["id"]= peaks[i] if isinstance(peaks[i], int) else
i
g.vs[i]["label"]= peaks[i]
# получаем список ребер и их веса
list_edges = [(row, col) for col in range(len(adj_mat)) for row in range(len(adj_mat)) if adj_mat[row][col]]
# задаем ребра g.add_edges(list_edges)
# задаем веса ребер
weights = [adj_mat[row][col] for col in range(len(adj_mat)) for row in range(len(adj_mat)) if adj_mat[row][col]]
g.es['label'] = weights |
|
g.es['edge_width'] = weights |
|
g.es["curved"] = curved_value |
# кривизна ребер |
ig.plot(g, bbox = (500, 500) |
# построение графика |
,margin = 30
,vertex_color = 'white') return 1
#Алгоритм создания матрицы смежности графа
#2 Правильная треугольная решетка
def get_adjacency_matrix_triangular_lattice_graph(size): adj_mat = [[0] * size**2 for i in range(size**2)] for v in range(size**2):
row = v // size col = v % size
if col < size-1: # строки adj_mat[v][v+1] = adj_mat[v+1][v] = 1
if row < size-1: # столбцы adj_mat[v][v+size] = adj_mat[v+size][v] = 1
# диагонали
if (row % 2 == 0 and col % 2 == 0) or (row % 2 == 1 and col % 2 == 1):
if col > 0: adj_mat[v][v+size-1] = adj_mat[v+size-
17
1][v] = 1
if col < size-1: adj_mat[v][v+size+1] = adj_mat[v+size+1][v] = 1
return pd.DataFrame(adj_mat)
#2 Алгоритм поиска минимального остовного дерева (алгоритм Прима)
#находит ребро с минимальным ввесом одна из вершин которой уже в def search_min(adj_mat, vizited):
min_v = (-1, -1, math.inf) for row in vizited:
for col, elem in enumerate(adj_mat[row]):
if col not in vizited and elem != 0 and elem <
min_v[2]:
min_v = (row, col, elem)
return [(min_v[0], min_v[1]), (min_v[1], min_v[0]), elem] |
|
||||
def prima_algoritm(adj_mat): |
|
|
|
|
|
size = len(adj_mat) |
# число вершин в графе |
|
|||
vizited = {rd.choice([i for i in range(size)])} |
# множество |
||||
соединенных вершин |
|
|
|
|
|
result = [] |
# список ребер остова |
|
|||
while len(vizited) < size: |
|
|
|
|
|
edge = search_min(adj_mat, vizited) |
# |
ребро |
с |
||
минимальным весом |
|
|
|
|
|
if edge[2] == math.inf: |
|
# если ребер нет, то |
|||
остов построен |
|
|
|
|
|
return False |
|
|
|
|
|
result.extend([edge[0], |
edge[1]]) |
# добавляем |
ребро |
в |
|
остов |
|
|
|
|
|
vizited.add(edge[0][0]) |
|
# добавляем вершины в |
|||
множество |
|
|
|
|
|
vizited.add(edge[0][1]) |
|
|
|
|
|
return pd.DataFrame([[adj_mat[row][col] if (row, col) in result else 0 for col in range(size)] for row in range(size)])
# отображение графика быстродействия def plot_info(data):
fig, ax = plt.subplots()
plt.title('График быстродействия алгоритма') ax.set_xlabel('Размер графа') ax.set_ylabel('Время выполнения (сек)') ax.grid()
ax.xaxis.set_major_locator(ticker.MultipleLocator(1)) plt.bar(data['size'], data['time']) plt.tight_layout()
plt.show()
18
# тест быстродействия функции
def performance_test(num, func_mat, func_alg):
result = pd.DataFrame([], columns=['size', 'time']) for size in range(1, num+1):
adj_mat = func_mat(size) start_time = time.time() func_alg(adj_mat)
end_time = (time.time() - start_time) result.loc[len(result)] = [size, end_time]
plot_info(result) return result
def |
menu(): |
|
|
|
|
|
|
|
|
|
|
# матрица смежности графа правильной треугольной решетка (1) |
|||||||||
|
adjacency_matrix = pd.DataFrame([[0, 10, |
0, 10, |
1, |
0, |
0, |
|||||
0, |
0], |
|
|
|
|
|
|
|
|
|
|
|
|
[10, |
0, |
10, |
0, |
1, |
0, |
0, |
|
0, |
0], |
|
|
|
|
|
|
|
|
|
|
|
|
[ |
0, |
10, |
0, |
0, |
1, |
10, |
0, |
0, |
0], |
|
|
|
|
|
|
|
|
|
|
|
|
[10, |
0, |
0, |
0, |
1, |
0, |
10, |
|
0, |
0], |
|
|
|
|
|
|
|
|
|
|
|
|
[ |
1, |
1, |
1, |
1, |
0, |
1, |
1, |
1, |
1], |
|
|
|
|
|
|
|
|
|
|
|
|
[ |
0, |
0, |
10, |
0, |
1, |
0, |
0, |
0, 10], |
|
|
|
|
|
|
|
|
|
|
|
|
|
[ |
0, |
0, |
0, |
10, |
1, |
0, |
0, |
10, |
0], |
|
|
|
|
|
|
|
|
|
|
|
|
[ |
0, |
0, |
0, |
0, |
1, |
0, |
10, |
0, 10], |
|
|
|
|
|
|
|
|
|
|
|
|
|
[ |
0, |
0, |
0, |
0, |
1, |
10, |
0, |
10, |
0]]) |
|
|
|
|
|
|
|
|
|
|
# тест алгоритма на вручную созданном графе |
|
|
|
|
|||||
|
view_graph(adjacency_matrix) |
# изображение графа для (1) |
||||||||
|
res = prima_algoritm(adjacency_matrix) |
# остовное дерево |
||||||||
для |
(1) |
|
|
|
|
|
|
|
|
|
|
view_graph(res) |
# изображение остовного дерева для (1) |
||||||||
|
# 2 Правильная треугольная решетка |
|
|
|
|
|
|
|
||
|
adj_mat_triangular |
|
|
|
|
|
|
|
|
= |
get_adjacency_matrix_triangular_lattice_graph(4) |
|
|
|
|
||||||
print(adj_mat_triangular) view_graph(adj_mat_triangular)
#тест алгоритма на созданном функцией графе res = prima_algoritm(adj_mat_triangular) view_graph(res)
#тест быстродействия алгоритма
data = performance_test(20, get_adjacency_matrix_triangular_lattice_graph, prima_algoritm)
print(data)
if __name__ == "__main__": menu()
19