TEI P5: Guidelines for Electronic Text Encoding and Interchange: 19 Graphs, Networks, and Trees

19 Graphs, Networks, and Trees

Table of contents

Graphical representations are widely used for displaying relations among informational units because they help readers to visualize those relations and hence to understand them better. Two general types of graphical representations may be distinguished.

Graphs, in the strictly mathematical sense, consist of points, often called nodes or vertices, and connections among them, called arcs, or under certain conditions, edges. Among the various types of graphs are networks and trees. Graphs generally and networks in particular are dealt with directly below. Trees are dealt with separately in sections 19.2 Trees and 19.3 Another Tree Notation.⁷¹
Charts, which typically plot data in two or more dimensions, including plots with orthogonal or radial axes, bar charts, pie charts, and the like. These can be described using the elements defined in the module for figures and graphics; see chapter 14 Tables, Formulæ, and Graphics.

Among the types of qualitative relations often represented by graphs are organizational hierarchies, flow charts, genealogies, semantic networks, transition networks, grammatical relations, tournament schedules, seating plans, and directions to people's houses. In developing recommendations for the encoding of graphs of various types, we have relied on their formal mathematical definitions and on the most common conventions for representing them visually. However, it must be emphasized that these recommendations do not provide for the full range of possible graphical representations, and deal only partially with questions of design, layout, and placement.

» 19.2 Trees
Home | Table of contents

19.1 Graphs and DigraphsTEI: Graphs and Digraphs¶

Broadly speaking, graphs can be divided into two types: undirected and directed. An undirected graph is a set of nodes (or vertices) together with a set of pairs of those vertices, called arcs or edges. Each node in an arc of an undirected graph is said to be incident with that arc, and the two vertices (nodes) which make up an arc are said to be adjacent. An directed graph is like an undirected graph except that the arcs are ordered pairs of nodes. In the case of directed graphs, the term edge is not used; moreover, each arc in a directed graph is said to be adjacent from the node from which the arc emanates, and adjacent to the node to which the arc is directed. We use the element graph to encode graphs as a whole, node to encode nodes or vertices, and arc to encode arcs or edges; arcs can also be encoded by attributes on the node element. These elements have the following descriptions and attributes:

graph encodes a graph, which is a collection of nodes, and arcs which connect the nodes.
node encodes a node, a possibly labeled point in a graph.
arc encodes an arc, the connection from one node to another in a graph.

Before proceeding, some additional terminology may be helpful. We define a path in a graph as a sequence of nodes n1, ..., nk such that there is an arc from each ni to ni+1 in the sequence. A cyclic path, or cycle is a path leading from a particular node back to itself. A graph that contains at least one cycle is said to be cyclic; otherwise it is acyclic. We say, finally, that a graph is connected if there is a path from some node to every other node in the graph; any graph that is not connected is said to be disconnected.

Here is an example of an undirected, cyclic disconnected graph, in which the nodes are annotated with three-letter codes for airports, and the arcs connecting the nodes are represented by horizontal and vertical lines, with 90 degree bends used simply to avoid having to draw diagonal lines.

Next is a markup of the graph, using arc elements to encode the arcs.

<graph
  type="undirected"
  xml:id="CUG1"
  order="5"
  size="4">
<label>Airline Connections in Southwestern USA</label>
<node xml:id="LAX" degree="2">
  <label>LAX</label>
</node>
<node xml:id="LVG" degree="2">
  <label>LVG</label>
</node>
<node xml:id="PHX" degree="3">
  <label>PHX</label>
</node>
<node xml:id="TUS" degree="1">
  <label>TUS</label>
</node>
<node xml:id="CIB" degree="0">
  <label>CIB</label>
</node>
<arc from="#LAX" to="#LVG"/>
<arc from="#LAX" to="#PHX"/>
<arc from="#LVG" to="#PHX"/>
<arc from="#PHX" to="#TUS"/>
</graph>

