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 Введение
- 2 Основные понятия
- 2.1 Простой граф
- 2.2 Заголовок
- 2.3 Топология графа
- 2.3.1 Объявление графа
- 2.3.2 Объявление узла
- 2.3.3 Объявление ребра
- 2.4 GraphML-атрибуты
- 2.4.1 Пример GraphML-атрибутов
- 2.4.2 Объявление GraphML-атрибутов
- 2.4.4 Определение значений GraphML-атрибутов
- 2.5 Информация для парсера
- 3 Дополнительные понятия I: вложенные графы, гиперребра и порты
- 3.1 Вложенные графы
- 3.2 Гиперребра
- 3.3 Порты
- 4 Дополнительные понятия II: расширение GraphML
- 4.1 Добавление XML-атрибутов в GraphML-элементы
- 4.2 Добавление комплексных типов
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-схему
<?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">
...
</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-схему не обязательна, но она обеспечивает механизм для синтаксической проверки документа и поэтому строго рекомендуется.
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns">
...
</graphml>
2.3 Топология графа
Граф обозначается с помощью элемента graph . Элементы расположенные внутри элемента graph обеспечивают объявление узлов и ребер. Узел объявляется с помощью элемента node , а ребро с помощью элемента edge .
Определение графа
<graph id="G" edgedefault="directed">
<node id="n0"/>
<node id="n1"/>
...
<node id="n10"/>
<edge source="n0" target="n2"/>
<edge source="n1" target="n2"/>
...
<edge source="n8" target="n10"/>
</graph>
В GraphML не установлен порядок появления элементов node и edge . Поэтому следующий пример является синтаксически правильным GraphML-фрагментом:
Определение графа
<graph id="G" edgedefault="directed">
<node id="n0"/>
<edge source="n0" target="n2"/>
<node id="n1"/>
<node id="n2"/>
...
</graph>
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 задается когда необходимо организовать ссылку на данное ребро.
Ребро со всеми XML-атрибутами
...
<edge id="e1" directed="true" source="n0" target="n2"/>
...
2.4 GraphML-атрибуты
В предыдущем разделе мы обсудили порядок описания топологии графа на языке GraphML. Поскольку для различных приложений может потребоваться различная информация о топологии графа, необходимо иметь механизм для включения такой информации в описание графа.
С помощью механизма расширения, который называется GraphML-атрибуты для элементов графа может быть задана дополнительная информация простого типа. Простой тип подразумевает, что данные ограничены скалярными величинами. Например, числами и строками.
Если в элементы графа вам необходимо добавить структурированные данные, то вы должны использовать механизм расширения GraphM L под названием ключ/данные (data/key). Более подробно этот механизм рассмотрен в разделе 4. GraphML-атрибуты специализированное расширение механизма ключ/данные (data/key).
GraphML-атрибуты не следует путать с XML-атрибутами, это разные понятия.
2.4.1 Пример GraphML-атрибутов
В качестве примера в данном разделе рассматривается граф с раскрашенными узлами и оцифрованными ребрами.
Граф с раскрашенными узлами и оцифрованными ребрами.
Мы будем использовать GraphML-атрибуты для хранения данных в узлах и ребрах. Результат показан в файле attributes.graphml:
Example of a GraphML Document with GraphML-Attributes
<?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">
<key id="d0" for="node" attr.name="color" attr.type="string">
<default>yellow</default>
</key>
<key id="d1" for="edge" attr.name="weight" attr.type="double"/>
<graph id="G" edgedefault="undirected">
<node id="n0">
<data key="d0">green</data>
</node>
<node id="n1"/>
<node id="n2">
<data key="d0">blue</data>
</node>
<node id="n3">
<data key="d0">red</data>
</node>
<node id="n4"/>
<node id="n5">
<data key="d0">turquoise</data>
</node>
<edge id="e0" source="n0" target="n2">
<data key="d1">1.0</data>
</edge>
<edge id="e1" source="n0" target="n1">
<data key="d1">1.0</data>
</edge>
<edge id="e2" source="n1" target="n3">
<data key="d1">2.0</data>
</edge>
<edge id="e3" source="n3" target="n2"/>
<edge id="e4" source="n2" target="n4"/>
<edge id="e5" source="n3" target="n5"/>
<edge id="e6" source="n5" target="n4">
<data key="d1">1.1</data>
</edge>
</graph>
</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-атрибута
...
<key id="d1" for="edge" attr.name="weight" attr.type="double"/>
...
Для GraphML-атрибутов можно определить значение по умолчанию. Содержимое элемента default определяет текстовое значение по умолчанию.
Объявление GraphML-атрибута со значением по умолчанию
...
<key id="d0" for="node" attr.name="color" attr.type="string">
<default>yellow</default>
</key>
...
2.4.3 Определение значений GraphML-атрибутов
Значение GraphML-атрибута в элементе графа задается с помощью элемента data вложенного в данный элемент. Элемент data имеет XML-атрибут key , который ссылается на идентификатор GraphML-атрибута. Значение GraphML-атрибута задается текстовым содержимым элемента data . Это значение должно иметь тип, объявленный в соответствующем элементе key .
Значения GraphML-атрибута
...
<key id="d0" for="node" attr.name="color" attr.type="string">
<default>yellow</default>
</key>
<key id="d1" for="edge" attr.name="weight" attr.type="double"/>
<graph id="G" edgedefault="undirected">
<node id="n0">
<data key="d0">green</data>
</node>
<node id="n1"/>
...
<edge id="e0" source="n0" target="n2">
<data key="d1">1.0</data>
</edge>
<edge id="e1" source="n0" target="n1">
<data key="d1">1.0</data>
</edge>
<edge id="e2" source="n1" target="n3">
<data key="d1">2.0</data>
</edge>
<edge id="e3" source="n3" target="n2"/>
...
</graph>
...
Могут быть такие 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.1 Вложенные графы
GraphML поддерживает вложенные графы, т.е., графы в которых узлы иерархически упорядочены. Иерархия выражается через структуру GraphML-документа. Узел в GraphML-документе может иметь элемент graph , который содержит узлы иерархически вложенные в данный узел. Ниже приводится пример вложенного графа и соответствующий ему GraphML-документ. Обратите внимание, что на рисунке графа иерархия выражена с помощью оболочки, т.е., узел а находится в иерархии ниже узла b если графическое представление узла a расположено внутри графического представления узла b .
Вложенный граф.
В файле nested.graphml содержится соответствующий GraphML-документ:
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">
<graph id="n5:" edgedefault="undirected">
<node id="n5::n0"/>
<node id="n5::n1"/>
<node id="n5::n2"/>
<edge id="e0" source="n5::n0" target="n5::n2"/>
<edge id="e1" source="n5::n1" target="n5::n2"/>
</graph>
</node>
<node id="n6">
<graph id="n6:" edgedefault="undirected">
<node id="n6::n0">
<graph id="n6::n0:" edgedefault="undirected">
<node id="n6::n0::n0"/>
</graph>
</node>
<node id="n6::n1"/>
<node id="n6::n2"/>
<edge id="e10" source="n6::n1" target="n6::n0::n0"/>
<edge id="e11" source="n6::n1" target="n6::n2"/>
</graph>
</node>
<edge id="e2" source="n5::n2" target="n0"/>
<edge id="e3" source="n0" target="n2"/>
<edge id="e4" source="n0" target="n1"/>
<edge id="e5" source="n1" target="n3"/>
<edge id="e6" source="n3" target="n2"/>
<edge id="e7" source="n2" target="n4"/>
<edge id="e8" source="n3" target="n6::n1"/>
<edge id="e9" source="n6::n1" target="n4"/>
</graph>
</graphml>
Ребра соединяющие два узла, находящиеся во вложенном графе, должны быть объявлены в графе, который является предком обоих узлов в иерархии. Обратите внимание, что в нашем примере именно так и сделано. Объявление ребра между узлом n6::n1 и узлом n4::n0:: n0 в графе n6::n0 было бы неправильно, а объявление их в графе G - правильно. Хорошая практика состоит в том, чтобы размещать объявление ребра в наиболее общем предке или на самом верхнем уровне иерархии.
Для приложений, которые не поддерживают вложенность графов, рекомендуется игнорировать узлы, которые не принадлежат графу верхнего уровня, и игнорировать ребра у которых обе конечные точки не принадлежат графу верхнего уровня.
3.2 Гиперребра
Гиперребра это смысловое объединение ребер которое не не только связывает две конечные точки, но и выражает зависимость между произвольным числом конечных точек (например, описание кратчайшего пути - примечание переводчика). Гиперребра объявляются с помощью элемента hyperedge . Каждой конечной точке входящей в данное гиперребро соответствует элемент endpoint . Элемент endpoint должен иметь XML-атрибут node , который содержит идентификатор узла в документе. Следующий пример содержит гиперребра и два ребра. Гиперребра изображены в виде дуг, а ребра в виде прямых линий. Заметим, что ребра задаются с помощью элемента edge или с помощью элемента hyperedge содержащего два элемента endpoint .
Граф с гиперребрами.
Файл hyper.graphml содержит соответствующий GraphML-документ:
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"/>
<hyperedge>
<endpoint node="n0"/>
<endpoint node="n1"/>
<endpoint node="n2"/>
</hyperedge>
<hyperedge>
<endpoint node="n3"/>
<endpoint node="n4"/>
<endpoint node="n5"/>
<endpoint node="n6"/>
</hyperedge>
<hyperedge>
<endpoint node="n1"/>
<endpoint node="n3"/>
</hyperedge>
<edge source="n0" target="n4"/>
</graph>
</graphml>
Как и ребра, гиперребра и конечные точки могут иметь XML-атрибут id , который является уникальным идентификатором для соответствующих элементов.
3.3 Порты
Узлы могут содержать различные логические точки подключения ребер и гиперребер. Такие точки подключения называются портами.
Порты узла объявляются с помощью элементов port, которые являются дочерними по отношению к соответствующему элементу node . Обратите внимание, что порты могут быть вложенными, т.е., они могут содержать внутри себя другие элементы port . Каждый элемент port должен иметь XML-атрибут name , который идентифицирует этот порт. Элемент edge имеет необязательные XML-атрибуты sourceport и targetport которые задают для ребра исходящий и входящий порты узла, соответственно. Аналогично элемент endpoint имеет необязательный XML-атрибут port .
Документ port.graphml - пример документа с портами:
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="directed">
<node id="n0">
<port name="North"/>
<port name="South"/>
<port name="East"/>
<port name="West"/>
</node>
<node id="n1">
<port name="North"/>
<port name="South"/>
<port name="East"/>
<port name="West"/>
</node>
<node id="n2">
<port name="NorthWest"/>
<port name="SouthEast"/>
</node>
<node id="n3">
<port name="NorthEast"/>
<port name="SouthWest"/>
</node>
<edge source="n0" target="n3" sourceport="North" targetport="NorthEast"/>
<hyperedge>
<endpoint node="n0" port="North"/>
<endpoint node="n1" port="East"/>
<endpoint node="n2" port="SouthEast"/>
</hyperedge>
</graph>
</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-ссылку на соответсвующую страницу:
Элемент node, содержащий URL-ссылку
...
<node id="n0" xlink:href="http://graphml.graphdrawing.org"/>
...
Для добавления XML-атрибутов в GraphML-элементы используется механизм расширение GraphML. Это расширение должно быть определено в XML-схеме. В документе graphml+xlink.xsd показан атрибут href добавленный к элементу node :
Расширение GraphML: атрибуты
<?xml version="1.0" encoding="UTF-8"?>
<xs:schema
targetNamespace="http://graphml.graphdrawing.org/xmlns"
xmlns="http://graphml.graphdrawing.org/xmlns"
xmlns:xlink="http://www.w3.org/1999/xlink"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
elementFormDefault="qualified"
attributeFormDefault="unqualified"
>
<xs:import namespace="http://www.w3.org/1999/xlink"
schemaLocation="xlink.xsd"/>
<xs:redefine
schemaLocation="http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
<xs:attributeGroup name="node.extra.attrib">
<xs:attributeGroup ref="node.extra.attrib"/>
<xs:attribute ref="xlink:href" use="optional"/>
</xs:attributeGroup>
</xs:redefine>
</xs:schema>
Приведенный выше документ имеет следующие функциональные составляющие: в качестве корневого элемента документ 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.
GraphML-документ с дополнительными XML-атрибутами
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"
xmlns:xlink="http://www.w3.org/1999/xlink"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns
graphml+xlink.xsd">
<graph edgedefault="directed">
<node id="n0" xlink:href="http://graphml.graphdrawing.org"/>
<node id="n1" />
<edge source="n0" target="n1"/>
</graph>
</graphml>
4.2 Добавление комплексных типов
Структурированное содержимое может быть добавлено с помощью элемента data . Например, пользователь может хранить для узлов их изображения в формате SVG .
Элемент node и его графическое представление
...
xmlns:svg="http://www.w3.org/2000/svg"
...
<node id="n0" >
<data key="k0">
<svg:svg width="4cm" height="8cm" version="1.1">
<svg:ellipse cx="2cm" cy="4cm" rx="2cm" ry="1cm" />
</svg:svg>
</data>
</node>
...
Для добавления структурированных данных в GraphML-элементы используется механизм расширения GraphML. Это расширение должно быть задано с помощью XML-схемы. Документ graphml+svg.xsd демонстрирует как элементы SVG могут быть добавлены в содержимое data :
Расширение GraphML структурированными данными
<?xml version="1.0" encoding="UTF-8"?>
<xs:schema
targetNamespace="http://graphml.graphdrawing.org/xmlns"
xmlns="http://graphml.graphdrawing.org/xmlns"
xmlns:svg="http://www.w3.org/2000/svg"
xmlns:xs="http://www.w3.org/2001/XMLSchema"
elementFormDefault="qualified"
attributeFormDefault="unqualified"
>
<xs:import namespace="http://www.w3.org/2000/svg"
schemaLocation="svg.xsd"/>
<xs:redefine
schemaLocation="http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
<xs:complexType name="data-extension.type">
<xs:complexContent>
<xs:extension base="data-extension.type">
<xs:sequence>
<xs:element ref="svg:svg"/>
</xs:sequence>
</xs:extension>
</xs:complexContent>
</xs:complexType>
</xs:redefine>
</xs:schema>
Вышеприведенная схема похожа на схему в примере с добавлением атрибутов. Во первых присутсвуют объявления именного пространтсва. Во вторых, импортировано именное пространство SVG. Наконец расширен комплексный тип data-extension.type , который является базовым для описания содержимого элемента data , путем добавления элемента svg из именного пространства SVG.
В файле svg.graphml приведен документ, соответствующий схеме graphml+svg.xsd:
GraphML - документ с данными типа SVG
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"
xmlns:svg="http://www.w3.org/2000/svg"
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns
graphml+svg.xsd">
<key id="k0" for="node">
<default>
<svg:svg width="5cm" height="4cm" version="1.1">
<svg:desc>Default graphical representation for nodes
</svg:desc>
<svg:rect x="0.5cm" y="0.5cm" width="2cm" height="1cm"/>
</svg:svg>
</default>
</key>
<key id="k1" for="edge">
<desc>Graphical representation for edges
</desc>
</key>
<graph edgedefault="directed">
<node id="n0">
<data key="k0">
<svg:svg width="4cm" height="8cm" version="1.1">
<svg:ellipse cx="2cm" cy="4cm" rx="2cm" ry="1cm" />
</svg:svg>
</data>
</node>
<node id="n1" />
<edge source="n0" target="n1">
<data key="k1">
<svg:svg width="12cm" height="4cm" viewBox="0 0 1200 400">
<svg:line x1="100" y1="300" x2="300" y2="100"
stroke-width="5" />
</svg:svg>
</data>
</edge>
</graph>
</graphml>
Заметим, что узел с идентификатором n1 допускает графическое изображение по умолчанию, заданное элементом key с идентификатором k0 . Вышеприведенный пример также демонстрирует использование именных пространств XML: задано два различных элемента desc - один в именном пространстве GraphML, а второй в именном пространстве SVG . Возможный конфликт, связанный с одинаковыми именами элементов в различных XML-языках, разрешен с помощью использования различных именных пространств.
|