Методы и средства визуализации информации на основе атрибутированных иерархических графов с портами

Полный текст

Введение

Визуализация структурированных или реляционных данных на основе графовых моделей имеет множество сфер применения как в реальных, так и в теоретических областях [1-3]. Среди них - физические сети связи и электрические сети, с одной стороны, и структуры данных компилятора и диаграммы изменения состояний - с другой. Поэтому в настоящее время на рынке широко представлены наукоемкие программные продукты, использующие методы визуализации информации на основе графовых моделей, такие как Cytoscape [4], Higres [5], Gephi [6], Graphviz [7], Tulip [8], yEd [9] и многие другие.

Поскольку информация, которую желательно визуализировать, постоянно увеличивается и усложняется, возникает все больше ситуаций, в которых классические графовые модели перестают быть адекватными. Требуются и возникают более мощные теоретико-графовые формализмы для представления информационных моделей, обладающих иерархической структурой, поскольку иерархичность является основой многочисленных методов визуальной обработки сложных больших данных в различных областях применения вычислительных систем [3; 10; 11]. Одним из таких формализмов являются так называемые иерархические графы и графовые модели [3]. Этот формализм позволяет выделить в исходном графе множество таких его частей (так называемых фрагментов), что все элементы каждого фрагмента заслуживают отдельного совместного рассмотрения, а все фрагменты выделенного множества образуют иерархию по вложенности. Такая иерархия фрагментов обеспечивает хорошие возможности для борьбы со сложностью при визуализации структурированных данных в тех приложениях, которые обязаны иметь дело с большими объемами сложных структурированных данных. Она формирует основу для естественных методов «абстракции» и «редукции», которые могут применяться исследователями для уменьшения визуальной сложности большого графа. В Институте систем информатики им. А. П. Ершова СО РАН по заказу компании Intel была создана система визуализации Visual Graph, которая основана на иерархических графовых моделях и позволяет исследовать сложные структурированные большие данные, возникающие в компиляторах и других системах конструирования программ, через их визуальные представления [12].

Во многих приложениях объекты, моделируемые вершинами графа, являются сложными и могут содержать по несколько разных логических частей, через которые эти объекты находятся во взаимосвязи, моделируемой ребрами. Например, в графе железнодорожных дорог страны (или некоторой другой территории) населенные пункты, моделируемые вершинами графа, могут соединяться железнодорожными путями, заходящими в разные железнодорожные вокзалы этих населенных пунктов. А при представлении потока данных между операторами программы в виде так называемого информационного графа у операторов программы, моделируемых вершинами графа, рассматриваются разные их операнды (так называемые информационные входы -разные те места, где данные используются в качестве аргументов операторов, и информационные выходы - разные те места, где данные возникают в качестве результатов операторов), через которые и происходит при исполнении программы обмен данными между операторами (от выходов к входам), и поэтому информационные связи между операторами (вершинами информационного графа) обычно представлены ориентированными ребрами (дугами), которые соединяют соответствующие операнды операторов [3]. При представлении графов с вершинами, моделирующими сложные объекты, в существующих форматах описания графов (например, стандартный формат описания графов GraphML [13]) эти разные логические части сложных объектов обычно выражаются с помощью так называемых портов вершин, которые при изображении графа могут представляться разными точками (или разными непересекающимися частями) изображений вершин, в которых соответствующие вершины соединяются с инцидентными им ребрами.

В данной статье введен формализм атрибутированных иерархических графов с портами, описаны способы изображения таких графов на плоскости и кратко представлены новые возможности системы Visual Graph по визуализации структурированных данных большого размера на основе атрибутированных иерархических графов с портами. Статья является расширенной версией доклада, прочитанного автором на III Сибирском научном семинаре Data Analysis Technologies with Applications (SibDATA-2022) [14].

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

Напомним некоторые термины и обозначения из [3].
Пусть G – граф некоторого типа, например, G может быть неориентированным или ориен- тированным графом. Граф G определяется двумя конечными множествами V и E, где элементы V – вершины графа G, а элементы E – ориентированные (или неориентированные) ребра графа G. G – тривиальный граф, если |V |=1 и | E |= 0 .
Граф C называется фрагментом графа G и обозначается C $\subset$ G , если C – часть графа G, т. е. состоит только из элементов (вершин и ребер) графа G.
Множество фрагментов F называется иерархией вложенных фрагментов графа G, если
(1) F содержит граф G и
(2) C1 ⊆ C2 , C 2 ⊆ C1 или пусто C1 ∩ C2 для любых C1,C2 ∈ F .
Для любых различных C1,C2 ∈ F фрагмент C1 непосредственно вложен в C2 , если C1 ⊆ C2 и не существует такого C3 ∈ F , отличного от C1 и C2 , что C1 ⊆ C3 ⊆ C2 .
Фрагмент C ∈ F – элементарный, если F не содержит фрагментов, непосредственно вложенных в C.

