492 lines
23 KiB
TeX
492 lines
23 KiB
TeX
\documentclass[bachelor, och, coursework]{SCWorks}
|
||
% параметр - тип обучения - одно из значений:
|
||
% spec - специальность
|
||
% bachelor - бакалавриат (по умолчанию)
|
||
% master - магистратура
|
||
% параметр - форма обучения - одно из значений:
|
||
% och - очное (по умолчанию)
|
||
% zaoch - заочное
|
||
% параметр - тип работы - одно из значений:
|
||
% referat - реферат
|
||
% coursework - курсовая работа (по умолчанию)
|
||
% diploma - дипломная работа
|
||
% pract - отчет по практике
|
||
% pract - отчет о научно-исследовательской работе
|
||
% autoref - автореферат выпускной работы
|
||
% assignment - задание на выпускную квалификационную работу
|
||
% review - отзыв руководителя
|
||
% critique - рецензия на выпускную работу
|
||
% параметр - включение шрифта
|
||
% times - включение шрифта Times New Roman (если установлен)
|
||
% по умолчанию выключен
|
||
\usepackage[T2A]{fontenc}
|
||
\usepackage[cp1251]{inputenc}
|
||
\usepackage{graphicx}
|
||
\usepackage{minted}
|
||
\usepackage{float}
|
||
|
||
\usepackage[sort,compress]{cite}
|
||
\usepackage{amsmath}
|
||
\usepackage{amssymb}
|
||
\usepackage{amsthm}
|
||
\usepackage{fancyvrb}
|
||
\usepackage{longtable}
|
||
\usepackage{array}
|
||
\usepackage[english,russian]{babel}
|
||
\usepackage[colorlinks=true]{hyperref}
|
||
\usepackage{caption}
|
||
\captionsetup[figure]{font=normalsize,labelfont=normalsize}
|
||
|
||
%\newcommand{\eqdef}{\stackrel {\rm def}{=}}
|
||
|
||
%\newtheorem{lem}{Лемма}
|
||
|
||
\begin{document}
|
||
|
||
% Кафедра (в родительном падеже)
|
||
\chair{дискретной математики и информационных технологий}
|
||
|
||
% Тема работы
|
||
\title{Создание приложения для отрисовки графов и алгоритмов для работы с ними}
|
||
|
||
% Курс
|
||
\course{2}
|
||
|
||
% Группа
|
||
\group{221}
|
||
|
||
% Факультет (в родительном падеже) (по умолчанию "факультета КНиИТ")
|
||
%\department{факультета КНиИТ}
|
||
|
||
% Специальность/направление код - наименование
|
||
%\napravlenie{02.03.02 "--- Фундаментальная информатика и информационные технологии}
|
||
%\napravlenie{02.03.01 "--- Математическое обеспечение и администрирование информационных систем}
|
||
\napravlenie{09.03.01 "--- Информатика и вычислительная техника}
|
||
%\napravlenie{09.03.04 "--- Программная инженерия}
|
||
%\napravlenie{10.05.01 "--- Компьютерная безопасность}
|
||
|
||
% Для студентки. Для работы студента следующая команда не нужна.
|
||
%\studenttitle{Студентки}
|
||
|
||
% Фамилия, имя, отчество в родительном падеже
|
||
\author{Морозова Андрея Денисовича}
|
||
|
||
% Заведующий кафедрой
|
||
\chtitle{к.\,ф.-м.\,н., доцент} % степень, звание
|
||
\chname{Л.\,Б.\,Тяпаев}
|
||
|
||
%Научный руководитель (для реферата преподаватель проверяющий работу)
|
||
\satitle{доцент каф. ДМиИТ} %должность, степень, звание
|
||
\saname{О.\,В.\,Мещерякова}
|
||
|
||
% Семестр (только для практики, для остальных
|
||
% типов работ не используется)
|
||
\term{2}
|
||
|
||
% Год выполнения отчета
|
||
\date{2021}
|
||
|
||
\maketitle
|
||
|
||
% Включение нумерации рисунков, формул и таблиц по разделам
|
||
% (по умолчанию - нумерация сквозная)
|
||
% (допускается оба вида нумерации)
|
||
%\secNumbering
|
||
|
||
\tableofcontents
|
||
|
||
% Раздел "Обозначения и сокращения". Может отсутствовать в работе
|
||
%\abbreviations
|
||
%\begin{description}
|
||
% \item SQL "--- англ. structured query language — «язык структурированных запросов;
|
||
% \item $\det B$ "--- определитель матрицы $B$;
|
||
% \item ИНС "--- Искусственная нейронная сеть;
|
||
% \item FANN "--- Feedforward Artifitial Neural Network
|
||
%\end{description}
|
||
|
||
% Раздел "Определения". Может отсутствовать в работе
|
||
%\definitions
|
||
|
||
% Раздел "Определения, обозначения и сокращения". Может отсутствовать в работе.
|
||
% Если присутствует, то заменяет собой разделы "Обозначения и сокращения" и "Определения"
|
||
%\defabbr
|
||
|
||
|
||
% Раздел "Введение"
|
||
\intro
|
||
Целью настоящей работы является изучение работы фреймворка для кроссплатформенной разработки ''Flutter'' и разработка приложения для создания графов и взаимодействия с ними.
|
||
|
||
Поставлены задачи:
|
||
\begin{itemize}
|
||
\item разбор алгоритмов на графах;
|
||
\item разбор работы с Flutter;
|
||
\item построение приложения.
|
||
\end{itemize}
|
||
|
||
\section{Введение}
|
||
\subsection{Графы}
|
||
Граф --- математический объект, состоящий из двух множеств. Одно из
|
||
них --- любое конечное множество, его элементы называются \textit{вершинами}
|
||
графа. Другое множество состоит из пар вершин, эти пары называются
|
||
\textit{ребрами} графа~\cite{IITMMM_2017}.
|
||
|
||
\subsection{Основные определения}
|
||
|
||
\textbf{Ориентированный граф} определяется как пара \textit{(V, E)}, где \textit{V} --- конечное множество, а \textit{E} --- бинарное отношение на \textit{V}, т.~е. подмножество множества ${V \times V}$. Ориентированный граф для краткости называют \textbf{орграфом}. Множество $V$ называют \textbf{множеством вершин графа}, а его элемент называют \textbf{вершиной} графа. Множество $E$ называют \textbf{множеством рёбер}, а его элементы называют \textbf{рёбрами}. Граф может содержать \textbf{рёбра-циклы}, соединяющие вершину с собой. На рисунке~\ref{fig:orgrapf_example} изображен ориентированный граф с множеством вершин \{0, 1, 2, 3, 4\}.~\cite{Algo_2013}
|
||
|
||
\begin{figure}[!ht]
|
||
\centering
|
||
\includegraphics[width=9cm]{./pic/orgraph.png}
|
||
\caption{\label{fig:orgrapf_example}
|
||
Пример орграфа}
|
||
\end{figure}
|
||
|
||
В \textbf{неориентированном} графе $G = (V, E)$ множество ребер состоит из \textbf{неупорядоченных} пар вершин: парами являются множества $\{u, v\}$, где $u, v \in V$ и $u \neq v$. Для неориентированного графа $\{u, v\}$ и $\{v, u\}$ обозначают одно и то же ребро. Неориентированный граф не может содержать рёбер-циклов, и каждое ребро состоит из двух различных вершин. На рисунке~\ref{fig:grapf_example} изображен неориентированный граф с множеством вершин \{0, 1, 2, 2, 4\}
|
||
|
||
\begin{figure}[!ht]
|
||
\centering
|
||
\includegraphics[width=9cm]{./pic/graph.png}
|
||
\caption{\normalsize\label{fig:grapf_example}
|
||
Пример неориентированного графа}
|
||
\end{figure}
|
||
|
||
|
||
Вершина \textit{v} \textbf{смежна} с вершиной \textit{u}, если в графе имеется ребро $\{u, v\}$. Для неориентированных графов отношение смежности является симметричным, но для ориентированных графов это не обязательно.
|
||
|
||
\textbf{Степенью} вершины в неориентированном графе называется число инцидентных ей рёбер. Для ориентированного графа различают исходящую степень, определяемую как число выходящих из неё рёбер, и входящую степень, определяемую как число входящих в неё рёбер. Сумма исходящей и входящей степеней называется степенью вершины.
|
||
|
||
\textbf{Маршрутом} в графе называется конечная чередующаяся последовательность смежных вершин и ребер, соединяющих эти вершины.
|
||
|
||
Маршрут называется открытым, если его начальная и конечная вершины различны, в противном случае он называется замкнутым.
|
||
|
||
Маршрут называется \textbf{цепью}, если все его ребра различны. Открытая цепь называется \textbf{путем}, если все ее вершины различны.
|
||
|
||
Замкнутая цепь называется \textbf{циклом}, если различны все ее вершины, за исключением концевых.
|
||
|
||
Граф называется \textbf{связным}, если для любой пары вершин существует соединяющий их путь.~\cite{intuit}
|
||
|
||
\subsection{Представление графа}
|
||
Граф можно описать несколькими способами.
|
||
|
||
\begin{enumerate}
|
||
\item Перечисление элементов:~\ref{ref:list}.
|
||
\item Матрица смежности:~\ref{ref:smej}.
|
||
\item Матрица инцидентности:~\ref{ref:incident}.
|
||
\item Список смежности:~\ref{ref:spisok}.
|
||
\end{enumerate}
|
||
|
||
Рассмотрим на примере графа на рисунке~\ref{fig:graph_prim1}.
|
||
|
||
\begin{figure}
|
||
\centering
|
||
\includegraphics[width=9cm]{./pic/prim1.png}
|
||
\caption{\label{fig:graph_prim1}
|
||
Рассматриваемый граф}
|
||
\end{figure}
|
||
|
||
\subsubsection{Перечисление элементов}\label{ref:list}
|
||
Исходя из определения, для того, чтобы задать граф, достаточно перечислить его вершины и ребра (т.е. пары вершин).
|
||
|
||
Пример:
|
||
$$ V = \{a, b, c, d, e\} $$
|
||
$$ E = \{(a, b), (a, c), (a, e), (b, c), (b, d), (c, e), (d, e)\}$$
|
||
|
||
\subsubsection{Матрица смежности}\label{ref:smej}
|
||
Пусть $G$ --- граф с $n$ вершинами, пронумерованными числами от 1 до $n$. \textbf{Матрица смежности} --- это таблица с $n$ строками и $n$ столбцами, в которой элемент, стоящий на пересечении строки с номером $i$ и столбца с номером $j$, равен 1, если вершины с номерами $i$ и $j$ смежны, и 0 в противоположном случае.
|
||
|
||
\begin{table}[!ht]
|
||
%\centering
|
||
\caption{Пример матрицы смежности}
|
||
\begin{tabular}{|l|c|c|c|c|}
|
||
\hline 0 & 1 & 1 & 0 & 1\\
|
||
\hline 1 & 0 & 1 & 1 & 0\\
|
||
\hline 1 & 1 & 0 & 0 & 1\\
|
||
\hline 0 & 1 & 0 & 0 & 1\\
|
||
\hline 1 & 0 & 1 & 1 & 0\\
|
||
\hline
|
||
\end{tabular}
|
||
\end{table}
|
||
|
||
\subsubsection{Матрица инцидентности}\label{ref:incident}
|
||
|
||
Пусть $G$ --- граф с вершинами, пронумерованными числами от 1 до $n$, и ребрами, пронумерованными от 1 до $m$. В матрице инцидентности строки соответствуют вершинам, а столбцы рёбрам. На пересечении строки с номером $i$ и столбца с номером $j$ стоит 1, если вершина с номером $i$ инцидентна ребру с номером $j$, и 0 в противном случае.
|
||
|
||
\begin{table}[!ht]
|
||
%\centering
|
||
\caption{Пример матрицы инцидентности}
|
||
\begin{tabular}{|c|c|c|c|c|c|c|}
|
||
\hline 1 & 1 & 1 & 0 & 0 & 0 & 0\\
|
||
\hline 1 & 0 & 0 & 1 & 1 & 0 & 0\\
|
||
\hline 0 & 1 & 0 & 1 & 0 & 1 & 0\\
|
||
\hline 0 & 0 & 0 & 0 & 1 & 0 & 1\\
|
||
\hline 0 & 0 & 1 & 0 & 0 & 1 & 1\\
|
||
\hline
|
||
\end{tabular}
|
||
\end{table}
|
||
|
||
\subsubsection{Списки смежности}\label{ref:spisok}
|
||
Списки смежности часто используются для компьютерного представления графов. Для каждой вершины задается список всех смежных с ней вершин. В структурах данных, применяемых в программировании, списки смежности могут быть реализованы как массив линейных списков.
|
||
|
||
Пример:
|
||
\begin{itemize}
|
||
\item[1] : 2, 3, 5
|
||
\item[2] : 1, 3, 4
|
||
\item[3] : 1, 2, 5
|
||
\item[4] : 2, 5
|
||
\item[5] : 1, 3, 4
|
||
\end{itemize}
|
||
|
||
\subsection{Алгоритмы}
|
||
\subsubsection{Обход в ширину}
|
||
Обход в ширину --- один из основных алгоритмов на графах.
|
||
|
||
Пусть задан граф $G = (V, E)$ и выделена исходная вершина $s$. Алгоритм поиска в ширину систематически обходит все ребра $G$ для «открытия» всех вершин, достижимых из $s$, вычисляя минимальное количество рёбер от $s$ s до каждой достижимой из $s$ вершины.
|
||
|
||
Поиск в ширину имеет такое название потому, что в процессе обхода мы идём вширь, то есть перед тем как приступить к поиску вершин на расстоянии $k + 1$, выполняется обход вершин на расстоянии $k$~\cite{Algo_2013}.
|
||
|
||
Приведенная ниже процедура поиска в ширину BFS предполагает, что входной граф $G = (V, E)$ представлен при помощи списков смежности. Псевдокод алгоритма:
|
||
\inputminted[fontsize=\footnotesize, linenos]{python}{./dart/pseudoBFS.txt}
|
||
|
||
Воспользуемся групповым анализом. Операции внесения в очередь и удаление из нее требует $O(1)$ времени. Следовательно на очередь потребуется $O(V)$ времени. Т.к. максимальная длина списков смежности $\theta(E)$, то время, необходимое для сканирования списков, равно $O(E)$. Расходы на инициализацию: $O(V)$. Таким образом, общее время работы алгоритма: $O(V + E)$. Время поиска в ширину линейно зависит от размера представления графа.
|
||
|
||
\subsubsection{Обход в глубину}
|
||
Стратегия обхода в ширину состоит в том, чтобы идти ''вглубь'' графа. Сначала исследуются ребра, выходящие из вершины, открытой последней, и покидаем вершину, когда не остается неисследованных ребер --- при этом происходит возврат в вершину, из которой была открыта вершина $v$. Процесс продолжается, пока не будут открыты все вершины, достижимые из исходной.
|
||
|
||
Псевдо код алгоритма:
|
||
\inputminted[fontsize=\footnotesize, linenos]{python}{./dart/pseudoDFS.txt}
|
||
|
||
\subsubsection{Алгоритм Дейкстры}
|
||
Алгоритм был предложен голландским исследователем Эдсгером Дейкстрой в 1959 году. Используется для поиска кратчайшего пути от одной вершины до всех остальных. Используется только если вес ребер неотрицательный.
|
||
В алгоритме поддерживается множество вершин $U$, для которых уже вычислены длины кратчайших путей до них из $s$. На каждой итерации основного цикла выбирается вершина, которой на текущий момент соответствует минимальная оценка кратчайшего пути. Вершина $u$ добавляется в множество $U$ и производится релаксация всех исходящих из неё рёбер.
|
||
|
||
Псевдокод алгоритма:
|
||
\inputminted[fontsize=\footnotesize, linenos]{python}{./dart/pseudoDijkstra.txt}
|
||
|
||
\subsubsection{Алгоритм Краскала}
|
||
Алгоритм Краскала — алгоритм поиска минимального остовного дерева во взвешенном неориентированном связном графе. Был описан Джозефом Краскалом в 1956 году.
|
||
|
||
Алгоритм Краскала изначально помещает каждую вершину в своё дерево, а затем постепенно объединяет эти деревья, объединяя на каждой итерации два некоторых дерева некоторым ребром. Перед началом выполнения алгоритма, все рёбра сортируются по весу (в порядке неубывания). Затем начинается процесс объединения: перебираются все рёбра от первого до последнего (в порядке сортировки), и если у текущего ребра его концы принадлежат разным поддеревьям, то эти поддеревья объединяются, а ребро добавляется к ответу. По окончании перебора всех рёбер, все вершины окажутся принадлежащими одному поддереву.\cite{krusc}
|
||
|
||
\inputminted[fontsize=\footnotesize, linenos]{python}{./dart/pseudoKruscal.txt}
|
||
|
||
\section{Инструменты}
|
||
Рассмотрим используемый язык и библиотеку для отрисовки.
|
||
\subsection{Dart}
|
||
В качестве основы используется язык \textbf{Dart}, разработанный компанией Google, и широко используемый для кросс-платформенной разработки~\cite{dart_web}.
|
||
|
||
Dart позиционируется в качестве замены/альтернативы JavaScript. Один из разработчиков языка Марк Миллер (Mark S. Miller) писал, что JavaScript «имеет фундаментальные изъяны»\cite{futureOfJavascript}, которые невозможно исправить.
|
||
|
||
Версия 1.0 вышла в 14 ноября 2013 года.
|
||
Вторая версия была выпущена в августе 2018 года. В языке появилась надежная система типов, т.~е. во время выполнении программы все переменные будут гарантированно указанному типу~\cite{dart_sound}.
|
||
|
||
В Dart используется сборщик мусора. Синтаксис похож на языки: JavaScript, C\#, Java~\cite{dartInAction}.
|
||
|
||
Пример HelloWorld на Dart:
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/helloWorld.dart}
|
||
|
||
Dart поддерживает сокращенную запись. Код примера HelloWorld можно записать так:
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/hW.dart}
|
||
|
||
Концепты языка~\cite{dart_tour}:
|
||
\begin{itemize}
|
||
\item Все, что можно поместить в переменную, является объектом, а каждый объект является частью класса.
|
||
\item Dart -- язык со строгой типизацией, но объявления типов опциональны, т.к. поддерживается определение типа при компиляции.
|
||
\item В версии языка 2.12 появилась Null безопасность. Каждый объект не может быть Null, если не указано обратное.
|
||
\item Поддерживаются дженерики.
|
||
\item Для объявления локальных функций и переменных необходимо начать имя со знака ''\_''.
|
||
\end{itemize}
|
||
.
|
||
\subsection{Flutter}
|
||
Для отрисовки информации используется фреймворк c открытым исходным кодом ''Flutter'', разработанный компанией Google.
|
||
Flutter не использует нативные компоненты для отрисовки интерфейса. В его основе лежит графический движок ''Skia'', написанный преимущественно на С++.
|
||
Skia --- библиотека для работы с 2D графикой с открытым исходным кодом, поддерживающая работу на большом количестве платформ~\cite{skia_docs}
|
||
|
||
Первая версия выпущена в 2015 году под названием ''Sky'', работала только для Android-приложений. Основная заявленная особенность --- высокая графическая производительность (возможность отображения 120 кадров в секунду). Полная поддержка создания веб-приложений появилась в версии 2.0 (март 2021 года), также разрабатывается поддержка создания настольных приложений для Windows, macOS и Linux и Google Fuchsia.
|
||
|
||
Простейший пример приложения с использованием Flutter:
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/flutter.dart}
|
||
Из кода видно, что интерфейс описывается с помощью виджетов.
|
||
Результат приложения изображен на рисунке~\ref{fig:flutter_example}.
|
||
\newpage
|
||
\begin{figure}[!ht]
|
||
\centering
|
||
\includegraphics[width=11cm]{./pic/flutter0.png}
|
||
\caption{\label{fig:flutter_example}
|
||
Простейшее приложение на Flutter}
|
||
\end{figure}
|
||
|
||
\section{Реализация}
|
||
Структура программы разбита на 4 файла:
|
||
|
||
\begin{itemize}
|
||
\item \textbf{main.dart} --- точка входа в программу;
|
||
\item \textbf{drawing\_page.dart} --- страница с описанием работы кнопок;
|
||
\item \textbf{curve\_painter.dart} --- функционал для отрисовки графа;
|
||
\item \textbf{graph.dart} --- класс для хранения графа и манипуляции с ним.
|
||
\end{itemize}
|
||
|
||
\subsection{Графы}
|
||
Информация хранится в виде списков смежности.
|
||
Полный код можно посмотреть в приложении~\ref{graph}.
|
||
\subsubsection{Класс для хранения вершины}
|
||
Класс \textbf{Dot} используется для хранения информации о ребрах, исходящих из данной вершины.
|
||
|
||
Основная информация:
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/graph/dot.dart}
|
||
\textit{String \_name} используется для хранения имени, \textit{int num} используется для хранения номера вершины.
|
||
Информация о ребрах задается в виде \textit{Map<int, int> \_ln}, где каждой вершине можно присвоить вес ребра.
|
||
|
||
Создать вершину можно тремя способами:
|
||
\begin{enumerate}
|
||
\item пустая точка;
|
||
\item из двух списков, где в первом список вершин, а во втором - длины пути;
|
||
\item из \textit{Map<int, int>}.
|
||
\end{enumerate}
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/graph/dot_constr.dart}
|
||
|
||
Для манипуляций с информацией доступно:
|
||
\begin{enumerate}
|
||
\item изменение имени;
|
||
\item добавление пути;
|
||
\item удаление пути.
|
||
\end{enumerate}
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/graph/dot_manip.dart}
|
||
|
||
\subsubsection{Класс для графов}
|
||
Класс \textbf{Graphs} используется для хранения точек и манипуляции с ними.
|
||
|
||
Основная информация:
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/graph/graph.dart}
|
||
\textit{String \_name} исользуется для имени графа, \textit{int \_amount} --- количество вершин, \textit{List<Dot> \_dots} --- массив точек, \textit{Map<int, String> \_nameTable} --- отслеживание имени каждой вершины, \textit{bool \_useLength} --- отслеживание взвешенности графа, \textit{bool \_oriented} --- отслеживание ориентированности графа.
|
||
|
||
Для работы графом доступны функции:
|
||
\begin{enumerate}
|
||
\item \textbf{String? addDot(Dot a)} --- добавление вершины;
|
||
\item \textbf{String? addIsolated(String name)} --- добавление изолированной точки;
|
||
\item \textbf{String? addPath(int from, int to, [int len = 0])} --- добавление пути;
|
||
\item \textbf{String? delPath(int from, int to)} --- удаление пути;
|
||
\item \textbf{String? delDot(int inn)} --- удаление вершины;
|
||
\item \textbf{void flushData()} --- удаление информации из графа;
|
||
\item \textbf{bool checkDots([bool verbose = false])} --- проверка графа на ошибки;
|
||
\item \textbf{void \_fixAfterDel(int inn}) --- испралвение нумерации после удаления;
|
||
\item \textbf{void \_syncNameTable()} --- синхронизация таблицы имен вершин;
|
||
\item \textbf{void setName(String name)} --- изменение имени;
|
||
\item \textbf{String? replaceDataFromFile(String path)} --- заменяет информацию графа на информацию из файла;
|
||
\item \textbf{List<LenDotPath> getSortedPathList()} --- возвращает список всех путей, отсортированный в порядке неубывания;
|
||
\item \textbf{void printG()} --- выводит информацию о графе в консоль;
|
||
\item \textbf{void printToFile(String name)} --- выводит информацию о графе в файл.
|
||
\end{enumerate}
|
||
|
||
Создать граф можно тремя способами:
|
||
\begin{enumerate}
|
||
\item пустой граф;
|
||
\item из списка смежности;
|
||
\item из файла.
|
||
\end{enumerate}
|
||
|
||
\subsubsection{Алгоритмы}
|
||
Алгоритмы описаны в классе графа в приложении~\ref{graph} .\newline
|
||
|
||
Обход в ширину:
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/graph/bfs.dart}
|
||
Обход в глубину:
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/graph/dfs.dart}
|
||
Алгоритм Дейкстры:
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/graph/dijkstra.dart}
|
||
Алгоритм Краскала:
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/graph/kruscal.dart}
|
||
\subsubsection{Интерфейс}
|
||
Интерфейс описан в файле drawing\_page.dart. Полный код доступен в приложении~\ref{buttons}.
|
||
|
||
Интерфейс программы изображен на рисунке~\ref{fig:programm}.
|
||
\begin{figure}[!ht]
|
||
\centering
|
||
\includegraphics[width=13cm]{./pic/grafs.png}
|
||
\caption{\label{fig:programm}
|
||
Интерфейс программы}
|
||
\end{figure}
|
||
\newpage
|
||
В качестве основы выбран виджет, сохраняющий состояние.
|
||
|
||
Построение интерфейса:
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/page/build.dart}
|
||
|
||
Запуск работы алгоритмов происходит по нажатию соответствующих кнопок, затем страница отрисовки, используя полученные данные, выводит на экране информацию.
|
||
\subsubsection{Отрисовка графа}
|
||
Отрисовка элементов графа описана в файле curve\_painter.dart. Код доступен в приложении~\ref{painter}.
|
||
|
||
Для отрисовки информации используется виджет CustomPaint~\cite{custompaint}.
|
||
|
||
Для передачи информации графа используется конструктор CurvePainter.
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/painter/constr.dart}
|
||
|
||
Отрисовка соединений происходит с помощью пакета ''arrow\_path''.
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/painter/arrow.dart}
|
||
|
||
Для упрощения отрисовки, точки располагаются на окружности с центом, совпадающим с центром экрана. Сначала вычисляется их местоположение на экране, точка с максимальным количеством соединений располагается в центре:
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./dart/painter/pos.dart}
|
||
Процесс вывода на экран:
|
||
\begin{enumerate}
|
||
\item вывод вершин на экран;
|
||
\item определение текущей операции и вывод работы текущего алгоритма;
|
||
\item вывод ребер;
|
||
\item вывод длин ребер;
|
||
\item вывод имен вершин.
|
||
\end{enumerate}
|
||
\subsubsection{Итоговый вид приложения}
|
||
Итоговый вид приложения отображен на картинке~\ref{fig:result}
|
||
\begin{figure}[!ht]
|
||
\centering
|
||
\includegraphics[width=15cm]{./pic/result.png}
|
||
\caption{\label{fig:result}
|
||
Интерфейс программы}
|
||
\end{figure}
|
||
\newpage
|
||
% Раздел "Заключение"
|
||
\conclusion
|
||
Было разработано простое приложение для создания и работы с графами с использованием Dart и Flutter.
|
||
|
||
В приложении возможно с помощью графического интерфейса:
|
||
\begin{itemize}
|
||
\item создать пустой граф;
|
||
\item добавить вершину;
|
||
\item удалить вершину;
|
||
\item добавить/изменить путь;
|
||
\item удалить путь;
|
||
\item сохранить граф;
|
||
\item загрузить граф;
|
||
\item построить минимальное остовное дерево с помощью алгоритма Краскала;
|
||
\item найти минимальный путь из выбранной вершины в другие с помощью алгоритма Дейкстры;
|
||
\item проверить доступность вершин с помощью обхода в глубину;
|
||
\item построить путь из одной вершины в другую с помощью обхода в ширину.
|
||
\end{itemize}
|
||
|
||
|
||
%Библиографический список, составленный с помощью BibTeX
|
||
%
|
||
\bibliographystyle{gost780uv}
|
||
\bibliography{thesis}
|
||
|
||
% Окончание основного документа и начало приложений
|
||
% Каждая последующая секция документа будет являться приложением
|
||
\appendix
|
||
|
||
\section{Код main.dart}\label{mainD}
|
||
Точка входа в программу.
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./lib/main.dart}
|
||
|
||
\section{Код страницы отрисовки}\label{buttons}
|
||
Описание интерфейса и базовые функции для взаимодействия с информацией.
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./lib/pages/drawing_page.dart}
|
||
|
||
\section{Код отрисовки графа}\label{painter}
|
||
Вывод на экран информации из графа.
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./lib/src/curve_painter.dart}
|
||
|
||
\section{Код класса для работы с графом}\label{graph}
|
||
Основной класс для хранения и взаимодействия с информацией.
|
||
\inputminted[fontsize=\footnotesize, linenos]{dart}{./lib/src/graph.dart}
|
||
|
||
\noindent
|
||
\end{document}
|