The first child element of graph may be a label to record a label for the graph; similarly, the label child of each node element records the labels of that node. The order and size attributes on the graph element record the number of nodes and number of arcs in the graph respectively; these values are optional (since they can be computed from the rest of the graph), but if they are supplied, they must be consistent with the rest of the encoding. They can thus be used to help check that the graph has been encoded and transmitted correctly. The degree attribute on the node elements record the number of arcs that are incident with that node. It is optional (because redundant), but can be used to help in validity checking: if a value is given, it must be consistent with the rest of the information in the graph. Finally, the from and to attributes on the arc elements provide pointers to the nodes connected by those arcs. Since the graph is undirected, no directionality is implied by the use of the from and to attributes; the values of these attributes could be interchanged in each arc without changing the graph.

The adj, adjFrom, and adjTo attributes of the node element provide an alternative method of representing unlabeled arcs, their values being pointers to the nodes which are adjacent to or from that node. The adj attribute is to be used for undirected graphs, and the adjFrom and adjTo attributes for directed graphs. It is a semantic error for the directed adjacency attributes to be used in an undirected graph, and vice versa. Here is a markup of the preceding graph, using the adj attribute to represent the arcs.

<graph
  type="undirected"
  xml:id="CUG2"
  order="5"
  size="4">
<label>Airline Connections in Southwestern USA</label>
<node xml:id="LAX2" degree="2" adj="#LVG2 #PHX2">
  <label>LAX2</label>
</node>
<node xml:id="LVG2" degree="2" adj="#LAX2 #PHX2">
  <label>LVG2</label>
</node>
<node xml:id="PHX2" degree="3" adj="#LAX2 #LVG2 #TUS2">
  <label>PHX2</label>
</node>
<node xml:id="TUS2" degree="1" adj="#PHX2">
  <label>TUS2</label>
</node>
<node xml:id="CIB2" degree="0">
  <label>CIB2</label>
</node>
</graph>

Note that each arc is represented twice in this encoding of the graph. For example, the existence of the arc from LAX to LVG can be inferred from each of the first two node elements in the graph. This redundancy, however, is not required: it suffices to describe an arc in any one of the three places it can be described (either adjacent node, or in a separate arc element). Here is a less redundant representation of the same graph.

<graph
  type="undirected"
  xml:id="CUG3"
  order="5"
  size="4">
<label>Airline Connections in Southwestern USA</label>
<node xml:id="LAX3" degree="2" adj="#LVG3 #PHX3">
  <label>LAX3</label>
</node>
<node xml:id="LVG3" degree="2" adj="#PHX3">
  <label>LVG3</label>
</node>
<node xml:id="PHX3" degree="3" adj="#TUS3">
  <label>PHX3</label>
</node>
<node xml:id="TUS3" degree="1">
  <label>TUS3</label>
</node>
<node xml:id="CIB3" degree="0">
  <label>CIB3</label>
</node>
</graph>

Although in many cases the arc element is redundant (since arcs can be described using the adjacency attributes of their adjacent nodes), it has nevertheless been included in this module, in order to allow the convenient specification of identifiers, display or rendition information, and labels for each arc (using the attributes xml:id, rend, and a child label element).

Next, let us modify the preceding graph by adding directionality to the arcs. Specifically, we now think of the arcs as specifying selected routes from one airport to another, as indicated by the direction of the arrowheads in the following diagram.

Here is an encoding of this graph, using the arc element to designate the arcs.

<graph
  type="directed"
  xml:id="RDG1"
  order="5"
  size="5">
<label>Selected Airline Routes in Southwestern USA</label>
<node xml:id="LAX4" inDegree="1" outDegree="1">
  <label>LAX4</label>
</node>
<node xml:id="LVG4" inDegree="1" outDegree="1">
  <label>LVG4</label>
</node>
<node xml:id="PHX4" inDegree="2" outDegree="2">
  <label>PHX4</label>
</node>
<node xml:id="TUS4" inDegree="1" outDegree="1">
  <label>TUS4</label>
</node>
<node xml:id="CIB4" inDegree="0" outDegree="0">
  <label>CIB4</label>
