Например, Бобцов

МЕТОД ВИЗУАЛИЗАЦИИ МЕТАГРАФА

МЕТОД ВИЗУАЛИЗАЦИИ МЕТАГРАФА

7 МАТЕМАТИЧЕСКОЕ И КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ MODELING AND SIMULATION

УДК 519.1
МЕТОД ВИЗУАЛИЗАЦИИ МЕТАГРАФА
Е.С. Штогринаa, А.С.Кривенкоa
a Национальный технический университет Украины «Киевский политехнический институт», Институт телекоммуникационных систем, Киев, Украина, L_Shtogrina@mail.ru
Проведен анализ методов визуализации разных типов графов. Сделан вывод об актуальности разработки метода визуализации метаграфов. Описываются проблемы размещения узлов, принадлежащих и не принадлежащих метавершинам, пересечения фигур метавершин, которые возникают при решении задачи визуализации метаграфа. Данные проблемы рассмотрены на примере. Определены критерии, по которым полученное изображение считается наглядным для пользователя и однозначно соответствует заданному метаграфу. Поставлена задача визуализации метаграфа. Для ее решения предложен метод визуализации, основанный на принципах силовых алгоритмов. В рамках данного метода определены правила действия сил между узлами. Эти силы зависят от типа узлов, между которыми действуют, и наличия ребер между ними. Применение предложенного метода позволяет строить графическое представление метаграфа, который соответствует заданной предметной области. Метод не предполагает участия человека при формировании изображения, что позволяет экономить время при частых изменениях, которые требуют перестройки изображения. Полученное изображение позволяет визуализировать сущности предметной области и связи между ними, применить методы графического анализа. Определены дальнейшие направления работы – минимизация количества пересечений ребер и площади, занимаемой результирующим изображением. Модификация метода визуализации метаграфа с учетом данных направлений позволит улучшить визуальное представление метаграфа. Ключевые слова: метаграф, визуализация, граф, метавершина, графическое представление.

METAGRAPH VISUALIZATION METHOD
O.S. Shtogrinaa, O.S. Kryvenkoa
a National Technical University of Ukraine «Kyiv Polytechnic Institute», Institute of Telecommunication Systems, Kyiv, Ukraine, L_Shtogrina@mail.ru
Analysis of visualization techniques for various types of graphs is done. Conclusion about the relevance of method development for metagraph visualizing is made. The paper deals with issues that arise when solving the problem of metagraph visualization, such as: the placement of nodes that belong to metavertices and do not belong to them, figures intersection of metavertices. These problems are exemplified. Criteria are proposed for the final image to be considered coherent, understandable for users and corresponding to a predetermined metagraph. The problem of metagraph visualization is posed. The method based on the principles of force algorithms is proposed for the problem solving. The rules for forces between metagraph nodes are defined in the framework of the method. These forces depend on nodes type between which they are performed and the presence of edges between them. This method does not involve human intervention during the formation of the image, thus saving time at frequent changes that require rebuilding of the image. The resulting image gives the possibility to portray clearly the entities of the subject area and the links between them. Graphical analysis methods can be applied to the image. Areas for the future researches are identified. They are: minimization of the number of edges intersections and the area occupied by the resulting image. Results of the modified visualization method can improve the visual metagraph representation. Keywords: metagraph, visualization, graph, metavertex, graphical representation.
Введение
Графы являются естественным и наглядным способом представления сложных структур. Это позволяет широко использовать их в задачах коммуникации и транспортировки, в задачах поиска маршрутов и создания карт, в системах обработки информации для параллельных и распределенных вычислений, в системах поддержки принятия решений, в системах обработки транзакций и др. Теория графов применяется при разработке эффективных алгоритмов оптимизации и наглядном представлении предметных областей для их дальнейшего анализа. Представление в виде простого графа позволяет рассматривать отдельные элементы информации и их связи между собой. Однако во многих случаях недостаточно представления и изучения взаимодействия отдельных элементов. Рассмотрение взаимосвязанных множеств элементов и взаимодействия между группами элементов может предоставить качественно новый взгляд на задачу и ее решение. Например, может возникнуть необходимость вместе рассматривать несколько переменных в моделях систем поддержки принятия решений, несколько логических переменных в правилах баз знаний, несколько документов в системах документооборота. Существуют структуры, которые позволяют частично решить эту проблему – это гиперграфы и hi-графы [1], но они имеют свои недостатки. В работе [2] для решения описанной выше проблемы предложена такая разновидность графов, как метаграфы, и рассмотрено применение метаграфов для формализации логического вывода, моделирова-

