Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

Миграция в облако #SotelCloud. Виртуальный сервер в облаке. Выбрать конфигурацию на сайте!

Виртуальная АТС для вашего бизнеса. Приветственные бонусы для новых клиентов!

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

VPS/VDS серверы. 30 локаций на выбор

Серверы VPS/VDS с большим диском

Хорошие условия для реселлеров

4VPS.SU - VPS в 17-ти странах

2Gbit/s безлимит

Современное железо!

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 ребер.

Простой граф

Image of example graph
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-схему
<?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-атрибутов

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

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

Image of colored example graph

Мы будем использовать 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. Дополнительные понятия I: вложенные графы, гиперребра и порты

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

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

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

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

Вложенный граф.

Image of a nested graph.

В файле 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.

Граф с гиперребрами.

Image of a graph with hyperedges

Файл 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-языках, разрешен с помощью использования различных именных пространств.

Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

✅ Дешевый VPS-хостинг на AMD EPYC: 1vCore, 3GB DDR4, 15GB NVMe всего за €3,50!

🔥 Anti-DDoS защита 12 Тбит/с!

VPS в России, Европе и США

Бесплатная поддержка и администрирование

Оплата российскими и международными картами

🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях

💸 Гифткод CITFORUM (250р на баланс) и попробуйте уже сейчас!

🛒 Скидка 15% на первый платеж (в течение 24ч)

Новости мира IT:

Архив новостей

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 7861149
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2019 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...