</node>
<arc from="#LAX4" to="#LVG4"/>
<arc from="#LVG4" to="#PHX4"/>
<arc from="#PHX4" to="#LAX4"/>
<arc from="#PHX4" to="#TUS4"/>
<arc from="#TUS4" to="#PHX4"/>
</graph>

The attributes inDegree and outDegree indicate the number of nodes which are adjacent to and from the node concerned respectively.

Here is another encoding of the graph, using the adjTo and adjFrom attributes on nodes to designate the arcs.

<graph
  type="directed"
  xml:id="RDG2"
  order="5"
  size="5">
<label>Selected Airline Routes in Southwestern USA</label>
<node
   xml:id="LAX5"
   inDegree="1"
   outDegree="1"
   adjTo="#LVG5"
   adjFrom="#PHX5">
  <label>LAX5</label>
</node>
<node
   xml:id="LVG5"
   inDegree="1"
   outDegree="1"
   adjFrom="#LAX5"
   adjTo="#PHX5">
  <label>LVG5</label>
</node>
<node
   xml:id="PHX5"
   inDegree="2"
   outDegree="2"
   adjTo="#LAX5 #TUS"
   adjFrom="#LVG5 #TUS5">
  <label>PHX5</label>
</node>
<node
   xml:id="TUS5"
   inDegree="1"
   outDegree="1"
   adjTo="#PHX5"
   adjFrom="#PHX5">
  <label>TUS5</label>
</node>
<node xml:id="CIB5" inDegree="0" outDegree="0">
  <label>CIB5</label>
</node>
</graph>

If we wish to label the arcs, say with flight numbers, then arc elements must be used to hold the label elements, as in the following example.

<graph
  type="directed"
  xml:id="RDG3"
  order="5"
  size="5">
<label>Selected Airline Routes in Southwestern USA</label>
<node xml:id="LAX6">
  <label>LAX6</label>
</node>
<node xml:id="LVG6">
  <label>LVG6</label>
</node>
<node xml:id="PHX6">
  <label>PHX6</label>
</node>
<node xml:id="TUS6">
  <label>TUS6</label>
</node>
<node xml:id="CIB6">
  <label>CIB6</label>
</node>
<arc from="#LAX6" to="#LVG6">
  <label>SW117</label>
</arc>
<arc from="#LVG6" to="#PHX6">
  <label>SW711</label>
</arc>
<arc from="#PHX6" to="#LAX6">
  <label>AA218</label>
</arc>
<arc from="#PHX6" to="#TUS6">
  <label>AW229</label>
</arc>
<arc from="#TUS6" to="#PHX6">
  <label>AW225</label>
</arc>
</graph>

19.1.1 Transition NetworksTEI: Transition Networks¶

For encoding transition networks and other kinds of directed graphs in which distinctions among types of nodes must be made, the type attribute is provided for node elements. In the following example, the initial and final nodes (or states) of the network are distinguished. It can be understood as accepting the set of strings obtained by traversing it from its initial node to its final node, and concatenating the labels.

<graph
  type="network-transition"
  xml:id="SS8"
  order="5"
  size="6">
<label>(8)</label>
<node
   xml:id="Q0"
   inDegree="0"
   outDegree="1"
   type="initial"/>
<node xml:id="Q1" inDegree="2" outDegree="3"/>
<node xml:id="Q2" inDegree="1" outDegree="1"/>
<node xml:id="Q3" inDegree="1" outDegree="1"/>
<node
   xml:id="Q4"
   inDegree="2"
   outDegree="0"
   type="final"/>
<arc from="#Q0" to="#Q1">
  <label>THE</label>
</arc>
<arc from="#Q1" to="#Q1">
  <label>OLD</label>
</arc>
<arc from="#Q1" to="#Q2">
  <label>MAN</label>
</arc>
<arc from="#Q1" to="#Q3">
  <label>MEN</label>
</arc>
<arc from="#Q2" to="#Q4">
  <label>COMES</label>
</arc>
<arc from="#Q3" to="#Q4">
  <label>COME</label>
</arc>
</graph>

A finite state transducer has two labels on each arc, and can be thought of as representing a mapping from one sequence of labels to the other. The following example represents a transducer for translating the English strings accepted by the network in the preceding example into French. The nodes have been annotated with numbers, for convenience.