124

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, №3 (91)

Е.С. Штогрина, А.С.Кривенко

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

Проблема визуализации метаграфа

На сегодняшний день развитие получили методы генерации изображений графов и графовых структур как малых (до 200 вершин), так и больших размеров (тысячи вершин). Классические силовые алгоритмы основаны на физических аналогиях и могут быть использованы для построения графов произвольного вида. Изображения, созданные с их помощью, содержат мало пересечений ребер и симметрию [3]. К этой группе относятся «пружинные алгоритмы» [4, 5], алгоритмы, имитирующие действие сил гравитации [6] и магнитных сил, а также алгоритмы, основанные на минимизации энергии [7]. Для визуализации графов больших размеров существуют многоуровневые алгоритмы [8, 9]. Они требуют решения NP-полных задач, задач кластеризации графа, GC-фильтрации графа [10]. В работах [11, 12] рассматриваются методы визуализации гиперграфов для отображения данных больших объемов. Данные подходы эффективны для графов, но не подходят для метаграфа, так как метаграф имеет отличную от графа структуру.
Наиболее полное и подробное описание метаграфа дано в работе [2], где метаграф был определен как двойка: порождающее множество и множество ребер. В работе [13] в силу специфики поставленной задачи, по аналогии к теории гиперграфов, к определению метаграфа были добавлены еще две составляющие: множество метавершин и множество метаребер. Так как для решения задачи визуализации метаграфа важны типы узлов и их соотношения, целесообразно расширить определение, данное в [2], и выделить отдельно множество вершин и множество метавершин метаграфа. Выделять и отдельно рассматривать метаребра нет необходимости, так как при визуализации метаграфа важным является наличие ребер, но не их тип. В связи с этим множество ребер будет содержать все ребра метаграфа, независимо от того, какие типы узлов метаграфа они соединяют.
Приведем определение метаграфа, которое учитывает описанные выше особенности и будет ис-
пользоваться при изложении последующего материала. Метаграф – это тройка множеств S  V , M , E ,

 где V  vr r  1, NV – порождающее множество (множество вершин метаграфа), NV – количество вер-

 шин метаграфа; M  mq q  1, NM – множество метавершин, NM – количество метавершин;

 E  eh h  1, NE – множество ребер, NE – общее количество ребер в метаграфе.
Метавершина метаграфа – это вершина, которая включает множество
 mq  vr vr V , r  1, Nmq , где Nmq – количество вершин, входящих в метавершину mq .

вершин

Для упрощения дальнейшей подачи материала введем понятие узла метаграфа mv  V  M  , таким

образом, это вершина или метавершина. Тогда ребро метаграфа определяется как eh  mvout , mvin  , где
mvout – узел, из которого выходит ребро, mvin – узел, в который входит ребро.
Так как алгоритмы визуализации графов не учитывают структуру метаграфа, то в них нет механизмов учета вложенности вершин в метавершины.
Рассмотрим подробнее проблемы, которые могут возникнуть, если для нахождения позиций вершин метаграфа использовать алгоритм визуализации графов. В этом случае можно получить неправильное графическое представление метаграфа, которое не соответствует заданному метаграфу.
Пусть дан метаграф (pис. 1)

v1, v2 , v3 , v4 , v5 , v6 , v7 , v8 , v9 , v10,

S1  m1, m2 , m3 , m4,

,

e1, e2 , e3 , e4 , e5

где m1  v6 , v7 , m2  v3, v4 , m3  v3, v5 , m4  v1, v2 , v3 , e1  m1, v9  , e2  m2 , v9  , e3  v4 , v7  ,

e4  v8 , m4  , e5  v5 , v10  .

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, №3 (91)

125

МЕТОД ВИЗУАЛИЗАЦИИ МЕТАГРАФА

m1 v7

v6

e1 e3 v8 e4

v1 m4
v2

v10 e5

