GraphML: практическое введение

2007 г.

GraphML: практическое введение

Редакторы: Ulrik Brandes, Markus Eiglsperger, Jürgen Lerner
Перевод: Шокоров В. П.

Предисловие переводчика

Данный документ представляет собой перевод документа “ GraphML Primer ” на русский язык. При этом нормативным документом считается оригинальный текст на английском языке, который можно найти по адресу http://graphml.graphdrawing.org/primer/graphml-primer.html. Представленный документ может содержать ошибки перевода. Перевод выполнил Шокоров В. П. (http://PenzaVld.narod.ru).

Аннотация

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

1 Введение

Данный документ представляет собой учебник для начинающих, и должен использоваться совместно с формальным описанием языка, содержащегося в GraphML-спецификации. Документ предназначен для разработчиков программного обеспечения, предназначенного для работы с GraphML-файлами. Текст документа предполагает, что Вы знакомы с XML 1.0 и XML-Namespaces . При чтении некоторых разделов требуются элементарные знания языка XML-схем. Каждый раздел учебника содержит новые особенности языка, и описывает их на конкретных примерах.

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

Раздел 3 описывает дополнительные возможности языка, связанные с вложенными графами, гиперребрами и портами.

Раздел 4 описывает механизм расширения языка в целях включения комплексных данных, специфичных для конкретных приложений.

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

2 Основные понятия

Назначение GraphML-документа - определение графа. Для начала рассмотрим граф показанный на приведенном ниже рисунке. Он содержит 11 узлов и 12 ребер.

Простой граф

2.1 Простой граф

Простой граф описан в файле simple.graphml:

Простой граф

<?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"/>
    <node id="n2"/>
    <node id="n3"/>
    <node id="n4"/>
    <node id="n5"/>
    <node id="n6"/>
    <node id="n7"/>
    <node id="n8"/>
    <node id="n9"/>
    <node id="n10"/>
    <edge source="n0" target="n2"/>
    <edge source="n1" target="n2"/>
    <edge source="n2" target="n3"/>
    <edge source="n3" target="n5"/>
    <edge source="n3" target="n4"/>
    <edge source="n4" target="n6"/>
    <edge source="n6" target="n5"/>
    <edge source="n5" target="n7"/>
    <edge source="n6" target="n8"/>
    <edge source="n8" target="n7"/>
    <edge source="n8" target="n9"/>
    <edge source="n8" target="n10"/>
  </graph>
</graphml>

GraphML-документ состоит из элемента graphml и ряда подэлементов: graph, node, edge. В конце раздела рассмотрим перечисленные элементы подробнее , и покажем, как они определяют граф.

2.2 Заголовок

Рассмотрим фрагмент , общий для всех GraphML-документов, основанный на элементе graphml.

Первая строка документа это инструкция обработки, которая определяет что документ является подмножеством стандарта XML 1.0, и что документ выполнен в кодировке UTF-8. Конечно, для GraphML-документов могут быть выбраны и другие кодировки.

Вторая строка содержит корневой элемент GraphML-документа: graphml. Элемент graphml, также как и все остальные элементы языка GraphML, принадлежит именному пространству http://graphml.graphdrawing.org/xmlns . По этой причине, с помощью XML-атрибута xmlns="http://graphml.graphdrawing.org/xmlns",мы определяем это именное пространство как именное пространство документа заданное по умолчанию. Следующие два XML-атрибута определяют XML-схему данного документа. В нашем примере мы используем стандартную схему GraphML-документа, расположенную на сервере graphdrawing.org. Первый атрибут, xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" - определяет, xsi в качестве префикса именного пространства XML-схемы. Второй атрибут, xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd" - определяет местонахождение XML-схемы для элементов именного пространства GraphML.

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

В GraphML не установлен порядок появления элементов node и edge. Поэтому следующий пример является синтаксически правильным GraphML-фрагментом:

2.3.1 Объявление графа

Граф в GraphML - смешанный, другими словами он может содержать направленные и ненаправленные ребра одновременно. Если при объявлении ребра его направленность не определена, то применяется направленность заданная по умолчанию. Направленность ребер, присваиваемая по умолчанию, задается XML-атрибутом edgedefault элемента graph. Этот XML-атрибут может принимать одно из двух значений: directed и undirected. Значение по умолчанию должно быть задано обязательно.

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

2.3.2 Объявление узла

