Листинг 6 – Подпрограмма выбора представления графа
def search_in_views(adj_mat, peaks, l_edg = [], g_info = []): while 1:
num = input('''\n
Выберете представление для поиска: 1 - матрица смежности; 2 - список ребер; 3 - массив записей;
Q - Выход. Введите номер: ''')
match num.upper(): case '1':
print('', pd.DataFrame(adj_mat, columns=peaks, index=peaks), sep='\n')
search_in_views_by_adj_mat(adj_mat, peaks)
case '2':
if l_edg == [] or isinstance(l_edg[0], str): l_edg = get_list_edges_by_adjacency_matrix(adj_mat, peaks)
print('', *l_edg, sep='\n') search_in_views_by_list_edges(l_edg, peaks)
case '3':
if g_info == []: g_info = get_array_of_graph_information(adj_mat, peaks)
print('\n', g_info) search_in_views_by_graph_mat(g_info, peaks)
case 'Q': break
case _:
print('\n!Команда не найдена! Повторите ввод.')
return -2
Рисунок 6 – Результат работы функции search_in_views
11
Функции search_in_views_by_adj_mat, search_in_views_by_list_edges, search_in_views_by_graph_mat для выбора и вызова функций для определенных вопросов. Список использованных переменных в соответствии с таблицей 6, код в соответствии с листингом 7. Результат работы функций в соответствии с рисунком 7.
Таблица 6 – Список переменных подпрограммы из Листинга 7
Название |
Значение |
|
|
adj_mat |
Список значений матрицы смежности |
|
|
peaks |
Список названий вершин |
|
|
l_edg |
Список ребер графа |
|
|
g_info |
Массив записей графа |
|
|
question |
Номер вопроса |
|
|
Листинг 7 – Подпрограмма вызова функций по заданным вопросам для представлений графа (матрица смежности, список ребер, массив записей)
# поиск в МАТРИЦЕ СМЕЖНОСТИ
def search_in_views_by_adj_mat(adj_mat, peaks):
while 1:
question = get_question_number()
match question:
case 1: # 1 - всех соседей заданной вершины графа;
top = get_peaks_for_search(peaks) |
|
|
|||
if top == -1: continue |
|
|
|
||
print('\nСоседи |
вершины |
№', |
top, |
'(', |
|
peaks[top], '):', |
get_neighbours_by_adj_mat(adj_mat, |
peaks, |
|||
top)) |
|
|
|
|
|
case 2: # 2 - ответ, образует ли заданная |
|||||
последовательность вершин цепь; |
|
|
|
|
|
peaks_num = get_peaks_for_chain(peaks) |
|
||||
if peaks_num == -1: continue |
|
|
|
||
chain_answer |
|
|
|
= |
|
get_chain_answer_by_adj_mat(adj_mat, peaks_num) |
|
|
|||
if |
chain_answer: |
print('\nЗаданная |
|||
последовательность вершин образует цепь.') |
|
|
|
||
else: |
print('\nЗаданная |
последовательность |
|||
вершин не образует цепь.') |
|
|
|
|
|
12
case 3: # 3 - номера вершин, сумма весов инцидентных ребер которых больше заданной величины;
value = get_value_for_search() if value == -1: continue
print('\nНомера вершин, сумма весов инцедентных ребер, которых больше', value, ':',
*get_peaks_weight_more_value_by_adj_mat(adj_mat, value))
case 4: # 4 - количество ребер в графе;
print('\nВ графе', get_edge_count_by_adj_mat(adj_mat), 'ребер.')
case -1: return -1
return -2
case 4: # 4 - количество ребер в графе;
print('\nВ графе', get_edge_count_by_graph_info(g_info), 'ребер.')
case -1: return -1
return -2
# поиск в СПИСОК РЕБЕР
def search_in_views_by_list_edges(l_edg, peaks): while 1:
question = get_question_number()
match question:
case 1: # 1 - всех соседей заданной вершины графа; top = get_peaks_for_search(peaks)
if top == -1: continue
print('\nСоседи вершины №', top, '(', peaks[top], '):', get_neighbours_by_l_edg(top, l_edg))
case 2: # 2 - ответ, образует ли заданная последовательность вершин цепь;
peaks_num = get_peaks_for_chain(peaks) if peaks_num == -1: continue
chain_answer = get_chain_answer_by_l_edg(l_edg,
peaks_num) |
|
|
if |
chain_answer: |
print('\nЗаданная |
последовательность вершин образует цепь.') |
|
|
else: |
print('\nЗаданная |
последовательность |
вершин не образует цепь.') |
|
|
case 3: # 3 - номера вершин, сумма весов инцидентных ребер которых больше заданной величины;
value = get_value_for_search() if value == -1: continue
print('\nНомера вершин, сумма весов инцедентных
13
ребер, которых больше'
, value, ':', *get_peaks_weight_more_value_by_l_edg(peaks, l_edg, value))
case 4: # 4 - количество ребер в графе;
print('\nВ графе', get_edge_count_by_l_edg(l_edg), 'ребер.')
case -1: return -1
return -2
# поиск в МАССИВ ЗАПИСЕЙ
def search_in_views_by_graph_mat(g_info, peaks): while 1:
question = get_question_number()
match question:
case 1: # 1 - всех соседей заданной вершины графа;
top = get_peaks_for_search(peaks) |
|
|
||
if top == -1: continue |
|
|
|
|
print('\nСоседи |
вершины |
№', |
top, |
'(', |
peaks[top], '):', get_neighbours_by_graph_info(top, g_info, peaks))
case 2: # 2 - ответ, образует ли заданная последовательность вершин цепь;
peaks_num = get_peaks_for_chain(peaks)
if |
peaks_num == -1: continue |
|
|
chain_answer |
= |
||
get_chain_answer_by_graph_info(g_info, peaks_num) |
|||
if |
|
chain_answer: |
print('\nЗаданная |
последовательность вершин образует цепь.') |
|
||
else: |
print('\nЗаданная |
последовательность |
|
вершин не образует цепь.') |
|
||
case 3: # 3 - номера вершин, сумма весов инцидентных ребер которых больше заданной величины;
value = get_value_for_search() if value == -1: continue
print('\nНомера вершин, сумма весов инцедентных ребер, которых больше', value
, ':', *get_peaks_weight_more_value_by_graph_info(peaks, g_info, value))
14
Рисунок 7 – Результат работы функции search_in_views_by_adj_mat
15
Функции get_question_number, get_peaks_for_search, get_peaks_for_chain, get_value_for_search для запроса параметров функций из листинга 6. Список использованных переменных в соответствии с таблицей
7, код в соответствии с листингом 8. Результат работы функций в соответствии с рисунками 8-11.
Таблица 7 – Список переменных подпрограммы из Листинга 8
Название |
Значение |
|
|
question |
Номер вопроса |
|
|
peaks_up |
Список вершин графа в верхнем регистре |
|
|
top |
Номер вершины графа |
|
|
chain_peaks |
Список вершин |
|
|
value |
Целое число для сравнения с весами сумм инцидентных |
|
вершин |
|
|
Листинг 8 – Подпрограмма запроса параметров через диалог с пользователем
# Запрос номера вопроса def get_question_number():
while 1:
question = input('''\nНайти:
1 - всех соседей заданной вершины графа;
2 - ответ, образует ли заданная последовательность вершин цепь;
3 - номера вершин, сумма весов инцидентных ребер которых больше заданной величины;
4 - количество ребер в графе; Q - Выход.
Введите номер: ''')
if question.isdigit(): question = int(question)
if question in range(1,5): return question
else: print('\n!Указан не существующй номер вопроса! Повторите ввод.')
elif question.upper() == 'Q': return -1
else: print('\n!Команда не найдена! Повторите ввод.')
# запрос и проверка корректности ввода вершины для поиска def get_peaks_for_search(peaks):
peaks_up = [i.upper() for i in peaks] while 1:
16
top = input('\nЗадайте вершину для поиска соседей:\n\t-
из списка: ('+', '.join(str(i) for i in peaks)
+')\n\t- по номеру: от 0 до ' + str(len(peaks)-1)
+'\n\t- Q для выхода' + '\nВведите вершину:
').upper()
if top in peaks_up:
top = peaks_up.index(top) break
if top.isdigit(): top = int(top)
if top in range(len(peaks)): break
else: print('\n!Вершины с указанным номером не существует! Повторите ввод.')
elif top == 'Q': return -1
else: print('\n!Вершины с указанным названием не существует! Повторите ввод.')
return top
# запрос списка вершин графа def get_peaks_for_chain(peaks):
while 1:
chain_peaks = input('\nЗадайте список вершин (по номерам от 0 до ' + str(len(peaks)-1)
+ ' через пробел) для проверки, образует ли заданная последовательность вершин цепь.'
+ '\n\t- Q для выхода' + '\nВведите вершины:
').split()
if all(map(lambda x: x.isdigit(), chain_peaks)): chain_peaks = list(map(int, chain_peaks))
if set(chain_peaks).issubset(range(len(peaks))): break
elif chain_peaks[0].upper() == 'Q': return -1
print('\n!Указаны не существующие номера вершин! Повторите ввод.')
return chain_peaks
# запрос и проверка корректности ввода значения для поиска def get_value_for_search():
while 1:
value = input('\nЗадайте значение для сравнения:
').upper()
if value.isdigit(): return int(value)
elif value == 'Q': return -1
else: print('\n!Введено неверное значение! Повторите
ввод.')
17
Рисунок 8 – Результат работы функции get_question_number
Рисунок 9 – Результат работы функции get_peaks_for_search
Рисунок 10 – Результат работы функции get_peaks_for_chain
Рисунок 11 – Результат работы функции get_value_for_search
18
Функции get_neighbours_by_adj_mat, get_neighbours_by_l_edg, get_neighbours_by_graph_info для поиска соседей указанной вершины.
Список использованных переменных в соответствии с таблицей 8, код в соответствии с листингом 9. Результат работы функций в соответствии с рисунком 12.
Таблица 8 – Список переменных подпрограммы из Листинга 9
Название |
Значение |
|
|
adj_mat |
Список значений матрицы смежности |
|
|
peaks |
Список названий вершин |
|
|
l_edg |
Список ребер графа |
|
|
g_info |
Массив записей графа |
|
|
top |
Номер вершины графа |
|
|
Листинг 9 |
– Подпрограмма поиск соседей указанной вершины в |
представлениях графа (матрица смежности, список ребер, массив записей)
#возвращает соседей указанной вершины по заданной МАТРИЦЕ СМЕЖНОСТИ
def get_neighbours_by_adj_mat(adj_mat, peaks, top):
children = [(i, peaks[i]) for i in range(len(adj_mat)) if adj_mat[top][i] != 0]
parents = [(i, peaks[i]) for i in range(len(adj_mat)) if adj_mat[i][top] != 0]
return tuple(set(children + parents))
#возвращает соседей указанной вершины по заданному СПИСОКУ РЕБЕР def get_neighbours_by_l_edg(top, l_edg):
return tuple(set(i[0][1] if i[0][0][0] == top else i[0][0] for i in l_edg if i[0][0][0] == top or i[0][1][0] == top))
#возвращает соседей указанной вершины по заданному МАССИВУ
ЗАПИСЕЙ
def get_neighbours_by_graph_info(top, g_info, peaks):
return tuple((i, peaks[i]) for i in g_info['№ вершин соседей'][top])
19
Рисунок 12 – Результат работы функции get_neighbours_by_adj_mat
20