<graph type="transducer" order="7" size="10">
<node
   xml:id="T0"
   inDegree="0"
   outDegree="3"
   type="initial">
  <label>0</label>
</node>
<node xml:id="T1" inDegree="2" outDegree="1">
  <label>1</label>
</node>
<node xml:id="T2" inDegree="2" outDegree="2">
  <label>2</label>
</node>
<node xml:id="T3" inDegree="2" outDegree="2">
  <label>3</label>
</node>
<node xml:id="T4" inDegree="1" outDegree="1">
  <label>4</label>
</node>
<node xml:id="T5" inDegree="1" outDegree="1">
  <label>5</label>
</node>
<node
   xml:id="T6"
   inDegree="2"
   outDegree="0"
   type="final">
  <label>6</label>
</node>
<arc from="#T0" to="#T1">
  <label>THE</label>
  <label>L'</label>
</arc>
<arc from="#T0" to="#T2">
  <label>THE</label>
  <label>LE</label>
</arc>
<arc from="#T0" to="#T3">
  <label>THE</label>
  <label>LES</label>
</arc>
<arc from="#T1" to="#T4">
  <label>MAN</label>
  <label>HOMME</label>
</arc>
<arc from="#T2" to="#T1">
  <label>OLD</label>
  <label>VIEIL</label>
</arc>
<arc from="#T2" to="#T2">
  <label>OLD</label>
  <label>VIEIL</label>
</arc>
<arc from="#T3" to="#T3">
  <label>OLD</label>
  <label>VIEUX</label>
</arc>
<arc from="#T3" to="#T5">
  <label>MEN</label>
  <label>HOMMES</label>
</arc>
<arc from="#T4" to="#T6">
  <label>COMES</label>
  <label>VIENT</label>
</arc>
<arc from="#T5" to="#T6">
  <label>COME</label>
  <label>VIENNENT</label>
</arc>
</graph>

19.1.2 Family TreesTEI: Family Trees¶

The next example provides an encoding a portion of a family tree, in which nodes are used to represent individuals and parents of individuals, and arcs are used to represent common parentage and descent links. Let us suppose, further, that information about individuals is contained in feature structures, which are contained in feature-structure libraries elsewhere (see 18.4 Feature and Feature-Value Libraries). We can use the value attribute on node elements to point to those feature structures. In this particular representation of the graph, nodes representing females are framed by ovals, nodes representing males are framed by boxes, and nodes representing parents are framed by diamonds.

<graph type="family_tree" order="13" size="12">
<node
   xml:id="KATHR"
   value="http://example.com/russell-fs/tei/kr1"
   inDegree="0"
   outDegree="1">
  <label>Katherine</label>
</node>
<node
   xml:id="AMBER"
   value="http://example.com/russell-fs/tei/ar1"
   inDegree="0"
   outDegree="1">
  <label>Amberley</label>
</node>
<node xml:id="KAR" inDegree="2" outDegree="3">
  <label>K+A</label>
</node>
<node
   xml:id="BERTR"
   value="http://example.com/russell-fs/tei/br1"
   inDegree="1"
   outDegree="2">
  <label>Bertrand</label>
</node>
<node
   xml:id="PETER"
   value="http://example.com/russell-fs/tei/pr1"
   inDegree="0"
   outDegree="1">
  <label>Peter</label>
</node>
<node
   xml:id="DORAR"
   value="http://example.com/russell-fs/tei/dr1"
   inDegree="0"
   outDegree="1">
  <label>Dora</label>
</node>
<node xml:id="PBR" inDegree="2" outDegree="1">
  <label>P+B</label>
</node>
<node xml:id="DBR" inDegree="2" outDegree="2">
  <label>D+B</label>
</node>
<node
   xml:id="FRANR"
   value="http://example.com/russell-fs/tei/fr1"
   inDegree="1"
   outDegree="0">
  <label>Frank</label>
