Визуализация графа с использованием парадигмы объектно-ориентированного программирования

Программное обеспечение, использующее в своей работе графы и конечные автоматы, изо дня в день набирают популярность. Системы проектирования технологических процессов, процессных диаграмм и схем взаимодействия немыслимы без визуализации и проектирования графов в графическом виде на экране монитора.

В отличие от представления графа в виде списков, матриц смежности, матриц инцидентности – графический вид обеспечивает удобное для конечного пользователя, как манипулирование, так и восприятие информации, заложенной в логику системы проектирования.

1.    Постановка задачи

Для построения сложных систем и комплексов в последнее время применяется объектно-ориентированный подход при написании компонентов и программного обеспечения. Чем больше и сложнее программа, тем важнее становится разбить ее на небольшие, четко очерченные части. Чтобы побороть сложность, необходимо абстрагирования от мелких деталей.

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

Целью данной работы является составление методики разработки компонента визуализации графа с использованием парадигмы объектноориентированного программирования, а также составление способа реализации расширения функционала реализованного компонента.

2.    Применение объектно-ориентированного подхода

Для применения объектно-ориентированного подхода при проектировании компонента, первоначально необходимо разделить весь компонент на отдельные сущности – классы. В качестве основных классов, при подходе к разработке компонента для визуализации и проектирования графа будут выступать:

Классы объектов графа – являющиеся сущностью, отвечающей за поведение и отображение ребер и вершин графа.

Классы модификаторы – набор классов, предназначенных для выполнения преобразования координатной сетки, с целью изменения масштаба и положения графа на экране монитора.

Классы способа визуализации – сущности, реализующие различные способы визуального построения ребер графа на двумерной плоскости.

Сюда относятся ортогональный и сеточный такие способы визуализации.

Классы алгоритмов – сущности, выполняющие обработку графов, в соответствии с заложенным алгоритмом. К таким алгоритмам можно отнести: нахождение кратчайшего и критического путей между двумя вершинами при помощи алгоритма Дейкстры, построение остовного дерева, нахождение эйлерова цикла.

Далее, для каждого класса необходимо определить методы и события, реализующие его основное поведение, инкапсулировать наиболее критичные данные и методы от несанкционированного доступа, а также определить методы и события, которые будут использоваться для расширения функционала компонента при помощи свойства полиморфизма. Для этого отдельно рассмотрим реализацию каждого класса.

Классы объектов графа реализуют хранения и манипулирование данными о ребрах и вершинах графа, а также выполняют функции визуализации и человеко-машинного взаимодействия с объектами графа.

На рис. 1. представлена диаграмма наследования классов объектов графа. Во главе классов лежит абстрактный класс TDKGraphObject, реализующий общий для всех объектов графа функционал, такой как размеры, занимаемые объектом при его отображении на мониторе, хранение адреса памяти привязанной к объекту дополнительной информации, а также основные события, такие как изменение размеров и положения объектов, изменение состояния объектов.

Рис. 1. Диаграмма наследования классов объектов графа

От абстрактного класса TDKGraphObject унаследованы отдельные классы реализующие поведение свойственное ребрам TDKGraphEdge и вершинам TDKGraphNode.

Для ребер, дополнительно хранятся ссылки на начальную и конечную вершину графа TDKGraphNode, а также информацию об ортогональном расположении ребер графа. Для вершин дополнительно хранится информация об их координатах.

От класса вершин унаследованы классы, реализующие отображение вершин графа в разных видах – прямоугольник или эллипс.

Для осуществления человеко-машинного взаимодействия в классе реализован метод PointIn, позволяющий определять попадание курсора мыши на объект графа, основываясь на классе объекта графа и информации содержащейся о данном объекте. Работа данного функционала основывается на использовании свойства полиморфизма, при котором для всех классов объектов графа имеется метод с одними интерфейсом, но каждый последующий унаследованный класс переопределяет поведение данного метода в соответствии со своим предназначением.

Таким образом, при движении курсора по координатной сетке графа производится вызов метода PointIn для каждого объекта графа, а объект, в свою очередь выполняет функционал в соответствии со своим классом. Так, для ребра выполняется поиск принадлежности точки всем сегментам ломаной линии ребра, а для вершины типа эллипс выполняется поиск принадлежности точки к заданному эллипсу.

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

Рис. 2. Диаграмма наследования классов модификаторов

Каждый из приведенных на диаграмме классов выполняет задачу преобразования входных координат в соответствии со своим предназначением. Рассмотрим работу каждого из модификатора.

TDKDrawBoxScaler отвечает за масштабирование конечного отображения координат на координатной сетке, которое задается в виде коэффициента S. При S = 1 – масштаб равен 1:1, при S < 0 – масштаб уменьшится на заданный коэффициент, а при S > 0 – масштаб увеличится на заданный коэффициент.

TDKDrawBoxPosition предназначен для смещения отображения рисунка относительно видимой части окна вывода. Смещение задается в пикселях отдельно для оси абсцисс Dx и ординат Dy.

TDKDrawBoxConstraints позволяет задавать границы выводимого рисунка при выполнении смещений по оси абсцисс Dx и ординат Dy.

Для каждой точки A, проходящей через данную цепочку модификаторов применяется преобразование (1), в результате которого получается точка A ' , выводимая на экране монитора.

A' = ( ( Ax + Dx )* S ,( Ay + Dy )* S )               (1)

На рис. 3 изображен вывод одного графа с разными значениями коэффициента масштабирования и смещения.

Рис. 3. Масштабирование и смещение при визуализации графа