Уз е л в графе объявляется с помощью элемента node. Каждый узел имеет уникальный (в пределах данного документа) идентификатор. Идентификатор узла задается с помощью XML-атрибута id.

2.3.3 Объявление ребра

Ребро в графе объявляется с помощью элемента edge. Каждое ребро имеет две конечные точки, задаваемые с помощью XML-атрибутов source и target. Значения атрибутов source и target должны содержать идентификаторы узлов, определенных в том же документе что и ребро.

Ребра с одной конечной точкой, называемые петлями, циклами, или замкнутыми ребрами, определяются с помощью одинаковых значений, заданных в атрибутах source и target.

Дополнительный XML-атрибут directed определяет направленность ребра, заданную в явном виде. Значение true задает направленное ребро, а false - ненаправленное. Если направленность в явном виде не задана, то применяется направленность заданная по умолчанию при объявлении графа.

Дополнительно, с помощью XML-атрибута id, может быть задан идентификатор ребра. XML-атрибут id задается когда необходимо организовать ссылку на данное ребро.

2.4 GraphML-атрибуты

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

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

Если в элементы графа вам необходимо добавить структурированные данные, то вы должны использовать механизм расширения GraphM L под названием ключ/данные (data/key). Более подробно этот механизм рассмотрен в разделе 4. GraphML-атрибуты специализированное расширение механизма ключ/данные (data/key).

GraphML-атрибуты не следует путать с XML-атрибутами, это разные понятия.

2.4.1 Пример GraphML-атрибутов

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

Граф с раскрашенными узлами и оцифрованными ребрами.

Мы будем использовать GraphML-атрибуты для хранения данных в узлах и ребрах. Результат показан в файле attributes.graphml:

2.4.2 Объявление GraphML-атрибутов

GraphML-атрибут объявляется с помощью элемента key который задает идентификатор, имя, тип, и домен атрибута.

Идентификатор задается XML-атрибутом id и используется для ссылки на данный GraphML-атрибут внутри документа.

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

Тип GraphML-атрибута может быть boolean, int, long, float, double, или string . Эти типы определены в соответствии с аналогичными типами в языке Java(TM) .

Домен GraphML-атрибута определяет перечень элементов в которых GraphML-атрибут может быть объявлен. Возможные значения: graph, node, edge, и all .

Для GraphML-атрибутов можно определить значение по умолчанию. Содержимое элемента default определяет текстовое значение по умолчанию.

2.4.3 Определение значений GraphML-атрибутов

Значение GraphML-атрибута в элементе графа задается с помощью элемента data вложенного в данный элемент. Элемент data имеет XML-атрибут key, который ссылается на идентификатор GraphML-атрибута. Значение GraphML-атрибута задается текстовым содержимым элемента data. Это значение должно иметь тип, объявленный в соответствующем элементе key.

Могут быть такие GraphML-атрибуты, которые определены, но не объявлены с помощью элемента data. Если значение по умолчанию определено для данного GraphML-атрибута, то тогда это значение применяется к соответствующему (входящему в домен GraphML-атрибута) элементу графа. В вышеприведенном примере значение не определено для узла с идентификатором n1 и GraphML-атрибута с именем color . Однако по для данного GraphML-атрибута определено значение по умолчанию yellow , которое будет присвоено данному узлу. Если значение по умолчанию не задано, как для GraphML-атрибута weight в вышеприведенном примере, то значение GraphML-атрибута для элемента графа не определено. В вышеприведенном примере не определено значение GraphML-атрибута, задающего вес ребра с идентификатором e3.

2.5 Информация для парсера

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

Во первых рассмотрим информацию о количестве элементов. Для элемента graph определены следующие XML-атрибуты: XML-атрибут parse.nodes задает количество узлов в графе, XML-атрибут parse.edges - количество ребер. XML-атрибут parse.maxindegree определяет максимальное количество входящих в вершину ребер, а XML-атрибут parse.maxoutdegree - максимальное количество исходящих из вершины ребер. Для элемента node XML-атрибут parse.indegree определяет максимальное количество входящих ребер для данной вершины, а XML-атрибут parse.outdegree - максимальное количество исходящих ребер для данной вершины.