</node>
<node
   xml:id="RACHR"
   value="http://example.com/russell-fs/tei/rr1"
   inDegree="1"
   outDegree="0">
  <label>Rachel</label>
</node>
<node
   xml:id="CONRR"
   value="http://example.com/russell-fs/tei/cr1"
   inDegree="1"
   outDegree="0">
  <label>Conrad</label>
</node>
<node
   xml:id="KATER"
   value="http://example.com/russell-fs/tei/kr2"
   inDegree="1"
   outDegree="0">
  <label>Kate</label>
</node>
<node
   xml:id="JOHNR"
   value="http://example.com/russell-fs/tei/jr1"
   inDegree="1"
   outDegree="0">
  <label>John</label>
</node>
<arc from="#KATHR" to="#KAR">
  <label>Mo</label>
</arc>
<arc from="#AMBER" to="#KAR">
  <label>Fa</label>
</arc>
<arc from="#KAR" to="#BERTR">
  <label>So</label>
</arc>
<arc from="#KAR" to="#FRANR">
  <label>So</label>
</arc>
<arc from="#KAR" to="#RACHR">
  <label>Da</label>
</arc>
<arc from="#PETER" to="#PBR">
  <label>Mo</label>
</arc>
<arc from="#BERTR" to="#PBR">
  <label>Fa</label>
</arc>
<arc from="#PBR" to="#CONRR">
  <label>So</label>
</arc>
<arc from="#DORAR" to="#DBR">
  <label>Mo</label>
</arc>
<arc from="#BERTR" to="#DBR">
  <label>Fa</label>
</arc>
<arc from="#DBR" to="#KATER">
  <label>Da</label>
</arc>
<arc from="#DBR" to="#JOHNR">
  <label>So</label>
</arc>
</graph>

bibliography

19.1.3 Historical InterpretationTEI: Historical Interpretation¶

For our final example, we represent graphically the relationships among various geographic areas mentioned in a seventeenth-century Scottish document. The document itself is a ‘sasine’, which records a grant of land from the earl of Argyll to one Donald McNeill, and reads in part as follows (abbreviations have been expanded silently, and ‘[...]’ marks illegible passages):

Item instrument of Sasine given the said Hector Mcneil confirmed and dated 28 May 1632 [...] at Edinburgh upon the 15 June 1632
Item ane charter granted by Archibald late earl of Argyle and Donald McNeill of Gallachalzie wh makes mention that ... the said late Earl yields and grants to the said Donald MacNeill ...
All and hail the two merk land of old extent of Gallachalzie with the pertinents by and in the lordship of Knapdale within the sherrifdome of Argyll
[description of other lands granted follows ...]
This Charter is dated at Inverary the 15th May 1669

In this example, we are concerned with the land and pertinents (i.e. accompanying sources of revenue) described as ‘the two merk land of old extent of Gallachalzie with the pertinents by and in the lordship of Knapdale within the sherrifdom of Argyll’.

The passage concerns the following pieces of land:

the Earl of Argyll's land (i.e. the lands granted by this clause of the sasine)
two mark of land in Gallachalzie
the pertinents for this land
the Lordship of Knapdale
the sherrifdom of Argyll

We will represent these geographic entities as nodes in a graph. Arcs in the graph will represent the following relationships among them:

containment (INCLUDE)
location within (IN)
contiguity (BY)
constituency (PART OF)

Note that these relationships are logically related: ‘include’ and ‘in’, for example, are inverses of each other: the Earl of Argyll's land includes the parcel in Gallachalzie, and the parcel is therefore in the Earl of Argyll's land. Given an explicit set of inference rules, an appropriate application could use the graph we are constructing to infer the logical consequences of the relationships we identify.

Let us assume that feature-structure analyses are available which describe Gallachalzie, Knapdale, and Argyll. We will link to those feature structures using the value attribute on the nodes representing those places. However, there may be some uncertainty as to which noun phrase is modified by the phrase ‘within the sheriffdome of Argyll’: perhaps the entire lands (land and pertinents) are in Argyll, perhaps just the pertinents are, or perhaps only Knapdale is (together with the portion of the pertinents which is in Knapdale). We will represent all three of these interpretations in the graph; they are, however, mutually exclusive, which we represent using the exclude attribute defined in chapter 16 Linking, Segmentation, and Alignment.⁷²