v9 v4 v3 V5 m2 m3
Рис. 1. Пример правильного графического представления метаграфа S1 Если алгоритм визуализации графов применить только к множеству вершин, то не будут рассчитываться собственно положения метавершин, а также учитываться ребра, инцидентные метавершинам. Метавершины в таком случае можно сформировать за счет обводки принадлежащих им вершин. После такой визуализации метавершин может возникнуть проблема размещения в метавершине узлов, не принадлежащих ей. На рис. 2 показан пример такого размещения. Узлы, расположенные неправильно, выделены
темным цветом, v1, m1 , v5  m4 , m3  m4 , но на рисунке видно, что это не так. В случае применения алгоритма визуализации графов к множеству вершин и метавершин верши-
ны, принадлежащие метавершине, будут расположены вне метавершины за счет того, что их положение будет вычисляться независимо друг от друга.

v7 v8 m1

v1

e1 e3 e4

v9 v4 e2 m2

v5 m3

v3

v6 m4
v2
e5

v10

Рис. 2. Пример неправильного графического представления метаграфа S1

Критерии правильной визуализации метаграфа

Каждая вершина vr и метавершина mq имеет позицию – координаты на плоскости

pvr  (xvr , yvr ) ,

pmq  (xmq , ymq ) . Вектора

PV



 

p

v1

,

p

v

2

,

p

v

N

V

 

– вектор позиций вершин,

PM



 

pm1

,

pm

2

,

pm

NM

 



вектор

позиций

метавершин,

полностью

определяют

расположение

узлов

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

mvi V , или метавершиной, если mvi  M . Расстояние между узлами рассчитывается как евклидово

расстояние между точками: leh  pmv i  pmv j .
Определим «графическое представление метавершины» на плоскости как геометрическую фигуру Fmq , которая имеет позицию pmq и форму. Позиция метавершины на конечном изображении метаграфа

126

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, №3 (91)

Е.С. Штогрина, А.С.Кривенко

– центр ее фигуры. «Графическое представление ребра» определим как кривую Feh , которая задана между координатами начала и конца ребра. Тогда «графическое представление метаграфа» будет определять-
   ся тройкой WS  PV, FM , FE , где FM  Fmq – множество фигур метавершин, FE  Feh – множество
кривых, определяющих ребра. Графическое представление будет правильным, т.е. будет соответствовать заданному метаграфу,
если отображение S WS изоморфно. Определим критерии, при выполнении которых графическое представление метаграфа будет правильным: 1. Координаты вершин не равны: i,j:i  j  pvi  pvj , причем координаты метавершин могут быть
равны при наличии общих внутренних вершин.
2. Только координаты вершин, принадлежащих метавершине mq , находятся в Fmq :
 vr :vr  mq  pvr  Fmq , vr:vr  mq  pvr  Fmq .
3. Фигуры метавершин, не имеющих общих внутренних вершин, не пересекаются: j,k:mj  mk    Fm j  Fmk   .
Основные требования к эстетичности графического представления графа – минимальное количество пересечений ребер, приблизительно равная длина ребер и др. – описаны в работах [3–5]. Эти требования также справедливы и для метаграфа. Но для метаграфа более важно правильное расположение метавершин и их форма, чем длина ребер.

Метод визуализации метаграфа

Опишем постановку задачи нахождения правильного графического представления метаграфа. Дано:
1. Метаграф S  V , M , E .
2. PV , PM – начальное расположение узлов.
3. Критерии правильной визуализации метаграфа. 4. Прямоугольная область U, в которой должно размещаться изображение метаграфа.
Найти: Графическое представление метаграфа. Для решения поставленной задачи необходимо определить: 1. расположение вершин, не входящих в метавершины; 2. расположение метавершин с учетом взаимного расположения метавершин, которые имеют общие внутренние вершины; 3. взаимное расположение вершин в метавершине; 4. форму фигур метавершин;
5. кривые Feh , определяющие ребра. Предложенный метод визуализации метаграфа основан на алгоритме Фрюхтермана–Рейнгольда
для визуализации ненаправленных графов [5]. Граф рассматривается как система объектов, соединенных пружинами по определенным правилам. Каждая из пружин действует на соединенные ею вершины с силой притяжения или отталкивания. Под действием пружин система движется до тех пор, пока не установится равновесие – сумма сил, действующих на узел, равна нулю. Гарантируется, что узлы размещаются внутри U – прямоугольной области экрана и (или) бумаги. С каждой итерацией алгоритма узлы двигают-
ся на расстояние (t) в направлении вектора суммарной силы, действующей на узел. Функция (t) зави-
сит от времени и убывает. Если вектор смещения выталкивает узел за границу области U, соответствующая координата вектора смещения обрезается, а сила продолжает действовать по касательной к границе области U.
Для визуализации метаграфа предлагается модифицировать алгоритм Фрюхтермана–Рейнгольда следующим образом: рассмотреть все возможные пары узлов и ввести дополнительные коэффициенты балансировки сил. Тогда силы будут вычисляться по следующим формулам:
 сила отталкивания узла u от узла v :

frepuv  Kruv

l2 pmvu  pmvv

p0 vu

при u  v , frepuv  0 ;

 сила притяжения узла u к узлу v :

(1)

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, №3 (91)

127

МЕТОД ВИЗУАЛИЗАЦИИ МЕТАГРАФА

fattruv  Kauv

pmvu  pmvv l

2
p0 uv

(2)

при u  v , fattruv  0 , где l – идеальная длина ребра для метаграфа – вычисляется как функция от площади размещения и количества узлов:

l

area(U ) , NV  NM

(3)

p0 vu – единичный вектор направления из pmv v в pmvu .

Коэффициенты Kruv и Kauv зависят от типа каждого узла в паре и их соотношения. Силы отталки-

вания действуют между каждой парой узлов с коэффициентом Kruv . Между парами «метавершина и вхо-

дящая в нее вершина» Kruv  0 . Коэффициент при силе отталкивания со стороны метавершины зависит от

количества ее внутренних вершин. Тогда метавершина с большим количеством внутренних вершин Nmq

будет отталкивать другие узлы сильнее, чем метавершина с меньшим количеством Nmq . Коэффициент
при силе отталкивания со стороны вершины равен 1.
Силы притяжения действуют между смежными узлами с коэффициентом Kauv , что гарантирует расположение узлов ближе друг к другу при наличии ребра между ними. Сила притяжения со стороны метавершины зависит от количества внутренних вершин, как и при вычислении сил отталкивания. Между метавершинами и вложенными в них вершинами сила притяжения действует с коэффициентом
Kauv 1. Эта сила обеспечивает расположение вложенных вершин внутри фигуры метавершины и их движение за метавершиной при ее перемещении под действием сил со стороны остальных узлов. Сила
притяжения между всеми вложенными в метавершину вершинами действует с коэффициентом Kauv 1, за счет чего обеспечивается меньшая площадь фигуры метавершины. Сила притяжения для пар вершинавершина действует с коэффициентом 1 для обеих вершин.
Тогда общая сила, действующая на узел u , будет рассчитываться по следующей формуле:

 Fspringu  v frepuv  v fattruv .

(4)

Блок-схема алгоритма решения задачи визуализации метаграфа представлена на рис. 3.

Применение данного метода позволяет найти такие координаты узлов, при которых графическое

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

уменьшения занимаемой площади, избегания пересечений фигур метавершин и повышения читаемости

изображения для метавершин с тремя и более внутренними вершинами ее можно определять как мини-

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

можно использовать алгоритмы Джарвиса, Грэхема или Чана [14].

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

таком изображении возникают проблемы множественных пересечений ребер и пересечений фигур мета-

вершин ребром. Исходя из этого, необходимо рассчитывать форму ребра, которое будет огибать узлы, как

кривую Безье или B-сплайн [15, 16].

Заключение

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

128

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, №3 (91)

Е.С. Штогрина, А.С.Кривенко

Начало Ввод данных

Сменить узел на малое
расстояние в направлении
случайного вектора r

Вычислить l по формуле (3)

Перебор пар узлов u, v
Определение Коэффициентов
Kruv, Kauv Для каждой пары узлов
вычислить силы отталкивания по формуле
(1) и притяжения по формуле (2)
Перебраны все узлы
Вычисление векторной суммы сил
для каждого узла

Силы действующие на все узлы равны нулю?

Да

Перебор метавершин q

Нет Перебор узлов и

Определение Fmq

Рmvи = Рmvи +Fspringи

Ограничение

Да

координаты по области

U

Рmvи U Нет

Рmvи = Рmvи +r

Да

Существуют узлы с идентичными

координатами?