Во вторых рассмотрим информацию, связанную с кодированием. Для элемента graph определены следующие XML-атрибуты: если XML-атрибут parse.nodeids имеет значение canonical , все узлы имеют идентификатор вида nX, где X обозначает количество элементов node предшествующих данному элементу. Второе значение XML-атрибута - free . Аналогично этому, XML-атрибут parse.edgeids задает вид идентификатора для узлов. Отличие состоит только в том, что идентификатор имеет вид eX. XML-атрибут parse.order определяет порядок в котором узлы и ребра располагаются в документе. При значении равном nodesfirst все элементы node располагаются раньше элементов edge. При значении равном adjacencylist, объявление узла предшествует объявлению его смежных вершин. Для значения free порядок следования не устанавливается.

Следующий пример иллюстрирует использование информации для парсера:

Граф с дополнительной информацией для парсера.

 <?xml version="1.0" encoding="UTF-8"?>
<!-- This file was written by the JAVA GraphML Library.-->
<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="directed" 
            parse.nodes="11" parse.edges="12" 
            parse.maxindegree="2" parse.maxoutdegree="3"
            parse.nodeids="canonical" parse.edgeids="free" 
            parse.order="nodesfirst">
    <node id="n0" parse.indegree="0" parse.outdegree="1"/>
    <node id="n1" parse.indegree="0" parse.outdegree="1"/>
    <node id="n2" parse.indegree="2" parse.outdegree="1"/>
    <node id="n3" parse.indegree="1" parse.outdegree="2"/>
    <node id="n4" parse.indegree="1" parse.outdegree="1"/>
    <node id="n5" parse.indegree="2" parse.outdegree="1"/>
    <node id="n6" parse.indegree="1" parse.outdegree="2"/>
    <node id="n7" parse.indegree="2" parse.outdegree="0"/>
    <node id="n8" parse.indegree="1" parse.outdegree="3"/>
    <node id="n9" parse.indegree="1" parse.outdegree="0"/>
    <node id="n10" parse.indegree="1" parse.outdegree="0"/>
    <edge id="edge0001" source="n0" target="n2"/>
    <edge id="edge0002" source="n1" target="n2"/>
    <edge id="edge0003" source="n2" target="n3"/>
    <edge id="edge0004" source="n3" target="n5"/>
    <edge id="edge0005" source="n3" target="n4"/>
    <edge id="edge0006" source="n4" target="n6"/>
    <edge id="edge0007" source="n6" target="n5"/>
    <edge id="edge0008" source="n5" target="n7"/>
    <edge id="edge0009" source="n6" target="n8"/>
    <edge id="edge0010" source="n8" target="n7"/>
    <edge id="edge0011" source="n8" target="n9"/>
    <edge id="edge0012" source="n8" target="n10"/>
  </graph>
</graphml>

3. Дополнительные понятия I: вложенные графы, гиперребра и порты

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

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

3.1 Вложенные графы

GraphML поддерживает вложенные графы, т.е., графы в которых узлы иерархически упорядочены. Иерархия выражается через структуру GraphML-документа. Узел в GraphML-документе может иметь элемент graph, который содержит узлы иерархически вложенные в данный узел. Ниже приводится пример вложенного графа и соответствующий ему GraphML-документ. Обратите внимание, что на рисунке графа иерархия выражена с помощью оболочки, т.е., узел а находится в иерархии ниже узла b если графическое представление узла a расположено внутри графического представления узла b.

В файле nested.graphml содержится соответствующий GraphML-документ:

Ребра соединяющие два узла, находящиеся во вложенном графе, должны быть объявлены в графе, который является предком обоих узлов в иерархии. Обратите внимание, что в нашем примере именно так и сделано. Объявление ребра между узлом n6::n1 и узлом n4::n0:: n0 в графе n6::n0 было бы неправильно, а объявление их в графе G - правильно. Хорошая практика состоит в том, чтобы размещать объявление ребра в наиболее общем предке или на самом верхнем уровне иерархии.

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

3.2 Гиперребра

Гиперребра это смысловое объединение ребер которое не не только связывает две конечные точки, но и выражает зависимость между произвольным числом конечных точек (например, описание кратчайшего пути - примечание переводчика). Гиперребра объявляются с помощью элемента hyperedge. Каждой конечной точке входящей в данное гиперребро соответствует элемент endpoint. Элемент endpoint должен иметь XML-атрибут node, который содержит идентификатор узла в документе. Следующий пример содержит гиперребра и два ребра. Гиперребра изображены в виде дуг, а ребра в виде прямых линий. Заметим, что ребра задаются с помощью элемента edge или с помощью элемента hyperedge содержащего два элемента endpoint.

