GraphML.py

Summary

Lines:

430 of 443 covered (97.1%)

Branches:

59 of 60 taken (98.3%), 1 lines partially

Coverage:

97.2%

Directory:

Graph

Missed lines:

307, 692, 735, 779, 867, 941, 950, 959, 1028, 1088, 1292-1294

Source

pyTooling/Graph/GraphML.pycoveredpartialuncoveredexcludednot executable

# ==================================================================================================================== #
#             _____           _ _               ____                 _                                                 #
#  _ __  _   |_   _|__   ___ | (_)_ __   __ _  / ___|_ __ __ _ _ __ | |__                                              #
# | '_ \| | | || |/ _ \ / _ \| | | '_ \ / _` || |  _| '__/ _` | '_ \| '_ \                                             #
# | |_) | |_| || | (_) | (_) | | | | | | (_| || |_| | | | (_| | |_) | | | |                                            #
# | .__/ \__, ||_|\___/ \___/|_|_|_| |_|\__, (_)____|_|  \__,_| .__/|_| |_|                                            #
# |_|    |___/                          |___/                 |_|                                                      #
# ==================================================================================================================== #
# Authors:                                                                                                             #
#   Patrick Lehmann                                                                                                    #
#                                                                                                                      #
# License:                                                                                                             #
# ==================================================================================================================== #
# Copyright 2017-2026 Patrick Lehmann - Bötzingen, Germany                                                             #
#                                                                                                                      #
# Licensed under the Apache License, Version 2.0 (the "License");                                                      #
# you may not use this file except in compliance with the License.                                                     #
# You may obtain a copy of the License at                                                                              #
#                                                                                                                      #
#   http://www.apache.org/licenses/LICENSE-2.0                                                                         #
#                                                                                                                      #
# Unless required by applicable law or agreed to in writing, software                                                  #
# distributed under the License is distributed on an "AS IS" BASIS,                                                    #
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.                                             #
# See the License for the specific language governing permissions and                                                  #
# limitations under the License.                                                                                       #
#                                                                                                                      #
# SPDX-License-Identifier: Apache-2.0                                                                                  #
# ==================================================================================================================== #
#
"""
A data model to write out GraphML XML files.

.. seealso::

   `GraphML Primer <http://graphml.graphdrawing.org/primer/graphml-primer.html>`__
      |rarr| The format's own introduction, describing the elements this module writes.
"""
from __future__            import annotations

from enum                  import Enum, auto
from pathlib               import Path
from typing                import Any, ClassVar, Union, Optional as Nullable

from pyTooling.Decorators  import export, notimplemented, readonly
from pyTooling.MetaClasses import ExtendedType, abstractmethod
from pyTooling.Graph       import Graph as pyToolingGraph, Subgraph as pyToolingSubgraph, Edge as pyToolingEdge, \
                                  Link as pyToolingLink, GraphViz
from pyTooling.Tree        import Node as pyToolingNode


_ATTRIBUTE_ESCAPES = str.maketrans({"&": "&amp;", "<": "&lt;", ">": "&gt;", '"': "&quot;"})
"""Translation table escaping an XML attribute value."""


def _escapeAttribute(value: Any) -> str:
	"""
	Escape a value for an XML attribute in double quotes: ``&``, ``<``, ``>`` and ``"``.

	:param value: The value, converted by :func:`str`.
	:returns:     The escaped text.
	"""
	return str(value).translate(_ATTRIBUTE_ESCAPES)

@export
class AttributeContext(Enum):
	"""
	Enumeration of all attribute contexts.

	An attribute context describes to what kind of GraphML node an attribute can be applied.
	"""
	GraphML = auto()
	Graph = auto()
	Node = auto()
	Edge = auto()
	Port = auto()

	def __str__(self) -> str:
		"""
		Return the enumeration value's name as it is written in a GraphML document.

		:returns: Name of the enumeration value in lower case.
		"""
		return f"{self.name.lower()}"


@export
class AttributeTypes(Enum):
	"""
	Enumeration of all attribute types.

	An attribute type describes what datatype can be applied to an attribute.
	"""
	Boolean = auto()
	Int = auto()
	Long = auto()
	Float = auto()
	Double = auto()
	String = auto()

	def __str__(self) -> str:
		"""
		Return the enumeration value's name as it is written in a GraphML document.

		:returns: Name of the enumeration value in lower case.
		"""
		return f"{self.name.lower()}"


@export
class EdgeDefault(Enum):
	"""An enumeration describing the default edge direction."""
	Undirected = auto()
	Directed = auto()

	def __str__(self) -> str:
		"""
		Return the enumeration value's name as it is written in a GraphML document.

		:returns: Name of the enumeration value in lower case.
		"""
		return f"{self.name.lower()}"


@export
class ParsingOrder(Enum):
	"""An enumeration describing the parsing order of the graph's representation."""
	NodesFirst = auto()     #: First, all nodes are given, then followed by all edges.
	AdjacencyList = auto()
	Free = auto()

	def __str__(self) -> str:
		"""
		Return the enumeration value's name as it is written in a GraphML document.

		:returns: Name of the enumeration value in lower case.
		"""
		return f"{self.name.lower()}"


@export
class IDStyle(Enum):
	"""An enumeration describing the style of identifiers (IDs)."""
	Canonical = auto()
	Free = auto()

	def __str__(self) -> str:
		"""
		Return the enumeration value's name as it is written in a GraphML document.

		:returns: Name of the enumeration value in lower case.
		"""
		return f"{self.name.lower()}"


@export
class Base(metaclass=ExtendedType, slots=True):
	"""
	Base-class for all GraphML data model classes.
	"""
	@readonly
	def HasClosingTag(self) -> bool:
		"""
		Check if this XML element is written with a separate closing tag.

		:returns: ``True``, if the element needs a closing tag.
		"""
		return True

	@abstractmethod
	def Tag(self, indent: int = 0) -> str:
		"""
		Return this element as a self-closing XML tag.

		An element always written with an opening and a closing tag overrides it with
		:deco:`~pyTooling.Decorators.notimplemented`.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The XML tag, indented and terminated by a newline.
		"""

	@abstractmethod
	def OpeningTag(self, indent: int = 0) -> str:
		"""
		Return the opening XML tag of this element.

		An element always written as a single tag overrides it with :deco:`~pyTooling.Decorators.notimplemented`.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The opening XML tag, indented and terminated by a newline.
		"""

	@abstractmethod
	def ClosingTag(self, indent: int = 0) -> str:
		"""
		Return the closing XML tag of this element.

		An element always written as a single tag overrides it with :deco:`~pyTooling.Decorators.notimplemented`.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The closing XML tag, indented and terminated by a newline.
		"""

	@abstractmethod
	def ToStringLines(self, indent: int = 0) -> list[str]:
		"""
		Render this element as a list of XML lines.

		:param indent: Optional, indentation level of the XML element.
		:returns:      List of XML lines describing this element.
		"""


@export
class BaseWithID(Base):
	"""Base-class for all GraphML elements carrying a document-wide unique ID."""
	_id: Nullable[str]  #: Unique identifier of this GraphML element. ``None`` if it has none, e.g. an edge.

	def __init__(self, identifier: Nullable[str]) -> None:
		"""
		Initialize a GraphML element with its unique ID.

		:param identifier: Unique ID of the element within the GraphML document, or ``None``.
		"""
		super().__init__()
		self._id = identifier

	@readonly
	def ID(self) -> Nullable[str]:
		"""
		Read-only property to access the element's unique ID (:attr:`_id`).

		:returns: Unique ID of the element, or ``None`` if it has none.
		"""
		return self._id


@export
class BaseWithData(BaseWithID):
	"""Base-class for all GraphML elements that can carry attached data items (key-value-pairs)."""
	_data: list[_Data]  #: Data items (key-value-pairs) attached to this GraphML element.

	def __init__(self, identifier: Nullable[str]) -> None:
		"""
		Initialize a GraphML element with its unique ID and an empty list of data items.

		:param identifier: Unique ID of the element within the GraphML document, or ``None``.
		"""
		super().__init__(identifier)

		self._data = []

	@readonly
	def Data(self) -> list[Data]:
		"""
		Read-only property to access the data elements attached to this element (:attr:`_data`).

		:returns: List of data elements.
		"""
		return self._data

	def AddData(self, data: Data) -> Data:
		"""
		Attach a data item (key-value-pair) to this element.

		:param data: The data item to attach.
		:returns:    The attached data item, so it can be used in the calling expression.
		"""
		self._data.append(data)
		return data


@export
class Key(BaseWithID):
	"""
	Declares an attribute that data items can refer to.

	A GraphML document declares its attributes once - name, data type, and the element kind they apply to - and every
	:class:`Data` item then references such a key by ID.
	"""
	_context:       AttributeContext  #: GraphML element kind this key can be used on.
	_attributeName: str               #: Name of the attribute described by this key.
	_attributeType: AttributeTypes    #: Data type of the attribute described by this key.

	def __init__(self, identifier: str, context: AttributeContext, name: str, type: AttributeTypes) -> None:
		"""
		Initialize a key declaring an attribute.

		:param identifier: Unique ID of the key within the GraphML document.
		:param context:    GraphML element kind this key can be used on.
		:param name:       Name of the declared attribute.
		:param type:       Data type of the declared attribute.
		"""
		super().__init__(identifier)

		self._context = context
		self._attributeName = name
		self._attributeType = type

	@readonly
	def Context(self) -> AttributeContext:
		"""
		Read-only property to access the context this key applies to (:attr:`_context`).

		:returns: The attribute's context (graph, node, edge, ...).
		"""
		return self._context

	@readonly
	def AttributeName(self) -> str:
		"""
		Read-only property to access the name of the described attribute (:attr:`_attributeName`).

		:returns: Name of the attribute.
		"""
		return self._attributeName

	@readonly
	def AttributeType(self) -> AttributeTypes:
		"""
		Read-only property to access the type of the described attribute (:attr:`_attributeType`).

		:returns: Type of the attribute.
		"""
		return self._attributeType

	@readonly
	def HasClosingTag(self) -> bool:
		"""
		Check if this XML element is written with a separate closing tag.

		A key is always written as a self-closing tag.

		:returns: ``False``, because a key never has a closing tag.
		"""
		return False

	def Tag(self, indent: int = 2) -> str:
		"""
		Return this key as a self-closing XML tag.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The XML tag, indented and terminated by a newline.
		"""
		identifier =    _escapeAttribute(self._id)
		attributeName = _escapeAttribute(self._attributeName)
		return f"""{'  '*indent}<key id="{identifier}" for="{self._context}" attr.name="{attributeName}" attr.type="{self._attributeType}" />\n"""

	@notimplemented("A key is always written as a self-closing tag.")
	def OpeningTag(self, indent: int = 2) -> str:
		"""
		A key has no content, so it is never written with an opening and a closing tag.

		:param indent: Optional, indentation level of the XML element.
		"""

	@notimplemented("A key is always written as a self-closing tag.")
	def ClosingTag(self, indent: int = 2) -> str:
		"""
		A key has no content, so it is never written with an opening and a closing tag.

		:param indent: Optional, indentation level of the XML element.
		"""

	def ToStringLines(self, indent: int = 2) -> list[str]:
		"""
		Render this key as a list of XML lines.

		:param indent: Optional, indentation level of the XML element.
		:returns:      List of XML lines describing this key and everything attached to it.
		"""
		return [self.Tag(indent)]


_Key = Key
"""Alias of :class:`Key` for annotations in a class with a property named ``Key``, which the class body binds."""


@export
class Data(Base):
	"""A single attached attribute: a value and the :class:`Key` describing it."""
	_key:  _Key  #: Key describing name and type of this data item.
	_data: Any   #: Value of this data item.

	def __init__(self, key: Key, data: Any) -> None:
		"""
		Initialize a data item with the key describing it and its value.

		:param key:  Key declaring name and type of this attribute.
		:param data: Value of this attribute.
		"""
		super().__init__()

		self._key = key
		self._data = data

	@readonly
	def Key(self) -> Key:
		"""
		Read-only property to access the key describing this data element (:attr:`_key`).

		:returns: The key this data element refers to.
		"""
		return self._key

	@readonly
	def Data(self) -> Any:
		"""
		Read-only property to access the data element's value (:attr:`_data`).

		:returns: Value of the data element.
		"""
		return self._data

	@readonly
	def HasClosingTag(self) -> bool:
		"""
		Check if this XML element is written with a separate closing tag.

		:returns: ``False``, because a data element is written inline.
		"""
		return False

	def Tag(self, indent: int = 2) -> str:
		"""
		Return this data item as a self-closing XML tag.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The XML tag, indented and terminated by a newline.
		"""
		data = str(self._data)
		data = data.replace("&", "&amp;")
		data = data.replace("<", "&lt;")
		data = data.replace(">", "&gt;")
		data = data.replace("\n", "\\n")
		return f"""{'  '*indent}<data key="{_escapeAttribute(self._key._id)}">{data}</data>\n"""

	@notimplemented("A data item is always written in one line by Tag().")
	def OpeningTag(self, indent: int = 2) -> str:
		"""
		A data item holds a value only, so :meth:`Tag` writes it in one line.

		:param indent: Optional, indentation level of the XML element.
		"""

	@notimplemented("A data item is always written in one line by Tag().")
	def ClosingTag(self, indent: int = 2) -> str:
		"""
		A data item holds a value only, so :meth:`Tag` writes it in one line.

		:param indent: Optional, indentation level of the XML element.
		"""

	def ToStringLines(self, indent: int = 2) -> list[str]:
		"""
		Render this data item as a list of XML lines.

		:param indent: Optional, indentation level of the XML element.
		:returns:      List of XML lines describing this data item and everything attached to it.
		"""
		return [self.Tag(indent)]


_Data = Data
"""Alias of :class:`Data` for annotations in a class with a property named ``Data``, which the class body binds."""


@export
class Node(BaseWithData):
	"""A node (vertex) of a GraphML graph."""

	def __init__(self, identifier: str) -> None:
		"""
		Initialize a node.

		:param identifier: Unique ID of the node within the GraphML document.
		"""
		super().__init__(identifier)

	@readonly
	def HasClosingTag(self) -> bool:
		"""
		Check if this XML element is written with a separate closing tag.

		:returns: ``True``, if the node carries data elements, otherwise ``False``.
		"""
		return len(self._data) > 0

	def Tag(self, indent: int = 2) -> str:
		"""
		Return this node as a self-closing XML tag.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The XML tag, indented and terminated by a newline.
		"""
		return f"""{'  '*indent}<node id="{_escapeAttribute(self._id)}" />\n"""

	def OpeningTag(self, indent: int = 2) -> str:
		"""
		Return the opening XML tag of this node.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The opening XML tag, indented and terminated by a newline.
		"""
		return f"""{'  '*indent}<node id="{_escapeAttribute(self._id)}">\n"""

	def ClosingTag(self, indent: int = 2) -> str:
		"""
		Return the closing XML tag of this node.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The closing XML tag, indented and terminated by a newline.
		"""
		return f"""{'  ' * indent}</node>\n"""

	def ToStringLines(self, indent: int = 2) -> list[str]:
		"""
		Render this node as a list of XML lines.

		:param indent: Optional, indentation level of the XML element.
		:returns:      List of XML lines describing this node and everything attached to it.
		"""
		if not self.HasClosingTag:
			return [self.Tag(indent)]

		lines = [self.OpeningTag(indent)]
		for data in self._data:
			lines.extend(data.ToStringLines(indent + 1))
		lines.append(self.ClosingTag(indent))

		return lines


