Языки описания и средства визуализации графов

Александр Качур

Как известно граф — это совокупность объектов со связями между ними.

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

Задача возникла в контексте проблемы визуального представления сети. От формата ожидалась возможность описания помимо топологии сети, еще и некоторых составных элементов рабочих станций. Идеальным для этой цели стал RDF-based формат NDL (http://www.science.uva.nl/research/sne/ndl).

NDL — Network Description Language, по сути является онтологией для описания компьютерных сетей.

NDL представляет собой совокупность пяти ключевых структур.

Topology schema — структура для описания устройств (рабочих станций), сетевых интерфейсов и соединений между ними. Также в этой структуре определен класс Location, определяющий месторасположение устройства.

Layer schema — абстрактная структура для описания специфических сетевых технологий и взаимосвязью между сетевыми уровнями.

Сapability schema —  структура служащая для описания совместимости устройств.

Domain schema  — описывает область администрирования(домен), сервисы в этой области, а также логическое представление данного сегмента сети, входящего в домен.

Physical schema — описание физических аспектов сетевых элементов, а также составных частей этих элементов.

Ниже представлена UML диаграмма классов данных структур.

UML

Но в связи со сложностью работы с сетями, описанными с помощью NDL, пришлось продолжить поиск, и  следующим рассмотренным форматом стал DOT.

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

Неориентированный граф

н граф graph graphname {
a — b — c;
b — d;
}

Ориентированный граф

о-граф digraph graphname {
a -> b -> c;
b -> d;
}

Конечно, данные примеры являются по сути «Hello world»-графами, но принцип описания узлов и связей между ними они отображают в полной мере. Для описания топологии данный формат подходит отлично, являясь простым и «обезжиренным». Набор атрибутов, применимых к объектам графа, предельно лаконичен ну и реализация API для работы с ним не представляет особого труда, в отличие от громоздкого NDL. Однако DOT не предоставляет возможности пользователю описывать и добавлять собственные параметры к ребрам и вершинам, что является серьезным минусом в контексте рассматриваемой проблемы.

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

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

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

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

Примитивный граф с двумя вершинами и ребром между ними выглядит так:

<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns
     http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
 <graph id="G" edgedefault="undirected">
    <node id="n0"/>
    <node id="n1"/>
    <edge id="e1" source="n0" target="n1"/>
  </graph>
</graphml>

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

Java Graph Editing Framework (GEF)

GEF

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

  • Простой и понятный  дизайн, который дает возможность разработчику расширять функциональность библиотеки.
  • Node-Port-Edge модель представления графа, которая позволяет выполнять подавляющее большинство задач встречающихся в приложениях для работы с графами.
  • XML-based формат файлов, основанный на стандарте PGML (в скором времени обещают поддержку SVG).

ILOG JViews
jviews

ILOG JViews предоставляет компоненты, предназначенные для использования в пользовательских приложениях, а также на совместно с Ajax и платформой Eclipse.

Java Universal Network / График Framework (JUNG)

jung
JUNG  — это программная библиотека, которая предоставляет удобный и расширяемый интерфейс для моделирования, анализа и визуализации данных, которые могут быть представлены в виде графа или сети. Он написан на Java, что позволяет JUNG-приложению использовать в полной мере Java API, а также сторонние библиотеки. Являясь open-source библиотекой, JUNG представляет собой фреймворк для анализа и визуализации, как графов так и  сетей.

jgrapht

JGraphT является свободно распространяемой библиотекой, которая обеспечивает математический аппарат теории графов. JGraphT поддерживает различные виды графов, включая: ориентированные и неориентированные графы; графы со взвешенными / невзвешенный / именованными или любым другим форматом ребер определенным пользователем; не модифицируемые графы – обеспечивается доступ в режиме «только чтение» к внутренним графам; listenable графы – разрешает внешним слушателям отслеживать возникновение событий; подграфы – графы, которые являются представлением других графах.

JGraphT являясь мощным средством, разрабатывался как простое и type-safe (с использованием Java кодогенераторов) средство для работы с графами. Например, вершиной графа может быть любой объект. Вы можете создавать графики на основе: строки, URL, XML документов и т.п., вы можете даже создавать графы графов.

Вот еще некоторые из визуализационных фреймворкков для Java — Piccolo, Processing, The Visualization Toolkit (VTK), JUNG, The InfoVis Toolkit, Improvise.

Наиболее интересным на мой взгляд средством визуализации графов является проект под названием prefuse, разработанный в Berkeley.

prefuse
Prefuse изначально разрабатывался как фреймворк  для создания интерактивных приложений визуализации информации с использованием языка программирования Java. Prefuse flare предоставляет собой средство для анимации с помощью ActionScript Adobe Flash Player.

Prefuse поддерживает богатый набор функций для передачи данных моделирования, визуализации и взаимодействия. Она предоставляет оптимизированные структуры данных для представления таблиц, графиков, а также деревьев, поддержку анимации, динамические запросы, комплексный поиск и подключение базы данных. Prefuse написан на Java, с использованием Java 2D графической библиотеки, и легко интегрировать в Java Swing приложений или веб-апплеты. Prefuse лицензируется по условиям лицензии BSD, и могут свободно использоваться как для коммерческих и некоммерческих целях. Он может быть использована для создания обычных приложений, визуальных компонентов, встроенных в более крупных приложений и веб-апплеты. Prefuse является гибким средством визуализции данных, существенно упрощающий процесс отображения данных на их визуальное представление, а также взаимодействия с данными.

API Рrefuse’a работает с такими форматами данных как GraphML, TreeML. Существует также поддержка простых типов представления данных таких как CSV и возможность получения данных напрямую из таблиц баз данных.

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

NDL — мощнейшее узкоспециализированное средство для представления сетей. Является RDF онтологией и позволяет детальнейшим образом описать компьютерную сеть.

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

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

6 Responses to Языки описания и средства визуализации графов

  1. Мне необходимо визуализировать часть owl Онтологии — только наборы экземляров классов + связи между ними, причем сделать так, чтоб визуализированные объекты были интерактивными(чтоб к ним можно было listener прикрутить). Подойдет ли для этого Prefuse?

  2. Подойдет. с помощью OWL2Prefuse добавите необходимую функциональность.

  3. Возникли проблемы — никак не могу додумать.
    С помощью OWL2Prefuse подготовил XML файл для загрузки в prefuse.
    Далее(в prefuse) подгрузил этот файл в объект Graph — далее он и визуализируется сделующим способом: добавляется в объект Visualization, далее этот Visualization, добавляется в Display, а Display уже в JFrame.
    Для визуализации того, что необходимо нужно накладывать на Display так называемы Predicate(по-сути фильтр). И вот тут проблема — накладываю — ошибка(фильтр думаю правильно сделал — через ExpressionParser.predicate()).
    Читал справку, там в примере вместо графа — таблица — показано, что Predicate накладывается на нее и все нормально, однако примера с графом — нет (справка на этом заканчивается с оптимистичной пометкой — как-только так сразу :cry:).
    Просмотрел JavaDOC увидел что Graph это на самом деле 2 таблицы (одна для вершин — другая для дуг), соответвенно, думаю проблема в том, что когда накладываем фильт на Display:
    display.setPredicate(ex);
    Он не знает к какой таблице его применять.
    Может кто-то сталкивался — подскажите где может быть ошибка?

  4. Наверное это мое упущение что я забыл добавить ссылки на материалы по префьюзу, так как хелпа вменяемого действительно нету.
    Итак:
    http://www.cs.mun.ca/~hoeber/teaching/cs4767/notes/04-prefuse/
    http://prefuse.blogspot.com/
    http://goosebumps4all.net/34all/bb/forumdisplay.php?fid=18
    Именно по предикатам. http://cs.marlboro.edu/courses/spring2007/tutorials/sam/Prefuse
    P.S.: У графа для работы с предикатом есть такой метод:
    tuples(Predicate filter)
    Get a filtered iterator over the edges and nodes of this graph.

  5. Пасибо, посмотрю ссылки 😛

  6. Теперь в список средств можно добавить Gephi , он уже достаточно живой для этого.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *


Ответить с помощью ВКонтакте: