Курсовая Реализация и моделирование графовой структуры данных. Алгоритм поиска минимального остовного дерева методом Прима. Майков отчет. Федеральное государственное бюджетное образовательное учреждение высшего образования московский авиационный институт
 Скачать 1.22 Mb.
|
 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ (НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)» (МАИ) филиал «РКТ» МАИ в г. Химки Московской области Специальность 09.02.07 Информационные системы и программирование Группа ИСП 31 Квалификация специалист по информационным системам КУРСОВОЙ ПРОЕКТ (РАБОТА) по_МДК 01.01. Разработка модулей программного обеспечения для компьютерных систем (указывается код и название дисциплины, МДК, ПМ) На тему: Реализация и моделирование графовой структуры данных. Алгоритм поиска минимального остовного дерева методом Прима позиций.______________________________________________________________________ Автор курсового проекта (работы) Майков Семён Андреевич_________(подпись) (Фамилия Имя Отчество) Руководитель Шумаев Александр Юрьевич____________________________(подпись) (Фамилия Имя Отчество) Химки 2022 г. МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ (НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)» (МАИ) филиал «РКТ» МАИ в г. Химки Московской области Специальность 09.02.07 Информационные системы и программирование Группа ИСП 31 Квалификация специалист по информационным системам З А Д А Н И Е на курсовой проект (работу) по МДК 01.01. Разработка модулей программного обеспечения для компьютерных систем_ (указывается код и название дисциплины, МДК, ПМ) Студенту Майкову Семёну Андреевичу (Фамилия Имя Отчество) Руководитель Шумаев Александр Юрьевич (Фамилия Имя Отчество) 1. Наименование темы: Реализация и моделирование графовой структуры данных. Алгоритм поиска минимального остовного дерева методом Прима 2. Срок сдачи студентом законченной работы _____________________________ 3. Техническое задание и исходные данные к работе: Реализация и моделирование графовой структуры данных. Алгоритм поиска минимального остовного дерева методом Прима . Предусмотреть возможность выполнения операций вставки, удаления и сохранения в базе данных. Разработать графический интерфейс отражающий принцип работы модуля. Выполнить тестирование и профилирование модулей. Выполнить интеграцию модулей в монолитную программу. 4. Перечень подлежащих разработке разделов и этапы выполнения работы