@export
class Edge(BaseWithData):
	"""An edge of a GraphML graph, connecting a source node to a target node."""
	_source: Node  #: Node the edge starts at.
	_target: Node  #: Node the edge ends at.

	def __init__(self, identifier: Nullable[str], source: Node, target: Node) -> None:
		"""
		Initialize an edge between two nodes.

		:param identifier: Unique ID of the edge within the GraphML document.
		:param source:     Node the edge starts at.
		:param target:     Node the edge ends at.
		"""
		super().__init__(identifier)

		self._source = source
		self._target = target

	@readonly
	def Source(self) -> Node:
		"""
		Read-only property to access the edge's source node (:attr:`_source`).

		:returns: Source node of the edge.
		"""
		return self._source

	@readonly
	def Target(self) -> Node:
		"""
		Read-only property to access the edge's target node (:attr:`_target`).

		:returns: Target node of the edge.
		"""
		return self._target

	def _IDAttribute(self) -> str:
		"""
		Return the ``id`` attribute of this edge's tag, or nothing for an edge without an ID - it is optional in GraphML.

		:returns: The attribute with a leading space, or an empty string.
		"""
		if self._id is None:
			return ""
		else:
			return f' id="{_escapeAttribute(self._id)}"'

	@readonly
	def HasClosingTag(self) -> bool:
		"""
		Check if this XML element is written with a separate closing tag.

		:returns: ``True``, if the edge carries data elements, otherwise ``False``.
		"""
		return len(self._data) > 0

	def Tag(self, indent: int = 2) -> str:
		"""
		Return this edge as a self-closing XML tag.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The XML tag, indented and terminated by a newline.
		"""
		source = _escapeAttribute(self._source._id)
		target = _escapeAttribute(self._target._id)
		return f"""{'  ' * indent}<edge{self._IDAttribute()} source="{source}" target="{target}" />\n"""

	def OpeningTag(self, indent: int = 2) -> str:
		"""
		Return the opening XML tag of this edge.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The opening XML tag, indented and terminated by a newline.
		"""
		source = _escapeAttribute(self._source._id)
		target = _escapeAttribute(self._target._id)
		return f"""{'  '*indent}<edge{self._IDAttribute()} source="{source}" target="{target}">\n"""

	def ClosingTag(self, indent: int = 2) -> str:
		"""
		Return the closing XML tag of this edge.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The closing XML tag, indented and terminated by a newline.
		"""
		return f"""{'  ' * indent}</edge>\n"""

	def ToStringLines(self, indent: int = 2) -> list[str]:
		"""
		Render this edge as a list of XML lines.

		:param indent: Optional, indentation level of the XML element.
		:returns:      List of XML lines describing this edge and everything attached to it.
		"""
		if not self.HasClosingTag:
			return [self.Tag(indent)]

		lines = [self.OpeningTag(indent)]
		for data in self._data:
			lines.extend(data.ToStringLines(indent + 1))
		lines.append(self.ClosingTag(indent))

		return lines


