«Применение ит при решении задач теории графов» (стр. 2 из 4)
1. Вызвать команду добавления плагина.
2. Выбрать необходимый плагин (весь плагин должен помещаться в одном файле)
3. Использовать функциональность плагина без перезагрузки приложения.
2.1.2 Кроссплатформенность
Второй основной особенностью системы является возможность её использования под различными операционными системами, используемыми целевой аудиторией пользователей. Как основные, поддерживаються следующие семейства операционных систем с графическим интерфейсом: Linux, Windows, Mac OS X последних версий.
Кроссплатформенность здесь означает возможность работы приложения в большинстве широко используемых средах, таких, которые использует целевая аудитория. Естесственно, что, так как система предназначена для визуализации, операционные системы должны обладать графическим интерфейсом.
2.1.3 Открытость и бесплатность
Третьей, особенностью системы является её разработка по модели open-source, которая позволяет использовать, распространять, изменять, распространять изменения любому заинтересованному лицу на бесплатной основе.
В связи с этим для разработки, тиражирования, передачи и изменения была принята лицензия GPLv2 (General Public License version 2) – стандартной общественной лицензии версии 2 разработанной Free Software Foundation в 1991 году.
2.2 Архитектура системы GraphMagic
Система GraphMagic логически разделена на несколько модулей, по функциям, ими выполняемым. Каждый модуль при сборке системы собирается в один архивный файл с именем модуля, версией модуля и общепринятым расширением .jar. Например, модуль gm-core версии 0.2, при сборке запакуется в файл gm-core-0.2.jar.
Проект разделён на 3 модуля: ядро, оболочка, и плагины. Ядро – центральный модуль системы, не зависит от других. Модуль оболочки – зависит от ядра. Плагины также зависят от ядра, причем изменения в визуализации графа «слушаются» модулем оболочки и автоматически отображаются на экране пользователя. Эта отображена на диаграмме ниже:
Зависимости между модулями
Первый модуль – gm-core, ядро системы. Содержит основные интерфейсы необходимые остальным модулям и плагинам, а также базовые их базовые реализации. Стоить отметить, что разработчикам плагинов рекомендуется создавать собственные форматы хранения данных графа, так как базовые реализации не могут удовлетворить всех потребностей всех алгоритмов на графах. Таким образом, естесственно предположить что каждый алгоритм по возможности должен отделять свою логику от логики базовой реализации структуры графа. Например, граф в базовой реализации интерфейса Graph – BasicGraph задаётся множеством вершин и множеством рёбер. Но для многих алгоритмов гораздо удобнее было бы пользоваться матричным представлением графа, особенно если элементами матрицы могут являться различные числовые значения, метки, стрелки и т. п. Поэтому плагин, реализующий такой алгоритм должен сам создавать структуру хранения графа используя предоставленный интерфейс, а после выполнения алгоритма возвращать полученный результат обратно в граф через этот же интерфейс.
На следующей диаграмме изображены некоторые основные интерфейсы и базовые реализации ядра системы.
Диаграмма одного из основных интерфейсов – Graph
Диаграммы интерфейсов вершины и ребра графа.
Разберём подробнее эти интерфейсы. У каждой вершины есть внутренний идентификатор (см. getId()), который используется для уникального идентифицирования вершины в графе. На данный момент система отображает этот идентификатор как метки вершин в визуализации графа, но в дальнейшем можно будет изменять визуализацию вершины произвольно.
Каждая вершина и ребро имеют смысл только в контексте некоторого графа. Поэтому в базовых реализациях нельзя создать объект вершины напрямую, а только через методы графа. Каждая вершина и ребро имеют ссылку на граф которому они принадлежат и используют её во внутренних реализациях. Например возьмём ребро, имеющее своей начальной вершиной (getTail()) вершину 1, и своей конечной вершиной (getHead()) вершину 2. Стандартный Java метод equals(), определяющий равенство этих объектов работает в зависимости от того, направлен наш граф или нет. Таким образом метод equals() для ребра (2,1) вернет значение «истина», если граф ненаправленный, и значение «ложь» если граф направленный.
Также, у каждой вершины и ребра имеется пометка (getMark()), которая содержит список значений, для использования в плагинах и визуализации.
Диаграмма интерфейса визуальной части вершины или ребра.
Стоит заметить, что сама визуализация вершины или ребра содержится в модуле gm-shell, этот же интерфейс визуализации доступен для плагинов и содержит всю необходимую информацию о расположении, цвете и выделенности элементов графа. Также было принято архитектурное решение преобразовывать координаты из точечных координат графической оболочки в пикселах в дробные координаты по следующему принципу:
· значение координаты равное 0 соответствует середине видимой на экране части визуализации графа,
· значение координаты равное 1 соответствует правому/нижнему краю видимой на экране части визуализации графа,
· значение координаты равное -1 соответствует левому/верхнему краю видимой на экране части визуализации графа,
· остальные значения пропорционально расчитываются по формулам:
X = (2x – 2Rx – Rw)/Rw;
Y = (2y – 2Ry – Rh)/Rh;
Где
X – дробная координата в интерфейсе Visual,
x – целочисленная координата, выводимая на экране (в пикселах)
Rx – сдвиг вправо видимой части экрана относительно холста визуализации графа (в пикселах)
Rw – ширина видимой части экрана (в пикселах)
Аналогично для координаты y (высоты).
Такое преобразование позволяет абстрагироваться от размеров экрана, видимой части и смещения видимой части относительно холста отрисовки графа, что упрощает разработку плагинов.
I. Второй модуль – gm-shell, графическая оболочка. Этот модуль отвечает за визуализацию системы на экран пользователя и пользовательский интерфейс для работы.
II. На данный момент в системе реализованы как пример два плагина: gm-dijkstra (реализующий алгоритм Дейкстры поиска кратчайшего пути из одной вершины) и gm-graphmaker (строящий некоторые типы графов (циклический, двудольный, полный итд и размещающий вершины соответственно). Каждый из плагинов оформлен как отдельный логический модуль в системе. На диаграмме ниже представлены связи между плагинами и основным модулем:
Как видно из диаграммы, модуль gm-core требует реализации своего интерфейса GraphMagicPlugin для любого плагина, подключаемого к системе:
Плагин, реализующий этот интерфейс получает себе:
· Объект типа GraphMagicAPI, через который он может получить граф, с которым в данный момент работает пользователь.
· Объект типа Locale – язык и региональные настройки пользователя.
Также плагин должен предоставить своё имя в списке плагинов через метод getName() и список возможных действий с которые этот плагин выполняет. Пользователь будет видеть этот список действий (у каждого действия плагин определяет имя) и сможет вызвать любое из них.
Глава 3 Плагин для системы GraphMagic
3.1 Описание плагина
Мой плагин edge-Disjoint-Algorithms для системы GraphMagic поможет специалистам, студентам и другим заинтересованным в теории графов людям работать с графовыми моделями и алгоритмами и решать две следующие задачи:
o Построение кратчайшей пары реберно-непересекающихся путей между двумя вершинами;
o Построение K(K>2) кратчайшего множества реберно-непересекающихся путей между двумя вершинами.
При реализации были использованы следующие технологии:
o Java
o Swing
o JUnit
o EasyMock
o Maven
В основе работы данного плагина лежат два алгоритма:
o Алгоритм Дейкстры (Dijkstra’s algorithm).
o Модифицированный aлгоритм Дейкстры (Modified Dijkstra’s algorithm.
3.2 Используемые технологии
3.2.1 Java
Java — объектно-ориентированный язык программирования, разрабатываемый компанией Sun Microsystems и официально выпущенный 23 мая 1995 года.
Java — так называют не только сам язык, но и платформу для создания приложений уровня предприятий на основе данного языка.
Изначально язык программирования назывался Oak (русск. Дуб) и разрабатывался Джеймсом Гослингом для бытовой электроники, но впоследствии был переименован в Java и стал использоваться для написания клиентских приложений и серверного программного обеспечения. Назван в честь марки кофе Java, любимого программистами, поэтому на официальной эмблеме языка Java изображена чашка с дымящимся кофе.