5. Перечень иллюстративно-графических материалов:
6. Исходные материалы и пособия ГОСТ 7.32―2017 отчет о научно-исследовательской работе _________________________ Алгоритмы: построение и анализ, 3-е издание: Пер. с англ.: учебное пособие / Корм_Томас Х., Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн; Москва, Санкт-Петербург, Киев: ООО “И. Д. Вильямс”, 2013. – 1238 с. - ISBN 978-5-8459-1794-2 (рус.).__________________ _____________________________________________________________________________ 7. Дата выдачи задания 15.03.21 Руководитель (подпись) Задание принял к исполнению (подпись) СОДЕРЖАНИЕ ВВЕДЕНИЕ 5 1Алгоритм Прима 6 3 Описание тестовых работ 12 4 Описание способа сборки программы 14 5 Описание способа и методов взаимодействия с базой данных 17 2Результаты проведения исследования структуры данных Linked List 18 ЗАКЛЮЧЕНИЕ 21 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 22 ПРИЛОЖЕННИЕ А. Исходный код программы 23 А.2 Код файла «main.py» 24 А.3 Код файла «DataBase.py» 30 ПРИЛОЖЕНИЕ Б. Исходный код функциональных тестов 32 ПРИЛОЖЕНИЕ Г. Листинг результатов профилирования модуля 36 ПРИЛОЖЕНИЕ Д. Исходный код профилирования 36 ВВЕДЕНИЕТема данной курсовой работы: «Реализация и моделирование графовой структуры данных. Алгоритм поиска минимального остовного дерева методом Прима .». Алгоритм Прима - используется для нахождения минимального остовного дерева графа. Алгоритм примитива начинается с любого узла, а затем добавляет любой соседний узел с минимальным весом, и этот процесс продолжается до тех пор, пока не будут посещены все узлы в графах. При создании минимального остовного дерева графа мы также не должны создавать циклы, потому что циклов не должно быть в минимальном остовном дереве. Целью курсовой работы является разработка программного модуля, реализующего основной функционал данной структуры данных. Задачи курсовой работы: 1) Изучить современную литературу для выявления основных алгоритмов работы, Алгоритма Прима 2) Определить и разработать модули программы необходимые отображения интерфейса для работы со структурой данных. 3) Реализовать модуль, отвечающий за сохранение структуры данных в базу данных. 4) Провести тестирование модуля, отвечающий за структуру данных. 5) Провести тестирование модуля, отвечающий за интерфейс программы. 6) Создать модуль, реализующий профилирование модуля «main». Алгоритм ПримаАлгоритм Прима – это жадный алгоритм, который находит минимальное остовное дерево для взвешенного неориентированного графа. Это означает, что он находит подмножество ребер, которое образует дерево, включающее каждую вершину, где общий вес всех ребер в дереве минимизируется. Алгоритм Прима используется для нахождения минимального остовного дерева графа. Алгоритм примитива начинается с любого узла, а затем добавляет любой соседний узел с минимальным весом, и этот процесс продолжается до тех пор, пока не будут посещены все узлы в графах. Преимущества: Гарантия получения глобально оптимального решения Число итераций равно │Х│ - 1, где Х– множество вершин. Простота и наглядность Недостатки алгоритма : Алгоритм применим только к неориентированным графам. Выбираем чисто случайно вершину E,далее рассмотрим все ребра исходящие из нее, включаем в наше остовное дерево ребро C <--> E; w = 9, так как данное ребро имеет минимальный вес из всех рёбер инцидентных множеству вершин нашего подграфа. Имеем следующее:  Рисунок 1 – Подграф после добавления 1-го ребра Теперь выборка производится из рёбер: D <--> C; w = 6 A <--> C; w = 8 F <--> E; w = 10 B <--> C; w = 11 D <--> E; w = 11 То есть, в данный момент, мы знаем только о двух вершинах, соответственно, знаем о всех ребрах, исходящих из них. Про связи между другими вершинами, которые не включены в наш подграф, мы ничего не знаем, поэтому они на этом шаге не рассматриваются. Добавляем в наш подграф реброD <--> C и по аналогии добаляем ребро D <--> B. Получаем следующее:  Рисунок 2 –Подграф, полученный после добавления рассмотренных рёбер Давайте добьем наш подграф до минимального остовного дерева. Вы, наверное, уже догадались о том, по каким ребрам мы будем связывать наши оставшиеся вершины: A и F. Проводим последние штрихи и получили тот же самый подграф в качестве минимального остовного дерева. Но как мы раннее говорили, сам подграф ничего не решает, главное тут - множество рёбер, которые включены в наше остовное дерево.  Рисунок 3 –Искомое минимальное остовное дерево 2 Техническое задание Описание графического интерфейсаПосле запуска main.py откроется интерфейс, в котором слева находится панель управления для изменения данных в структуре и справа таблица для отображения данных из структуры на рисунке 4.  Рисунок 4 – интерфейс программы Добавить вершину – добавление вершину. Эта вершина отобразиться на экране (смотреть рисунок 5).  Рисунок 5 – результат добавления вершины Добавить/изменить путь к вершине – после нажатия появляется окно для создание путя к выбранной вершине. В окне можно выбрать вершины и значение. После нажатия кнопки создать появится путь (смотреть рисунок 6 и рисунок 7).  Рисунок 6 – результат нажатия кнопки Добавить/изменить путь к вершине  Рисунок 7 – результат нажатия кнопки создать Найти кратчайший путь – при нажатие будет выполнен алгоритм Прима. Результатом нажатия будет изменение цвета путей с синего на красный. На рисунке 8  Рисунок 8 –нажатие на Найти кратчайший путь Граф — при нажатие появляется возможность сохранить созданный граф в бд, а также загрузить граф из бд (смотреть рисунок 9).  Рисунок 9 – результат нажатия Граф Загрузить из бд – при нажатие появляется оно в котором можно выбрать уже созданный граф. После нажатия на ОК открывается созданный графи (рисунок 10 и рисунок 11)  Рисунок 10 – результат нажатия загрузить из бд  Рисунок 11 – результат нажатия ОК 3 Описание тестовых работОписание наборов функциональных тестовыхТаблица 1 – функциональные тесты
Описание набора модульных тестовТаблица 2 – модульные тесты
4 Описание способа сборки программыЯзык Python сам по себе не компилируемый, в нем не задумывалась возможность преобразования программ в исполняемый вид. Вместо этого, в языке используется интерпретатор, который переводит код языка в машинный и выполняет его на месте. В теории, можно взять интерпретатор Python и объединить его с программой и её компонентами, получив портативную программу, которую можно запускать без установки языка. Скорее всего эта мысль и пришла в голову разработчикам пакета Pyinstaller, выполняющего все эти действия. Одним из преимуществ этого пакета является то, что он собирает только необходимые зависимости, а не все подряд, поэтому приложение на выходе имеет меньший вес по сравнению с другими библиотеками. PyInstaller собирает в один пакет Python-приложение (.exe) и все необходимые ему библиотеки следующим образом: Считывает файл скрипта. Анализирует код для выявления всех зависимостей, необходимых для работы. Создает файл spec, который содержит название скрипта, библиотеки-зависимости, любые файлы, включая те параметры, которые были переданы в команду PyInstaller. Собирает копии всех библиотек и файлов вместе с активным интерпретатором Python. Создает папку BUILD в папке со скриптом и записывает логи вместе с рабочими файлами в BUILD. Создает папку DIST в папке со скриптом, если она еще не существует. Записывает все необходимые файлы вместе со скриптом или в одну папку, или в один исполняемый файл. Pyinstaller поддерживает Python 2.7, Python 3.3 и выше, такие библиотеки как: numpy, PyQt, Django, wxPython, Tkinter и другие. Команда для установки pyinstaller через pip - pip install pyinstaller (смотреть рисунки 7 и 8).  Рисунок 9 – установка pyinstaller Продолжение установки pyinstaller через pip смотреть на рисунке 10.  Рисунок 11 – продолжение установки pyinstaller Возьмем в качестве примера код курсовой работы на Python c файлами gui.py. Создадим один исполняемый файл. В командной строке вводим: pyinstaller --onefile gui.py. Если же при открытии .exe файла не нужна консоль, тогда в команду добавляем параметр -w: pyinstaller -w --onefile gui.py (смотреть рисунок 12).  Рисунок 13 – создание исполняемого файла После выполнении команды будет создана папка dist с исполняемым файлом gui.py. (рисунок 14).  Рисунок 15 – результат создания После этого можно запускать .exe файл. (рисунок 16).  Рисунок 17 – окно исполняемого файла 5 Описание способа и методов взаимодействия с базой данныхSQL и Python — обязательные инструменты для любого специалиста в сфере анализа данных. SQLite – это автономный, работающий без сервера механизм базы данных SQL. Python получил модуль sqlite3 в версии 2.5, что значит, что вы можете создавать базу данных SQLite в любой настоящей версии Python, без необходимости скачивания дополнительных инструментов. Mozilla использует базы данных SQLite в своем популярном браузере Firefox для хранения закладок и прочей различной информации. База данных – это совокупность таблиц или же в некоторых случаях всего одна таблица (смотреть рисунок 26).  Рисунок 26 – Схема данных Таблицы в свою очередь состоят из столбцов и строк, в которых хранятся данные. Пример таблицы с двумя столбцами, приведен на рисунке 27.  Рисунок 27 – Пример таблицы с данными В данной курсовой работе для хранения структуры данных связанного списка была использована база данных SQLite с расшерением .db, которая реализована с помощью библиотеки sqlite3 (смотреть приложение А). Все методы взаимодействия с базой данных реализованы в файле «DataBase.py» Класс «DataBase» содержит следующие методы: 1) «__init__» - вызывается при создании объекта класса «DataBase». Данный метод создаёт базу данных с названием, что передается при создании объекта данного класса. В данном случае база данных будет называться «Primo.db». База данных создастся в той же папке, что и «DataBase.py» при условии, что в данной папке нет базы данных с таким же названием, иначе база данных создана не будет. Данная база данных будет содержать всего одну таблицу – «BloomFilter», имеющую два поля (столбца): «id» и «str» 2) «insert» - метод, который нужен для вставки данных (id и str) в базу данных. 3 «update» - метод, который нужен для обновления данных в БД 4) «delete» - Нужен, чтобы удалить все данные из базы данных (id и str). Результаты проведения исследования структуры данных Linked ListПрофилирование модуля нужно, чтобы понять сколько по времени выполняется та или иная функция. Зная, время выполнения функции можно понять, что тормозит программу и какой модуль можно оптимизировать. Для создания файла с покрытием тестов необходимо установить coverage. Для этого нужно ввести в терминал следующую команду: pip install coverage (смотреть рисунок 39).  Рисунок 39 – установка coverageФайл с покрытием тестов нужен, чтобы узнать на сколько проверен модуль с помощью тестов. Далее запускаем файлы тестов с помощью команды coverage run -m unittest discover (смотреть рисунок 40).  Рисунок 40 – запуск тестов И создаем html файл с покрытием тестов кода с помощью команды coverage html (рисунок 41).  Рисунок 41 – создание HTML файла с результатами покрытия В итоге создастся файл index.html в папке htmlcov. Покрытие кода модульными и функциональными тестами приведено на рисунке 42.  Рисунок 42 – Покрытие кода Чтобы вывести результат покрытия кода в терминал, нужно в консоли ввести следующую команду: coverage report -m. Результат приведён на рисунке 43.  Рисунок 43 – покрытие кода в консоли ЗАКЛЮЧЕНИЕВ ходе выполнения курсовой работы была достигнута её цель и решены следующие задачи: Изучена современная литература для выявления основных алгоритмов работы структуры данных связанного списка. Были выявлены основные свойства алгоритма работы. Выполнено описание основных функций структуры данных. Определены и разработаны модули программы необходимые для выполнения визуализации структуры данных связанного списка. А именно: Модуль, который реализует операции структуры данных связанного списка (смотреть приложение А). Модуль, реализующий графический интерфейс программы (смотреть приложение А). Графический интерфейс программы обладает возможностью отобразить изменения, вносимые пользователем в структуру данных списка, то есть выполняет прямое отображение всех изменений структуры данных. Модуль, реализующий сохранение структуры данных в базе данных (смотреть приложение А). Проведено тестирование программного модуля с целью проверки соответствия алгоритмам работы данной структуры. Были написаны следующие модули: Модуль, реализующий тесты основных операций над структурой данных алгоритма Прима (смотреть приложение В). Нужен для проверки модуля «graph» на работоспособность. Модуль, реализующий функциональные тесты (смотреть приложение Б). Нужен для проверки модуля «main» на работоспособность. Модуль, реализующий профилирование модуля «graph» (результаты профилирования смотреть в приложении Г, код профилирования смотреть в приложение Д). Нужен для проверки модуля «graph» на его практическое применение. В ходе написания курсовой роботы были закреплены основы в области разработки программных модулей. Результатом закрепленных знаний являются разработанные и корректно функционирующие модули программы. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВГОСТ 7.32-2017 отчет о научно-исследовательской работе. Python 3 и PyQt 5. Разработка приложений. — 2-е изд., перераб. и доп. / Н. А. Прохоренок, В. А. Дронов. — СПб.: БХВ-Петербург, 2018. — 832 с.: ил. — (Профессиональное программирование) Дональд Р. Шихин – Структуры данных в Python: начальный курс / пер. с англ.А. В. Снастина. – М.: ДМК Пресс, 2022. – 186 с.: ил. ПРИЛОЖЕННИЕ А. Исходный код программыА.1 Код файла «graph.py»Сlass Graph: def __init__(self, V, G): self.V = V self.G = G def elprimo(self): result = [] self.V = 5 selected = [0] * self.V no_edge = 0 selected[0] = True print("Edge : Weight") # Нужно выбрать V-1 while no_edge < self.V - 1: minimum = float("inf") x = y = 0 # Узлы пересечения V for i in range(self.V): # Выбранный узел if selected[i]: for j in range(self.V): # Выбранные соседние узлы не выделены и имеют ребра if (not selected[j]) and self.G[i][j]: if minimum > self.G[i][j]: minimum = self.G[i][j] x, y = i, j result.append([x, y]) print(str(x) + "-" + str(y) + ":" + str(self.G[x][y])) selected[y] = True no_edge += 1 return result def to_str(self): self.matrix = [] for i, m in enumerate(self.G): self.matrix.append('') for num in m: self.matrix[i] = self.matrix[i] + str(num) + ' ' print(self.matrix) return self.matrix if __name__ == '__main__': matrix = [[0, 1, 0, 0, 0, 3], [1, 0, 2, 0, 3, 0], [0, 2, 0, 3, 0, 0], [0, 0, 3, 0, 4, 0], [0, 3, 0, 4, 0, 5],[3, 0, 0, 0, 5, 0]] size = len(matrix) graph = Graph(size, matrix) graph.elprimo() graph.to_str() А.2 Код файла «main.py»import sys import networkx as nx from PyQt5 import QtWidgets from PyQt5.QtWidgets import QWidget, QApplication, QGridLayout, QMenuBar, QPushButton, QMessageBox, \ QDialog, QInputDialog, QComboBox import matplotlib.pyplot as plt from matplotlib.backends.backend_qt5agg import FigureCanvasQTAgg as FigureCanvas from DataBase import DataBase from graph import Graph class EditWayDialog(QDialog): def __init__(self, parent=None): super(EditWayDialog, self).__init__(parent) self.parent = parent self.resize(200, 100) self.setWindowTitle('Путь к вершине') self.setModal(True) self.from_line = QComboBox() self.to_line = QComboBox() self.value = QtWidgets.QSpinBox() self.btn_confirm = QtWidgets.QPushButton("Создать") self.from_line.addItems(self.parent.list_vertex) self.to_line.addItems(self.parent.list_vertex) self.form = QtWidgets.QFormLayout() self.form.setSpacing(20) self.form.addRow("&Из вершину:", self.from_line) self.form.addRow("&В вершину:", self.to_line) self.form.addRow("&Значение:", self.value) self.form.addRow(self.btn_confirm) self.setLayout(self.form) self.btn_confirm.clicked.connect(self.confirm_way) def confirm_way(self): from_index = self.from_line.currentIndex() to_index = self.to_line.currentIndex() if from_index == to_index: QMessageBox.critical(self, 'Ошибка', 'Невозможно создать путь к одной и той же вершине!') return 0 distance = self.value.value() self.parent.matrix[from_index][to_index] = distance self.parent.matrix[to_index][from_index] = distance self.parent.update_view() class Window(QWidget): def __init__(self): super(Window, self).__init__() self.initUI() self.setWindowTitle('Граф и метод Прима') self.graph = nx.Graph() self.list_vertex = [] self.matrix = [] self.short_way = [] def initUI(self): self.grid = QGridLayout() self.setLayout(self.grid) self.figure = plt.figure() self.canvas = FigureCanvas(self.figure) self.grid.addWidget(self.canvas, 0, 0, 1, 3) self.btn_add = QPushButton('Добавить вершину') self.btn_add.clicked.connect(self.add_vertex) self.grid.addWidget(self.btn_add, 1, 0) self.btn_way = QPushButton('Добавить/изменить путь к вершине') self.btn_way.clicked.connect(self.open_way_windows) self.grid.addWidget(self.btn_way, 1, 1) self.btn_find = QPushButton('Найти кратчайший путь') self.btn_find.clicked.connect(self.find_short_way) self.grid.addWidget(self.btn_find, 1, 2) menu_bar = QMenuBar() menu_project = menu_bar.addMenu('Граф') action_new = menu_project.addAction('новый граф') action_save = menu_project.addAction('Сохранить граф в БД') action_load = menu_project.addAction('Загрузить граф из БД') action_new.triggered.connect(self.create_graph) action_save.triggered.connect(self.save_graph) action_load.triggered.connect(self.load_graph) self.grid.setMenuBar(menu_bar) def open_way_windows(self): self.ui = EditWayDialog(self) self.ui.show() def create_graph(self): self.graph = nx.Graph() self.list_vertex = [] self.matrix = [] self.update_view() def save_graph(self): value, ok = QInputDialog.getText(self, 'Сохранить граф', 'Введите название сохранения') if ok: convert_data = ' '.join([','.join(list(map(str, arr))) for arr in self.matrix]) db = DataBase() db.insert('Matrix', {'name': value, 'str': convert_data}) QMessageBox.information(self, 'Сохранение графа', 'Успешно сохранён граф') db.close() def load_graph(self): db = DataBase() data = db.select('Matrix', ['name']) data = [item['name'] for item in data] if len(data) == 0: QMessageBox.information(self, 'Загрузка графа', 'в БД нет сохранённых графов!') return 0 value, ok = QInputDialog.getItem(self, 'Загрзука графа', 'Выберите граф из БД', data, 0, False) if ok: data = db.select('Matrix', ['str'], f'`name`="{value}"')[0]['str'] convert_data = [list(map(int, arr.split(','))) for arr in data.split(' ')] self.matrix = convert_data self.list_vertex = [chr(ord('A') + i) for i in range(len(self.matrix))] self.update_view() db.close() def add_vertex(self): self.list_vertex.append(chr(ord('A') + len(self.list_vertex))) for arr in self.matrix: arr.append(0) self.matrix.append([0 for i in range(len(self.matrix)+1)]) self.update_view() def find_short_way(self): graph = Graph(len(self.matrix), self.matrix) result = graph.elprimo() short_way = [] #for i in range(1, len(result)): # if result[i*-1][0] == 0: # short_way = result[i*-1:] # break self.short_way = result self.update_view() def update_view(self): plt.clf() self.graph = nx.Graph() for vertex in self.list_vertex: self.graph.add_node(vertex) for i in range(len(self.matrix)): for j in range(i+1, len(self.matrix[i])): if self.matrix[i][j] > 0: if len(self.short_way) > 0: if [i, j] in self.short_way: print('lol') self.graph.add_edge(self.list_vertex[i], self.list_vertex[j], color='r', weight=self.matrix[i][j]) continue self.graph.add_edge(self.list_vertex[i], self.list_vertex[j], color='b', weight=self.matrix[i][j]) pos = nx.spring_layout(self.graph) colors = nx.get_edge_attributes(self.graph, 'color').values() nx.draw(self.graph, pos, with_labels=True, edge_color=colors) labels = nx.get_edge_attributes(self.graph, 'weight') nx.draw_networkx_edge_labels(self.graph, pos, edge_labels=labels) self.canvas.draw_idle() app = QApplication(sys.argv) if __name__ == '__main__': w = Window() w.resize(1000, 600) w.show() sys.exit(app.exec_()) А.3 Код файла «DataBase.py»import sqlite3 class DataBase: def __init__(self, debug: bool = False): self.con = sqlite3.connect(':memory:') if debug else sqlite3.connect('Primo') cursor = self.con.cursor() cmd = f'CREATE TABLE IF NOT EXISTS Matrix(id INT PRIMARY KEY, str TEXT, name TEXT)' cursor.execute(cmd) def close(self): self.con.close() def select(self, name_table: str, fields: list, condition: str = '') -> list: cursor = self.con.cursor() for field in fields: field = f'`{field}`' if len(condition) > 0: condition = 'WHERE ' + condition cmd = f'SELECT {",".join(fields)} FROM {name_table} {condition}' cursor.execute(cmd) result = cursor.fetchall() result2 = [] for data in result: data_dict = {} for index, field in enumerate(fields): data_dict[field] = data[index] result2.append(data_dict) self.con.commit() return result2 def insert(self, name_table: str, data: dict) -> int: cursor = self.con.cursor() fields = [] values = [] for key, value in data.items(): fields.append(f'`{key}`') if type(value) is int: values.append(f'{value}') else: values.append(f'\'{value}\'') cmd = f'INSERT INTO `{name_table}` ({",".join(fields)}) VALUES ({",".join(values)})' try: cursor.execute(cmd) self.con.commit() return 0 except Exception as ex: template = "An exception of type {0} occurred. Arguments:\n{1!r}" message = template.format(type(ex).__name__, ex.args) print(message) return 1 def delete(self, name_table: str, condition: str) -> bool: cursor = self.con.cursor() cmd = f'DELETE FROM {name_table} WHERE {condition}' try: cursor.execute(cmd) self.con.commit() return True except: return False ПРИЛОЖЕНИЕ Б. Исходный код функциональных тестовimport os import sys import unittest from threading import Timer from PyQt5 import QtCore from PyQt5.QtTest import QTest from main import Window from PyQt5.QtWidgets import QApplication class MyTestCase(unittest.TestCase): def setUp(self): self.w = Window() def msg_close(self): msg = QApplication.activeWindow() msg.close() def msg_ok(self): msg = QApplication.activeWindow() msg.done(1) msg.close() def test_add(self): for i in range(5): QTest.mouseClick(self.w.btn_add, QtCore.Qt.LeftButton) self.assertEqual(self.w.graph.number_of_nodes(), 5) def test_way(self): for i in range(6): QTest.mouseClick(self.w.btn_add, QtCore.Qt.LeftButton) QTest.mouseClick(self.w.btn_way, QtCore.Qt.LeftButton) for i in range(5): self.w.ui.from_line.setCurrentIndex(i) self.w.ui.to_line.setCurrentIndex(i+1) self.w.ui.value.setValue(i+1) QTest.mouseClick(self.w.ui.btn_confirm, QtCore.Qt.LeftButton) self.assertEqual(list(self.w.graph.edges), [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'F')]) def test_find(self): for i in range(6): QTest.mouseClick(self.w.btn_add, QtCore.Qt.LeftButton) QTest.mouseClick(self.w.btn_way, QtCore.Qt.LeftButton) for i in range(5): self.w.ui.from_line.setCurrentIndex(i) self.w.ui.to_line.setCurrentIndex(i+1) self.w.ui.value.setValue(i+1) QTest.mouseClick(self.w.ui.btn_confirm, QtCore.Qt.LeftButton) for i in range(3): self.w.ui.from_line.setCurrentIndex(i) self.w.ui.to_line.setCurrentIndex(5-i) self.w.ui.value.setValue(3) QTest.mouseClick(self.w.ui.btn_confirm, QtCore.Qt.LeftButton) QTest.mouseClick(self.w.btn_find, QtCore.Qt.LeftButton) self.assertEqual(self.w.short_way,[[0, 1], [1, 2], [1, 4], [2, 3]]) def test_save_and_load(self): os.rename('Primo', 'Primo.tmp') for i in range(15): QTest.mouseClick(self.w.btn_add, QtCore.Qt.LeftButton) Timer(0.5, self.msg_ok).start() Timer(1, self.msg_close).start() self.w.save_graph() Timer(0.5, self.msg_ok).start() Timer(1, self.msg_close).start() self.w.save_graph() Timer(0.5, self.msg_ok).start() self.w.load_graph() os.remove('Primo') os.rename('Primo.tmp', 'Primo') self.assertEqual(self.w.graph.number_of_nodes(), 15) if __name__ == '__main__': unittest.main() ПРИЛОЖЕНИЕ В. Исходный код модульных тестов import unittest from graph import Graph class MyTestCase(unittest.TestCase): def test_graph_build(self): matrix = [[0, 1, 0, 0, 0, 3], [1, 0, 2, 0, 3, 0], [0, 2, 0, 3, 0, 0], [0, 0, 3, 0, 4, 0], [0, 3, 0, 4, 0, 5], [3, 0, 0, 0, 5, 0]] size = len(matrix) graph = Graph(size, matrix) res = graph.to_str() self.assertEqual(res, ['0 1 0 0 0 3 ', '1 0 2 0 3 0 ', '0 2 0 3 0 0 ', '0 0 3 0 4 0 ', '0 3 0 4 0 5 ', '3 0 0 0 5 0 ']) def test_find(self): matrix = [[0, 1, 0, 0, 0, 3], [1, 0, 2, 0, 3, 0], [0, 2, 0, 3, 0, 0], [0, 0, 3, 0, 4, 0], [0, 3, 0, 4, 0, 5], [3, 0, 0, 0, 5, 0]] size = len(matrix) graph = Graph(size, matrix) res = graph.elprimo() self.assertEqual(res, [[0, 1], [1, 2], [1, 4], [2, 3]]) if __name__ == '__main__': unittest.main() ПРИЛОЖЕНИЕ Г. Листинг результатов профилирования модуляРезультаты профилирования методов «addL», «ins», «rmv» с одним тысячам чисел (от 0 до 999 включительно) приведены на рисунке 44.  Рисунок 44 – результаты профилирования ПРИЛОЖЕНИЕ Д. Исходный код профилированияimport cProfile from DataBase import DataBase from graph import Graph cProfile.run('DataBase()') db = DataBase() cProfile.run('db.select("Matrix",["id", "name", "name"])') cProfile.run('db.delete("Matrix", "`id`=-1")') cProfile.run('db.is_except("Matrix", "`id`=-1")') cProfile.run('Graph(0, [])') |