РАЗРАБОТКА СИСТЕМЫ ДЛЯ РАБОТЫ С АЛГОРИТМАМИ НА ГРАФАХ Жигмонт Андрей Владимирович e-mail: zhigmont@gmail.com@gmail.com Магистрант ММФ БГУ, кафедра численных. - презентация

1 РАЗРАБОТКА СИСТЕМЫ ДЛЯ РАБОТЫ С АЛГОРИТМАМИ НА ГРАФАХ Жигмонт Андрей Владимирович Магистрант ММФ БГУ, кафедра численных методов и программирования руководитель: СУЗДАЛЬ Станислав Валерьевич, кандидат физ.-мат. наук

2 Введение Теория графов предоставляет исследователям эффектив- ные средства математического моделирования дискретных систем. А задачи исследования таких систем возникают достаточно часто во многих областях, в частности, в теории процессов передачи информации, теории транспортных сетей, в теории распределения ресурсов и планирования производства, и во многих других. При решении таких практических задач активно используются средства вычислительной техники.

3 Немного истории В 2009 году на механико-математическом факультете в СНИЛ Дискретные структуры и алгоритмы начала раз- рабатываться система работы с графовыми моделями и алгоритмами GraphMagic, которая должна была быть лишена многих недостатков других известных специа- лизированных систем.

4 Изучить и проанализировать архитектуру системы GraphMagic и её возможности по расширению. Задачи Разработать плагин(дополнительный программный модуль), позволяющий применять к графам алгоритм поиска множества K реберно-непересекающихся путей между двумя заданными вершинами графа с наименьшей суммой весов ребер, входящих в цепи множества(кратчайшего K множества реберно- непересекающихся цепей), K2.

5 Преимущества GraphMagic Дополняемость Кроссплатформенность Открытость и бесплатность(General Public License version 2, разработанная Free Software Foundation в 1991 году)

6 Основные модули проекта: ядро, оболочка и плагины Архитектура GraphMagic

7 Интерфейс Graph Архитектура GraphMagic

8 Интерфейсы вершины и ребра графа Архитектура GraphMagic

9 Интерфейс GraphMagicPlugin Архитектура GraphMagic

10 Plugin edge-Disjoint-Paths Описание плагина Разработанный плагин позволяет решать две следующие задачи: Построение кратчайшей пары реберно- непересекающихся путей между двумя вершинами; Построение K(K>2) кратчайшего множества реберно- непересекающихся путей между двумя вершинами.

11 Используемые технологии и алгоритмы Описание плагина Технологии: o Java o Swing o JUnit o EasyMock o Maven Алгоритмы: o Алгоритм Дейкстры (Dijkstras algorithm). o Модифицированный aлгоритм Дейкстры (Modified Dijkstras algorithm).

12 Алгоритм нахождения кратчайшей пары реберно- непересекающихся путей между двумя вершинами Описание плагина 1.Находим кратчайший путь Р из стартовой вершины s в конечную вершину t (Алгоритм Дейкстры). 2.Ориентируем (разворачиваем) все рёбра пути Р по направлению от t к s и присваиваем им отрицательный вес. 3.В получившемся графе находим кратчайший путь Q из s в t (используя модифицированный алгоритм Дейкстры). 4.Удаляем из P и Q ребра, принадлежащие и Р и Q. 5.Из P и Q формируются два кратчайших рёберно- непересекающихся пути из s в t.

13 Алгоритм нахождения K(K>2) кратчайшего множества реберно-непересекающихся путей между двумя вершинами Описание плагина 1.Находим кратчайший путь Р из стартовой вершины s в конечную вершину t (Алгоритм Дейкстры). 2.Ориентируем (разворачиваем) все рёбра пути Р по направлению от t к s и присваиваем им отрицательный вес. 3.В получившемся графе находим кратчайший путь Q из s в t (используя модифицированный алгоритм Дейкстры). 4.Ориентируем (разворачиваем) все рёбра пути Q по направлению от t к s и присваиваем им отрицательный вес(если ребро уже было с отрицательным весом, тогда его вес не меняеться).

14 Алгоритм нахождения K(K>2) кратчайшего множества реберно-непересекающихся путей между двумя вершинами Описание плагина Проделываем K-2 раз следующие операции: o В получившемся графе находим кратчайший путь Qi из s в t (используя модифицированный алгоритм Дейкстры). o Ориентируем (разворачиваем) все рёбра пути Qi по направлению от t к s и присваиваем им отрицательный вес(если ребро уже было с отрицательным весом, тогда его вес не меняеться). Удаляем из P,Q,Qi (i=1,K-2) все ребра, принадлежащие хотя бы двум путям. Из P,Q,Qi (i=1,K-2) формируются k кратчайших рёберно- непересекающихся путей из s в t.

15 K=2 Результаты работы плагина

16 K=3 Результаты работы плагина

17 K=4 Результаты работы плагина

18 Изучена и проанализирована система GraphMagic и её возможности по расширению. Заключение Разработан плагин, позволяющий применять к графам алгоритм поиска множества K реберно- непересекающихся путей между двумя заданными вершинами графа с наименьшей суммой весов ребер, K2.

19 СПАСИБО ЗА ЗАВНИМАНИЕ!