Александр Качур
Как известно граф — это совокупность объектов со связями между ними.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах. Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. В данной заметке речь пойдет о представлении, при помощи графа, такой структуры как компьютерные сети.
Задача возникла в контексте проблемы визуального представления сети. От формата ожидалась возможность описания помимо топологии сети, еще и некоторых составных элементов рабочих станций. Идеальным для этой цели стал 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 диаграмма классов данных структур.
Но в связи со сложностью работы с сетями, описанными с помощью 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:
- Простой и понятный дизайн, который дает возможность разработчику расширять функциональность библиотеки.
- Node-Port-Edge модель представления графа, которая позволяет выполнять подавляющее большинство задач встречающихся в приложениях для работы с графами.
- XML-based формат файлов, основанный на стандарте PGML (в скором времени обещают поддержку SVG).
ILOG JViews
ILOG JViews предоставляет компоненты, предназначенные для использования в пользовательских приложениях, а также на совместно с Ajax и платформой Eclipse.
Java Universal Network / График Framework (JUNG)
JUNG - это программная библиотека, которая предоставляет удобный и расширяемый интерфейс для моделирования, анализа и визуализации данных, которые могут быть представлены в виде графа или сети. Он написан на Java, что позволяет JUNG-приложению использовать в полной мере Java API, а также сторонние библиотеки. Являясь open-source библиотекой, JUNG представляет собой фреймворк для анализа и визуализации, как графов так и сетей.
JGraphT является свободно распространяемой библиотекой, которая обеспечивает математический аппарат теории графов. JGraphT поддерживает различные виды графов, включая: ориентированные и неориентированные графы; графы со взвешенными / невзвешенный / именованными или любым другим форматом ребер определенным пользователем; не модифицируемые графы – обеспечивается доступ в режиме "только чтение" к внутренним графам; listenable графы – разрешает внешним слушателям отслеживать возникновение событий; подграфы – графы, которые являются представлением других графах.
JGraphT являясь мощным средством, разрабатывался как простое и type-safe (с использованием Java кодогенераторов) средство для работы с графами. Например, вершиной графа может быть любой объект. Вы можете создавать графики на основе: строки, URL, XML документов и т.п., вы можете даже создавать графы графов.
Вот еще некоторые из визуализационных фреймворкков для Java - Piccolo, Processing, The Visualization Toolkit (VTK), JUNG, The InfoVis Toolkit, Improvise.
Наиболее интересным на мой взгляд средством визуализации графов является проект под названием prefuse, разработанный в Berkeley.
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 структура позволяет легко расширять узлы свойствами, в то-же время сохраняя простую структуру описания графа.