Нет

Рmvи = Рmvи

Fmvq =centr(Fmq) Перебраны все метавершины Перебор ребер h Определение Fеh Перебраны все
ребра Конец

Перебраны все ребра

В зависимости от комбинации типов узлов вычислить коэффициенты Для каждого узла вычислить векторную сумму сил по формуле (4) Задать позицию метавершины, как центр ее вершины

Рис. 3. Блок-схема алгоритма решения задачи визуализации метаграфа

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics 2014, №3 (91)

129

МЕТОД ВИЗУАЛИЗАЦИИ МЕТАГРАФА

Литература

1. Grossman O., Harel D. On the algorithmics of higraphs. Technical Report, Rehovot, Israel. 1997. 32 p. 2. Basu A., Blanning R.W. Metagraphs and their applications. Springer, 2006. 172 p. 3. Eades P., Lin X. Spring algorithms and symmetry // Theoretical Computer Science. 2000. V. 240. N 2.
P. 379–405. 4. Eades P. A heuristic for graph drawing // Congressus Nutnerantiunt. 1984. N 42. P. 149–160. 5. Fruchterman T.M.J., Reingold E.M. Graph drawing by force-directed placement // Software-Practice and
Experience. 1991. V. 21. N 11. P. 1129–1164. 6. Barnes J., Hut P. A hierarchical O (N log N) force-calculation algorithm // Nature. 1986. V. 324. N 4. P. 446–
449. 7. Kamada T., Kawai S. An algorithm for drawing general undirected graphs // Information Processing Letters.
1989. V. 31. N 1. P. 7–15. 8. Hachul S., Junger M. Drawing Drawing large graphs with a potential-field-based multilevel algorithm // Lec-
ture Notes in Computer Science. 2004. V. 3383. P. 285–295. 9. Archambault D., Munzner T., Auber D. TopoLayout: Multilevel graph layout by topological features // IEEE
Transactions on Visualization and Computer Graphics. 2007. V.13. N 2. P. 305–316. 10. Harel D., Koren Y. A fast multi-scale method for drawing large graphs // Journal of Graph Algorithms and
Applications. 2002. V. 6. N 3. P. 177–202. 11. Jin R., Xiang Y., Fuhry D., Dragan F.F. Overlapping Matrix Pattern Visualization: A Hypergraph Approach //
Proc. of IEEE International Conference on Data Mining, ICDM. Pisa, Italy, 2008. Art. N 4781126. P. 313– 322. 12. Paquette J., Tokuyasu T. Hypergraph visualization and enrichment statistics: How the EGAN paradigm facilitates organic discovery from big data // Proc. SPIE - The International Society for Optical Engineering. 2011. V. 7865. Art. N 78650E. 13. Астанин С.В., Драгныш Н.В., Жуковская Н.К. Вложенные метаграфы как модели сложных объектов // Инженерный вестник Дона. 2012. Т. 23. № 4-2 (23). С. 76. 14. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. 2-e изд. М.: Вильямс, 2005. 1296 c. 15. Роджерс Д., Адамс Дж. Математические основы машинной графики. М.: Мир, 2001. 604 с. 16. Holten D. Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data // IEEE Transactions on Visualization and Computer Graphics. 2006. V. 12. N 5. P. 741–748.

Штогрина Елена Сергеевна



Кривенко Александра Сергеевна –

ассистент, Национальный технический университет Украины «Киевский политехнический институт», Институт телекоммуникационных систем, Киев, Украина, L_Shtogrina@mail.ru студент, Национальный технический университет Украины «Киевский политехнический институт», Институт телекоммуникационных систем, Киев, Украина, alexakryvenko@gmail.com

Olena S. Shtogrina Oleksandra S. Kryvenko

– assistant, National Technical University of Ukraine «Kyiv Polytechnic Institute», Institute of Telecommunication Systems, Kyiv, Ukraine, L_Shtogrina@mail.ru
– student, National Technical University of Ukraine «Kyiv Polytechnic Institute», Institute of Telecommunication Systems, Kyiv, Ukraine, alexakryvenko@gmail.com

Принято к печати 12.02.14 Accepted 12.02.14

130

Научно-технический вестник информационных технологий, механики и оптики Scientific and Technical Journal of Information Technologies, Mechanics and Optics
2014, №3 (91)