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

Цель работы

Изучение представления графов в ЭВМ при помощи матрицы смежности, множества пар вершин и массива структур. Визуализация графов.

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

Граф согласно индивидуальному варианту №10 в соответствии с рисунком 1.

Рисунок 1 – Граф индивидуального варианта

2

Ход работы

1)Матрица смежности в соответствии с рисунком 2.

Рисунок 2 – Матрица смежности

2) Ввели в ЭВМ матрицу смежности в явном виде. Код в соответствии с листингом 1. Листинг всей программы приведен в Приложении A. Код программы.

Листинг 1 – Матрица смежности в явном виде

peaks = ['Pavel I', 'Aleksandr I', 'Nikolai I', 'Aleksandr II', 'Aleksandr III', 'Nikolai II', 'Petr III', 'Ekaterina II'] adjacency_matrix = [[0, 6, 6, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 7, 0, 0, 0, 0], [0, 0, 0, 0, 8, 0, 2, 0], [0, 0, 0, 0, 0, 9, 0, 0], [0, 0, 0, 0, 0, 0, 2, 0], [34, 0, 0, 0, 4, 0, 0, 4], [5, 0, 0, 0, 0, 5, 0, 0]]

3

3) Написали подпрограмму для построения списка ребер по заданной матрицы смежности. Код подпрограммы и вспомогательной подпрограммы для проверки введенной матрицы смежности в соответствии с листингами 2 – 3, списки использованных в подпрограммах переменных в соответствии с таблицами 1-2. Результат работы в соответствии с рисунком 3.

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

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

# построение списка ребер по матрице смежности

def list_edges_by_adjacency_matrix(adj_mat, peaks = []):

4

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

adj_mat Список значений матрицы смежности

Листинг 3 – Подпрограмма проверка корректности ввода матрицы смежности

# проверка ввода матрицы смежност def adjacency_matrix_check(adj_mat):

if len(adj_mat)**2 != sum([len(row) for row in adj_mat]): return 'Ошибка: !Кол-во строк и столбцов матрицы

смежности не равно!' return True

Рисунок 3 – Результат работы подпрограммы построения списка ребер графа

5

4) Визуализировали заданный граф. Убедились в том, что он

совпадает с исходным графом. Код подпрограммы в соответствии с

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

#добавление идентификаторов и меток к вершинам for i in range(len(g.vs)):

g.vs[i]["id"]= i g.vs[i]["label"]= peaks[i]

#получаем список ребер и их веса

list_edges = list_edges_by_adjacency_matrix(adj_mat, peaks)

# задаем ребра g.add_edges([(peaks.index(edge[0][0]),

peaks.index(edge[0][1])) for edge in list_edges])

# задаем веса ребер

weights = [edge[1] for edge in list_edges] g.es['label'] = weights g.es['edge_width'] = weights g.es["curved"] = False

# построение графика ig.plot(g, bbox = (350,350)

,margin = 30

,vertex_label_size = 10

,vertex_size = 55

,vertex_color = 'white') return 1

6

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

# представление графа в виде массива записей

def get_array_of_graph_information(adj_mat, peaks): info = []

for row in range(len(adj_mat)):

# находим по матрице № и веса вершин детей, родителей и соседей children = [(i, adj_mat[row][i]) for i in

range(len(adj_mat[row])) if adj_mat[row][i] != 0]

parents = [(i, adj_mat[i][row]) for i in range(len(adj_mat)) if adj_mat[i][row] != 0]

neighbours = tuple(set(children + parents))

# записываем найденные данные в массив info.append([row

,peaks[row]

,*tuple(len(i) for i in [children, parents, neighbours])

,*tuple(tuple([j[0] for j in i]) for i in [children, parents, neighbours])

,*tuple(tuple([j[1] for j in i]) for i in [children, parents, neighbours])])

col_name = ['№ вершины', 'Подпись вершины', 'Кол-во детей /', 'родителей /', 'соседей', '№ вершин детей /', 'родителей /', 'соседей', 'Веса исходящих /', 'входящих /', 'инцидентных ребер']

g_info = pd.DataFrame(info, columns=col_name) print(g_info)

return g_info

Рисунок 5 – Результат работы подпрограммы, представляющей граф в виде

8

массива записей

9

6)Для каждого из представлений (матрица смежности, список ребер,

массив записей) написали подпрограммы поиска и вывода на экран:

•всех соседей заданной вершины графа;

•ответа, образует ли заданная последовательность вершин цепь;

•номеров вершин, сумма весов инцидентных ребер которых больше заданной величины;

•количества ребер в графе.

Для каждой подпрограммы организовали диалог с пользователем

(запрос параметра – вывод результата). Данные для представления результатов выполнения данных подпрограмм подобрать самостоятельно.

Функция search_in_views для выбора представления графа для поиска.

Список использованных переменных в соответствии с таблицей 5, код в соответствии с листингом 6. Результат работы функций в соответствии с рисунком 6.

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

10