@export
class BaseGraph(BaseWithData, mixin=True):
	"""
	Mixin-class for everything that contains nodes, edges and subgraphs - a graph as well as a subgraph.

	Beside the elements themselves, it carries the document-level settings applied while writing them: the default edge
	direction, the parsing order, and the ID styles for nodes and edges.
	"""
	_subgraphs:      dict[str, Subgraph]  #: Subgraphs of this graph, by ID.
	_nodes:          dict[str, Node]      #: Nodes of this graph, by ID.
	_edges:          dict[str, Edge]      #: Edges of this graph with an ID, by ID.
	_edgesWithoutID: list[Edge]           #: Edges of this graph without an ID.
	_edgeDefault:    EdgeDefault          #: Direction applied to edges that don't specify one.
	_parseOrder:     ParsingOrder         #: Order in which nodes and edges may appear in the XML document.
	_nodeIDStyle:    IDStyle              #: Whether node IDs are free-form or canonical.
	_edgeIDStyle:    IDStyle              #: Whether edge IDs are free-form or canonical.

	def __init__(self, identifier: Nullable[str] = None) -> None:
		"""
		Initialize an empty graph with the default document settings.

		Edges are directed, nodes are written before edges, and both ID styles are free-form until they are changed.

		:param identifier: Optional, unique ID of the graph within the GraphML document.
		"""
		super().__init__(identifier)

		self._subgraphs =      {}
		self._nodes =          {}
		self._edges =          {}
		self._edgesWithoutID = []
		self._edgeDefault =    EdgeDefault.Directed
		self._parseOrder =     ParsingOrder.NodesFirst
		self._nodeIDStyle =    IDStyle.Free
		self._edgeIDStyle =    IDStyle.Free

	@readonly
	def Subgraphs(self) -> dict[str, Subgraph]:
		"""
		Read-only property to access the graph's subgraphs (:attr:`_subgraphs`).

		:returns: Dictionary of subgraph IDs and subgraphs.
		"""
		return self._subgraphs

	@readonly
	def Nodes(self) -> dict[str, Node]:
		"""
		Read-only property to access the graph's nodes (:attr:`_nodes`).

		:returns: Dictionary of node IDs and nodes.
		"""
		return self._nodes

	@readonly
	def Edges(self) -> dict[str, Edge]:
		"""
		Read-only property to access the graph's edges with an ID (:attr:`_edges`).

		An edge without an ID is in :attr:`EdgesWithoutID`.

		:returns: Dictionary of edge IDs and edges.
		"""
		return self._edges

	@readonly
	def EdgesWithoutID(self) -> list[Edge]:
		"""
		Read-only property to access the graph's edges without an ID (:attr:`_edgesWithoutID`).

		An edge with an ID is in :attr:`Edges`.

		:returns: List of edges without an ID, in the order they were added.
		"""
		return self._edgesWithoutID

	def AddSubgraph(self, subgraph: Subgraph) -> Subgraph:
		"""
		Add a subgraph to this graph, which is a node of this graph as well.

		:param subgraph: The subgraph to add.
		:returns:        The added subgraph, so it can be used in the calling expression.
		"""
		self._subgraphs[subgraph._subgraphID] = subgraph
		self._nodes[subgraph._id] = subgraph
		return subgraph

	def GetSubgraph(self, subgraphName: str) -> Subgraph:
		"""
		Return the subgraph with the given ID.

		:param subgraphName: ID of the subgraph.
		:returns:            The subgraph with that ID.
		:raises KeyError:    If no subgraph has that ID.
		"""
		return self._subgraphs[subgraphName]

	def AddNode(self, node: Node) -> Node:
		"""
		Add a node to this graph.

		:param node: The node to add.
		:returns:    The added node, so it can be used in the calling expression.
		"""
		self._nodes[node._id] = node
		return node

	def GetNode(self, nodeName: str) -> Node:
		"""
		Return the node with the given ID.

		:param nodeName:  ID of the node.
		:returns:         The node with that ID.
		:raises KeyError: If no node has that ID.
		"""
		return self._nodes[nodeName]

	def AddEdge(self, edge: Edge) -> Edge:
		"""
		Add an edge to this graph.

		:param edge: The edge to add.
		:returns:    The added edge, so it can be used in the calling expression.
		"""
		if edge._id is None:
			self._edgesWithoutID.append(edge)
		else:
			self._edges[edge._id] = edge

		return edge

	def GetEdge(self, edgeName: str) -> Edge:
		"""
		Return the edge with the given ID.

		:param edgeName:  ID of the edge.
		:returns:         The edge with that ID.
		:raises KeyError: If no edge has that ID.
		"""
		return self._edges[edgeName]

	@notimplemented("A graph is always written with an opening and a closing tag.")
	def Tag(self, indent: int = 1) -> str:
		"""
		A graph is written with its nodes and edges inside, so it is never written as a self-closing tag.

		:param indent: Optional, indentation level of the XML element.
		"""

	def OpeningTag(self, indent: int = 1) -> str:
		"""
		Return the opening XML tag of this graph.

		Beside the graph's ID, the tag carries the parsing hints a reader needs: the default edge direction, the
		number of nodes and edges, the parsing order and both ID styles.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The opening XML tag, indented and terminated by a newline.
		"""
		return f"""\
{'  '*indent}<graph id="{_escapeAttribute(self._id)}"
{'  '*indent}  edgedefault="{self._edgeDefault!s}"
{'  '*indent}  parse.nodes="{len(self._nodes)}"
{'  '*indent}  parse.edges="{len(self._edgesWithoutID) + len(self._edges)}"
{'  '*indent}  parse.order="{self._parseOrder!s}"
{'  '*indent}  parse.nodeids="{self._nodeIDStyle!s}"
{'  '*indent}  parse.edgeids="{self._edgeIDStyle!s}">
"""

	def ClosingTag(self, indent: int = 1) -> str:
		"""
		Return the closing XML tag of this graph.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The closing XML tag, indented and terminated by a newline.
		"""
		return f"{'  '*indent}</graph>\n"

	def ToStringLines(self, indent: int = 1) -> list[str]:
		"""
		Render this graph as a list of XML lines.

		:param indent: Optional, indentation level of the XML element.
		:returns:      List of XML lines describing this graph and everything it contains.
		"""
		lines = [self.OpeningTag(indent)]
		for node in self._nodes.values():
			lines.extend(node.ToStringLines(indent + 1))

		for edge in (*self._edgesWithoutID, *self._edges.values()):
			lines.extend(edge.ToStringLines(indent + 1))
		# for data in self._data:
		# 	lines.extend(data.ToStringLines(indent + 1))
		lines.append(self.ClosingTag(indent))

		return lines


