ЛР / ЛР3 / ПиАГМ ЛР3

Цель работы

Рассмотреть различные подходы к генерации случайных графов в ЭВМ. Провести анализ свойств созданных графов.

Индивидуальный вариант

Задание согласно индивидуальному варианту №10 в соответствии с таблицами 1-2.

Таблица 1 – Задание индивидуального варианта (тип случайного графа)

№ варианта Алгоритм создания графа

Регулярные структуры

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

Закрасить M случайно выбранных областей, имеющих форму квадрата 2 на 2 клетки ( = 2/4, расположение области определяется координатами ее левого верхнего угла,

10квадрат должен целиком располагаться на решетке, области могут полностью или частично перекрывать друг друга, но

вершины при этом не дублируются. - округление вверх до целого числа).

Таблица 2 – Задание индивидуального варианта (свойства случайного графа)

2

Ход работы

1) Написали подпрограмму, реализующую отображение графа на экране. Функция view_graph для отображения графа на экране. Список использованных переменных в соответствии с таблицей 3, код в соответствии с листингом 1. Результат работы функций в соответствии с рисунком 1.

Таблица 3 – Список переменных подпрограммы из Листинга 1

Листинг 1 – Подпрограмма отображения графа на экране

# Рисует график по МАТРИЦЕ СМЕЖНОСТИ

def view_graph(adj_mat, peaks = [], curved_value = False): if not peaks: peaks = list(adj_mat)

# добавление идентификаторов и меток к вершинам 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]]

3

Рисунок 1 – Результат работы функции view_graph

4

2) Согласно варианту, реализовали функцию создания матрицы смежности случайного графа, основываясь на заданном алгоритме.

Визуализировали полученный граф.

Функции get_adjacency_matrix_by_algorithm, get_adjacency_matrix_by_square_lattice и get_square_lattice_by_algorithm для

«Закрашивания» квадратной решетки случайным образом на основе коэффициента вероятности закрашивания p и последующего построения матрицы смежности графа на основе полученной решетки. Список использованных переменных в соответствии с таблицами 4-6, код в соответствии с листингами 2-4. Результат работы функций в соответствии с рисунками 2-3.

Таблица 4 – Список переменных подпрограммы из Листинга 2

p Коэффициент вероятности закрашивания клетки решетки

N Размер решетки

Листинг 2 – Подпрограмма заполнения квадратной решетки

5

Таблица 5 – Список переменных подпрограммы из Листинга 3

Листинг 3 – Подпрограмма перевода квадратной решетки в матрицу смежности графа согласно варианту

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): # заполнение матрицы смежности 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)

6

Листинг 4 – Подпрограмма создания матрицы смежности на основе функций

«закрашивания» квадратной решетки и перевода ее в матрицу смежности

графа

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)

7

3) Реализовали функцию поиска спектра степеней графа. Построили график по полученному спектру для графа.

Функции get_graph_degree_spectrum и plot_info для нахождения спектра степеней графа и отображения найденных данных на графе. Список использованных переменных в соответствии с таблицами 7-8, код в соответствии с листингами 5-6. Результат работы функций в соответствии с рисунком 4, график в соответствии с рисунком 5.

Таблица 7 – Список переменных подпрограммы из Листинга 5

Листинг 5 – Подпрограмма построения графика

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

9

Таблица 8 – Список переменных подпрограммы из Листинга 6

Листинг 6 – Подпрограмма нахождения спектра степеней графа

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

10