GraphML - язык описания графов

2007 г.

GraphML - язык описания графов

По материалам сайта http://graphml.graphdrawing.org/
Перевод: Шокоров В. П.

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

Проект GraphML имеет целью создание стандартизованного языка описания графов являющегося подмножеством языка XML. Данный документ представляет собой перевод материалов сайта http://graphml.graphdrawing.org/ , содержащего информацию о проекте GraphML на русский язык, и объединяет в одном файле материалы из нескольких разделов указанного выше сайта. При этом нормативными документами считаются оригинальные тексты на английском языке, которые можно найти в соответствующих разделах сайта http://graphml.graphdrawing.org/. Представленный документ может содержать ошибки перевода. Перевод выполнил Шокоров В. П. (http://PenzaVld.narod.ru).

Аннотация

Проект GraphML был начат комитетом "Graph Drawing Steering Committee" до начала симпозиума Graph Drawing 2000 в Вильямсбурге. Рабочая встреча относительно формата файла была проведена накануне симпозиума, и на ней было согласовано создание группы, которая определила новый, основанный на языке XML, формат файла, который должен в конечном счете лечь в основу стандарта описания графов.

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

Один из главных предшественников GraphML - GML. GML появился в результате работы, начатой на Graph Drawing 1995 в Пассау и завершенной на Graph Drawing 1996 в Беркли. GML был (и все еще остается) основным файловым форматом для Graphlet, а также поддерживается рядом других систем обработки графов.

Рабочая группа

GraphML создается многими людьми, находящимися в различных местах. Наравне с другими текущую работу координируют: Ulrik Brandes (University of Konstanz); Markus Eiglsperger; Michael Kaufmann (University of Tübingen); Jürgen Lerner (University of Konstanz); Christian Pich (University of Konstanz).

В консультативную группу входят: Ivan Herman (CWI); Stephen North (AT&T Research); Roberto Tamassia (Brown University).

На этапе формирования структуры активно работали, или были подписаны на полуоткрытый список обсуждения GraphML: Michael Himsolt (DaimlerChrysler); M. Scott Marshall (then CWI); Vladimir Batagelj (University of Ljubljana); Anne-Lise Gros (LIRMM); Carsten Gutwenger (Caesar); David Jensen (University of Massachusetts); Serban Jora (AT&T Research); Sascha Meinert (University of Tübingen); Guy Melancon (LIRMM); Petra Mutzel (Technical University of Vienna); Maurizio Patrignani (University of Rome III); Tim Pattison (DSTO); Matthew Phillips (DSTO); John Punin (Rensselaer Polytechnic Institute); Susan Sim (University of Toronto); Adrian Vasiliu (Ilog); Vance Waddle (IBM Research); Andreas Winter (University of Koblenz).

О сайте GraphML

Сайт GraphML перепроектирован и перезапущен 22 июня 2002 года. С этого времени страницы генерируются с помощью Apache Software Foundation's XML publishing framework Cocoon. Мы благодарим Джона Риттера (университет Konstanz) за эту работу.

Введение

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

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

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

С чего начать

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

1.Спецификация

1.1. Общие сведения