Файл hyper.graphml содержит соответствующий GraphML-документ:

Как и ребра, гиперребра и конечные точки могут иметь XML-атрибут id, который является уникальным идентификатором для соответствующих элементов.

3.3 Порты

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

Порты узла объявляются с помощью элементов port, которые являются дочерними по отношению к соответствующему элементу node. Обратите внимание, что порты могут быть вложенными, т.е., они могут содержать внутри себя другие элементы port. Каждый элемент port должен иметь XML-атрибут name, который идентифицирует этот порт. Элемент edge имеет необязательные XML-атрибуты sourceport и targetport которые задают для ребра исходящий и входящий порты узла, соответственно. Аналогично элемент endpoint имеет необязательный XML-атрибут port.

Документ port.graphml - пример документа с портами:

4. Дополнительные понятия II: расширение GraphML

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

Расширения GraphML должны быть заданы в XML-схеме. Схема, в которой определены расширения, может быть порождена из схемы GraphML-документа с помощью стандартного механизма похожего на механизм, применяемый в XHTML.

4.1 Добавление XML-атрибутов в GraphML-элементы

В большинстве случаев, дополнительная информация может (и должна) быть связана с GraphML-элементами с помощью GraphML-атрибутов, что гарантируется совместимостью GraphML-парсеров. Однако, в ряде случаев более удобно использовать XML-атрибуты. Предположим у вас имеется парсер, который умеет обрабатывать XLink-атрибут href и корректно интерпретировать его как URL. Предположим вы хотите хранить в GraphML граф, узлы которого представляют собой WWW-страницы. Для ассоциации узла со страницей его модель должна позволять вам в теге node присваивать атрибуту xlink:href URL-ссылку на соответсвующую страницу:

Для добавления XML-атрибутов в GraphML-элементы используется механизм расширение GraphML. Это расширение должно быть определено в XML-схеме. В документе graphml+xlink.xsd показан атрибут href добавленный к элементу node:

Приведенный выше документ имеет следующие функциональные составляющие: в качестве корневого элемента документ graphml+xlink.xsd имеет элемент schema. Значение атрибута targetNamespace ="http://graphml.graphdrawing.org/xmlns" говорит о том, что данный документ соответствует спецификации языка GraphML. Три следующих строки задают именное пространство документа, используемое по умолчанию и префикс именного пространства для XLink и XMLSchema . Атрибуты elementFormDefault и attributeFormDefault в данном примере неважны.

<xs:import namespace="http://www.w3.org/1999/xlink" schemaLocation="xlink.xsd"/> задает адрес местоположения именного пространства XLink , заданного в файле xlink.xsd .

<xs:redefine schemaLocation="http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd"> задает файл со схемой которая должна быть переопределена. Группа атрибутов node.extra.attrib включается в список атрибутов элемента node. После переопределения указанная группа атрибутов будет содержать старое содержимое , плюс атрибут с именем xlink:href, который является необязательным.

Кроме node.extra.attrib, имеются соответствующие группы атрибутов для всех основных GraphML-элементов.

В документе attributes.ext.graphml приведен пример документа который соответствует схеме graphml+xlink.xsd.

4.2 Добавление комплексных типов

Структурированное содержимое может быть добавлено с помощью элемента data. Например, пользователь может хранить для узлов их изображения в формате SVG .

Для добавления структурированных данных в GraphML-элементы используется механизм расширения GraphML. Это расширение должно быть задано с помощью XML-схемы. Документ graphml+svg.xsd демонстрирует как элементы SVG могут быть добавлены в содержимое data:

Вышеприведенная схема похожа на схему в примере с добавлением атрибутов. Во первых присутсвуют объявления именного пространтсва. Во вторых, импортировано именное пространство SVG. Наконец расширен комплексный тип data-extension.type, который является базовым для описания содержимого элемента data, путем добавления элемента svg из именного пространства SVG.

В файле svg.graphml приведен документ, соответствующий схеме graphml+svg.xsd:

Заметим, что узел с идентификатором n1 допускает графическое изображение по умолчанию, заданное элементом key с идентификатором k0. Вышеприведенный пример также демонстрирует использование именных пространств XML: задано два различных элемента desc - один в именном пространстве GraphML, а второй в именном пространстве SVG . Возможный конфликт, связанный с одинаковыми именами элементов в различных XML-языках, разрешен с помощью использования различных именных пространств.