ЛР / ЛР3 / graph_LR3

import math
import random as rd
import pandas as pd
import igraph as ig
import matplotlib.pyplot as plt
import matplotlib.ticker as ticker


# Рисует график по МАТРИЦЕ СМЕЖНОСТИ
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


# Регулярные структуры
# Дана квадратная решетка размером N на N. Закрашивание клетки такой
# решетки эквивалентно тому, что в граф добавляется вершина. Между двумя
# вершинами графа ставится ребро тогда, когда клетки решетки,
# соответствующие этим вершинам, прилегают друг к другу по горизонтали
# или вертикали (N = 10, р меняется от 0 до 1 с шагом 0.05).

# 10 Закрасить M случайно выбранных областей, имеющих форму квадрата 2 на 2 клетки
# (расположение области определяется координатами ее левого верхнего угла, квадрат
# должен целиком располагаться на решетке, области могут полностью или частично
# перекрывать друг друга, но вершины при этом не дублируются.)

# возвращет заполеную в соответствии с алгоритмом 10 решотку
def get_square_lattice_by_algorithm_10(N, p):
square_lattice = [[0] * N for i in range(N)] # нулевая матрицы размера N*N
M = math.ceil(p * N**2 / 4) # кол-во областей
# print('Кол-во областей M =', M, end='\n')
for iter in range(M): # Закрашивание областей 2*2 клетки
row = rd.randint(0, N-2)
col = rd.randint(0, N-2)
square_lattice[row][col] = square_lattice[row][col+1] \
= square_lattice[row+1][col] = square_lattice[row+1][col+1] = 1
return square_lattice

# возвращает матрицу смежности заполненую в соответствии с полученной решеткой
def get_adjacency_matrix_by_square_lattice(square_lattice):
N = len(square_lattice)
adj_mat = pd.DataFrame([[0] * N**2 for iter in range(N**2)]) # нулевая матрица смежности
for row in range(N): # заполнение матрицы смежности согласно square_lattice
for col in range(N):
if square_lattice[row][col] !=0: # закрашена ли клетка
if col-1 > 0 and square_lattice[row][col-1] != 0: # связь с левой клеткой
adj_mat[col + row * (N-1)][(col-1) + row * (N-1)] = \
adj_mat[(col-1) + row * (N-1)][col + row * (N-1)] = 1
if col+1 < N and square_lattice[row][col+1] != 0: # связь с правой клеткой
adj_mat[col + row * (N-1)][(col+1) + row * (N-1)] = \
adj_mat[(col+1) + row * (N-1)][col + row * (N-1)] = 1
if row-1 > 0 and square_lattice[row-1][col] != 0: # связь с верхней клеткой
adj_mat[col + row * (N-1)][col + (row-1) * (N-1)] = \
adj_mat[col + (row-1) * (N-1)][col + row * (N-1)] = 1
if row+1 < N and square_lattice[row+1][col] != 0: # связь с нижней клеткой
adj_mat[col + row * (N-1)][col + (row+1) * (N-1)] = \
adj_mat[col + (row+1) * (N-1)][col + row * (N-1)] = 1
for row in reversed(range(N**2)): # удаление личшних вершин
if sum(adj_mat[row]) == 0:
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

# вызывает функуии создания решетки и матрицы смежности, возвращает матрицу смежности
def get_adjacency_matrix_by_algorithm(algorithm, p = 0.5, N = 10):
square_lattice = algorithm(N, p)
# print('\nЗаполненая квадратная решетка:', *square_lattice, sep='\n')
return get_adjacency_matrix_by_square_lattice(square_lattice)


# построение графика
def plot_info(data, xdata, ydata, title = 'График', xlabel = 'x', ylabel = 'y', type = 0, xstep = 1, ystep = 1):
fig, ax = plt.subplots()
plt.title(title)
ax.set_xlabel(xlabel)
ax.set_ylabel(ylabel)
ax.grid()
ax.xaxis.set_major_locator(ticker.MultipleLocator(xstep))
ax.yaxis.set_major_locator(ticker.MultipleLocator(ystep))
match type:
case 0: plt.plot(data[xdata], data[ydata])
case 1: plt.bar(data[xdata], data[ydata])
plt.tight_layout()
plt.show()

