ЛР / ЛР2 / graph_LR2

import igraph as ig
import pandas as pd
import networkx as nx
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 # кривизна ребер
# g.es["curved"] = True # кривизна ребер
ig.plot(g, bbox = (500, 500) # построение графика
, margin = 30
# , vertex_label_size = 10
# , vertex_size = 20
, vertex_color = 'white')
return 1

# Рисует график по МАТРИЦЕ СМЕЖНОСТИ (networkx)
def view_graph_nx(adj_mat, peaks = []):
if not peaks: peaks = [i for i in range(len(adj_mat))]
list_edges = [(row, col) for col in range(len(adj_mat)) for row in range(len(adj_mat)) if adj_mat[row][col]]
G = nx.Graph() #Создание объекта пустого графа без ребер и узлов
#DG = nx.DiGraph(directed=True) # Создание объекта пустого ориентированного графа
G.add_nodes_from(peaks) #Добавление вершин в виде списка
G.add_edges_from(list_edges) #Добавление ребер в виде списка
#G.add_weighted_edges_from([(0, 2, 0.3), (1, 3, 0.7), …]) #Добавление ребер в виде списка с указанием веса
#Построение графа
plt.figure(figsize=(7,7))
pos = nx.spring_layout(G) #Определение карты расположения узлов
nx.draw(G, node_size = 2000
, pos = pos, with_labels=True
# , labels = labels
) #Создание изображения графа
# nx.draw_networkx_edge_labels(G, pos, edge_labels = edge_labels) #Добавление надписей для ребер
plt.show() #Отображение графа
#plt.savefig("filename.png") #Сохранение изображения в файл



# Алгоритм создания матрицы смежности графа
# 1 Правильная квадратная решетка
def get_adjacency_matrix_square_lattice_graph(size):
adj_mat = [[0] * size**2 for i in range(size**2)]
for v in range(size**2):
if v % size < size-1: adj_mat[v][v+1] = adj_mat[v+1][v] = 1 # строки
if v // size < size-1: adj_mat[v][v+size] = adj_mat[v+size][v] = 1 # столбцы
return pd.DataFrame(adj_mat)

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

# 3 Правильная шестиугольная решетка
def get_adjacency_matrix_hexagonal_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 (row % 4 == 0 and col % 2 == 1) or (row % 4 == 2 and col % 2 == 0):
if row > 0: adj_mat[v][v-size] = adj_mat[v-size][v] = 1
if row < size-1 and col < size-1:
adj_mat[v][v+size+1] = adj_mat[v+size+1][v] = 1
if row < size-1 and col > 0:
adj_mat[v][v+size-1] = adj_mat[v+size-1][v] = 1
adj_mat = pd.DataFrame(adj_mat)
for row in reversed(range(size**2)):
if sum(adj_mat[row]) < 2:
adj_mat.drop(labels=[row], axis=0, inplace=True)
adj_mat.drop(labels=[row], axis=1, inplace=True)
adj_mat.reset_index(drop=True, inplace=True)
adj_mat.columns = range(len(adj_mat))
return 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()


# тест быстродействия функции
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)

# # # 1 Правильная квадратная решетка
# # adj_mat_square = get_adjacency_matrix_square_lattice_graph(5)
# # print(adj_mat_square)
# # view_graph(adj_mat_square)

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

# # # 3 Правильная шестиугольная решетка
# # adj_mat_hexagonal = get_adjacency_matrix_hexagonal_lattice_graph(9)
# # print(adj_mat_hexagonal)
# # view_graph(adj_mat_hexagonal)

data = performance_test(20, get_adjacency_matrix_triangular_lattice_graph, prima_algoritm)
print(data)

if __name__ == "__main__": menu()