We represent the graph and its encoding as follows, where the dotted lines in the graph indicate the mutually exclusive arcs; in the encoding, we use the exclude attribute to indicate those arcs.

The graph formalizes the following relationships:

the Earl of Argyll's land includes (the parcel of land in) Gallachalzie
the Earl of Argyll's land includes the pertinents of that parcel
the pertinents are (in part) by the Lordship of Knapdale
the pertinents are (in part) part of the Lordship of Knapdale
the Earl of Argyll's land, or the pertinents, or the Lordship of Knapdale, is in the Sherrifdom of Argyll

We encode the graph thus:

<graph type="directed" order="7" size="9">
<node xml:id="EARL">
  <label>Earl of Argyll's land</label>
</node>
<node xml:id="GALL"
   value="http://example.com/people/scots#gall">
  <label>Gallachalzie</label>
</node>
<node xml:id="PERT">
  <label>Pertinents</label>
</node>
<node xml:id="PER1">
  <label>Pertinents part</label>
</node>
<node xml:id="PER2">
  <label>Pertinents part</label>
</node>
<node
   xml:id="KNAP"
   value="http://example.com/people/scots#knapfs">
  <label>Lordship of Knapdale</label>
</node>
<node
   xml:id="ARGY"
   value="http://example.com/people/scots#argyfs">
  <label>Sherrifdome of Argyll</label>
</node>
<arc xml:id="EARLGALL" from="#EARL" to="#GALL">
  <label>INCLUDE</label>
</arc>
<arc
   xml:id="EARLARGY"
   from="#EARL"
   to="#ARGY"
   exclude="#PERTARGY #KNAPARGY">
  <label>IN</label>
</arc>
<arc xml:id="EARLPERT" from="#EARL" to="#PERT">
  <label>INCLUDE</label>
</arc>
<arc xml:id="PERTPER1" from="#PERT" to="#PER1">
  <label>INCLUDE</label>
</arc>
<arc xml:id="PERTPER2" from="#PERT" to="#PER2">
  <label>INCLUDE</label>
</arc>
<arc
   xml:id="PERTARGY"
   from="#PERT"
   to="#ARGY"
   exclude="#EARLARGY #KNAPARGY">
  <label>IN</label>
</arc>
<arc xml:id="PER1KNAP" from="#PER1" to="#KNAP">
  <label>BY</label>
</arc>
<arc xml:id="PER2KNAP" from="#PER2" to="#KNAP">
  <label>PART OF</label>
</arc>
<arc
   xml:id="KNAPARGY"
   from="#KNAP"
   to="#ARGY"
   exclude="#EARLARGY #PERTARGY">
  <label>IN</label>
</arc>
</graph>

19.2 TreesTEI: Trees¶

A tree is a connected acyclic graph. That is, it is possible in a tree graph to follow a path from any vertex to any other vertex, but there are no paths that lead from any vertex to itself. A rooted tree is a directed graph based on a tree; that is, the arcs in the graph correspond to the arcs of a tree such that there is exactly one node, called the root, for which there is a path from that node to all other nodes in the graph. For our purposes, we may ignore all trees except for rooted trees, and hence we shall use the tree element for rooted trees, and the root element for its root. The nodes adjacent to a given node are called its children, and the node adjacent from a given node is called its parent. Nodes with both a parent and children are called internal nodes, for which we use the iNode element. A node with no children is tagged as a leaf. If the children of a node are ordered from left to right, then we say that that node is ordered. If all the nodes of a tree are ordered, then we say that the tree is an ordered tree. If some of the nodes of a tree are ordered and others are not, then the tree is a partially ordered tree. The ordering of nodes and trees may be specified by an attribute; we take the default ordering for trees to be ordered, that roots inherit their ordering from the trees in which they occur, and internal nodes inherit their ordering from their parents. Finally, we permit a node to be specified as following other nodes, which (when its parent is ordered) it would be assumed to precede, giving rise to crossing arcs. The elements used for the encoding of trees have the following descriptions and attributes.