# находит спектр степеней графа
def get_graph_degree_spectrum(adj_mat):
deg_spec = pd.DataFrame([], columns=['degree', 'frequence'])
# подсчет степеней вершин
vertex_degree = adj_mat.astype(bool).sum(axis=1)
# опрнднлнние частот степеней вершин
for degree in range(min(vertex_degree), max(vertex_degree)+1):
deg_spec.loc[len(deg_spec)] = [degree, len([d for d in vertex_degree if d == degree])]
plot_info(data=deg_spec
, xdata='degree'
, ydata='frequence'
, title='График спектра степеней графа'
, xlabel='Степень вершины'
, ylabel='Кол-во вершин'
, type=1)
return deg_spec


# возвращает список соседей для всех закрашеных клеток
def graph_ways(lattice):
size = len(lattice)
ways = {}
for row in range(size):
for col in range(size):
if lattice[row][col] != 0: # закрашена ли клетка
direction = {}
if col-1 > 0 and lattice[row][col-1] != 0: # связь с левой клеткой
direction['left'] = (row, col-1)
if col+1 < size and lattice[row][col+1] != 0: # связь с правой клеткой
direction['right'] = (row, col+1)
if row-1 > 0 and lattice[row-1][col] != 0: # связь с верхней клеткой
direction['up'] = (row-1, col)
if row+1 < size and lattice[row+1][col] != 0: # связь с нижней клеткой
direction['down'] = (row+1, col)
ways[(row, col)] = direction
return ways

# проверка существования пути от первого столбца до последнего в квадратной решетке
def exist_path_first_to_last_col(lattice):
size = len(lattice)
start = [(row, 0) for row in range(size) if lattice[row][0] != 0]
# print('', *start, sep='\n')
end = [(row, size-1) for row in range(size) if lattice[row][size-1] != 0]
# print('', *end, sep='\n')
ways = graph_ways(lattice)
for start_head in start:
head = start_head
visited = []
path = [head]
while head not in end:
direct = ways[head]
for dir in direct.keys():
if direct[dir] not in visited:
path.append(direct[dir])
visited.append(direct[dir])
head = direct[dir]
continue
if head in direct.values(): continue
elif head == start_head: break
else:
path.pop(len(path)-1)
head = path[len(path)-1]
if head in end: return True
return False

# нахождение зависимости вероятности существования пути между первым и последним столбцами решетки от вероятности закрашивания клетки
def probab_exist_path_first_to_last_col(sample_size, N = 10):
probab_exist_path = pd.DataFrame([], columns=['p','N', 'M', 'sample size', 'success way','probability'])
for p in [i/100 for i in range(0, 101, 5)]:
probab = 0
for iter in range(sample_size):
lattice = get_square_lattice_by_algorithm_10(N, p)
probab = probab + exist_path_first_to_last_col(lattice)
probab_exist_path.loc[len(probab_exist_path)] = [p, N, math.ceil(p * N**2 / 4), sample_size, probab, probab/sample_size]
plot_info(data=probab_exist_path
, xdata='p', ydata='probability'
, title='''График зависимости вероятности существования пути
между первым и последним столбцами решетки
от вероятности закрашивания клетки'''
, xlabel='Вероятность закрашивания клетки'
, ylabel='Вероятность существования пути'
, type=0
, xstep = 0.1, ystep = 0.05)
return probab_exist_path


def menu():
N = 10
print('Размер сетки N =', N, end='\n')

p = rd.choice([i/100 for i in range(0, 101, 5)])
print('Коэф. вероятности p =', p, end='\n')

adjacency_matrix = get_adjacency_matrix_by_algorithm(get_square_lattice_by_algorithm_10, p, N)
print('\nМатрица смежности:', adjacency_matrix, sep='\n')
view_graph(adjacency_matrix)

degree_spectrum = get_graph_degree_spectrum(adjacency_matrix)
print('\nCпектр степеней графа:', degree_spectrum, sep='\n')

probab_exist_path = probab_exist_path_first_to_last_col(10000)
print('\nЗависимость вероятности существования пути между\
первым и последним столбцами решетки от вероятности закрашивания клетки:', probab_exist_path, sep='\n')


if __name__ == "__main__": menu()