Аннотация
Проект GraphML был начат комитетом "Graph Drawing Steering Committee" до начала симпозиума в Вильямсбурге. Рабочая была проведена накануне симпозиума, и на ней было согласовано создание группы, которая определила новый, основанный на языке XML, формат файла, который должен в конечном счете лечь в основу стандарта описания графов.
С тех пор, язык был расширен в части поддержки основных типов атрибутов и в части включения информации для использования синтаксическими анализаторами. Следующим важным шагом в расширении языка будет включение абстрактной информации для описания топологии графа и шаблонов с помощью которых эту информацию можно было бы преобразовать в различные графические форматы. Программное обеспечение для поддержки работы с GraphML находится в стадии разработки.
Один из главных предшественников GraphML - . GML появился в результате работы, начатой на в Пассау и завершенной на Graph Drawing 1996 в Беркли. GML был (и все еще остается) основным файловым форматом для , а также поддерживается рядом других систем обработки графов.
<Data>
Назначение: в GraphML возможно определение данных привязанных к графам, узлам, портам, ребрам, гиперребрам, конечной точке, а также ко всей совокупности графов, описанных в <graphml>. Объявление типов данных производится с помощью элементов <key>, являющихся потомками <graphml>, а определение данных с помощью элементов <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>.
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>
Назначение: в GraphML возможно определение данных привязанных к графам, узлам, портам, ребрам, гиперребрам, конечной точке, а также ко всей совокупности графов, описанных в <graphml>. Объявление типов данных производится с помощью элементов <key> (потомки <graphml>), а определение данных с помощью элементов <data>. Необязательный элемент <default>, являющийся потомком элемента <key>, задает значение по умолчанию для типа данных объявленного с помощью данного элемента <key>.
Область применения: <key>.
Тип: default.type - комплексный тип, содержащий описание элемента <default>. Тип default.type - смешанный, поэтому он может содержать данные типа #PCDATA. Допустимое содержание - расширения типа data-extension.type, которое по умолчанию задает пустое значение. Определение типа конечно.
Атрибуты: default.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.
Default.type
Комплексный тип, определяющий элемент <default>. default.type является смешанным типом, поэтому элемент может содержать #PCDATA. Тип содержимого: расширение типа data-extension.type, который по умолчанию пуст. Описание типа конечно.
Атрибуты:
default.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов .
<Desc>
Назначение: позволяет включать в элементы текст комментария. Элемент для которого предназначены комментарии должен включать элемент <desc> в качестве первого потомка.
Область применения: <key>, <graphml>, <graph>, <node>, <port>, <edge>, <hyperedge>,<endpoint>.
Тип - xs:string.
Добавление комплексных типов
Структурированное содержимое может быть добавлено с помощью элемента data. Например, пользователь может хранить для узлов их изображения в формате .
Элемент 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-схемы. Документ демонстрирует как элементы могут быть добавлены в содержимое 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.
В файле приведен документ, соответствующий схеме :
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-языках, разрешен с помощью использования различных именных пространств.
Добавление XML-атрибутов в GraphML-элементы
В большинстве случаев, дополнительная информация может (и должна) быть связана с GraphML-элементами с помощью , что гарантируется совместимостью GraphML-парсеров. Однако, в ряде случаев более удобно использовать XML-атрибуты. Предположим у вас имеется парсер, который умеет обрабатывать -атрибут href и корректно интерпретировать его как URL. Предположим вы хотите хранить в GraphML граф, узлы которого представляют собой WWW-страницы. Для ассоциации узла со страницей его модель должна позволять вам в теге node присваивать атрибуту xlink:href URL-ссылку на соответсвующую страницу:
Элемент node, содержащий URL-ссылку
... <node id="n0" xlink:href="http://graphml.graphdrawing.org"/> ...
Для добавления XML-атрибутов в GraphML-элементы используется механизм расширение GraphML. Это расширение должно быть определено в XML-схеме. В документе показан атрибут 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>
Приведенный выше документ имеет следующие функциональные составляющие: в качестве корневого элемента документ имеет элемент 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-элементов.
В документе приведен пример документа который соответствует схеме .
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>
Дополнительные данные
GraphML обеспечивают механизм добавление данных к структурным элементам (например, таким как <graph>, <node>, <edge>, и т.д.). Такой механизм реализуется с помощью типизированных данных, которые могут использоваться для определения данных заданного типа внутри структурных элементов. Тип данных задается элементом <key>. Область определения типа (домен) задается с помощью атрибута 'for' элемента <key>. Значения данных задаются с помощью элемента <default> (потомок элемента <key>) и/или элементов <data> (потомки элементов, которые находятся в домене типа), у которых значение атрибута 'key' равно значению атрибута 'id' элемента <key>.
Дополнительные понятия I: вложенные графы, гиперребра и порты
Для некоторых приложений модель графа, описанная в предыдущем разделе слишком ограничена и не моделирует адекватно данные прикладной программы.
В данном разделе мы рассмотрим расширенную модель, которая позволяет описать вложенную иерархию графов, гиперребра и порты.
Дополнительные понятия II: расширение GraphML
Язык GraphML может быть легко расширен. В GraphML легко описывать топологию графа с помощью элементов имеющих простые атрибуты. Для хранения комплексных данных GraphML может быть расширен. В данном разделе мы рассмотрим различные возможности расширения GraphML.
Расширения GraphML должны быть заданы в XML-схеме. Схема, в которой определены расширения, может быть порождена из схемы GraphML-документа с помощью стандартного механизма похожего на механизм, применяемый в XHTML.
<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 - ссылка на описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, *, ?
Ограничения целостности: edge_data_key_unique - обеспечивает уникальность атрибутов 'key' элементов <data>, являющихся потомками данного элемента <edge>.
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 - описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, *, ?
<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 - ссылка на описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?
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 - описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?
Endpoint.type.type
Простой тип, задающий допустимые значения атрибута 'type' элемента <endpoint>. endpoint.type.type является подмножеством типа xs:NMTOKEN. Допустимые значения: 'in', 'out', 'undir'.
Гиперребра
Гиперребра это смысловое объединение ребер которое не не только связывает две конечные точки, но и выражает зависимость между произвольным числом конечных точек (например, описание кратчайшего пути - примечание переводчика). Гиперребра объявляются с помощью элемента hyperedge. Каждой конечной точке входящей в данное гиперребро соответствует элемент endpoint. Элемент endpoint должен иметь XML-атрибут node, который содержит идентификатор узла в документе. Следующий пример содержит гиперребра и два ребра. Гиперребра изображены в виде дуг, а ребра в виде прямых линий. Заметим, что ребра задаются с помощью элемента edge или с помощью элемента hyperedge содержащего два элемента endpoint.
Граф с гиперребрами.
Файл содержит соответствующий 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, который является уникальным идентификатором для соответствующих элементов.
<Graph>
Назначение: элемент описывает граф (подграф).
Область применения: <graphml>, <node>, <edge>, <hyperedge>.
Тип: graph.type - комплексный тип, содержащий описание элемента <graph>. Определение типа конечно.
Атрибуты:
id - (необязателен) содержит идентификатор графа. Тип содержимого - xs:NMTOKEN. Ограничение уникальности идентификатора - graph_id_unique;
edgedefault - (обязателен) задает по умолчанию направленность ребер графа: направленные ('directed') или ненаправленные ('undirected'). Тип содержимого - graph.extra.attrib.
Содержимое: ?, ( ( | | | ) * | )
Ограничения целостности:
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>. Тем самым задается привязка узла к гиперребру.
XML - статьи
Простой тип, задающий допустимые значения атрибута 'edgedefault' элемента <graph>. graph.edgedefault.type является подмножеством типа xs:NMTOKEN. Допустимые значения: 'directed', 'undirected'.
XML - статьи
Комплексный тип, определяющий элемент <graph>. Описание типа конечно.
Атрибуты:
id (необязателен) задает идентификатор данного графа. Тип - xs:NMTOKEN. Описание ограничений целостности: graph_id_unique;
edgedefault (обязателен) задает, по умолчанию, тип ребер графа: направленные или ненаправленные. При определении ребра его тип может быть явно определен с помощью атрибута 'directed' элемента <edge>;
graph.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, ( ( | | | ) * | )
<Graphml>
Назначение: <graphml> - корневой элемент документа.
Область применения: root.
Тип: graphml.type - комплексный тип, содержащий описание элемента <graphml>. Определение типа конечно.
Атрибуты: graphml.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, *, ( | ) *
Ограничения целостности:
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'. Это ограничение обеспечивает связь переменной с ее типом.
XML - статьи
В предыдущем разделе мы обсудили порядок описания топологии графа на языке GraphML. Поскольку для различных приложений может потребоваться различная информация о топологии графа, необходимо иметь механизм для включения такой информации в описание графа.
С помощью механизма расширения, который называется GraphML-атрибуты для элементов графа может быть задана дополнительная информация простого типа. Простой тип подразумевает, что данные ограничены скалярными величинами. Например, числами и строками.
Если в элементы графа вам необходимо добавить структурированные данные, то вы должны использовать механизм расширения GraphM L под названием ключ/данные (data/key). Более подробно этот механизм рассмотрен в . GraphML-атрибуты специализированное расширение механизма ключ/данные (data/key).
GraphML-атрибуты не следует путать с XML-атрибутами, это разные понятия.
XML - статьи
Описание синтаксиса GraphML с помощью DTD представлено в файле .
XML - статьи
GraphML-схема представлена следующими файлами:
(включает содержимое всех трех, перечисленных ниже, файлов);
- описание базового синтаксиса языка;
- расширение синтаксиса языка в части описания атрибутов базовых типов;
- расширение синтаксиса языка в части описания информации для синтаксического анализа.
XML - статьи
Комплексный тип, определяющий элемент <graphml>. Описание типа конечно.
Атрибуты: graphml.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, *, ( | ) *
<Hyperedge>
Назначение: элемент описывает гиперребро. Аналогично тому, как ребро задает связь между двумя узлами, гиперребро задает связь между произвольным числом узлов.
Область применения: <graph>.
Тип: hyperedge.type - комплексный тип, содержащий описание элемента <hyperedge>. Описание типа конечно.
Атрибуты:
id - (обязателен) задает идентификатор данного гиперребра. Тип содержимого - xs:NMTOKEN. Ограничение уникальности - hyperedge_id_unique;
hyperedge.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, ( | ) *, ?
Ограничение целостности: hyperedge_data_key_unique - обеспечивает уникальность атрибутов 'key' элементов <data>, являющихся потомками данного элемента <hyperedge>.
Hyperedge.type
Комплексный тип, определяющий элемент <hyperedge>. Описание типа конечно.
Атрибуты:
id (необязателен) задает идентификатор данного гиперребра. Тип - xs:NMTOKEN. Описание ограничений целостности: hyperedge_id_unique;
hyperedge.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, ( | ) *, ?
Информация для парсера
Для оптимизации синтаксического разбора документа с помощью парсера используются специальные метаданные, которые могут быть добавлены к некоторым 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>
Информация для синтаксических анализаторов
Расширение базового языка в части описания информации для синтаксического анализа добавляет несколько дополнительных атрибутов к элементам <graph> и <node>, которые помогают анализаторам более эффективно обрабатывать документ. Эти атрибуты, например, определяют число узлов или ребер, степень узлов, максимальную/минимальную степень и т.д.
<Key>
Назначение: в GraphML возможно определение данных привязанных к графам, узлам, портам, ребрам, гиперребрам, конечной точке, а также ко всей совокупности графов, описанных в <graphml>. Объявление типов данных производится с помощью элементов <key> (потомки <graphml>), а определение данных с помощью элементов <data>.
Область применения: <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 - ссылка на описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, ?
Key.for.type
Простой тип, задающий допустимые значения атрибута 'for' элемента <key>. key.for.type является подмножеством типа xs:NMTOKEN. Допустимые значения: 'all', 'graph', 'node', 'edge', 'hyperedge', 'port' и 'endpoint'.
Key.type
Комплексный тип, определяющий элемент <key>. Описание типа конечно.
Атрибуты:
id - (обязателен) задает идентификатор данного элемента <key>. Тип - xs:NMTOKEN. Описание ограничений целостности: key_id_key;
for - (необязателен) задает область применения (домен) данного типа данных. Тип - key.for.type.
key.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов .
Содержимое: ?, ?
<Locator >
Назначение: графы и узлы объявляются с помощью элементов <graph> и <node>, соответственно. Необязательный элемент <locator> который может быть потомком этих элементов указывает на их определение. Если элемент-потомок <locator> не задан, то графы и узлы определяются содержимым элементов <graph> и <node>.
Область применения: <graph>,<node>.
Тип: locator.type - комплексный тип, содержащий описание элемента <locator>. Допустимое содержание - пусто. Определение типа конечно.
Атрибуты:
xlink:href - (обязателен) указатель на ресурс;
xlink:type - (необязателен) тип ссылки (может принимать фиксированное значение 'simple');
locator.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов .
Locator.type
Комплексный тип, определяющий элемент <locator>. Тип содержимого: пусто. Описание типа конечно.
Атрибуты:
xlink:href (обязателен) ссылка на ресурс данного локатора.
xlink:type (необязателен) тип гиперссылки (может быть только типа 'simple').
locator.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.
<Node>
Назначение: элемент описывает узел (<node>) в графе (<graph>).
Область применения: <graph>.
Тип: node.type - комплексный тип, содержащий описание элемента <node>. Описание типа конечно.
Атрибуты:
id - (обязательный) содержит идентификатор узла. Тип содержимого - xs:NMTOKEN. Ограничение уникальности идентификатора - node_id_key;
node.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, ( ( | ) *, ? | )
Ограничения целостности:
node_data_key_unique - обеспечивает уникальность атрибутов 'key' элементов <data>, являющихся потомками данного элемента <node>;
port_name_key - обеспечивает существование и уникальность атрибутов 'name' у каждого элемента <port> в данном элементе <node>.
Node.type
Комплексный тип, определяющий элемент <node>. Описание типа конечно.
Атрибуты:
id (обязателен) задает идентификатор данного узла. Тип - xs:NMTOKEN. Описание ограничений целостности: node_id_key;
node.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, ( ( | ) *, ? | )
О сайте GraphML
Сайт GraphML перепроектирован и перезапущен 22 июня 2002 года. С этого времени страницы генерируются с помощью XML publishing framework . Мы благодарим Джона Риттера (университет Konstanz) за эту работу.
Объявление графа
Граф в GraphML - смешанный, другими словами он может содержать направленные и ненаправленные ребра одновременно. Если при объявлении ребра его направленность не определена, то применяется направленность заданная по умолчанию. Направленность ребер, присваиваемая по умолчанию, задается XML-атрибутом edgedefault элемента graph. Этот XML-атрибут может принимать одно из двух значений: directed и undirected. Значение по умолчанию должно быть задано обязательно.
Дополнительно, с помощью атрибута id, графу может быть присвоен идентификатор. Идентификатор присваивают тогда, когда на данный граф требуется организовать ссылку.
Объявление 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> ...
Объявление ребра
Ребро в графе объявляется с помощью элемента 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"/> ...
Объявление узла
Уз е л в графе объявляется с помощью элемента node. Каждый узел имеет уникальный (в пределах данного документа) идентификатор. Идентификатор узла задается с помощью XML-атрибута id.
Общие сведения
Спецификация языка GraphML определяет его синтаксис, правила правила обработки базового языка (структурный уровень) и двух его расширений, связанных с описанием атрибутов базовых типов и описанием информации для синтаксического анализа. Хотя достаточно подробное введение в описание языка можно найти , дополнительную информацию, связанную с GraphML можно найти по адресу: U. Brandes, M. Eiglsperger, I. Herman, M. Himsolt, and M.S. Marshall: . Proc. 9th Intl. Symp. Graph Drawing (GD '01), LNCS 2265, pp. 501-512. © Springer-Verlag, 2002.
1 2
2.1 2.2 2.3
2.3.1 2.3.2 2.3.3
2.4
2.4.1 2.4.2 2.4.4
2.5
3
3.1 3.2 3.3
4
4.1 4.2
Определение значений 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.
Основные понятия
Назначение GraphML-документа - определение графа. Для начала рассмотрим граф показанный на приведенном ниже рисунке. Он содержит 11 узлов и 12 ребер.
Простой граф
Пользовательские расширения
GraphML может быть расширен двумя способами:
пользователи могут включить структурированные элементы в элементы <data> и <default>;
пользователи могут добавить атрибуты ко всем элементам GraphML
Как это можно сделать, будет разъяснено в более подробном описании, которое в настоящее время готовится.
<Port>
Назначение: элемент описывает порт в данном узле. Узлы могут быть структурированы с помощью портов. Таким образом ребра могут быть связаны не только с некоторым узлом графа, но и с некоторым портом в данном узле.
Область применения: <node>, <port>.
Тип: port.type - комплексный тип, содержащий описание элемента <port>. Описание типа конечно.
Атрибуты:
name - (обязательный) идентифицирует порт внутри данного узла. Тип содержимого - xs:NMTOKEN. Ограничение уникальности - port_name_key;
port.extra.attrib - ссылка на описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, ( | ) *
Ограничения целостности: port_data_key_unique - обеспечивает уникальность атрибутов 'key' элементов <data>, являющихся потомками данного элемента <port>.
Port.type
Комплексный тип, определяющий элемент <port>. Описание типа конечно.
Атрибуты:
name (обязателен) идентифицирует данный порт внутри узла. Тип - xs:NMTOKEN. Описание ограничений целостности: port_name_key;
port.extra.attrib - описание дополнительных, определяемых пользователем, атрибутов.
Содержимое: ?, ( | ) *
Порты
Узлы могут содержать различные логические точки подключения ребер и гиперребер. Такие точки подключения называются портами.
Порты узла объявляются с помощью элементов port, которые являются дочерними по отношению к соответствующему элементу node. Обратите внимание, что порты могут быть вложенными, т.е., они могут содержать внутри себя другие элементы port. Каждый элемент port должен иметь XML-атрибут name, который идентифицирует этот порт. Элемент edge имеет необязательные XML-атрибуты sourceport и targetport которые задают для ребра исходящий и входящий порты узла, соответственно. Аналогично элемент endpoint имеет необязательный XML-атрибут port.
Документ - пример документа с портами:
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>
Правила обработки
Элементы, которые приложение не может обработать, игнорируются. То есть GraphML-документ интерпретируется так, как будто он состоит только из тех элементов, которые известны и понятны приложению. В частности:
элементы <port>, <hyperedge>, <endpoint>, и <locator> просто игнорируются приложениями, не обеспечивающими их обработку. Синтаксический анализатор может выдать предупреждение о том, что обнаружен неизвестный ему элемент;
для приложения, способного работать только с одним графом в документе, нет никаких рекомендаций на счет того, как обрабатывать документ, содержащий несколько графов. Поэтому такое приложение может выбрать: или работать только с первым графом, или обрабатывать все графы, или применить другой способ обработки документа. В любом случае, приложение должно сформировать предупреждение и проинформировать пользователя;
для приложения неспособного работать с вложенными графами нет никаких рекомендаций на счет того, как такое приложение должно обрабатывать вложенные графы. Например, приложение может выбрать: или игнорировать всю информацию о вложенных графах, или поднять вложенные графы на верхний уровень, или использовать другой способ обработки документа. В любом случае, приложение должно сформировать предупреждение и проинформировать пользователя.
Проект GraphML имеет целью создание
Проект GraphML имеет целью создание стандартизованного языка описания графов являющегося подмножеством языка XML. Данный документ представляет собой перевод материалов сайта , содержащего информацию о проекте GraphML на русский язык, и объединяет в одном файле материалы из нескольких разделов указанного выше сайта. При этом нормативными документами считаются оригинальные тексты на английском языке, которые можно найти в соответствующих разделах сайта . Представленный документ может содержать ошибки перевода. Перевод выполнил Шокоров В. П. ().
Данный документ представляет собой перевод документа “ GraphML Primer ” на русский язык. При этом нормативным документом считается оригинальный текст на английском языке, который можно найти по адресу . Представленный документ может содержать ошибки перевода. Перевод выполнил Шокоров В. П. ().
Пример GraphML-атрибутов
В качестве примера в данном разделе рассматривается граф с раскрашенными узлами и оцифрованными ребрами.
Граф с раскрашенными узлами и оцифрованными ребрами.
Мы будем использовать 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>
Простой граф
Простой граф описан в файле
Простой граф
<?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. В конце раздела рассмотрим перечисленные элементы подробнее , и покажем, как они определяют граф.
Рабочая группа
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. Нормативное описание языка содержится в нижеприведённой спецификации GraphML.
Не смотря на то, что
Синтаксис GraphML определяется GraphML-схемой. Не смотря на то, что схема является более информативным документом, также обеспечено менее строгое описание синтаксиса с помощью Document Type Definition (DTD), в котором, например, не описаны ссылочные типы вроде идентификаторов ребер и узлов графа. Однако, для нормальной работы некоторых приложений, возможно, требуется DTD.
Типизация данных
позволяет специфицировать диапазон значений вышеупомянутых типов данных. Это делает с помощью дополнительного атрибута 'attr.type' элемента <key>. Атрибут 'attr.type' (может принимать значения: 'boolean', 'int', 'long', 'float', 'double', 'string') определяет, как интерпретировать символьную строку в элементах <data> и <default>.
С помощью атрибута 'attr.name' элемента <key> тип данных может быть поименован.
Топология графа
Граф обозначается с помощью элемента 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>
Вложенные графы
GraphML поддерживает вложенные графы, т.е., графы в которых узлы иерархически упорядочены. Иерархия выражается через структуру GraphML-документа. Узел в GraphML-документе может иметь элемент graph, который содержит узлы иерархически вложенные в данный узел. Ниже приводится пример вложенного графа и соответствующий ему GraphML-документ. Обратите внимание, что на рисунке графа иерархия выражена с помощью оболочки, т.е., узел а находится в иерархии ниже узла b если графическое представление узла a расположено внутри графического представления узла b.
Вложенный граф.
В файле содержится соответствующий 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 - правильно. Хорошая практика состоит в том, чтобы размещать объявление ребра в наиболее общем предке или на самом верхнем уровне иерархии.
Для приложений, которые не поддерживают вложенность графов, рекомендуется игнорировать узлы, которые не принадлежат графу верхнего уровня, и игнорировать ребра у которых обе конечные точки не принадлежат графу верхнего уровня.
в работе файловый формат для
GraphML - полнофункциональный и удобный в работе файловый формат для описания графов. Он включает базовый язык предназначенный для описания структурных свойств графа и гибкий механизм расширения его расширения, что позволяет включать в описание графа данные специфичные для приложений.
GraphML включает поддержку направленных, ненаправленных, и смешанных графов, гиперграфов, иерархических графов, описание графического представления, ссылок к внешним данным, специфических для приложения атрибутов, и облегченного синтаксического анализатора.
В отличие от многих других форматов описания графов, GraphML не использует заказной синтаксис. Вместо этого он использует синтаксис основанный на языке , и следовательно идеально подходит в качестве универсального средства для формирования, архивирования, или обработки графов.
Данный документ представляет собой учебник для начинающих, и должен использоваться совместно с формальным описанием языка, содержащегося в . Документ предназначен для разработчиков программного обеспечения, предназначенного для работы с GraphML-файлами. Текст документа предполагает, что Вы знакомы с и . При чтении некоторых разделов требуются элементарные знания языка . Каждый раздел учебника содержит новые особенности языка, и описывает их на конкретных примерах.
раскрывает базовые понятия GraphML. Он описывает порядок объявления простого графа путем определения его узлов и ребер, а также метод включения в граф простых данных пользователя.
описывает дополнительные возможности языка, связанные с вложенными графами, гиперребрами и портами.
описывает механизм расширения языка в целях включения комплексных данных, специфичных для конкретных приложений.
Учебник - это ненормативный документ, что означает, что он не обеспечивает точную спецификацию языка GraphML. Примеры и другой пояснительный материал предназначены для того, чтобы помочь понять основные принципы GraphML, но они не всегда могут обеспечить ответы на конкретные вопросы. В таких случаях, вам необходимо обратиться к спецификации GraphML. Для этого в тексте содержится много ссылок на соответствующие разделы спецификации.
Заголовок
Рассмотрим фрагмент , общий для всех GraphML-документов, основанный на элементе graphml.
Заголовок со ссылкой на XML-схему
<?xml version="1.0" encoding="UTF-8"?> <graphml xmlns="http://graphml.graphdrawing.org/xmlns" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
...
</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>