tree encodes a tree, which is made up of a root, internal nodes, leaves, and arcs from root to leaves.

arity	gives the maximum number of children of the root and internal nodes of the tree.
ord	(ordered) indicates whether or not the tree is ordered, or if it is partially ordered.
order	gives the order of the tree, i.e., the number of its nodes.

root (root node) represents the root node of a tree.

value	provides the value of the root, which is a feature structure or other analytic element.
children	provides a list of identifiers of the elements which are the children of the root node.
ord	(ordered) indicates whether or not the root is ordered.
outDegree	gives the out degree of the root, the number of its children.

iNode (intermediate (or internal) node) represents an intermediate (or internal) node of a tree.

value	provides the value of an intermediate node, which is a feature structure or other analytic element.
children	provides a list of identifiers of the elements which are the children of the intermediate node.
parent	provides the identifier of the element which is the parent of this node.
ord	(ordered) indicates whether or not the internal node is ordered.
follow	provides an identifier of the element which this node follows.
outDegree	gives the out degree of an intermediate node, the number of its children.

leaf encodes the leaves (terminal nodes) of a tree.
value provides a pointer to a feature structure or other analytic element.
parent provides the identifier of parent of a leaf.
follow provides an identifier of an element which this leaf follows.

Here is an example of a tree. It represents the order in which the operators of addition (symbolized by +), exponentiation (symbolized by **) and division (symbolized by /) are applied in evaluating the arithmetic formula ((a**2)+(b**2))/((a+b)**2). In drawing the graph, the root is placed on the far right, and directionality is presumed to be to the left.

In this encoding, the arity attribute represents the arity of the tree, which is the greatest value of the outDegree attribute for any of the nodes in the tree. If, as in this case, arity is 2, we say that the tree is a binary tree.

Since the left-to-right (or top-to-bottom!) order of the children of the two + nodes does not affect the arithmetic result in this case, we could represent in this tree all of the arithmetically equivalent formulas involving its leaves, by specifying the attribute ord as false on those two iNode elements, the attribute ord as true on the root and other iNode elements, and the attribute ord as partial on the tree element, as follows.

This encoding represents all of the following:

((a**2)+(b**2))/((a+b)**2)
((b**2)+(a**2))/((a+b)**2)
((a**2)+(b**2))/((b+a)**2)
((b**2)+(a**2))/((a+b)**2)

Linguistic phrase structure is very commonly represented by trees. Here is an example of phrase structure represented by an ordered tree with its root at the top, and a possible encoding.

<tree
  n="ex3"
  ord="true"
  arity="2"
  order="8">
<root xml:id="GD-PP1" children="#GD-P1 #GD-NP1">
  <label>PP</label>
</root>
<iNode xml:id="GD-P1" parent="#GD-PP1" children="#GD-WITH1">
  <label>P</label>
</iNode>
<leaf xml:id="GD-WITH1" parent="#GD-P1">
  <label>with</label>
</leaf>
<iNode xml:id="GD-NP1" parent="#GD-PP1" children="#GD-THE1 #GD-PERI1">
  <label>NP</label>
</iNode>
<iNode xml:id="GD-ART1" parent="#GD-NP1" children="#GD-THE1">
  <label>Art</label>
</iNode>
<leaf xml:id="GD-THE1" parent="#GD-ART1">
  <label>the</label>
</leaf>
<iNode xml:id="GD-N1" parent="#GD-NP1" children="#GD-PERI1">
  <label>N</label>
</iNode>
<leaf xml:id="GD-PERI1" parent="#GD-N1">
  <label>periscope</label>
</leaf>
</tree>

Finally, here is an example of an ordered tree, in which a particular node which ordinarily would precede another is specified as following it. In the drawing, the xxx symbol indicates that the arc from VB to PT crosses the arc from VP to PN.

value	provides a pointer to a feature structure or other analytic element.
parent	provides the identifier of parent of a leaf.
follow	provides an identifier of an element which this leaf follows.