@export
class Graph(BaseGraph):
	"""
	The root graph of a GraphML document.

	It owns the ID space: every node, edge and subgraph registers itself here, so an ID is used only once per document.
	"""
	_document: GraphMLDocument                         #: The GraphML document this graph belongs to.
	_ids:      dict[str, Union[Node, Edge, Subgraph]]  #: Every element of this graph by ID, used to keep IDs unique.

	def __init__(self, document: GraphMLDocument, identifier: str) -> None:
		"""
		Initialize the root graph of a GraphML document.

		:param document:   The GraphML document this graph belongs to.
		:param identifier: Unique ID of the graph within the GraphML document.
		"""
		super().__init__(identifier)
		self._document = document
		self._ids = {}

	def GetByID(self, identifier: str) -> Union[Node, Edge, Subgraph]:
		"""
		Return the element with the given ID, whichever kind it is.

		:param identifier: ID of the node, edge or subgraph.
		:returns:          The element registered under that ID.
		:raises KeyError:  If no element has that ID.
		"""
		return self._ids[identifier]

	def AddSubgraph(self, subgraph: Subgraph) -> Subgraph:
		"""
		Add a subgraph to the root graph and register its ID.

		:param subgraph: The subgraph to add.
		:returns:        The added subgraph, so it can be used in the calling expression.
		"""
		result = super().AddSubgraph(subgraph)
		self._ids[subgraph._subgraphID] = subgraph
		subgraph._root = self
		return result

	def AddNode(self, node: Node) -> Node:
		"""
		Add a node to the root graph and register its ID.

		:param node: The node to add.
		:returns:    The added node, so it can be used in the calling expression.
		"""
		result = super().AddNode(node)
		self._ids[node._id] = node
		return result

	def AddEdge(self, edge: Edge) -> Edge:
		"""
		Add an edge to the root graph and register its ID, if it has one.

		:param edge: The edge to add.
		:returns:    The added edge, so it can be used in the calling expression.
		"""
		result = super().AddEdge(edge)
		if edge._id is not None:
			self._ids[edge._id] = edge

		return result


_Graph = Graph
"""Alias of :class:`Graph` for annotations in a class with a property named ``Graph``, which the class body binds."""


@export
class Subgraph(Node, BaseGraph):
	"""
	A nested graph, which is a node of its parent graph and a graph of its own.

	It therefore carries two identifiers: the node's ID it is referenced by, and :attr:`_subgraphID` for the graph it
	contains.
	"""
	_subgraphID: str              #: ID of the subgraph, which is distinct from the node's own ID.
	_root:       Nullable[Graph]  #: The graph this subgraph is nested in.

	def __init__(self, nodeIdentifier: str, graphIdentifier: str) -> None:
		"""
		Initialize a subgraph, which is a node in its parent graph and a graph of its own.

		:param nodeIdentifier:  Unique ID of the node representing the subgraph.
		:param graphIdentifier: Unique ID of the graph contained in that node.
		"""
		super().__init__(nodeIdentifier)
		BaseGraph.__init__(self, nodeIdentifier)

		self._subgraphID = graphIdentifier
		self._root = None

	@readonly
	def RootGraph(self) -> Graph:
		"""
		Read-only property to access the graph this subgraph is embedded in (:attr:`_root`).

		:returns: The root graph.
		"""
		return self._root

	@readonly
	def SubgraphID(self) -> str:
		"""
		Read-only property to access the subgraph's ID (:attr:`_subgraphID`).

		:returns: ID of the subgraph.
		"""
		return self._subgraphID

	@readonly
	def HasClosingTag(self) -> bool:
		"""
		Check if this XML element is written with a separate closing tag.

		:returns: ``True``, because a subgraph always has a closing tag.
		"""
		return True

	def AddNode(self, node: Node) -> Node:
		"""
		Add a node to this subgraph and register its ID at the root graph.

		:param node: The node to add.
		:returns:    The added node, so it can be used in the calling expression.
		"""
		result = super().AddNode(node)
		self._root._ids[node._id] = node
		return result

	def AddEdge(self, edge: Edge) -> Edge:
		"""
		Add an edge to this subgraph and register its ID at the root graph, if it has one.

		:param edge: The edge to add.
		:returns:    The added edge, so it can be used in the calling expression.
		"""
		result = super().AddEdge(edge)
		if edge._id is not None:
			self._root._ids[edge._id] = edge

		return result

	@notimplemented("A subgraph is always written with an opening and a closing tag.")
	def Tag(self, indent: int = 2) -> str:
		"""
		A subgraph always contains a graph, so it is never written as a self-closing tag.

		:param indent: Optional, indentation level of the XML element.
		"""

	def OpeningTag(self, indent: int = 1) -> str:
		"""
		Return the opening XML tag of this subgraph.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The opening XML tag, indented and terminated by a newline.
		"""
		return f"""\
{'  ' * indent}<graph id="{_escapeAttribute(self._subgraphID)}"
{'  ' * indent}  edgedefault="{self._edgeDefault!s}"
{'  ' * indent}  parse.nodes="{len(self._nodes)}"
{'  ' * indent}  parse.edges="{len(self._edgesWithoutID) + len(self._edges)}"
{'  ' * indent}  parse.order="{self._parseOrder!s}"
{'  ' * indent}  parse.nodeids="{self._nodeIDStyle!s}"
{'  ' * indent}  parse.edgeids="{self._edgeIDStyle!s}">
"""

	def ClosingTag(self, indent: int = 2) -> str:
		"""
		Return the closing XML tag of this subgraph.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The closing XML tag, indented and terminated by a newline.
		"""
		return BaseGraph.ClosingTag(self, indent)

	def ToStringLines(self, indent: int = 2) -> list[str]:
		"""
		Render this subgraph as a list of XML lines.

		:param indent: Optional, indentation level of the XML element.
		:returns:      List of XML lines describing this subgraph and everything it contains.
		"""
		lines = [super().OpeningTag(indent)]
		for data in self._data:
			lines.extend(data.ToStringLines(indent + 1))
		# lines.extend(Graph.ToStringLines(self, indent + 1))
		lines.append(self.OpeningTag(indent + 1))
		for node in self._nodes.values():
			lines.extend(node.ToStringLines(indent + 2))

		for edge in (*self._edgesWithoutID, *self._edges.values()):
			lines.extend(edge.ToStringLines(indent + 2))
		# for data in self._data:
		# 	lines.extend(data.ToStringLines(indent + 1))
		lines.append(self.ClosingTag(indent + 1))
		lines.append(super().ClosingTag(indent))

		return lines