Иерархический граф H = (G,T) состоит из графа G и корневого дерева T, которое представляет отношение непосредственной вложенности между элементами некоторой иерархии F вложенных фрагментов G. G называется основным графом H. T называется деревом вложенности H.
Иерархический граф H = (G,T) называется простым, если все его фрагменты являются порожденными подграфами графа G.
Нетрудно увидеть, что каждый кластерный граф может быть рассмотрен как простой иерар- хический граф H = (G,T) , в котором G – неориентированный граф, а листья дерева T – тривиальные подграфы графа G.

Рис. 1. Простой иерархический граф

Fig. 1. A simple hierarchical graph

Пример простого иерархического графа H = (G,T) приведен на рис. 1, на котором ребра основного графа G изображены сплошными линиями, а ребра дерева вложенности T – пунктирными. Данный простой иерархический граф H содержит шесть тривиальных фрагментов и два нетривиальных фрагмента: G и C = {1, 2, 3.5}.
Определим иерархические графы с портами как подкласс иерархических графов следующим образом.
Пусть H = (G,T) – иерархический граф и пусть P ⊆ V – некоторое выделенное подмножество вершин графа G. Будем называть портами фрагмента C все те его вершины из P, которые не принадлежат ни одному вложенному в него фрагменту из F.
Нетрудно увидеть, что в любом иерархическом графе с портами H = (G,T) каждая вершина из P является портом некоторого фрагмента C ∈  F и только одного его фрагмента. 

Таким образом, множество всех вершин графа H = (G,T) распадается на три попарно непересекающихся множества:

(1) множество всех портов P;
(2) множество простых вершин – всех тех вершин его основного графа G, которые не являются портами фрагментов из F;
(3) множество всех тех вершин дерева вложенности T, которые не являются тривиальными фрагментами основного графа.

Например, информационный граф программы может быть рассмотрен как такой иерархический граф с портами H = (G,T) , в котором G – ориентированный граф с P = V , а каждый фрагмент C ∈  F , отличный от G, является элементарным пустым фрагментом, множество пор- тов которого распадается на два таких непересекающихся подмножества In(C) и Out(C) , что нет дуг, исходящих из портов In(C) или заходящих в порты Out(C) . При таком рассмотрении элементарные фрагменты C ∈  F моделируют операторы программы, In(C) и Out(C) – множества информационных входов и выходов соответствующих операторов, а дуги основного графа G – информационные связи между соответствующими выходами и входами операторов.

Изображение (или укладка) иерархического графа с портами H = (G,T) является таким представлением элементов H на плоскости, что выполняются следующие свойства:

В качестве примера рассмотрим использование введенного формализма для изображения операторной схемы над распределенной памятью (или Р-схемы) [3]. В операторной схеме данного типа управляющий граф (уграф) программы, вершины которого соответствуют операторам программы, а дуги представляют управляющие связи (возможные передачи управления) между ними, как бы дополнен информационным графом, представляющим информационные связи между соответствующими выходами и входами операторов. На рис 2 приведен пример изображения конкретной схемы над распределенной памятью. Здесь, как и обычно, операторы программы изображены в виде прямоугольников, снабженных кругами, изображающими операнды операторов (входы оператора располагаются сверху соответствующего прямоугольника, а выходы снизу). Управляющие связи изображены сплошными линиями (со стрелками), соединяющими операторы, а информационные связи – пунктирными линиями (со стрелками), соединяющими выходы операторов с входами.

Каждая Р-схема может быть представлена в виде такого иерархического графа с портами H = (G,T) , в котором любой фрагмент C ∈  F , отличный от основного графа G, является элементарным пустым фрагментом, состоящим из одной основной вершины q∈ V \ P и возможно пустого множества портов p∈ P , которое распадается на два непересекающихся подмножества In(C) и Out(C) . При таком представлении простые вершины q элементарных фрагментов C ∈  F моделируют операторы Р-схемы, а порты p из множеств In(C) и Out(C) моделируют их информационные входы и выходы. Дуги основного графа G, соединяющие вершины q∈ V \ P , – это управляющие связи, а дуги основного графа G, соединяющие порты p∈ P , – это информационные связи между соответствующими выходами и входами операторов. Если изображать каждый элементарный фрагмент такого иерархического графа в виде фигуры, образованной прямоугольником, изображающим его вершину, и примыкающими к нему кругами, изображающими его порты (входы сверху прямоугольника, а выходы снизу), а каждую дугу основного графа рисовать либо сплошной линией со стрелкой, если это управляющая связь, либо пунктирной линией со стрелкой в случае информационной связи, то можно получить стандартное изображение Р-схемы, приведенное на рис. 2.

Рис. 2. Р-схема

Fig. 2. P-diagram

Пусть задано множество объектов W, называемых атрибутами, и пусть каждому элементу w∈ W сопоставлено в соответствие множество объектов B(w) , называемых возможными значениями атрибута w. Например, в качестве B(w) могут использоваться определенные множества чисел, символов или строк (цепочек символов). Пусть M обозначает множество всех пар (w,v), образованных из атрибутов w∈W и их значений v∈B(w) .

