Функции get_chain_answer_by_adj_mat, get_chain_answer_by_l_edg, get_chain_answer_by_graph_info для проверки последовательности вершин на цепь. Список использованных переменных в соответствии с таблицей 9, код в соответствии с листингом 10. Результат работы функций в соответствии с рисунком 13.
Таблица 9 – Список переменных подпрограммы из Листинга 10
Название |
Значение |
|
|
adj_mat |
Список значений матрицы смежности |
|
|
peaks |
Список названий вершин |
|
|
l_edg |
Список ребер графа |
|
|
g_info |
Массив записей графа |
|
|
peaks_num |
Список вершин |
|
|
Листинг 10 – Подпрограмма проверки последовательности вершин на цепь в
представлениях графа (матрица смежности, список ребер, массив записей)
#проверка вершин на цепь в передставлении графа МАТРИЦА СМЕЖНОСТИ
def get_chain_answer_by_adj_mat(adj, peaks_num): if len(peaks_num) == 1: return True
for i in range(1, len(peaks_num)):
if adj[peaks_num[i-1]][peaks_num[i]] == 0: return False return True
#проверка вершин на цепь в передставлении графа СПИСОК РЕБЕР def get_chain_answer_by_l_edg(l_edg, peaks_num):
if len(peaks_num) == 1: return True
temp_l_edg = [[j[0][1][0] for j in l_edg if j[0][0][0] == i] for i in peaks_num]
for i in range(1, len(peaks_num)):
if peaks_num[i] not in temp_l_edg[i-1]: return False return True
#проверка вершин на цепь в МАССИВ ЗАПИСЕЙ
def get_chain_answer_by_graph_info(g_info, peaks_num): if len(peaks_num) == 1: return True
for i in range(1, len(peaks_num)):
if peaks_num[i] not in g_info['№ вершин детей'][peaks_num[i-1]]: return False
return True
21
Рисунок 13 – Результат работы функции get_chain_answer_by_adj_mat
22
Функции get_peaks_weight_more_value_by_adj_mat, get_peaks_weight_more_value_by_l_edg, get_peaks_weight_more_value_by_graph_info для поиска номеров вершин,
сумма весов инцидентных ребер которых больше заданной величины.
Список использованных переменных в соответствии с таблицей 10, код в соответствии с листингом 11. Результат работы функций в соответствии с рисунком 14.
Таблица 10 – Список переменных подпрограммы из Листинга 11
Название |
Значение |
|
|
adj_mat |
Список значений матрицы смежности |
|
|
peaks |
Список названий вершин |
|
|
l_edg |
Список ребер графа |
|
|
g_info |
Массив записей графа |
|
|
value |
Число для сравнения |
|
|
Листинг 11 – Подпрограмма поиска номеров вершин, сумма весов инцидентных ребер которых больше заданной величины в представлениях графа (матрица смежности, список ребер, массив записей)
#номера вершин, сумма весов инцидентных ребер которых больше заданной величины в передставлении графа МАТРИЦА СМЕЖНОСТИ
def get_peaks_weight_more_value_by_adj_mat(adj_mat, value): return [i for i in range(len(adj_mat)) if sum([col for col
in adj_mat[i]]+[row[i] for row in adj_mat]) > value]
#номера вершин, сумма весов инцидентных ребер которых больше
заданной величины в передставлении графа СПИСОК РЕБЕР
def get_peaks_weight_more_value_by_l_edg(peaks, l_edg, value): return [i for i in range(len(peaks)) if sum([j[1] for j in
l_edg if j[0][0][0] == i or j[0][1][0] == i]) > value]
#номера вершин, сумма весов инцидентных ребер которых больше заданной величины в передставлении графа МАССИВ ЗАПИСЕЙ
def get_peaks_weight_more_value_by_graph_info(peaks, g_info, value):
return [i for i in range(len(peaks)) if sum(g_info['Веса инцидентных ребер'][i]) > value]
23
Рисунок 14 – Результат работы функции
get_peaks_weight_more_value_by_adj_mat
24
Функции get_edge_count_by_adj_mat, get_edge_count_by_l_edg, get_edge_count_by_graph_info для поиска количества ребер графа. Список использованных переменных в соответствии с таблицей 11, код в соответствии с листингом 12. Результат работы функций в соответствии с рисунком 15.
Таблица 11 – Список переменных подпрограммы из Листинга 12
Название |
Значение |
|
|
adj_mat |
Список значений матрицы смежности |
|
|
l_edg |
Список ребер графа |
|
|
g_info |
Массив записей графа |
|
|
Листинг 12 – Подпрограмма определения кол-ва ребер в представлениях графа
(матрица смежности, список ребер, массив записей)
#определение кол-ва ребер в передставлении графа МАТРИЦА СМЕЖНОСТИ
def get_edge_count_by_adj_mat(adj_mat):
return sum([sum([1 for j in i if j != 0]) for i in adj_mat])
#определение кол-ва ребер в передставлении графа СПИСОК РЕБЕР def get_edge_count_by_l_edg(l_edg):
return len(l_edg)
#определение кол-ва ребер в передставлении графа МАССИВ ЗАПИСЕЙ def get_edge_count_by_graph_info(g_info):
return g_info['Кол-во детей'].sum()
Рисунок 15 – Результат работы функции get_edge_count_by_adj_mat
Приведены результаты работы функций для поиска в матрице смежности, функции для представлений графа список ребер и массив записей дают такие же результаты для таких же входных параметров.
25
7)Для каждого из представлений (матрица смежности, список ребер,
массив записей) вывели на экран размер содержащего их объекта в байтах.
Функция view_objects_size для определения размера объектов,
содержащих представления графа. Список использованных переменных в соответствии с таблицей 12, код в соответствии с листингом 13. Результат работы функций в соответствии с рисунком 16.
Таблица 12 – Список переменных подпрограммы из Листинга 13
Название |
Значение |
|
|
adj_mat |
Список значений матрицы смежности |
|
|
l_edg |
Список ребер графа |
|
|
g_info |
Массив записей графа |
|
|
Листинг 13 – Подпрограмма определения размера объектов, содержащих
представления графа (матрица смежности, список ребер, массив значений)
# узнать размер представлений графа
def view_objects_size(adja_mat, l_edg, g_info):
info = '\nРазмер представлений:\n\t- матрица смежности: ' + str(sys.getsizeof(adja_mat)) +\
'байт;\n\t- список ребер: ' +
str(sys.getsizeof(l_edg)) +\
'байт;\n\t- массив записей: ' +
str(sys.getsizeof(g_info)) + ' байт.' print(info)
return info
Рисунок 16 – Результат работы функции view_objects_size
26
8) Каждую подпрограмму, реализующую выполнение пункта 6 п/р (в
том числе и для каждого представления графа), повторили 10^6 раз при постоянных входных параметрах. Засекли время выполнения каждой подпрограммы и оценить среднее время ее выполнения. Вывели полученные результаты на экран.
Функция func_time_test для определения времени работы функций.
Список использованных переменных в соответствии с таблицей 13, код в соответствии с листингом 14. Результат работы функций в соответствии с рисунком 17.
Таблица 13 – Список переменных подпрограммы из Листинга 14
Название |
Значение |
|
|
adj_mat |
Список значений матрицы смежности |
|
|
l_edg |
Список ребер графа |
|
|
g_info |
Массив записей графа |
|
|
peaks |
Список вершин графа |
|
|
view |
Список названий представлений графа |
|
|
fun_name |
Список названий функций |
|
|
fun |
Список функций с параметрами их вызова |
|
|
f |
Итератор по списку функций |
|
|
Листинг 14 – Подпрограмма определения времени работы функций
# тест времени работы функций пункта 4
def func_time_test(adj_mat, l_edg, g_info, peaks): view = ('в представлении графа матрица смежности'
,'в представлении графа список ребер'
,'в представлении графа массив записей') fun_name = ('поиска соседей'
,'проверки последовательности вершин на
образование цепи' , 'поиска вершин, сумма инцедентных ребер которых
больше заданного числа' , 'определения кол-ва ребер')
fun = (
(get_neighbours_by_adj_mat, (adj_mat, peaks, 6)),
27
(get_neighbours_by_l_edg, (6, l_edg)), (get_neighbours_by_graph_info, (6, g_info, peaks)),
(get_chain_answer_by_adj_mat, (adj_mat, (5, 6, 7, 0,
1))),
(get_chain_answer_by_l_edg, (l_edg, (5, 6, 7, 0, 1))), (get_chain_answer_by_graph_info, (g_info, (5, 6, 7, 0,
1))),
(get_peaks_weight_more_value_by_adj_mat, (adj_mat,
16)),
(get_peaks_weight_more_value_by_l_edg, (peaks, l_edg,
16)),
(get_peaks_weight_more_value_by_graph_info, (peaks, g_info, 16)),
(get_edge_count_by_adj_mat, (adj_mat,)), (get_edge_count_by_l_edg, (l_edg,)), (get_edge_count_by_graph_info, (g_info,)),
)
for f in range(len(fun)):
print('\nФункция', fun[f][0].__name__, fun_name[f // 3], view[f % 3])
start_time = time.time()
for iter in range(10**6): fun[f][0](*fun[f][1]) end_time = (time.time() - start_time)
print('\tВремя выполнения функции 10^6 раз:' , round(end_time, 3), 'секунд')
print('\tСреднее время одного выполнения функции:' , round(end_time / 10**6, 8), 'секунд')
28
Рисунок 17 – Результат работы функции func_time_test
29
Вывод
Выполнив лабораторную работу, мы научились работать с различными представлениями графа (матрицы смежности, множества пар вершин и массива структур) в ЭВМ при помощи языка Python. Научились находить детей, родителей и соседей вершины и работать с их весами, и
визуализировать графы.
В работе для отображения графика использовали библиотеку IGraph с
помощью которой очень удобно создавать изображения графа. Так же использовали библиотеку Pandas для удобного хранения представлений графа.
Для выполнения 7 и 8 пункта воспользовались стандартными библиотеками
Sys и Time позволившие нам узнать размеры объектов представлений графа и засечь время работы функций соответственно.
Проанализировав результаты оценки времени работы функций с различными представлениями графа можно сделать вывод что наибольшего быстродействия можно добиться, используя представление в виде матрице смежности, за исключением функции определения количества ребер графа,
так как для этого лучше подходит список ребер, где длина списка является искомым значением что значительно ускоряет работу функции.
30