@export
class GraphMLDocument(Base):
	"""
	A GraphML document: the root graph, the keys it declares, and the XML boilerplate to write it out.
	"""

	_XML_NS: ClassVar[dict[Nullable[str], str]] = {
		None:  "http://graphml.graphdrawing.org/xmlns",
		"xsi": "http://www.w3.org/2001/XMLSchema-instance"
	}  #: XML namespaces of a GraphML document.
	_XSI: ClassVar[dict[str, str]] = {
		"schemaLocation": "http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd"
	}  #: XML schema instance attributes of a GraphML document.

	_graph: _Graph          #: The document's root graph.
	_keys:  dict[str, Key]  #: Keys declared by this document, by ID.

	def __init__(self, identifier: str = "G") -> None:
		"""
		Initialize a GraphML document with an empty root graph.

		:param identifier: Optional, unique ID of the root graph.
		"""
		super().__init__()

		self._graph = Graph(self, identifier)
		self._keys = {}

	@readonly
	def Graph(self) -> BaseGraph:
		"""
		Read-only property to access the document's graph (:attr:`_graph`).

		:returns: The graph described by this document.
		"""
		return self._graph

	@readonly
	def Keys(self) -> dict[str, Key]:
		"""
		Read-only property to access the attribute keys declared in this document (:attr:`_keys`).

		:returns: Dictionary of key IDs and keys.
		"""
		return self._keys

	def AddKey(self, key: Key) -> Key:
		"""
		Declare an attribute, so data items can refer to it.

		:param key: The key to declare.
		:returns:   The declared key, so it can be used in the calling expression.
		"""
		self._keys[key._id] = key
		return key

	def GetKey(self, keyName: str) -> Key:
		"""
		Return the declared key with the given ID.

		:param keyName:   ID of the key.
		:returns:         The key with that ID.
		:raises KeyError: If no key has that ID.
		"""
		return self._keys[keyName]

	def ContainsKey(self, keyName: str) -> bool:
		"""
		Check if a key with the given ID was declared.

		:param keyName: ID of the key.
		:returns:       ``True``, if such a key exists.
		"""
		return keyName in self._keys

	def FromGraph(self, graph: pyToolingGraph) -> None:
		"""
		Fill this document from a :class:`pyTooling.Graph.Graph`.

		Vertices become nodes, edges become edges, and the vertex and edge values are attached as data items,
		declared by two keys this method adds. A subgraph becomes a GraphML subgraph. A link connects vertices of two
		graphs; it becomes an edge of the root graph.

		A node's ID is its vertex' ID. A vertex without an ID gets a generated ID ``vertex<number>``, which no vertex' ID
		is, because GraphML requires one. Subgraphs are translated ordered by name, so the generated IDs don't change from
		one run to the next. A graph without a name keeps the document's graph ID.

		:param graph: The graph to translate into this document.
		"""
		document = self
		if graph._name is not None:
			self._graph._id = graph._name

		nodeValue = self.AddKey(Key("nodeValue", AttributeContext.Node, "value", AttributeTypes.String))
		edgeValue = self.AddKey(Key("edgeValue", AttributeContext.Edge, "value", AttributeTypes.String))

		subgraphs = sorted(graph.Subgraphs, key=lambda subgraph: "" if subgraph._name is None else subgraph._name)
		vertices = [vertex for subgraph in subgraphs for vertex in subgraph.IterateVertices()]
		vertices += graph.IterateVertices()
		identifiers = GraphViz.Graph._Identifiers(vertices)
		nodes: dict[int, Node] = {}

		def getKey(keyID: str, context: AttributeContext, name: str) -> Key:
			"""
			Nested function returning the key with the given ID, which is declared on first use.

			:param keyID:   ID of the key.
			:param context: Kind of element the key's data items belong to.
			:param name:    Attribute name of the key.
			:returns:       The key.
			"""
			if document.ContainsKey(keyID):
				return document.GetKey(keyID)

			return document.AddKey(Key(keyID, context, name, AttributeTypes.String))

		def translateEdge(edge: Union[pyToolingEdge, pyToolingLink], prefix: str) -> Edge:
			"""
			Nested function translating an edge or a link, with its value and key-value pairs, into a GraphML edge.

			:param edge:   The edge or link to translate.
			:param prefix: Prefix of the key IDs for its key-value pairs: ``edge`` or ``link``.
			:returns:      The GraphML edge between the nodes of its source and destination vertex.
			"""
			newEdge = Edge(edge._id, nodes[id(edge._source)], nodes[id(edge._destination)])
			if edge._value is not None:
				newEdge.AddData(Data(edgeValue, edge._value))

			for key, value in edge._dict.items():
				newEdge.AddData(Data(getKey(f"{prefix}{key!s}", AttributeContext.Edge, str(key)), value))

			return newEdge

		def translateGraph(graphMLGraph: BaseGraph, pyTGraph: Union[pyToolingGraph, pyToolingSubgraph]) -> None:
			"""
			Nested function translating the vertices and edges of a graph or subgraph into GraphML nodes and edges.

			:param graphMLGraph: The GraphML graph or subgraph the elements are added to.
			:param pyTGraph:     The pyTooling graph or subgraph to translate.
			"""
			for vertex in pyTGraph.IterateVertices():
				newNode = graphMLGraph.AddNode(Node(identifiers[id(vertex)]))
				nodes[id(vertex)] = newNode
				if vertex._value is not None:
					newNode.AddData(Data(nodeValue, vertex._value))

				for key, value in vertex._dict.items():
					newNode.AddData(Data(getKey(f"node{key!s}", AttributeContext.Node, str(key)), value))

			for edge in pyTGraph.IterateEdges():
				graphMLGraph.AddEdge(translateEdge(edge, "edge"))

		for subgraph in subgraphs:
			nodeGraph = Subgraph(subgraph.Name, "sg" + subgraph.Name)
			self._graph.AddSubgraph(nodeGraph)
			translateGraph(nodeGraph, subgraph)

		translateGraph(self._graph, graph)

		# A link is known to both graphs it connects: collect it from all graphs, and write it once into the root graph.
		translatedLinks: set[int] = set()
		for pyTGraph in (*subgraphs, graph):
			for link in pyTGraph.IterateLinks():
				if id(link) not in translatedLinks:
					translatedLinks.add(id(link))
					self._graph.AddEdge(translateEdge(link, "link"))

	def FromTree(self, tree: pyToolingNode) -> None:
		"""
		Fill this document from a :class:`pyTooling.Tree.Node`.

		Every node of the tree becomes a GraphML node, and every parent-child relation becomes an edge.

		A GraphML node's ID is the tree node's ID. A tree node without an ID gets a generated ID ``vertex<number>``, which
		no tree node's ID is, because GraphML requires one. A root without an ID keeps the document's graph ID.

		:param tree: The root node of the tree to translate into this document.
		"""
		if tree._id is not None:
			self._graph._id = tree._id

		nodeValue = self.AddKey(Key("nodeValue", AttributeContext.Node, "value", AttributeTypes.String))

		treeNodes  = [tree]
		treeNodes += tree.GetDescendants()
		identifiers = GraphViz.Graph._Identifiers(treeNodes)
		nodes: dict[int, Node] = {}

		for i, treeNode in enumerate(treeNodes):
			newNode = self._graph.AddNode(Node(identifiers[id(treeNode)]))
			nodes[id(treeNode)] = newNode
			if treeNode._value is not None:
				newNode.AddData(Data(nodeValue, treeNode._value))

			if treeNode is not tree:
				self._graph.AddEdge(Edge(f"e{i - 1}", newNode, nodes[id(treeNode._parent)]))

	@notimplemented("A GraphML document is always written with an opening and a closing tag.")
	def Tag(self, indent: int = 0) -> str:
		"""
		A GraphML document always contains keys and a graph, so it is never written as a self-closing tag.

		:param indent: Optional, indentation level of the XML element.
		"""

	def OpeningTag(self, indent: int = 0) -> str:
		"""
		Return the opening XML tag of this document.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The opening XML tag, indented and terminated by a newline.
		"""
		return f"""\
{'  '*indent}<graphml xmlns="{self._XML_NS[None]}"
{'  '*indent}         xmlns:xsi="{self._XML_NS["xsi"]}"
{'  '*indent}         xsi:schemaLocation="{self._XSI["schemaLocation"]}">
"""

	def ClosingTag(self, indent: int = 0) -> str:
		"""
		Return the closing XML tag of this document.

		:param indent: Optional, indentation level of the XML element.
		:returns:      The closing XML tag, indented and terminated by a newline.
		"""
		return f"{'  '*indent}</graphml>\n"

	def ToStringLines(self, indent: int = 0) -> list[str]:
		"""
		Render this document as a list of XML lines.

		:param indent: Optional, indentation level of the XML element.
		:returns:      List of XML lines describing this document and everything it contains.
		"""
		lines = [self.OpeningTag(indent)]
		for key in self._keys.values():
			lines.extend(key.ToStringLines(indent + 1))
		lines.extend(self._graph.ToStringLines(indent + 1))
		lines.append(self.ClosingTag(indent))

		return lines

	def WriteToFile(self, file: Path) -> None:
		"""
		Write this document as a GraphML file.

		:param file: Path of the file to write.
		"""
		with file.open("w", encoding="utf-8") as f:
			f.write("""<?xml version="1.0" encoding="utf-8"?>""")
			f.writelines(self.ToStringLines())