Спецификация языка GraphML определяет его синтаксис, правила правила обработки базового языка (структурный уровень) и двух его расширений, связанных с описанием атрибутов базовых типов и описанием информации для синтаксического анализа. Хотя достаточно подробное введение в описание языка можно найти здесь, дополнительную информацию, связанную с GraphML можно найти по адресу: U. Brandes, M. Eiglsperger, I. Herman, M. Himsolt, and M.S. Marshall: GraphML Progress Report: Structural Layer Proposal. Proc. 9th Intl. Symp. Graph Drawing (GD '01), LNCS 2265, pp. 501-512. © Springer-Verlag, 2002.

1.2. Синтаксис

Синтаксис GraphML определяется GraphML-схемой. Не смотря на то, что схема является более информативным документом, также обеспечено менее строгое описание синтаксиса с помощью Document Type Definition (DTD), в котором, например, не описаны ссылочные типы вроде идентификаторов ребер и узлов графа. Однако, для нормальной работы некоторых приложений, возможно, требуется DTD.

1.3.GraphML-схема

GraphML-схема представлена следующими файлами:

graphml.xsd (включает содержимое всех трех, перечисленных ниже, файлов);
graphml-structure.xsd - описание базового синтаксиса языка;
graphml-attributes.xsd - расширение синтаксиса языка в части описания атрибутов базовых типов;
graphml-parseinfo.xsd - расширение синтаксиса языка в части описания информации для синтаксического анализа.

1.4. GraphML-DTD

Описание синтаксиса GraphML с помощью DTD представлено в файле graphml.dtd.

1.5.Правила обработки

Элементы, которые приложение не может обработать, игнорируются. То есть GraphML-документ интерпретируется так, как будто он состоит только из тех элементов, которые известны и понятны приложению. В частности:

элементы <port>, <hyperedge>, <endpoint>, и <locator> просто игнорируются приложениями, не обеспечивающими их обработку. Синтаксический анализатор может выдать предупреждение о том, что обнаружен неизвестный ему элемент;
для приложения, способного работать только с одним графом в документе, нет никаких рекомендаций на счет того, как обрабатывать документ, содержащий несколько графов. Поэтому такое приложение может выбрать: или работать только с первым графом, или обрабатывать все графы, или применить другой способ обработки документа. В любом случае, приложение должно сформировать предупреждение и проинформировать пользователя;
для приложения неспособного работать с вложенными графами нет никаких рекомендаций на счет того, как такое приложение должно обрабатывать вложенные графы. Например, приложение может выбрать: или игнорировать всю информацию о вложенных графах, или поднять вложенные графы на верхний уровень, или использовать другой способ обработки документа. В любом случае, приложение должно сформировать предупреждение и проинформировать пользователя.

1.6. Дополнительные данные

GraphML обеспечивают механизм добавление данных к структурным элементам (например, таким как <graph>, <node>, <edge>, и т.д.). Такой механизм реализуется с помощью типизированных данных, которые могут использоваться для определения данных заданного типа внутри структурных элементов. Тип данных задается элементом <key>. Область определения типа (домен) задается с помощью атрибута 'for' элемента <key>. Значения данных задаются с помощью элемента <default> (потомок элемента <key>) и/или элементов <data> (потомки элементов, которые находятся в домене типа), у которых значение атрибута 'key' равно значению атрибута 'id' элемента <key>.

1.6.1. Типизация данных

Расширение базового языка для описания атрибутов базовых типов позволяет специфицировать диапазон значений вышеупомянутых типов данных. Это делает с помощью дополнительного атрибута 'attr.type' элемента <key>. Атрибут 'attr.type' (может принимать значения: 'boolean', 'int', 'long', 'float', 'double', 'string') определяет, как интерпретировать символьную строку в элементах <data> и <default>.

С помощью атрибута 'attr.name' элемента <key> тип данных может быть поименован.

1.6.2. Информация для синтаксических анализаторов

Расширение базового языка в части описания информации для синтаксического анализа добавляет несколько дополнительных атрибутов к элементам <graph> и <node>, которые помогают анализаторам более эффективно обрабатывать документ. Эти атрибуты, например, определяют число узлов или ребер, степень узлов, максимальную/минимальную степень и т.д.

1.6.3. Пользовательские расширения

GraphML может быть расширен двумя способами:

пользователи могут включить структурированные элементы в элементы <data> и <default>;
пользователи могут добавить атрибуты ко всем элементам GraphML

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

1.7. Описание элементов

Описание элементов дается в соответствии с GraphML-схемой.

<desc>

Назначение: позволяет включать в элементы текст комментария. Элемент для которого предназначены комментарии должен включать элемент <desc> в качестве первого потомка.

Область применения: <key>, <graphml>, <graph>, <node>, <port>, <edge>, <hyperedge>,<endpoint>.

Тип - xs:string.

<locator >

Назначение: графы и узлы объявляются с помощью элементов <graph> и <node>, соответственно. Необязательный элемент <locator> который может быть потомком этих элементов указывает на их определение. Если элемент-потомок <locator> не задан, то графы и узлы определяются содержимым элементов <graph> и <node>.

Область применения: <graph>,<node>.

Тип: locator.type - комплексный тип, содержащий описание элемента <locator>. Допустимое содержание - пусто. Определение типа конечно.

Атрибуты:

xlink:href - (обязателен) указатель на ресурс;
xlink:type - (необязателен) тип ссылки (может принимать фиксированное значение 'simple');
locator.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов .

<data>

Область применения: <graphml>, <graph>, <node>, <port>, <edge>, <hyperedge>, <endpoint>.

Тип: data.type - комплексный тип, содержащий описание элемента <data>. Тип data.type - смешанный, поэтому элемент <data> может содержать данные типа #PCDATA. Допустимое содержание - расширения типа data-extension.type, которое по умолчанию задает пустое значение. Определение типа конечно.

Атрибуты:

key - (обязателен) задает ссылку на атрибут 'id' элемента <key>, и тем самым идентифицирует тип объявленных данных. Тип содержимого - xs:NMTOKEN;
id - (необязателен) содержит идентификатор данного элемента <data>. Тип содержимого - xs:NMTOKEN;
data.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.

Ограничения целостности: data_data_key_unique. Это ограничение гарантирует уникальность атрибутов 'key' у элементов <data>, являющихся потомками данного элемента <data>.

<key>

Область применения: <graphml>.

Тип: key.type - комплексный тип, содержащий описание элемента <key>. Определение типа конечно.

Атрибуты:

id - (обязателен) содержит идентификатор данного элемента <key>. Тип содержимого - xs:NMTOKEN . Ограничение уникальности идентификатора - key_id_key;
for - (необязателен) задает область применения (домен) данного типа данных. Тип содержимого - key.for.type. Атрибут может принимать одно из следующих значений:'all' - данные этого типа могут быть определены во всех структурных элементах; 'graph'; 'node'; 'edge'; 'hyperedge'; 'port'; 'endpoint' - данные этого типа могут быть определены в элементах <graph>, <node>, <edge>, <hyperedge>, <port>, <endpoint>, соответственно;
key.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, <default>?

<default>

Назначение: в GraphML возможно определение данных привязанных к графам, узлам, портам, ребрам, гиперребрам, конечной точке, а также ко всей совокупности графов, описанных в <graphml>. Объявление типов данных производится с помощью элементов <key> (потомки <graphml>), а определение данных с помощью элементов <data>. Необязательный элемент <default>, являющийся потомком элемента <key>, задает значение по умолчанию для типа данных объявленного с помощью данного элемента <key>.

Область применения: <key>.

Тип: default.type - комплексный тип, содержащий описание элемента <default>. Тип default.type - смешанный, поэтому он может содержать данные типа #PCDATA. Допустимое содержание - расширения типа data-extension.type, которое по умолчанию задает пустое значение. Определение типа конечно.

Атрибуты: default.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.

<graphml>

Назначение: <graphml> - корневой элемент документа.

Область применения: root.

Тип: graphml.type - комплексный тип, содержащий описание элемента <graphml>. Определение типа конечно.

Атрибуты: graphml.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, <key>*, ( <graph> | <data> ) *

Ограничения целостности:

graphml_data_key_unique. Это ограничение гарантирует уникальность атрибутов 'key' у элементов <data>, являющихся потомками <graphml>.
graph_id_unique. Это ограничение гарантирует уникальность идентификаторов (атрибутов 'id') у всех графов (<graph>) данного документа;
key_id_key. Это ограничение гарантирует уникальность всех идентификаторов типов (атрибут 'id') у всех элементов объявления типа данных (<key>) данного документа;
data_key_ref - ссылка на key_id_key. Это ограничение на атрибут 'key' для каждого элемента <data> обеспечивает гарантию того, что он ссылается на существующий в данном документе элемент <key>, у которого задано соответсвующее значение атрибута 'id'. Это ограничение обеспечивает связь переменной с ее типом.

<graph>

Назначение: элемент описывает граф (подграф).

Область применения: <graphml>, <node>, <edge>, <hyperedge>.

Тип: graph.type - комплексный тип, содержащий описание элемента <graph>. Определение типа конечно.

Атрибуты:

id - (необязателен) содержит идентификатор графа. Тип содержимого - xs:NMTOKEN. Ограничение уникальности идентификатора - graph_id_unique;
edgedefault - (обязателен) задает по умолчанию направленность ребер графа: направленные ('directed') или ненаправленные ('undirected'). Тип содержимого - graph.extra.attrib.

Содержимое: <desc>?, ( ( <data> | <node> | <edge> | <hyperedge> ) * | <locator> )

Ограничения целостности:

graph_data_key_unique - обеспечивает уникальность атрибута 'key' элементов <data>, являющихся потомками данного элемента <graph>;
edge_id_unique - обеспечивает уникальность идентификаторов (атрибутов 'id') для каждого ребра (<edge>) в графе;
hyperedge_id_unique - обеспечивает уникальность идентификаторов (атрибутов 'id') для каждого гиперребра (<hyperedge>) в графе;
endpoint_id_unique - обеспечивает уникальность идентификаторов (атрибутов 'id') для каждой конечной точки (<endpoint>) в графе;
node_id_key - обеспечивает наличие и уникальность идентификаторов (атрибутов 'id') для каждого узла (<node>) графа;
edge_source_ref - ссылка на node_id_key - для атрибута 'source' элемента <edge> гарантируется значение, заданное в одном из атрибутов 'id' элемента <node>. Тем самым задается исходящий узел ребра;
edge_target_ref ссылка на node_id_key - для атрибута 'target' элемента <edge> гарантируется значение, заданное в одном из атрибутов 'id' элемента <node>. Тем самым задается целевой узел ребра;
endpoint_node_ref ссылка на node_id_key - для атрибута 'node' элемента <endpoint> гарантируется значение, заданное в одном из атрибутов 'id' элемента <node>. Тем самым задается привязка узла к гиперребру.

<node>

Назначение: элемент описывает узел (<node>) в графе (<graph>).

Область применения: <graph>.

Тип: node.type - комплексный тип, содержащий описание элемента <node>. Описание типа конечно.

Атрибуты:

id - (обязательный) содержит идентификатор узла. Тип содержимого - xs:NMTOKEN. Ограничение уникальности идентификатора - node_id_key;
node.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, ( ( <data> | <port> ) *, <graph>? | <locator> )

Ограничения целостности:

node_data_key_unique - обеспечивает уникальность атрибутов 'key' элементов <data>, являющихся потомками данного элемента <node>;
port_name_key - обеспечивает существование и уникальность атрибутов 'name' у каждого элемента <port> в данном элементе <node>.

<port>

Назначение: элемент описывает порт в данном узле. Узлы могут быть структурированы с помощью портов. Таким образом ребра могут быть связаны не только с некоторым узлом графа, но и с некоторым портом в данном узле.

Область применения: <node>, <port>.

Тип: port.type - комплексный тип, содержащий описание элемента <port>. Описание типа конечно.

Атрибуты:

name - (обязательный) идентифицирует порт внутри данного узла. Тип содержимого - xs:NMTOKEN. Ограничение уникальности - port_name_key;
port.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, ( <data> | <port> ) *

Ограничения целостности: port_data_key_unique - обеспечивает уникальность атрибутов 'key' элементов <data>, являющихся потомками данного элемента <port>.

<edge>

Назначение: элемент описывает одно ребро в графе <graph>.

Область применения: <graph>.

Тип: edge.type - комплексный тип, содержащий описание элемента <edge>. Описание типа конечно.

Атрибуты:

id - (необязателен) задает идентификатор ребра. Тип содержимого - xs:NMTOKEN. Ограничение уникальности - edge_id_unique;
directed - (необязателен) задает направленность ребра. Тип содержимого - xs:boolean. Атрибут переопределяет значение, заданное по умолчанию атрибутом 'edgedefault' элемента <graph>;
source - (обязателен) задает идентификатор ('id') исходящего узла (<node>) данного ребра. Тип содержимого - xs:NMTOKEN. Ограничение целостности - edge_source_ref;
target - (обязателен) задает идентификатор ('id') входящего узла (<node>) данного ребра. Тип содержимого - xs:NMTOKEN. Ограничение целостности - edge_target_ref ;
sourceport - (необязателен) задает имя ('name') исходящего порта (<port>). Тип содержимого - xs:NMTOKEN;
targetport - (необязательный) задает имя ('name') входящего порта (<port>). Тип содержимого - xs:NMTOKEN;
edge.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, <data>*, <graph>?

Ограничения целостности: edge_data_key_unique - обеспечивает уникальность атрибутов 'key' элементов <data>, являющихся потомками данного элемента <edge>.

<hyperedge>

Назначение: элемент описывает гиперребро. Аналогично тому, как ребро задает связь между двумя узлами, гиперребро задает связь между произвольным числом узлов.

Область применения: <graph>.

Тип: hyperedge.type - комплексный тип, содержащий описание элемента <hyperedge>. Описание типа конечно.

Атрибуты:

id - (обязателен) задает идентификатор данного гиперребра. Тип содержимого - xs:NMTOKEN. Ограничение уникальности - hyperedge_id_unique;
hyperedge.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, ( <data> | <endpoint> ) *, <graph>?

Ограничение целостности: hyperedge_data_key_unique - обеспечивает уникальность атрибутов 'key' элементов <data>, являющихся потомками данного элемента <hyperedge>.

<endpoint>

Назначение: элемент задает конечную точку, входящую в список конечных точек гиперребра. Каждая конечная точка <endpoint> определяет соответствующий ей узел <node>.

Область применения: <hyperedge>.

Тип: endpoint.type - комплексный тип, содержащий описание элемента <endpoint>. Описание типа конечно.

Атрибуты:

id - (обязателен) идентификатор данной конечной точки. Тип содержимого - xs:NMTOKEN. Ограничение уникальности -endpoint_id_unique;
port - (необязателен) имя порта с которым связана данная конечная точка. Тип содержимого - xs:NMTOKEN;
node - (обязателен) идентификатор узла, который соответствует данной конечной точке. Тип содержимого - xs:NMTOKEN. Ограничение целостности - endpoint_node_ref;
type - (необязателен) определяет направленность данной конечной точки. По умолчанию - ненаправленная (undirected);
endpoint.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?

1.8.Описание типов

Описание типов дается в соответствии с GraphML-схемой.

key.for.type

Простой тип, задающий допустимые значения атрибута 'for' элемента <key>. key.for.type является подмножеством типа xs:NMTOKEN. Допустимые значения: 'all', 'graph', 'node', 'edge', 'hyperedge', 'port' и 'endpoint'.

graph.edgedefault.type

Простой тип, задающий допустимые значения атрибута 'edgedefault' элемента <graph>. graph.edgedefault.type является подмножеством типа xs:NMTOKEN. Допустимые значения: 'directed', 'undirected'.

endpoint.type.type

Простой тип, задающий допустимые значения атрибута 'type' элемента <endpoint>. endpoint.type.type является подмножеством типа xs:NMTOKEN. Допустимые значения: 'in', 'out', 'undir'.

data-extension.type

Механизм расширения содержимого элементов <data> и <default>. По умолчанию комплексный тип data-extension.type пуст. Пользователи могут переопределить этот тип в соответствии с тем содержимым, которое требуется дополнительно определить в комплексных типах data.type и default.type, являющихся расширениями типа data-extension.type.

data.type

Комплексный тип, определяющий элемент <data>. data.type является смешанным типом, поэтому элемент <data> может содержать #PCDATA. Тип содержимого: расширение типа data-extension.type, который по умолчанию пуст. Описание типа конечно.

Атрибуты:

key - (обязателен) содержит ссылку на атрибут 'id' элемента <key>. Тип - xs:NMTOKEN .
id - (необязателен) задает идентификатор данного элемента <data>. Тип - xs:NMTOKEN.
data.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов .

default.type

Комплексный тип, определяющий элемент <default>. default.type является смешанным типом, поэтому элемент может содержать #PCDATA. Тип содержимого: расширение типа data-extension.type, который по умолчанию пуст. Описание типа конечно.

Атрибуты:

default.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов .

key.type

Комплексный тип, определяющий элемент <key>. Описание типа конечно.

Атрибуты:

id - (обязателен) задает идентификатор данного элемента <key>. Тип - xs:NMTOKEN. Описание ограничений целостности: key_id_key;
for - (необязателен) задает область применения (домен) данного типа данных. Тип - key.for.type.
key.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов .

Содержимое: <desc>?, <default>?

graphml.type

Комплексный тип, определяющий элемент <graphml>. Описание типа конечно.

Атрибуты: graphml.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, <key>*, ( <graph> | <data> ) *

graph.type

Комплексный тип, определяющий элемент <graph>. Описание типа конечно.

Атрибуты:

id (необязателен) задает идентификатор данного графа. Тип - xs:NMTOKEN. Описание ограничений целостности: graph_id_unique;
edgedefault (обязателен) задает, по умолчанию, тип ребер графа: направленные или ненаправленные. При определении ребра его тип может быть явно определен с помощью атрибута 'directed' элемента <edge>;
graph.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, ( ( <data> | <node> | <edge> | <hyperedge> ) * | <locator> )

node.type

Комплексный тип, определяющий элемент <node>. Описание типа конечно.

Атрибуты:

id (обязателен) задает идентификатор данного узла. Тип - xs:NMTOKEN. Описание ограничений целостности: node_id_key;
node.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, ( ( <data> | <port> ) *, <graph>? | <locator> )

port.type

Комплексный тип, определяющий элемент <port>. Описание типа конечно.

Атрибуты:

name (обязателен) идентифицирует данный порт внутри узла. Тип - xs:NMTOKEN. Описание ограничений целостности: port_name_key;
port.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, ( <data> | <port> ) *

edge.type

Комплексный тип, определяющий элемент <edge>. Описание типа конечно.

Атрибуты:

id (необязателен) задает идентификатор данного ребра. Тип - xs:NMTOKEN. Описание ограничений целостности: edge_id_unique;
directed (необязателен) переопределяет тип ребра, заданный по умолчанию с помощью атрибута 'edgedefault' элемента <graph>;
source (обязателен) содержит ссылку на идентификатор ('id') исходящего узла (<node>). Тип - xs:NMTOKEN. Описание ограничений целостности: edge_source_ref;
target (обязателен) содержит ссылку на идентификатор ('id') входящего узла (<node>). Тип - xs:NMTOKEN. Описание ограничений целостности: edge_target_ref;
sourceport (необязателен) содержит ссылку на имя ('name') исходящего порта (<port>). Тип - xs:NMTOKEN;
targetport (обязателен) содержит ссылку на имя ('name') входящего порта (<port>). Тип - xs:NMTOKEN;
edge.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, <data>*, <graph>?

hyperedge.type

Комплексный тип, определяющий элемент <hyperedge>. Описание типа конечно.

Атрибуты:

id (необязателен) задает идентификатор данного гиперребра. Тип - xs:NMTOKEN. Описание ограничений целостности: hyperedge_id_unique;
hyperedge.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?, ( <data> | <endpoint> ) *, <graph>?

endpoint.type

Комплексный тип, определяющий элемент <endpoint>. Описание типа конечно.

Атрибуты:

id (необязателен) задает идентификатор данной конечной точки. Тип - xs:NMTOKEN. Описание ограничений целостности: endpoint_id_unique;
port (необязателен) содержит ссылку на имя ('name') порта (<port>) с которым соединена данная конечная точка;
node (обязателен) содержит ссылку на идентификатор ('id') узла (<node>) с которым соединена данная конечная точка. Тип - xs:NMTOKEN. Описание ограничений целостности: endpoint_node_ref;
type (необязателен) определяет направленность данной конечной точки (по умолчанию - 'undirected').
endpoint.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.

Содержимое: <desc>?

locator.type

Комплексный тип, определяющий элемент <locator>. Тип содержимого: пусто. Описание типа конечно.

Атрибуты:

xlink:href (обязателен) ссылка на ресурс данного локатора.

xlink:type (необязателен) тип гиперссылки (может быть только типа 'simple').

locator.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.