Атрибутированный иерархический граф с портами – это пара (H,L) , где H – иерархический граф с портами, а L – функция атрибутирования, сопоставляющая каждому его элементу h не которое подмножество L(h)⊆ M.
При изображении атрибутированного иерархического графа с портами атрибуты и их значения для элементов иерархического графа могут либо выражаться неявно через определенные свойства способа представления этих элементов (например, через геометрическую форму области вершины, ее размеры и т. д.), либо изображаться явно в виде определенного вида пометок соответствующих элементов. Например, явное представление атрибутов может определять место и вид изображений атрибутов в виде текстов внутри областей вершин или рядов с линиями, изображающими ребра.

Новые возможности системы Visual Graph по визуализации структурированных данных большого размера на основе атрибутированных иерархических графов с портами

Система Visual Graph [12] предназначена главным образом для визуального и структурного анализа структурированных данных, возникающих при работе компилятора (или другой системы конструирования программ), на основе атрибутированных иерархических графов достаточно большого размера, а теперь еще и с портами. Предполагается следующий сценарий использования системы (рис. 3). Сначала компилятор (сам либо с помощью вспомогательной программы) переводит графовую модель из ее внутреннего представления в файл одного из поддерживаемых системой Visual Graph форматов, как правило, GraphML-файл. После этого система Visual Graph сможет прочитать эту графовую модель из файла, визуализировать ее и предоставить пользователю средства навигации по ней и ее анализа. В отличие от зарубежных аналогов (и другой нашей системы Higres), система Visual Graph поддерживает обработку произвольных атрибутированных иерархических графов достаточно большого размера, ориентирована на пошаговое построение многооконного изображения графовой модели, состоящего из укрупненных изображений интересных пользователю фрагментов модели, и предоставляет богатые возможности для навигации по графовой модели и ее структурного анализа, работы с атрибутами ее элементов, а также простого расширения и настройки системы на нужды конкретного пользователя.

Рис. 3. Сценарий использования системы Visual Graph

Fig. 3. The scenario of using the Visual Graph system

Изначально система поддерживала только один формат для представления графов – это стандартный язык описания графов GraphML. В текущей же версии системы добавлена поддержка таких форматов, как DOT [15] и GML [16], поскольку некоторые весьма популярные компиляторы и системы визуализации ориентированы на работу с этими форматами. Добавлена также возможность экспорта системой частей графа в GraphML-формат для их дальнейшей обработки.
В текущей версии системы изменился набор встроенных алгоритмов укладки графов за счет его расширения двумя алгоритмами: алгоритмом циркулярной укладки атрибутированных иерархических графов с портами [17], а также алгоритмом поуровневой укладки атрибутированных иерархических графов с портами, представляющими внутреннее представление функциональных программ [18]. При этом, библиотека JGraph [19], которая изначально использовалась в системе для отображения и укладки графов, в текущей версии системы заменена на специально разработанный модуль для отображения графовых моделей. Дело в том, что библиотека JGraph имеет ряд ограничений, которые затрудняли реализацию работы с атрибутированными иерархическими графами с портами в полном объеме. Основными трудностями ее использования для реализации новых встроенных алгоритмов укладки стали проблемы, связанные с существенно возросшим за счет портов количеством элементов графов, а также с требуемыми изменениями способов отображения портов и фрагментов.

Произошли также изменения в пользовательском интерфейсе системы, который по-прежнему включает рабочий стол, навигационную панель, а также атрибутную панель (рис. 4).

Рис. 4. Система Visual Graph

Fig. 4. Visual Graph System

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

Каждая вкладка имеет свой фильтр (поисковую строку), используя который можно найти и выделить все те элементы у видимой части графовой модели, текстовые атрибуты которых удовлетворяют регулярному выражению, введенному пользователем в поисковую строку. Расширены возможности фильтра по его настройке на то, какие элементы нужно искать. Так, например, можно осуществлять поиск только среди вершин или ребер. Мини-карта позволяет обозревать весь граф целиком вместе с выделенной той его частью, которая видна в текущей вкладке, а также предоставляет пользователю возможность перемещать и масштабировать видимую часть графа. Сама мини-карта была перенесена с панели инструментов, где она размещалась первоначально, в правую верхнюю часть текущей вкладки. Также была добавлена возможность отключения показа мини-карты; что позволяет пользователю, если необходимо, увеличить по вертикали размер той области текущей вкладки, которая используется для рассмотрения построенного изображения видимого фрагмента графа.

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

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

Заключение

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

Об авторах

Виктор Николаевич Касьянов

Автор, ответственный за переписку.
Email: kvn@iis.nsk.su

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

Список литературы

Дополнительные файлы

Доп. файлы

Действие

1. JATS XML

Скачать

2. Рис. 1. Простой иерархический граф

Скачать (34KB)

Метаданные

3. Рис. 2. Р-схема

Скачать (62KB)

Метаданные

4. Рис. 3. Сценарий использования системы Visual Graph

Скачать (269KB)

Метаданные

5. Рис. 4. Система Visual Graph

Скачать (659KB)

Метаданные