Рисунок 4 – Результат работы функции get_graph_degree_spectrum
Рисунок 5 – Результат работы функции plot_info на основе данных из функции get_graph_degree_spectrum
11
4)Согласно своему варианту, выполнили задание из Таблицы 2.
Построили соответствующий график.
Функции graph_ways, exist_path_first_to_last_col и probab_exist_path_first_to_last_col для нахождения зависимости вероятности существования пути между первым и последним столбцами решетки от вероятности закрашивания клетки. Список использованных переменных в соответствии с таблицами 9-11, код в соответствии с листингом 7-9. Результат работы функций в соответствии с рисунком 6, график в соответствии с рисунком 7.
Таблица 9 – Список переменных подпрограммы из Листинга 7
Название |
Значение |
|
|
lattice |
Матрица квадратной решетки |
|
|
size |
Размер квадратной решетки |
|
|
ways |
Словарь закрашенных соседей для закрашенных клеток |
|
|
row |
Итератор по номерам строк решетки |
|
|
col |
Итератор по номерам столбцов решетки |
|
|
direction |
Словарь закрашенных соседей для одной конкретной |
|
закрашенной клетки |
|
|
Листинг 7 – Подпрограмма построения словаря всех возможных переходов для “закрашенных” клеток квадратной решетки
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: |
# |
|
|
|
|
12
связь с верхней |
клеткой |
|
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 |
|
|
|
Таблица 10 – Список переменных подпрограммы из Листинга 8 |
|
Название |
Значение |
|
|
lattice |
Матрица квадратной решетки |
|
|
size |
Размер квадратной решетки |
|
|
start |
Список начальных позиций пути в квадратной решетке |
|
|
end |
Список конечных позиций пути в квадратной решетке |
|
|
ways |
Словарь закрашенных соседей для закрашенных клеток |
|
|
start_head |
Начальная позиция поти |
|
|
head |
Текущая точка пути |
|
|
visited |
Список посещенных клеток |
|
|
path |
Список клеток пути |
|
|
direct |
Словарь возможных переходов для текущей клетки пути |
|
|
dir |
Итератор по возможным направлениям перехода для текущей |
|
клетке пути |
|
|
Листинг 8 – Подпрограмма проверки существования пути от первого до последнего столбца квадратной решетки
def exist_path_first_to_last_col(lattice): size = len(lattice)
start = [(row, 0) for row in range(size) if lattice[row][0] != 0]
end = [(row, size-1) for row in range(size) if lattice[row][size-1] != 0]
ways = graph_ways(lattice) for start_head in start: head = start_head
visited = [] path = [head]
13
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
Таблица 11 – Список переменных подпрограммы из Листинга 9
Название |
Значение |
|
|
sample_size |
Размер выборки |
|
|
N |
Размер решетки |
|
|
probab_exist_path |
Датафрейм данных об вероятности существования пути |
|
|
p |
Итератор по всем возможным значениям вероятности |
|
|
iter |
Итератор по экспериментам выборки |
|
|
lattice |
Заполненная квадратная решетка |
|
|
probab |
Количество успешных проверок существования пути |
|
|
Листинг 9 – Подпрограмма нахождения зависимости вероятности существования пути между первым и последним столбцами решетки от вероятности закрашивания клетки
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
14
,xdata='p', ydata='probability'
,title='''График зависимости вероятности
существования пути между первым и последним столбцами решетки
от вероятности закрашивания клетки'''
,xlabel='Вероятность закрашивания клетки'
,ylabel='Вероятность существования пути'
,type=0
,xstep = 0.1, ystep = 0.05)
return probab_exist_path
Рисунок 6 – Результат работы функций probab_exist_path_first_to_last_col, exist_path_first_to_last_col и graph_ways
Рисунок 7 – Результат работы функции plot_info на основе данных из функции probab_exist_path_first_to_last_col
15
Вывод
Выполнив лабораторную работу, мы разработали программы, которые строят и выводят на экран случайно сгенерированный граф в зависимости от входных параметров размера и вероятности закрашивания клеток квадратной решетки. Также были реализованы программы для анализа характеристик полученного графа.
Анализ полученного в ходе выполнения работы графа показал, что при генерации графа на основе случайным образом заполненной квадратной решетки, мы получаем в количественном соотношении больше вершин со степенью 2 чем всех остальных. При такой генерации графа максимальная степень вершины равна 4, а минимальная 2, это связанно с тем, что при
«закрашивании» решетки случайно расположенными областями 2х2 клетки каждая клетка сразу имеет 2 соседей, что в дальнейшем дает нам 2
инцидентных ребра, если же области соприкасаются количество соседей может увеличиться на 1 или 2 в зависимости от характера соприкосновения/пересечения областей. Поэтому изображение графа имеет вид «квадратных» клеток, образованных связями 4 вершин, которые в свою очередь могут соединяться с другими такими же «квадратными» клетками.
Исследование, проведенное на выборках из 100000 сгенерированных квадратных решеток для каждого возможного коэффициента вероятности
«закрашивания» клеток решётки показало, что чем больше вероятность
«закрашивания» тем больше шанс получить такое сочетание «закрашенных» клеток, которое образует путь от первого столбца решетки до последнего.
Наименьший коэффициент «закрашивания», при котором мог образоваться путь равен 0,25, однако он критически мал и не превышает 0,01%, наибольшая вероятность была получена при наибольшем значении коэффициента равного 1, и составила почти 40%.
Данный граф может представлять структуру слоя клеток ткани животного, в которой соседние клетки могут быть связаны и могут обмениваться полезными веществами.
16
Список использованных источников
1) Методические указания по практической работе 3, «Случайные
графы и их свойства» – СПб: ГУАП, 2022
17
ПРИЛОЖЕНИЕ A. Код программы
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
# возвращет заполеную в соответствии с алгоритмом 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
18
#возвращает матрицу смежности заполненую в соответствии с полученной решеткой
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)
19
# построение графика
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: |
# |
|
20 |
|
|