Классы способа визуализации предназначены для задания поведения при построении ребер графа. Для визуализации графа в текущей работе используется ортогональный и сеточный способ визуализации. При ортогональной визуализации построение сегментов ребер происходит параллельно осям координат, а при сеточном способе сегменты ребер не могут отображаться под произвольным углом относительно осей координат. На рис. 4 изображена диаграмма классов способов визуализации.

• (a)                           (6)

Рис. 4. Диаграмма наследования классов визуализации графа (а), ортогональная визуализация графа (б), сеточная визуализация графа (в)

Классы алгоритмов предназначены для наделения компонента возможностью выполнения различных алгоритмов над графом. Для реализации необходимого алгоритма необходимо унаследовать свой класс от абстрактного TDKGraphAlgorithm и запрограммировать необходимые действия над данными, хранящимися в графе и способом его визуализации на экране монитора.

Каждый класс алгоритмов получает на вход граф в виде списка вершин и ребер, выполняет свои внутренние расчеты. Отображение результатов производится при помощи перехвата метода рисования вершин и ребер OnDrawObject, а также метода рисования холста графа OnDrawGraph.

На рис. 5 приведен пример выполнения алгоритма поиска кратчайшего пути между 14 и 22 вершиной графа. При этом найденный путь выделен другим цветом и утолщенными стрелками.

Рис. 5. Применение алгоритма поиска кратчайшего пути к графу

После того, как все сущности определены и имеют свое поведение, необходимо объединить их работу в единую, взаимосвязанную систему. Для взаимодействия классов между собой используется класс TDKCustom-Graph, изображенный на рис. 6, который является связующим звеном между классами объектов, модификации, отображения и алгоритмов графа. Данный класс отвечает за процесс выполнения отдельных этапов построения и управления графом, производит необходимые промежуточные вычисления перед передачей информации в TDKCustomDrawGraph, а также координирует работу классов алгоритмов и передает подготовленные для вывода данные в TDKCustomDrawBox.

В свою очередь класс TDKCustomDrawBox выполняет визуализацию графа на экране монитора, а также осуществляет человеко-машинное взаимодействие с пользователем при помощи класса TDKDrawBoxCon-troller, который выполняет обнаружение объекта в координате, над которым находится курсор мыши и предлагает пользователю выполнить соответствующие действия над графом, такие, как добавление и удаление вершин и ребер.

Стоит отметить, что в результате использования в работе свойств объектно-ориентированной парадигмы программирования, такие как наследование и полиморфизм, любой программист может реализовать необходимый ему дополнительный функционал. Для расширения функционала программисту необходимо только унаследовать свой класс от уже существующего абстрактного или реализованных другими программистами классов, а затем переопределить методы заложенные, необходимые для работы класса в соответствии со своими предпочтениями.

При этом свойство инкапсуляции не позволит нарушить основную логику при построении графа, заложенную в абстрактные классы и методы, поскольку реализация внутренней работы классов скрыта от программиста и ему предоставляется только возможность использования только разрешенных методов, которые контролируют внутреннее состояние классов и основанных на их основе объектов.

3.    Визуализация графа

Визуальное отображение графа на экране монитора требует выполнение операций графического вывода. При увеличении количества объектов, выводимых на экран, возрастает нагрузка на графическую подсистему. С целью уменьшения данной нагрузки в представленной работе разработан класс TDKCustomDrawBox, который является холстом для визуализации графа, и в котором применяется несколько методов по оптимизации отображения объектов графа:

Метод 1. Вывод только видимой части. Для каждого объекта, при изменении размеров или положения, вычисляется прямоугольная область, описывающая данный объект. В дальнейшем, в процессе визуализации, проверяется условие попадания вычисленной области в окно вывода. Если область попадает, то производится рисование объекта, если область не попадает в окно вывода, то рисование данного объекта не производится.

Метод 2. Вывод построенного изображения через буфер. При этом каждый новый цикл вывода графа на экран сопровождается предварительной отрисовкой графа в буфере, размер которого соответствует размеру экрана вывода. После полного построения кадра в буфере производится его вывод на экран при помощи WinAPI функции BitBlt.

Метод 3. Применение допуска. Каждое перемещение объекта или смещение холста вывода сопровождается полной перерисовкой всего холста. Для уменьшения количества перерисовок в работе используется допуск R, задаваемый в пикселях, при достижении которого выполняется полная перерисовка холста.

Применение на практике всех трех методов позволило снизить нагрузку на графическую подсистему, тем самым повысить производительность вывода графа. Для вычисления эффективности методов были проведены замеры производительности вывода изображения на экран монитора, в рамках которых производилась визуализация графа с различным количеством объектов и различным соотношением попадания объектов на экран. Результаты замеров представлены в таблице 1 и показывают, что применение данных методов позволяет уменьшить нагрузку при визуализации графа в 24 раза, а также увеличить количество объектов в отображаемом графе в 100 раз, при условии, что в видимую часть будет попадать до 500 объектов, что вполне достаточно для отображения графа.

Таблица 1

Серия проведенных замеров производительности вывода графа на экран монитора

Общее количество объектов, шт	Количество объектов, попадающих в область видимости, шт	Производительность вывода на экран без применения методов оптимизации. FPS	Производительность вывода на экран c применением методов оптимизации. FPS
500	500	12	277
500	50	16	395
5000	5000	1	26
5000	50	-	37
50000	50	-	8
50000	500	-	8
500000	50	-	1

Заключение

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

Приведенные методы оптимизации визуализации графа позволили снизить нагрузку на графическую систему ЭВМ, тем самым увеличить количество отображаемых объектов графа, а применение допуска позволило уменьшить отклик при изменении масштаба и позиции отображаемого графа.