https://github.com/TEIC/TEI
Tip revision: 347c64fac3fa1a64ade0d8d1842813d4b8f7acec authored by Hugh Cayless on 12 May 2017, 16:57:59 UTC
Updates.
Updates.
Tip revision: 347c64f
GD.html
<!DOCTYPE html
SYSTEM "about:legacy-compat">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en"><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8" /><!--THIS FILE IS GENERATED FROM AN XML MASTER. DO NOT EDIT (4)--><title>19 Graphs, Networks, and Trees - The TEI Guidelines</title><meta property="Language" content="en" /><meta property="DC.Title" content="19 Graphs, Networks, and Trees - The TEI Guidelines" /><meta property="DC.Language" content="SCHEME=iso639 en" /><meta property="DC.Creator.Address" content="tei@oucs.ox.ac.uk" /><meta charset="utf-8" /><link href="guidelines.css" rel="stylesheet" type="text/css" /><link href="odd.css" rel="stylesheet" type="text/css" /><link rel="stylesheet" media="print" type="text/css" href="guidelines-print.css" /><script type="text/javascript" src="jquery-1.2.6.min.js"></script><script type="text/javascript" src="columnlist.js"></script><script type="text/javascript" src="popupFootnotes.js"></script><script type="text/javascript">
$(function() {
$('ul.attrefs-class').columnizeList({cols:3,width:30,unit:'%'});
$('ul.attrefs-element').columnizeList({cols:3,width:30,unit:'%'});
$(".displayRelaxButton").click(function() {
$(this).parent().find('.RNG_XML').toggle();
$(this).parent().find('.RNG_Compact').toggle();
});
$(".tocTree .showhide").click(function() {
$(this).find(".tocShow,.tocHide").toggle();
$(this).parent().find("ul.continuedtoc").toggle();
});
})
</script><script type="text/javascript"><!--
var displayXML=0;
states=new Array()
states[0]="element-a"
states[1]="element-b"
states[2]="element-c"
states[3]="element-d"
states[4]="element-e"
states[5]="element-f"
states[6]="element-g"
states[7]="element-h"
states[8]="element-i"
states[9]="element-j"
states[10]="element-k"
states[11]="element-l"
states[12]="element-m"
states[13]="element-n"
states[14]="element-o"
states[15]="element-p"
states[16]="element-q"
states[17]="element-r"
states[18]="element-s"
states[19]="element-t"
states[20]="element-u"
states[21]="element-v"
states[22]="element-w"
states[23]="element-x"
states[24]="element-y"
states[25]="element-z"
function startUp() {
}
function hideallExcept(elm) {
for (var i = 0; i < states.length; i++) {
var layer;
if (layer = document.getElementById(states[i]) ) {
if (states[i] != elm) {
layer.style.display = "none";
}
else {
layer.style.display = "block";
}
}
}
var mod;
if ( mod = document.getElementById('byMod') ) {
mod.style.display = "none";
}
}
function showall() {
for (var i = 0; i < states.length; i++) {
var layer;
if (layer = document.getElementById(states[i]) ) {
layer.style.display = "block";
}
}
}
function showByMod() {
hideallExcept('');
var mod;
if (mod = document.getElementById('byMod') ) {
mod.style.display = "block";
}
}
--></script></head><body><div id="container"><div id="banner"><img src="Images/banner.jpg" alt="Text Encoding Initiative logo and banner" /></div></div><div class="mainhead"><h1>P5:
Guidelines for Electronic Text Encoding and Interchange</h1><p>Version 3.1.1a. Last updated on
10th May 2017, revision bd8dda3</p></div><div id="onecol" class="main-content"><h2><span class="headingNumber">19 </span>Graphs, Networks, and Trees</h2><div class="div1" id="GD"><div class="miniTOC miniTOC_left"><p><span class="subtochead">Table of contents</span></p><div class="subtoc"><ul class="subtoc"><li class="subtoc"><a class="subtoc" href="GD.html#GDGR" title="Graphs and Digraphs">19.1 Graphs and Digraphs</a></li><li class="subtoc"><a class="subtoc" href="GD.html#GDTR" title="Trees">19.2 Trees</a></li><li class="subtoc"><a class="subtoc" href="GD.html#GDAT" title="Another Tree Notation">19.3 Another Tree Notation</a></li><li class="subtoc"><a class="subtoc" href="GD.html#GDstem" title="Representing Textual Transmission">19.4 Representing Textual Transmission</a></li><li class="subtoc"><a class="subtoc" href="GD.html#index-body.1_div.19_div.5">19.5 Module for Graphs, Networks, and Trees</a></li></ul></div><ul class="subtoc"><li class="subtoc"><span class="previousLink"> « </span><a class="navigation" href="FS.html"><span class="headingNumber">18 </span>Feature Structures</a></li><li class="subtoc"><span class="nextLink"> » </span><a class="navigation" href="NH.html"><span class="headingNumber">20 </span>Non-hierarchical Structures</a></li><li class="subtoc"><a class="navigation" href="index.html">Home</a></li></ul></div><p>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. </p><ul class="bulleted"><li class="item"><span class="term">Graphs</span>, in the strictly mathematical sense, consist of points, often called <span class="term">nodes</span> or <span class="term">vertices</span>, and connections among them, called <span class="term">arcs</span>, or under certain conditions, <span class="term">edges</span>. Among the various types of graphs are <span class="term">networks</span> and <span class="term">trees</span>. Graphs generally and networks in particular are dealt with directly below. Trees are dealt with separately in sections <a class="link_ptr" href="GD.html#GDTR" title="Trees"><span class="headingNumber">19.2 </span>Trees</a> and <a class="link_ptr" href="GD.html#GDAT" title="Another Tree Notation"><span class="headingNumber">19.3 </span>Another Tree Notation</a>.<span id="Note115_return"><a class="notelink" title="The treatment here is largely based on the characterizations of graph types in" href="#Note115"><sup>78</sup></a></span></li><li class="item"><span class="term">Charts</span>, 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 <a class="link_ptr" href="FT.html" title="22"><span class="headingNumber">14 </span>Tables, Formulæ, Graphics and Notated Music</a>.</li></ul><p>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.</p><div class="div2" id="GDGR"><div class="miniTOC miniTOC_right"><ul class="subtoc"><li class="subtoc"></li><li class="subtoc"><span class="nextLink"> » </span><a class="navigation" href="GD.html#GDTR"><span class="headingNumber">19.2 </span>Trees</a></li><li class="subtoc"><a class="navigation" href="index.html">Home</a></li></ul></div><h3><span class="bookmarklink"><a class="bookmarklink" href="#GDGR" title="link to this section "><span class="invisible">TEI: Graphs and Digraphs</span><span class="pilcrow">¶</span></a></span><span class="headingNumber">19.1 </span><span class="head">Graphs and Digraphs</span></h3><p>Broadly speaking, graphs can be divided into two types: <span class="term">undirected</span> and <span class="term">directed</span>. An undirected graph is a set of <span class="term">nodes</span> (or <span class="term">vertices</span>) together with a set of pairs of those vertices, called <span class="term">arcs</span> or <span class="term">edges</span>. Each node in an arc of an undirected graph is said to be <span class="term">incident</span> with that arc, and the two vertices (nodes) which make up an arc are said to be <span class="term">adjacent</span>. An directed graph is like an undirected graph except that the arcs are <span class="term">ordered pairs</span> of nodes. In the case of directed graphs, the term <span class="term">edge</span> is not used; moreover, each arc in a directed graph is said to be <span class="term">adjacent from</span> the node from which the arc emanates, and <span class="term">adjacent to </span> the node to which the arc is directed. We use the element <a class="gi" title="encodes a graph, which is a collection of nodes, and arcs which connect the nodes." href="ref-graph.html">graph</a> to encode graphs as a whole, <a class="gi" title="encodes a node, a possibly labeled point in a graph." href="ref-node.html">node</a> to encode nodes or vertices, and <a class="gi" title="encodes an arc, the connection from one node to another in a graph." href="ref-arc.html">arc</a> to encode arcs or edges; arcs can also be encoded by attributes on the <a class="gi" title="encodes a node, a possibly labeled point in a graph." href="ref-node.html">node</a> element. These elements have the following descriptions and attributes: </p><ul class="specList"><li><span class="specList-elementSpec"><a href="ref-graph.html">graph</a></span> encodes a graph, which is a collection of nodes, and arcs which connect the nodes.</li><li><span class="specList-elementSpec"><a href="ref-node.html">node</a></span> encodes a node, a possibly labeled point in a graph.</li><li><span class="specList-elementSpec"><a href="ref-arc.html">arc</a></span> encodes an arc, the connection from one node to another in a graph.</li></ul><p>Before proceeding, some additional terminology may be helpful. We define a <span class="term">path</span> 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 <span class="term">cyclic path</span>, or <span class="term">cycle</span> is a path leading from a particular node back to itself. A graph that contains at least one cycle is said to be <span class="term">cyclic</span>; otherwise it is <span class="term">acyclic</span>. We say, finally, that a graph is <span class="term">connected</span> 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 <span class="term">disconnected</span>.</p><p>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.</p><p><img src="Images/graph1.jpg" alt="" class="graphic" style=" width:70%;" /></p><div class="p">Next is a markup of the graph, using <a class="gi" title="encodes an arc, the connection from one node to another in a graph." href="ref-arc.html">arc</a> elements to encode the arcs. <div id="index-egXML-d52e133669" class="pre egXML_valid"><span class="element"><graph <span class="attribute">type</span>="<span class="attributevalue">undirected</span>" <span class="attribute">xml:id</span>="<span class="attributevalue">CUG1</span>"<br /> <span class="attribute">order</span>="<span class="attributevalue">5</span>" <span class="attribute">size</span>="<span class="attributevalue">4</span>"></span><br /> <span class="element"><label></span>Airline Connections in Southwestern USA<span class="element"></label></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LAX</span>" <span class="attribute">degree</span>="<span class="attributevalue">2</span>"></span><br /> <span class="element"><label></span>LAX<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LVG</span>" <span class="attribute">degree</span>="<span class="attributevalue">2</span>"></span><br /> <span class="element"><label></span>LVG<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">PHX</span>" <span class="attribute">degree</span>="<span class="attributevalue">3</span>"></span><br /> <span class="element"><label></span>PHX<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">TUS</span>" <span class="attribute">degree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>TUS<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">CIB</span>" <span class="attribute">degree</span>="<span class="attributevalue">0</span>"></span><br /> <span class="element"><label></span>CIB<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#LAX</span>" <span class="attribute">to</span>="<span class="attributevalue">#LVG</span>"/></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#LAX</span>" <span class="attribute">to</span>="<span class="attributevalue">#PHX</span>"/></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#LVG</span>" <span class="attribute">to</span>="<span class="attributevalue">#PHX</span>"/></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#PHX</span>" <span class="attribute">to</span>="<span class="attributevalue">#TUS</span>"/></span><br /><span class="element"></graph></span></div></div><p>The first child element of <a class="gi" title="encodes a graph, which is a collection of nodes, and arcs which connect the nodes." href="ref-graph.html">graph</a> may be a <a class="gi" title="contains any label or heading used to identify part of a text, typically but not exclusively in a list or glossary." href="ref-label.html">label</a> to record a label for the graph; similarly, the <a class="gi" title="contains any label or heading used to identify part of a text, typically but not exclusively in a list or glossary." href="ref-label.html">label</a> child of each <a class="gi" title="encodes a node, a possibly labeled point in a graph." href="ref-node.html">node</a> element records the labels of that node. The <span class="att">order</span> and <span class="att">size</span> attributes on the <a class="gi" title="encodes a graph, which is a collection of nodes, and arcs which connect the nodes." href="ref-graph.html">graph</a> 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 <span class="att">degree</span> attribute on the <a class="gi" title="encodes a node, a possibly labeled point in a graph." href="ref-node.html">node</a> 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 <span class="att">from</span> and <span class="att">to</span> attributes on the <a class="gi" title="encodes an arc, the connection from one node to another in a graph." href="ref-arc.html">arc</a> elements provide pointers to the nodes connected by those arcs. Since the graph is undirected, no directionality is implied by the use of the <span class="att">from</span> and <span class="att">to</span> attributes; the values of these attributes could be interchanged in each arc without changing the graph.</p><div class="p">The <span class="att">adj</span>, <span class="att">adjFrom</span>, and <span class="att">adjTo</span> attributes of the <a class="gi" title="encodes a node, a possibly labeled point in a graph." href="ref-node.html">node</a> 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 <span class="att">adj</span> attribute is to be used for undirected graphs, and the <span class="att">adjFrom</span> and <span class="att">adjTo</span> 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 <span class="att">adj</span> attribute to represent the arcs. <div id="index-egXML-d52e133766" class="pre egXML_valid"><span class="element"><graph <span class="attribute">type</span>="<span class="attributevalue">undirected</span>" <span class="attribute">xml:id</span>="<span class="attributevalue">CUG2</span>"<br /> <span class="attribute">order</span>="<span class="attributevalue">5</span>" <span class="attribute">size</span>="<span class="attributevalue">4</span>"></span><br /> <span class="element"><label></span>Airline Connections in Southwestern USA<span class="element"></label></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LAX2</span>" <span class="attribute">degree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">adj</span>="<span class="attributevalue">#LVG2 #PHX2</span>"></span><br /> <span class="element"><label></span>LAX2<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LVG2</span>" <span class="attribute">degree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">adj</span>="<span class="attributevalue">#LAX2 #PHX2</span>"></span><br /> <span class="element"><label></span>LVG2<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">PHX2</span>" <span class="attribute">degree</span>="<span class="attributevalue">3</span>"<br /> <span class="attribute">adj</span>="<span class="attributevalue">#LAX2 #LVG2 #TUS2</span>"></span><br /> <span class="element"><label></span>PHX2<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">TUS2</span>" <span class="attribute">degree</span>="<span class="attributevalue">1</span>" <span class="attribute">adj</span>="<span class="attributevalue">#PHX2</span>"></span><br /> <span class="element"><label></span>TUS2<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">CIB2</span>" <span class="attribute">degree</span>="<span class="attributevalue">0</span>"></span><br /> <span class="element"><label></span>CIB2<span class="element"></label></span><br /> <span class="element"></node></span><br /><span class="element"></graph></span></div></div><div class="p">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 <a class="gi" title="encodes a node, a possibly labeled point in a graph." href="ref-node.html">node</a> 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 <a class="gi" title="encodes an arc, the connection from one node to another in a graph." href="ref-arc.html">arc</a> element). Here is a less redundant representation of the same graph. <div id="index-egXML-d52e133793" class="pre egXML_valid"><span class="element"><graph <span class="attribute">type</span>="<span class="attributevalue">undirected</span>" <span class="attribute">xml:id</span>="<span class="attributevalue">CUG3</span>"<br /> <span class="attribute">order</span>="<span class="attributevalue">5</span>" <span class="attribute">size</span>="<span class="attributevalue">4</span>"></span><br /> <span class="element"><label></span>Airline Connections in Southwestern USA<span class="element"></label></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LAX3</span>" <span class="attribute">degree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">adj</span>="<span class="attributevalue">#LVG3 #PHX3</span>"></span><br /> <span class="element"><label></span>LAX3<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LVG3</span>" <span class="attribute">degree</span>="<span class="attributevalue">2</span>" <span class="attribute">adj</span>="<span class="attributevalue">#PHX3</span>"></span><br /> <span class="element"><label></span>LVG3<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">PHX3</span>" <span class="attribute">degree</span>="<span class="attributevalue">3</span>" <span class="attribute">adj</span>="<span class="attributevalue">#TUS3</span>"></span><br /> <span class="element"><label></span>PHX3<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">TUS3</span>" <span class="attribute">degree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>TUS3<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">CIB3</span>" <span class="attribute">degree</span>="<span class="attributevalue">0</span>"></span><br /> <span class="element"><label></span>CIB3<span class="element"></label></span><br /> <span class="element"></node></span><br /><span class="element"></graph></span></div></div><p>Although in many cases the <a class="gi" title="encodes an arc, the connection from one node to another in a graph." href="ref-arc.html">arc</a> 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 <span class="att">xml:id</span>, <span class="att">rend</span>, and a child <a class="gi" title="contains any label or heading used to identify part of a text, typically but not exclusively in a list or glossary." href="ref-label.html">label</a> element).</p><p>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.</p><p><img src="Images/graph2.jpg" alt="" class="graphic" style=" width:70%;" /></p><div class="p">Here is an encoding of this graph, using the <a class="gi" title="encodes an arc, the connection from one node to another in a graph." href="ref-arc.html">arc</a> element to designate the arcs. <div id="index-egXML-d52e133835" class="pre egXML_valid"><span class="element"><graph <span class="attribute">type</span>="<span class="attributevalue">directed</span>" <span class="attribute">xml:id</span>="<span class="attributevalue">RDG1</span>"<br /> <span class="attribute">order</span>="<span class="attributevalue">5</span>" <span class="attribute">size</span>="<span class="attributevalue">5</span>"></span><br /> <span class="element"><label></span>Selected Airline Routes in Southwestern USA<span class="element"></label></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LAX4</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>LAX4<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LVG4</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>LVG4<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">PHX4</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">2</span>"></span><br /> <span class="element"><label></span>PHX4<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">TUS4</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>TUS4<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">CIB4</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">0</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">0</span>"></span><br /> <span class="element"><label></span>CIB4<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#LAX4</span>" <span class="attribute">to</span>="<span class="attributevalue">#LVG4</span>"/></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#LVG4</span>" <span class="attribute">to</span>="<span class="attributevalue">#PHX4</span>"/></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#PHX4</span>" <span class="attribute">to</span>="<span class="attributevalue">#LAX4</span>"/></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#PHX4</span>" <span class="attribute">to</span>="<span class="attributevalue">#TUS4</span>"/></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#TUS4</span>" <span class="attribute">to</span>="<span class="attributevalue">#PHX4</span>"/></span><br /><span class="element"></graph></span></div> The attributes <span class="att">inDegree</span> and <span class="att">outDegree</span> indicate the number of nodes which are adjacent to and from the node concerned respectively.</div><div class="p">Here is another encoding of the graph, using the <span class="att">adjTo</span> and <span class="att">adjFrom</span> attributes on nodes to designate the arcs. <div id="index-egXML-d52e133874" class="pre egXML_valid"><span class="element"><graph <span class="attribute">type</span>="<span class="attributevalue">directed</span>" <span class="attribute">xml:id</span>="<span class="attributevalue">RDG2</span>"<br /> <span class="attribute">order</span>="<span class="attributevalue">5</span>" <span class="attribute">size</span>="<span class="attributevalue">5</span>"></span><br /> <span class="element"><label></span>Selected Airline Routes in Southwestern USA<span class="element"></label></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LAX5</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>" <span class="attribute">adjTo</span>="<span class="attributevalue">#LVG5</span>" <span class="attribute">adjFrom</span>="<span class="attributevalue">#PHX5</span>"></span><br /> <span class="element"><label></span>LAX5<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LVG5</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>" <span class="attribute">adjFrom</span>="<span class="attributevalue">#LAX5</span>" <span class="attribute">adjTo</span>="<span class="attributevalue">#PHX5</span>"></span><br /> <span class="element"><label></span>LVG5<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">PHX5</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">2</span>" <span class="attribute">adjTo</span>="<span class="attributevalue">#LAX5 #TUS</span>" <span class="attribute">adjFrom</span>="<span class="attributevalue">#LVG5 #TUS5</span>"></span><br /> <span class="element"><label></span>PHX5<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">TUS5</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>" <span class="attribute">adjTo</span>="<span class="attributevalue">#PHX5</span>" <span class="attribute">adjFrom</span>="<span class="attributevalue">#PHX5</span>"></span><br /> <span class="element"><label></span>TUS5<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">CIB5</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">0</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">0</span>"></span><br /> <span class="element"><label></span>CIB5<span class="element"></label></span><br /> <span class="element"></node></span><br /><span class="element"></graph></span></div></div><div class="p">If we wish to label the arcs, say with flight numbers, then <a class="gi" title="encodes an arc, the connection from one node to another in a graph." href="ref-arc.html">arc</a> elements must be used to hold the <a class="gi" title="contains any label or heading used to identify part of a text, typically but not exclusively in a list or glossary." href="ref-label.html">label</a> elements, as in the following example. <div id="index-egXML-d52e133901" class="pre egXML_valid"><span class="element"><graph <span class="attribute">type</span>="<span class="attributevalue">directed</span>" <span class="attribute">xml:id</span>="<span class="attributevalue">RDG3</span>"<br /> <span class="attribute">order</span>="<span class="attributevalue">5</span>" <span class="attribute">size</span>="<span class="attributevalue">5</span>"></span><br /> <span class="element"><label></span>Selected Airline Routes in Southwestern USA<span class="element"></label></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LAX6</span>"></span><br /> <span class="element"><label></span>LAX6<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">LVG6</span>"></span><br /> <span class="element"><label></span>LVG6<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">PHX6</span>"></span><br /> <span class="element"><label></span>PHX6<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">TUS6</span>"></span><br /> <span class="element"><label></span>TUS6<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">CIB6</span>"></span><br /> <span class="element"><label></span>CIB6<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#LAX6</span>" <span class="attribute">to</span>="<span class="attributevalue">#LVG6</span>"></span><br /> <span class="element"><label></span>SW117<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#LVG6</span>" <span class="attribute">to</span>="<span class="attributevalue">#PHX6</span>"></span><br /> <span class="element"><label></span>SW711<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#PHX6</span>" <span class="attribute">to</span>="<span class="attributevalue">#LAX6</span>"></span><br /> <span class="element"><label></span>AA218<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#PHX6</span>" <span class="attribute">to</span>="<span class="attributevalue">#TUS6</span>"></span><br /> <span class="element"><label></span>AW229<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#TUS6</span>" <span class="attribute">to</span>="<span class="attributevalue">#PHX6</span>"></span><br /> <span class="element"><label></span>AW225<span class="element"></label></span><br /> <span class="element"></arc></span><br /><span class="element"></graph></span></div> </div><div class="div3" id="GDTN"><div class="miniTOC miniTOC_right"><ul class="subtoc"><li class="subtoc"></li><li class="subtoc"><span class="nextLink"> » </span><a class="navigation" href="GD.html#GDFT"><span class="headingNumber">19.1.2 </span>Family Trees</a></li><li class="subtoc"><a class="navigation" href="index.html">Home</a></li></ul></div><h4><span class="bookmarklink"><a class="bookmarklink" href="#GDTN" title="link to this section "><span class="invisible">TEI: Transition Networks</span><span class="pilcrow">¶</span></a></span><span class="headingNumber">19.1.1 </span><span class="head">Transition Networks</span></h4><p>For encoding transition networks and other kinds of directed graphs in which distinctions among types of nodes must be made, the <span class="att">type</span> attribute is provided for <a class="gi" title="encodes a node, a possibly labeled point in a graph." href="ref-node.html">node</a> elements. In the following example, the <span class="term">initial</span> and <span class="term">final</span> nodes (or <span class="term">states</span>) 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. </p><div class="p"><img src="Images/graph3.jpg" alt="" class="graphic" style=" width:60%;" /> <div id="index-egXML-d52e134948" class="pre egXML_valid"><span class="element"><graph <span class="attribute">type</span>="<span class="attributevalue">network-transition</span>"<br /> <span class="attribute">xml:id</span>="<span class="attributevalue">SS8</span>" <span class="attribute">order</span>="<span class="attributevalue">5</span>" <span class="attribute">size</span>="<span class="attributevalue">6</span>"></span><br /> <span class="element"><label></span>(8)<span class="element"></label></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">Q0</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">0</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>" <span class="attribute">type</span>="<span class="attributevalue">initial</span>"/></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">Q1</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">3</span>"/></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">Q2</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"/></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">Q3</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"/></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">Q4</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">0</span>" <span class="attribute">type</span>="<span class="attributevalue">final</span>"/></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#Q0</span>" <span class="attribute">to</span>="<span class="attributevalue">#Q1</span>"></span><br /> <span class="element"><label></span>THE<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#Q1</span>" <span class="attribute">to</span>="<span class="attributevalue">#Q1</span>"></span><br /> <span class="element"><label></span>OLD<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#Q1</span>" <span class="attribute">to</span>="<span class="attributevalue">#Q2</span>"></span><br /> <span class="element"><label></span>MAN<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#Q1</span>" <span class="attribute">to</span>="<span class="attributevalue">#Q3</span>"></span><br /> <span class="element"><label></span>MEN<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#Q2</span>" <span class="attribute">to</span>="<span class="attributevalue">#Q4</span>"></span><br /> <span class="element"><label></span>COMES<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#Q3</span>" <span class="attribute">to</span>="<span class="attributevalue">#Q4</span>"></span><br /> <span class="element"><label></span>COME<span class="element"></label></span><br /> <span class="element"></arc></span><br /><span class="element"></graph></span></div></div><p>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.</p><div class="p"><img src="Images/graph4.jpg" alt="" class="graphic" style=" width:60%;" /> <div id="index-egXML-d52e134981" class="pre egXML_valid"><span class="element"><graph <span class="attribute">type</span>="<span class="attributevalue">transducer</span>" <span class="attribute">order</span>="<span class="attributevalue">7</span>" <span class="attribute">size</span>="<span class="attributevalue">10</span>"></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">T0</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">0</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">3</span>" <span class="attribute">type</span>="<span class="attributevalue">initial</span>"></span><br /> <span class="element"><label></span>0<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">T1</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>1<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">T2</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">2</span>"></span><br /> <span class="element"><label></span>2<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">T3</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">2</span>"></span><br /> <span class="element"><label></span>3<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">T4</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>4<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">T5</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>5<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">T6</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">0</span>" <span class="attribute">type</span>="<span class="attributevalue">final</span>"></span><br /> <span class="element"><label></span>6<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#T0</span>" <span class="attribute">to</span>="<span class="attributevalue">#T1</span>"></span><br /> <span class="element"><label></span>THE<span class="element"></label></span><br /> <span class="element"><label></span>L'<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#T0</span>" <span class="attribute">to</span>="<span class="attributevalue">#T2</span>"></span><br /> <span class="element"><label></span>THE<span class="element"></label></span><br /> <span class="element"><label></span>LE<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#T0</span>" <span class="attribute">to</span>="<span class="attributevalue">#T3</span>"></span><br /> <span class="element"><label></span>THE<span class="element"></label></span><br /> <span class="element"><label></span>LES<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#T1</span>" <span class="attribute">to</span>="<span class="attributevalue">#T4</span>"></span><br /> <span class="element"><label></span>MAN<span class="element"></label></span><br /> <span class="element"><label></span>HOMME<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#T2</span>" <span class="attribute">to</span>="<span class="attributevalue">#T1</span>"></span><br /> <span class="element"><label></span>OLD<span class="element"></label></span><br /> <span class="element"><label></span>VIEIL<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#T2</span>" <span class="attribute">to</span>="<span class="attributevalue">#T2</span>"></span><br /> <span class="element"><label></span>OLD<span class="element"></label></span><br /> <span class="element"><label></span>VIEIL<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#T3</span>" <span class="attribute">to</span>="<span class="attributevalue">#T3</span>"></span><br /> <span class="element"><label></span>OLD<span class="element"></label></span><br /> <span class="element"><label></span>VIEUX<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#T3</span>" <span class="attribute">to</span>="<span class="attributevalue">#T5</span>"></span><br /> <span class="element"><label></span>MEN<span class="element"></label></span><br /> <span class="element"><label></span>HOMMES<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#T4</span>" <span class="attribute">to</span>="<span class="attributevalue">#T6</span>"></span><br /> <span class="element"><label></span>COMES<span class="element"></label></span><br /> <span class="element"><label></span>VIENT<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#T5</span>" <span class="attribute">to</span>="<span class="attributevalue">#T6</span>"></span><br /> <span class="element"><label></span>COME<span class="element"></label></span><br /> <span class="element"><label></span>VIENNENT<span class="element"></label></span><br /> <span class="element"></arc></span><br /><span class="element"></graph></span></div></div></div><div class="div3" id="GDFT"><div class="miniTOC miniTOC_right"><ul class="subtoc"><li class="subtoc"><span class="previousLink"> « </span><a class="navigation" href="GD.html#GDTN"><span class="headingNumber">19.1.1 </span>Transition Networks</a></li><li class="subtoc"><span class="nextLink"> » </span><a class="navigation" href="GD.html#GDHI"><span class="headingNumber">19.1.3 </span>Historical Interpretation</a></li><li class="subtoc"><a class="navigation" href="index.html">Home</a></li></ul></div><h4><span class="bookmarklink"><a class="bookmarklink" href="#GDFT" title="link to this section "><span class="invisible">TEI: Family Trees</span><span class="pilcrow">¶</span></a></span><span class="headingNumber">19.1.2 </span><span class="head">Family Trees</span></h4><p>The next example provides an encoding a portion of a family tree<span id="Note116_return"><a class="notelink" title="The family tree is that of the mathematician and philosopher Bertrand Russell, whose third wife was commonly known as Peter. The information presented…" href="#Note116"><sup>79</sup></a></span> 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 <a class="link_ptr" href="FS.html#FSFL" title="Feature Libraries and FeatureValue Libraries"><span class="headingNumber">18.4 </span>Feature Libraries and Feature-Value Libraries</a>). We can use the <span class="att">value</span> attribute on <a class="gi" title="encodes a node, a possibly labeled point in a graph." href="ref-node.html">node</a> 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.</p><div class="p"><img src="Images/graph5.jpg" alt="" class="graphic" style=" width:70%;" /> <div id="index-egXML-d52e135078" class="pre egXML_valid"><span class="element"><graph <span class="attribute">type</span>="<span class="attributevalue">family_tree</span>" <span class="attribute">order</span>="<span class="attributevalue">13</span>"<br /> <span class="attribute">size</span>="<span class="attributevalue">12</span>"></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">KATHR</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/russell-fs/tei/kr1</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">0</span>" <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>Katherine<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">AMBER</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/russell-fs/tei/ar1</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">0</span>" <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>Amberley<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">KAR</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">3</span>"></span><br /> <span class="element"><label></span>K+A<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">BERTR</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/russell-fs/tei/br1</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>" <span class="attribute">outDegree</span>="<span class="attributevalue">2</span>"></span><br /> <span class="element"><label></span>Bertrand<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">PETER</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/russell-fs/tei/pr1</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">0</span>" <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>Peter<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">DORAR</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/russell-fs/tei/dr1</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">0</span>" <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>Dora<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">PBR</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">1</span>"></span><br /> <span class="element"><label></span>P+B<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">DBR</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">outDegree</span>="<span class="attributevalue">2</span>"></span><br /> <span class="element"><label></span>D+B<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">FRANR</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/russell-fs/tei/fr1</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>" <span class="attribute">outDegree</span>="<span class="attributevalue">0</span>"></span><br /> <span class="element"><label></span>Frank<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">RACHR</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/russell-fs/tei/rr1</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>" <span class="attribute">outDegree</span>="<span class="attributevalue">0</span>"></span><br /> <span class="element"><label></span>Rachel<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">CONRR</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/russell-fs/tei/cr1</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>" <span class="attribute">outDegree</span>="<span class="attributevalue">0</span>"></span><br /> <span class="element"><label></span>Conrad<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">KATER</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/russell-fs/tei/kr2</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>" <span class="attribute">outDegree</span>="<span class="attributevalue">0</span>"></span><br /> <span class="element"><label></span>Kate<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">JOHNR</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/russell-fs/tei/jr1</span>" <span class="attribute">inDegree</span>="<span class="attributevalue">1</span>" <span class="attribute">outDegree</span>="<span class="attributevalue">0</span>"></span><br /> <span class="element"><label></span>John<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#KATHR</span>" <span class="attribute">to</span>="<span class="attributevalue">#KAR</span>"></span><br /> <span class="element"><label></span>Mo<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#AMBER</span>" <span class="attribute">to</span>="<span class="attributevalue">#KAR</span>"></span><br /> <span class="element"><label></span>Fa<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#KAR</span>" <span class="attribute">to</span>="<span class="attributevalue">#BERTR</span>"></span><br /> <span class="element"><label></span>So<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#KAR</span>" <span class="attribute">to</span>="<span class="attributevalue">#FRANR</span>"></span><br /> <span class="element"><label></span>So<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#KAR</span>" <span class="attribute">to</span>="<span class="attributevalue">#RACHR</span>"></span><br /> <span class="element"><label></span>Da<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#PETER</span>" <span class="attribute">to</span>="<span class="attributevalue">#PBR</span>"></span><br /> <span class="element"><label></span>Mo<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#BERTR</span>" <span class="attribute">to</span>="<span class="attributevalue">#PBR</span>"></span><br /> <span class="element"><label></span>Fa<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#PBR</span>" <span class="attribute">to</span>="<span class="attributevalue">#CONRR</span>"></span><br /> <span class="element"><label></span>So<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#DORAR</span>" <span class="attribute">to</span>="<span class="attributevalue">#DBR</span>"></span><br /> <span class="element"><label></span>Mo<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#BERTR</span>" <span class="attribute">to</span>="<span class="attributevalue">#DBR</span>"></span><br /> <span class="element"><label></span>Fa<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#DBR</span>" <span class="attribute">to</span>="<span class="attributevalue">#KATER</span>"></span><br /> <span class="element"><label></span>Da<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">from</span>="<span class="attributevalue">#DBR</span>" <span class="attribute">to</span>="<span class="attributevalue">#JOHNR</span>"></span><br /> <span class="element"><label></span>So<span class="element"></label></span><br /> <span class="element"></arc></span><br /><span class="element"></graph></span><div style="float: right;"><a href="BIB.html#GDFT-eg-12">bibliography</a> </div></div> </div></div><div class="div3" id="GDHI"><div class="miniTOC miniTOC_right"><ul class="subtoc"><li class="subtoc"><span class="previousLink"> « </span><a class="navigation" href="GD.html#GDFT"><span class="headingNumber">19.1.2 </span>Family Trees</a></li><li class="subtoc"></li><li class="subtoc"><a class="navigation" href="index.html">Home</a></li></ul></div><h4><span class="bookmarklink"><a class="bookmarklink" href="#GDHI" title="link to this section "><span class="invisible">TEI: Historical Interpretation</span><span class="pilcrow">¶</span></a></span><span class="headingNumber">19.1.3 </span><span class="head">Historical Interpretation</span></h4><p>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 <span class="q">‘[...]’</span> marks illegible passages): </p><div class="q"><p>Item instrument of Sasine given the said Hector Mcneil confirmed and dated 28 May 1632 [...] at Edinburgh upon the 15 June 1632</p> <p>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 ...</p> <p>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</p> <p>[description of other lands granted follows ...]</p> <p>This Charter is dated at Inverary the 15th May 1669</p></div><p>In this example, we are concerned with the land and pertinents (i.e. accompanying sources of revenue) described as <span class="q">‘the two merk land of old extent of Gallachalzie with the pertinents by and in the lordship of Knapdale within the sherrifdom of Argyll’</span>.</p><p>The passage concerns the following pieces of land: </p><ul class="bulleted"><li class="item">the Earl of Argyll's land (i.e. the lands granted by this clause of the sasine)</li><li class="item">two mark of land in Gallachalzie</li><li class="item">the pertinents for this land</li><li class="item">the Lordship of Knapdale</li><li class="item">the sherrifdom of Argyll</li></ul><p> We will represent these geographic entities as nodes in a graph. Arcs in the graph will represent the following relationships among them: </p><ul class="bulleted"><li class="item">containment (INCLUDE)</li><li class="item">location within (IN)</li><li class="item">contiguity (BY)</li><li class="item">constituency (PART OF)</li></ul><p> Note that these relationships are logically related: <span class="q">‘include’</span> and <span class="q">‘in’</span>, 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.</p><p>Let us assume that feature-structure analyses are available which describe Gallachalzie, Knapdale, and Argyll. We will link to those feature structures using the <span class="att">value</span> attribute on the nodes representing those places. However, there may be some uncertainty as to which noun phrase is modified by the phrase <span class="q">‘within the sheriffdome of Argyll’</span>: 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 <span class="att">exclude</span> attribute defined in chapter <a class="link_ptr" href="SA.html" title="14"><span class="headingNumber">16 </span>Linking, Segmentation, and Alignment</a>.<span id="Note117_return"><a class="notelink" title="That is, the three syntactic interpretations of the clause are mutually exclusive. The notion that the pertinents are in Argyll is clearly not inconsi…" href="#Note117"><sup>80</sup></a></span></p><p>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 <span class="att">exclude</span> attribute to indicate those arcs.</p><p><img src="Images/graph6.jpg" alt="" class="graphic" style=" width:80%;" /></p><div class="p">The graph formalizes the following relationships: <ul class="bulleted"><li class="item">the Earl of Argyll's land <span class="mentioned">includes</span> (the parcel of land in) Gallachalzie</li><li class="item">the Earl of Argyll's land <span class="mentioned">includes</span> the pertinents of that parcel</li><li class="item">the pertinents are (in part) <span class="mentioned">by</span> the Lordship of Knapdale</li><li class="item">the pertinents are (in part) <span class="mentioned">part of</span> the Lordship of Knapdale</li><li class="item">the Earl of Argyll's land, or the pertinents, or the Lordship of Knapdale, is <span class="mentioned">in</span> the Sherrifdom of Argyll</li></ul> We encode the graph thus: <div id="index-egXML-d52e135278" class="pre egXML_valid"><span class="element"><graph <span class="attribute">type</span>="<span class="attributevalue">directed</span>" <span class="attribute">order</span>="<span class="attributevalue">7</span>" <span class="attribute">size</span>="<span class="attributevalue">9</span>"></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">EARL</span>"></span><br /> <span class="element"><label></span>Earl of Argyll's land<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">GALL</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/people/scots#gall</span>"></span><br /> <span class="element"><label></span>Gallachalzie<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">PERT</span>"></span><br /> <span class="element"><label></span>Pertinents<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">PER1</span>"></span><br /> <span class="element"><label></span>Pertinents part<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">PER2</span>"></span><br /> <span class="element"><label></span>Pertinents part<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">KNAP</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/people/scots#knapfs</span>"></span><br /> <span class="element"><label></span>Lordship of Knapdale<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><node <span class="attribute">xml:id</span>="<span class="attributevalue">ARGY</span>"<br /> <span class="attribute">value</span>="<span class="attributevalue">http://example.com/people/scots#argyfs</span>"></span><br /> <span class="element"><label></span>Sherrifdome of Argyll<span class="element"></label></span><br /> <span class="element"></node></span><br /> <span class="element"><arc <span class="attribute">xml:id</span>="<span class="attributevalue">EARLGALL</span>" <span class="attribute">from</span>="<span class="attributevalue">#EARL</span>"<br /> <span class="attribute">to</span>="<span class="attributevalue">#GALL</span>"></span><br /> <span class="element"><label></span>INCLUDE<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">xml:id</span>="<span class="attributevalue">EARLARGY</span>" <span class="attribute">from</span>="<span class="attributevalue">#EARL</span>"<br /> <span class="attribute">to</span>="<span class="attributevalue">#ARGY</span>" <span class="attribute">exclude</span>="<span class="attributevalue">#PERTARGY #KNAPARGY</span>"></span><br /> <span class="element"><label></span>IN<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">xml:id</span>="<span class="attributevalue">EARLPERT</span>" <span class="attribute">from</span>="<span class="attributevalue">#EARL</span>"<br /> <span class="attribute">to</span>="<span class="attributevalue">#PERT</span>"></span><br /> <span class="element"><label></span>INCLUDE<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">xml:id</span>="<span class="attributevalue">PERTPER1</span>" <span class="attribute">from</span>="<span class="attributevalue">#PERT</span>"<br /> <span class="attribute">to</span>="<span class="attributevalue">#PER1</span>"></span><br /> <span class="element"><label></span>INCLUDE<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">xml:id</span>="<span class="attributevalue">PERTPER2</span>" <span class="attribute">from</span>="<span class="attributevalue">#PERT</span>"<br /> <span class="attribute">to</span>="<span class="attributevalue">#PER2</span>"></span><br /> <span class="element"><label></span>INCLUDE<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">xml:id</span>="<span class="attributevalue">PERTARGY</span>" <span class="attribute">from</span>="<span class="attributevalue">#PERT</span>"<br /> <span class="attribute">to</span>="<span class="attributevalue">#ARGY</span>" <span class="attribute">exclude</span>="<span class="attributevalue">#EARLARGY #KNAPARGY</span>"></span><br /> <span class="element"><label></span>IN<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">xml:id</span>="<span class="attributevalue">PER1KNAP</span>" <span class="attribute">from</span>="<span class="attributevalue">#PER1</span>"<br /> <span class="attribute">to</span>="<span class="attributevalue">#KNAP</span>"></span><br /> <span class="element"><label></span>BY<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">xml:id</span>="<span class="attributevalue">PER2KNAP</span>" <span class="attribute">from</span>="<span class="attributevalue">#PER2</span>"<br /> <span class="attribute">to</span>="<span class="attributevalue">#KNAP</span>"></span><br /> <span class="element"><label></span>PART OF<span class="element"></label></span><br /> <span class="element"></arc></span><br /> <span class="element"><arc <span class="attribute">xml:id</span>="<span class="attributevalue">KNAPARGY</span>" <span class="attribute">from</span>="<span class="attributevalue">#KNAP</span>"<br /> <span class="attribute">to</span>="<span class="attributevalue">#ARGY</span>" <span class="attribute">exclude</span>="<span class="attributevalue">#EARLARGY #PERTARGY</span>"></span><br /> <span class="element"><label></span>IN<span class="element"></label></span><br /> <span class="element"></arc></span><br /><span class="element"></graph></span></div></div></div></div><div class="div2" id="GDTR"><div class="miniTOC miniTOC_right"><ul class="subtoc"><li class="subtoc"><span class="previousLink"> « </span><a class="navigation" href="GD.html#GDGR"><span class="headingNumber">19.1 </span>Graphs and Digraphs</a></li><li class="subtoc"><span class="nextLink"> » </span><a class="navigation" href="GD.html#GDAT"><span class="headingNumber">19.3 </span>Another Tree Notation</a></li><li class="subtoc"><a class="navigation" href="index.html">Home</a></li></ul></div><h3><span class="bookmarklink"><a class="bookmarklink" href="#GDTR" title="link to this section "><span class="invisible">TEI: Trees</span><span class="pilcrow">¶</span></a></span><span class="headingNumber">19.2 </span><span class="head">Trees</span></h3><p>A <span class="term">tree</span> 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 <span class="term">root</span>, 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 <a class="gi" title="encodes a tree, which is made up of a root, internal nodes, leaves, and arcs from root to leaves." href="ref-tree.html">tree</a> element for rooted trees, and the <a class="gi" title="(root node) represents the root node of a tree." href="ref-root.html">root</a> element for its root. The nodes adjacent to a given node are called its <span class="term">children</span>, and the node adjacent from a given node is called its <span class="term">parent</span>. Nodes with both a parent and children are called <span class="term">internal nodes</span>, for which we use the <a class="gi" title="(intermediate (or internal) node) represents an intermediate (or internal) node of a tree." href="ref-iNode.html">iNode</a> element. A node with no children is tagged as a <a class="gi" title="encodes the leaves (terminal nodes) of a tree." href="ref-leaf.html">leaf</a>. If the children of a node are ordered from left to right, then we say that that node is <span class="term">ordered</span>. If all the nodes of a tree are ordered, then we say that the tree is an <span class="term">ordered tree</span>. If some of the nodes of a tree are ordered and others are not, then the tree is a <span class="term">partially ordered tree</span>. 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. </p><ul class="specList"><li><span class="specList-elementSpec"><a href="ref-tree.html">tree</a></span> encodes a tree, which is made up of a root, internal nodes, leaves, and arcs from root to leaves.<table class="specDesc"><tr><td class="Attribute"><span class="att">arity</span></td><td>gives the maximum number of children of the root and internal nodes of the tree.</td></tr><tr><td class="Attribute"><span class="att">ord</span></td><td>(ordered) indicates whether or not the tree is ordered, or if it is partially ordered.</td></tr><tr><td class="Attribute"><span class="att">order</span></td><td>gives the order of the tree, i.e., the number of its nodes.</td></tr></table></li><li><span class="specList-elementSpec"><a href="ref-root.html">root</a></span> (root node) represents the root node of a tree.<table class="specDesc"><tr><td class="Attribute"><span class="att">value</span></td><td>identifies the root node of the network by pointing to a feature structure or other analytic element.</td></tr><tr><td class="Attribute"><span class="att">children</span></td><td>identifies the elements which are the children of the root node.</td></tr><tr><td class="Attribute"><span class="att">ord</span></td><td>(ordered) indicates whether or not the root is ordered.</td></tr><tr><td class="Attribute"><span class="att">outDegree</span></td><td>gives the out degree of the root, the number of its children.</td></tr></table></li><li><span class="specList-elementSpec"><a href="ref-iNode.html">iNode</a></span> (intermediate (or internal) node) represents an intermediate (or internal) node of a tree.<table class="specDesc"><tr><td class="Attribute"><span class="att">value</span></td><td>indicates an intermediate node, which is a feature structure or other analytic element.</td></tr><tr><td class="Attribute"><span class="att">children</span></td><td>provides a list of identifiers of the elements which are the children of the intermediate node.</td></tr><tr><td class="Attribute"><span class="att">parent</span></td><td>provides the identifier of the element which is the parent of this node.</td></tr><tr><td class="Attribute"><span class="att">ord</span></td><td>(ordered) indicates whether or not the internal node is ordered.</td></tr><tr><td class="Attribute"><span class="att">follow</span></td><td>provides the identifier of an element which this node follows.</td></tr><tr><td class="Attribute"><span class="att">outDegree</span></td><td>gives the out degree of an intermediate node, the number of its children.</td></tr></table></li><li><span class="specList-elementSpec"><a href="ref-leaf.html">leaf</a></span> encodes the leaves (terminal nodes) of a tree.<table class="specDesc"><tr><td class="Attribute"><span class="att">value</span></td><td>provides a pointer to a feature structure or other analytic element.</td></tr><tr><td class="Attribute"><span class="att">parent</span></td><td>provides the identifier of parent of a leaf.</td></tr><tr><td class="Attribute"><span class="att">follow</span></td><td>provides an identifier of an element which this leaf follows.</td></tr></table></li></ul><p>Here is an example of a tree. It represents the order in which the operators of addition (symbolized by <code>+</code>), exponentiation (symbolized by <code>**</code>) and division (symbolized by <code>/</code>) are applied in evaluating the arithmetic formula <code>((a**2)+(b**2))/((a+b)**2)</code>. In drawing the graph, the root is placed on the far right, and directionality is presumed to be to the left.</p><div class="p"><img src="Images/graph7.jpg" alt="" class="graphic" style=" width:50%;" /> <div id="index-egXML-d52e135394" class="pre egXML_valid"><span class="element"><tree <span class="attribute">n</span>="<span class="attributevalue">ex1</span>" <span class="attribute">arity</span>="<span class="attributevalue">2</span>" <span class="attribute">ord</span>="<span class="attributevalue">true</span>" <span class="attribute">order</span>="<span class="attributevalue">12</span>"></span><br /> <span class="element"><root <span class="attribute">xml:id</span>="<span class="attributevalue">G-DIV1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#PLU1 #EXP1</span>"></span><br /> <span class="element"><label></span>/<span class="element"></label></span><br /> <span class="element"></root></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">PLU1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#G-DIV1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#EXP2 #EXP3</span>"></span><br /> <span class="element"><label></span>+<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">EXP1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#G-DIV1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#PLU2 #NUM2.3</span>"></span><br /> <span class="element"><label></span>**<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">EXP2</span>" <span class="attribute">parent</span>="<span class="attributevalue">#PLU1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#VARA1 #NUM2.1</span>"></span><br /> <span class="element"><label></span>**<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">EXP3</span>" <span class="attribute">parent</span>="<span class="attributevalue">#PLU1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#VARB1 #NUM2.2</span>"></span><br /> <span class="element"><label></span>**<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">PLU2</span>" <span class="attribute">parent</span>="<span class="attributevalue">#EXP1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#VARA2 #VARB2</span>"></span><br /> <span class="element"><label></span>+<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">VARA1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#EXP2</span>"></span><br /> <span class="element"><label></span>a<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">NUM2.1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#EXP2</span>"></span><br /> <span class="element"><label></span>2<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">VARB1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#EXP3</span>"></span><br /> <span class="element"><label></span>b<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">NUM2.2</span>" <span class="attribute">parent</span>="<span class="attributevalue">#EXP3</span>"></span><br /> <span class="element"><label></span>2<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">VARA2</span>" <span class="attribute">parent</span>="<span class="attributevalue">#PLU2</span>"></span><br /> <span class="element"><label></span>a<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">VARB2</span>" <span class="attribute">parent</span>="<span class="attributevalue">#PLU2</span>"></span><br /> <span class="element"><label></span>b<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">NUM2.3</span>" <span class="attribute">parent</span>="<span class="attributevalue">#EXP1</span>"></span><br /> <span class="element"><label></span>2<span class="element"></label></span><br /> <span class="element"></leaf></span><br /><span class="element"></tree></span></div></div><p>In this encoding, the <span class="att">arity</span> attribute represents the <span class="term">arity</span> of the tree, which is the greatest value of the <span class="att">outDegree</span> attribute for any of the nodes in the tree. If, as in this case, <span class="att">arity</span> is <span class="val">2</span>, we say that the tree is a <span class="term">binary</span> tree.</p><div class="p">Since the left-to-right (or top-to-bottom!) order of the children of the two <code>+</code> 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 <span class="att">ord</span> as <span class="val">false</span> on those two <a class="gi" title="(intermediate (or internal) node) represents an intermediate (or internal) node of a tree." href="ref-iNode.html">iNode</a> elements, the attribute <span class="att">ord</span> as <span class="val">true</span> on the <a class="gi" title="(root node) represents the root node of a tree." href="ref-root.html">root</a> and other <a class="gi" title="(intermediate (or internal) node) represents an intermediate (or internal) node of a tree." href="ref-iNode.html">iNode</a> elements, and the attribute <span class="att">ord</span> as <span class="val">partial</span> on the <a class="gi" title="encodes a tree, which is made up of a root, internal nodes, leaves, and arcs from root to leaves." href="ref-tree.html">tree</a> element, as follows. <div id="index-egXML-d52e135494" class="pre egXML_valid"><span class="element"><tree <span class="attribute">n</span>="<span class="attributevalue">ex2</span>" <span class="attribute">ord</span>="<span class="attributevalue">partial</span>" <span class="attribute">arity</span>="<span class="attributevalue">2</span>"<br /> <span class="attribute">order</span>="<span class="attributevalue">13</span>"></span><br /> <span class="element"><root <span class="attribute">xml:id</span>="<span class="attributevalue">divi1</span>" <span class="attribute">ord</span>="<span class="attributevalue">true</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#plu1 #exp1</span>"></span><br /> <span class="element"><label></span>/<span class="element"></label></span><br /> <span class="element"></root></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">plu1</span>" <span class="attribute">ord</span>="<span class="attributevalue">false</span>"<br /> <span class="attribute">parent</span>="<span class="attributevalue">#divi1</span>" <span class="attribute">children</span>="<span class="attributevalue">#exp2 #exp3</span>"></span><br /> <span class="element"><label></span>+<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">exp1</span>" <span class="attribute">ord</span>="<span class="attributevalue">true</span>"<br /> <span class="attribute">parent</span>="<span class="attributevalue">#divi1</span>" <span class="attribute">children</span>="<span class="attributevalue">#plu2 #num2.3</span>"></span><br /> <span class="element"><label></span>**<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">exp2</span>" <span class="attribute">ord</span>="<span class="attributevalue">true</span>"<br /> <span class="attribute">parent</span>="<span class="attributevalue">#plu1</span>" <span class="attribute">children</span>="<span class="attributevalue">#vara1 #num2.1</span>"></span><br /> <span class="element"><label></span>**<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">exp3</span>" <span class="attribute">ord</span>="<span class="attributevalue">true</span>"<br /> <span class="attribute">parent</span>="<span class="attributevalue">#plu1</span>" <span class="attribute">children</span>="<span class="attributevalue">#varb1 #num2.2</span>"></span><br /> <span class="element"><label></span>**<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">plu2</span>" <span class="attribute">ord</span>="<span class="attributevalue">false</span>"<br /> <span class="attribute">parent</span>="<span class="attributevalue">#exp1</span>" <span class="attribute">children</span>="<span class="attributevalue">#vara2 #varb2</span>"></span><br /> <span class="element"><label></span>+<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">vara1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#exp2</span>"></span><br /> <span class="element"><label></span>a<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">num2.1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#exp2</span>"></span><br /> <span class="element"><label></span>2<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">varb1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#exp3</span>"></span><br /> <span class="element"><label></span>b<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">num2.2</span>" <span class="attribute">parent</span>="<span class="attributevalue">#exp3</span>"></span><br /> <span class="element"><label></span>2<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">vara2</span>" <span class="attribute">parent</span>="<span class="attributevalue">#plu2</span>"></span><br /> <span class="element"><label></span>a<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">varb2</span>" <span class="attribute">parent</span>="<span class="attributevalue">#plu2</span>"></span><br /> <span class="element"><label></span>b<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">num2.3</span>" <span class="attribute">parent</span>="<span class="attributevalue">#exp1</span>"></span><br /> <span class="element"><label></span>2<span class="element"></label></span><br /> <span class="element"></leaf></span><br /><span class="element"></tree></span></div></div><p>This encoding represents all of the following: </p><ul class="bulleted"><li class="item"><code>((a**2)+(b**2))/((a+b)**2)</code></li><li class="item"><code>((b**2)+(a**2))/((a+b)**2)</code></li><li class="item"><code>((a**2)+(b**2))/((b+a)**2)</code></li><li class="item"><code>((b**2)+(a**2))/((a+b)**2)</code></li></ul><p>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. </p><div class="p"><img src="Images/graph8.jpg" alt="" class="graphic" style=" width:30%;" /> <div id="index-egXML-d52e135557" class="pre egXML_valid"><span class="element"><tree <span class="attribute">n</span>="<span class="attributevalue">ex3</span>" <span class="attribute">ord</span>="<span class="attributevalue">true</span>" <span class="attribute">arity</span>="<span class="attributevalue">2</span>" <span class="attribute">order</span>="<span class="attributevalue">8</span>"></span><br /> <span class="element"><root <span class="attribute">xml:id</span>="<span class="attributevalue">GD-PP1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#GD-P1 #GD-NP1</span>"></span><br /> <span class="element"><label></span>PP<span class="element"></label></span><br /> <span class="element"></root></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">GD-P1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-PP1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#GD-WITH1</span>"></span><br /> <span class="element"><label></span>P<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">GD-WITH1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-P1</span>"></span><br /> <span class="element"><label></span>with<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">GD-NP1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-PP1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#GD-THE1 #GD-PERI1</span>"></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">GD-ART1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-NP1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#GD-THE1</span>"></span><br /> <span class="element"><label></span>Art<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">GD-THE1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-ART1</span>"></span><br /> <span class="element"><label></span>the<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">GD-N1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-NP1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#GD-PERI1</span>"></span><br /> <span class="element"><label></span>N<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">GD-PERI1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-N1</span>"></span><br /> <span class="element"><label></span>periscope<span class="element"></label></span><br /> <span class="element"></leaf></span><br /><span class="element"></tree></span></div></div><p>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 <code>xxx</code> symbol indicates that the arc from VB to PT crosses the arc from VP to PN.</p><div class="p"><img src="Images/graph9.jpg" alt="" class="graphic" style=" width:30%;" /> <div id="index-egXML-d52e135591" class="pre egXML_valid"><span class="element"><tree <span class="attribute">n</span>="<span class="attributevalue">ex4</span>" <span class="attribute">arity</span>="<span class="attributevalue">2</span>" <span class="attribute">order</span>="<span class="attributevalue">8</span>" <span class="attribute">ord</span>="<span class="attributevalue">true</span>"></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">GD-LOOK1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-VB2</span>"></span><br /> <span class="element"><label></span>look<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">GD-THEM1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-PN1</span>"></span><br /> <span class="element"><label></span>them<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><leaf <span class="attribute">xml:id</span>="<span class="attributevalue">GD-UP1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-PT1</span>"></span><br /> <span class="element"><label></span>up<span class="element"></label></span><br /> <span class="element"></leaf></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">GD-VB2</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-VB1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#GD-LOOK1</span>"></span><br /> <span class="element"><label></span>VB<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">GD-PN1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-VP1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#GD-THEM1</span>"></span><br /> <span class="element"><label></span>PN<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">GD-PT1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-VB1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#GD-UP1</span>" <span class="attribute">follow</span>="<span class="attributevalue">#GD-PN1</span>"></span><br /> <span class="element"><label></span>PT<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><iNode <span class="attribute">xml:id</span>="<span class="attributevalue">GD-VB1</span>" <span class="attribute">parent</span>="<span class="attributevalue">#GD-VP1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#GD-VB2 #GD-PT1</span>"></span><br /> <span class="element"><label></span>VB<span class="element"></label></span><br /> <span class="element"></iNode></span><br /> <span class="element"><root <span class="attribute">xml:id</span>="<span class="attributevalue">GD-VP1</span>"<br /> <span class="attribute">children</span>="<span class="attributevalue">#GD-VB1 #GD-PN1</span>"></span><br /> <span class="element"><label></span>VP<span class="element"></label></span><br /> <span class="element"></root></span><br /><span class="element"></tree></span></div></div></div><div class="div2" id="GDAT"><div class="miniTOC miniTOC_right"><ul class="subtoc"><li class="subtoc"><span class="previousLink"> « </span><a class="navigation" href="GD.html#GDTR"><span class="headingNumber">19.2 </span>Trees</a></li><li class="subtoc"><span class="nextLink"> » </span><a class="navigation" href="GD.html#GDstem"><span class="headingNumber">19.4 </span>Representing Textual Transmission</a></li><li class="subtoc"><a class="navigation" href="index.html">Home</a></li></ul></div><h3><span class="bookmarklink"><a class="bookmarklink" href="#GDAT" title="link to this section "><span class="invisible">TEI: Another Tree Notation</span><span class="pilcrow">¶</span></a></span><span class="headingNumber">19.3 </span><span class="head">Another Tree Notation</span></h3><p>In this section, we present an alternative to the method of representing the structure of ordered rooted trees given in section <a class="link_ptr" href="GD.html#GDTR" title="Trees"><span class="headingNumber">19.2 </span>Trees</a>, which is based on the observation that any node of such a tree can be thought of as the root of the subtree that it dominates. Thus subtrees can be thought of as the same type as the trees they are embedded in, hence the designation <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a>, for <span class="term">embedding tree</span>. Whereas in a <a class="gi" title="encodes a tree, which is made up of a root, internal nodes, leaves, and arcs from root to leaves." href="ref-tree.html">tree</a> the relationship among the parts is indicated by the <span class="att">children</span> attribute, and by the names of the elements <a class="gi" title="(root node) represents the root node of a tree." href="ref-root.html">root</a>, <a class="gi" title="(intermediate (or internal) node) represents an intermediate (or internal) node of a tree." href="ref-iNode.html">iNode</a>, and <a class="gi" title="encodes the leaves (terminal nodes) of a tree." href="ref-leaf.html">leaf</a>, the relationship among the parts of an <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> is indicated simply by the arrangement of their content. However, we have chosen to enable encoders to distinguish the terminal elements of an <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> by means of the empty <a class="gi" title="(leaf or terminal node of an embedding tree) provides explicitly for a leaf of an embedding tree, which may also be encoded with the <eTree> element." href="ref-eLeaf.html">eLeaf</a> element, though its use is not required; the <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> element can also be used to identify the terminal nodes of <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> elements. We also provide a <a class="gi" title="(underspecified embedding tree, so called because of its characteristic shape when drawn) provides for an underspecified eTree, that is, an eTree with information left out." href="ref-triangle.html">triangle</a> element, which can be thought of as an underspecified <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a>, i.e. an <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> in which certain information has been left out. In addition, we provide a <a class="gi" title="provides for groups of rooted trees." href="ref-forest.html">forest</a> element, which consists of one or more <a class="gi" title="encodes a tree, which is made up of a root, internal nodes, leaves, and arcs from root to leaves." href="ref-tree.html">tree</a>, <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a>, or <a class="gi" title="(underspecified embedding tree, so called because of its characteristic shape when drawn) provides for an underspecified eTree, that is, an eTree with information left out." href="ref-triangle.html">triangle</a> elements, and a <a class="gi" title="provides for lists of forests." href="ref-listForest.html">listForest</a> element, which consists of one or more <a class="gi" title="provides for groups of rooted trees." href="ref-forest.html">forest</a> elements. The elements used for the encoding of embedding trees and the units containing them have the following descriptions and attributes. </p><ul class="specList"><li><span class="specList-elementSpec"><a href="ref-eTree.html">eTree</a></span> (embedding tree) provides an alternative to the <a class="gi" title="encodes a tree, which is made up of a root, internal nodes, leaves, and arcs from root to leaves." href="ref-tree.html">tree</a> element for representing ordered rooted tree structures.<table class="specDesc"><tr><td class="Attribute"><span class="att">value</span></td><td>provides the value of an embedding tree, which is a feature structure or other analytic element.</td></tr></table></li><li><span class="specList-elementSpec"><a href="ref-triangle.html">triangle</a></span> (underspecified embedding tree, so called because of its
characteristic shape when drawn) provides for an underspecified eTree, that is, an eTree with information left out.<table class="specDesc"><tr><td class="Attribute"><span class="att">value</span></td><td>supplies a value for the triangle, in the form of the identifier of a feature structure or other analytic element.</td></tr></table></li><li><span class="specList-elementSpec"><a href="ref-eLeaf.html">eLeaf</a></span> (leaf or terminal node of an embedding tree) provides explicitly for a leaf of an embedding tree, which may also be encoded with the <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> element.<table class="specDesc"><tr><td class="Attribute"><span class="att">value</span></td><td>indicates the value of an embedding leaf, which is a feature structure or other analytic element.</td></tr></table></li><li><span class="specList-elementSpec"><a href="ref-forest.html">forest</a></span> provides for groups of rooted trees.</li><li><span class="specList-elementSpec"><a href="ref-listForest.html">listForest</a></span> provides for lists of forests.</li></ul><p>Like the <a class="gi" title="(root node) represents the root node of a tree." href="ref-root.html">root</a>, <a class="gi" title="(intermediate (or internal) node) represents an intermediate (or internal) node of a tree." href="ref-iNode.html">iNode</a>, and <a class="gi" title="encodes the leaves (terminal nodes) of a tree." href="ref-leaf.html">leaf</a> of a <a class="gi" title="encodes a tree, which is made up of a root, internal nodes, leaves, and arcs from root to leaves." href="ref-tree.html">tree</a>, the <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a>, <a class="gi" title="(underspecified embedding tree, so called because of its characteristic shape when drawn) provides for an underspecified eTree, that is, an eTree with information left out." href="ref-triangle.html">triangle</a> and <a class="gi" title="(leaf or terminal node of an embedding tree) provides explicitly for a leaf of an embedding tree, which may also be encoded with the <eTree> element." href="ref-eLeaf.html">eLeaf</a> elements may also have <span class="att">value</span> attributes and <a class="gi" title="contains any label or heading used to identify part of a text, typically but not exclusively in a list or glossary." href="ref-label.html">label</a> children.</p><p>To illustrate the use of the <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> and <a class="gi" title="(leaf or terminal node of an embedding tree) provides explicitly for a leaf of an embedding tree, which may also be encoded with the <eTree> element." href="ref-eLeaf.html">eLeaf</a> elements, here is an encoding of the second example in section <a class="link_ptr" href="GD.html#GDTR" title="Trees"><span class="headingNumber">19.2 </span>Trees</a>, repeated here for convenience.</p><div class="p"><img src="Images/graph10.jpg" alt="" class="graphic" style=" width:30%;" /> <div id="index-egXML-d52e136592" class="pre egXML_valid"><span class="element"><eTree <span class="attribute">n</span>="<span class="attributevalue">ex1</span>"></span><br /> <span class="element"><label></span>PP<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>P<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>with<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>Art<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>the<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>N<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>periscope<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /><span class="element"></eTree></span></div></div><p>Next, we provide an encoding, using the <a class="gi" title="(underspecified embedding tree, so called because of its characteristic shape when drawn) provides for an underspecified eTree, that is, an eTree with information left out." href="ref-triangle.html">triangle</a> element, in which the internal structure of the <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> labeled <code>NP</code> is omitted.</p><div class="p"><img src="Images/graph11.jpg" alt="" class="graphic" style=" width:30%;" /> <div id="index-egXML-d52e136631" class="pre egXML_valid"><span class="element"><eTree <span class="attribute">n</span>="<span class="attributevalue">ex2</span>"></span><br /> <span class="element"><label></span>PP<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>P<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>with<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><triangle></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>the periscope<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></triangle></span><br /><span class="element"></eTree></span></div></div><p>Ambiguity involving alternative tree structures associated with the same terminal sequence can be encoded relatively conveniently using a combination of the <span class="att">exclude</span> and <span class="att">copyOf</span> attributes described in sections <a class="link_ptr" href="SA.html#SAAT" title="Alternation"><span class="headingNumber">16.8 </span>Alternation</a> and <a class="link_ptr" href="SA.html#SAIE" title="Identical Elements and Virtual Copies"><span class="headingNumber">16.6 </span>Identical Elements and Virtual Copies</a>. In the simplest case, an <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> may be part of the content of exactly one of two different <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> elements. To mark it up, the embedded <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> may be fully specified within one of the embedding <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> elements to which it may belong, and a virtual copy, specified by the <span class="att">copyOf</span> attribute, may appear on the other. In addition, each of the embedded elements in question is specified as excluding the other, using the <span class="att">exclude</span> attribute. To illustrate, consider the English phrase <span class="mentioned">see the vessel with the periscope</span>, which may be considered to be structurally ambiguous, depending on whether the phrase <span class="mentioned">with the periscope</span> is a modifier of the phrase <span class="mentioned">the vessel</span> or a modifier of the phrase <span class="mentioned">see the vessel</span>. This ambiguity is indicated in the sketch of the ambiguous tree by means of the dotted-line arcs. The markup using the <span class="att">copyOf</span> and <span class="att">exclude</span> attributes follows the sketch.</p><div class="p"><img src="Images/graph12.jpg" alt="" class="graphic" style=" width:80%;" /> <div id="index-egXML-d52e136701" class="pre egXML_valid"><span class="element"><eTree <span class="attribute">n</span>="<span class="attributevalue">ex3</span>"></span><br /> <span class="element"><label></span>VP<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>V<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>see<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>Art<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>the<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>N<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>vessel<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">GD-PPA</span>" <span class="attribute">exclude</span>="<span class="attributevalue">#GD-PPB</span>"></span><br /> <span class="element"><label></span>PP<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>P<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>with<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>Art<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>the<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>N<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>periscope<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">GD-PPB</span>" <span class="attribute">copyOf</span>="<span class="attributevalue">#GD-PPA</span>"<br /> <span class="attribute">exclude</span>="<span class="attributevalue">#GD-PPA</span>"></span><br /> <span class="element"><label></span>PP<span class="element"></label></span><br /> <span class="element"></eTree></span><br /><span class="element"></eTree></span></div></div><p>To indicate that one of the alternatives is selected, one may specify the <span class="att">select</span> attribute on the highest <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> as either <span class="val">#GD-PPA</span> or <span class="val">#GD-PPB</span>; see section <a class="link_ptr" href="SA.html#SAAT" title="Alternation"><span class="headingNumber">16.8 </span>Alternation</a>.</p><p>Depending on the grammar one uses to associate structures with examples like <span class="mentioned">see the man with the periscope</span>, the representations may be more complicated than this. For example, adopting a version of the <span class="term">X-bar</span> theory of phrase structure originated by Jackendoff,<span id="Note118_return"><a class="notelink" title="" href="#Note118"><sup>81</sup></a></span> the attachment of a modifier may require the creation of an intermediate node which is not required when the attachment is not made, as shown in the following diagram. A possible encoding of this ambiguous structure immediately follows the diagram.</p><div class="p"><img src="Images/graph13.jpg" alt="" class="graphic" style=" width:80%;" /> <div id="index-egXML-d52e136784" class="pre egXML_valid"><span class="element"><eTree <span class="attribute">n</span>="<span class="attributevalue">ex4</span>"></span><br /> <span class="element"><label></span>VP<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">VBARA</span>" <span class="attribute">exclude</span>="<span class="attributevalue">#VBARB</span>"></span><br /> <span class="element"><label></span>V'<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">VA</span>"></span><br /> <span class="element"><label></span>V<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>see<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">SPEC1A</span>"></span><br /> <span class="element"><label></span>Spec<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>the<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>N'<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">NBAR2A</span>"></span><br /> <span class="element"><label></span>N'<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>N<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>vessel<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">PPA1</span>"></span><br /> <span class="element"><label></span>PP<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>P<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>with<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>Spec<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>the<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>N'<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>N<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>periscope<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">VBARB</span>" <span class="attribute">exclude</span>="<span class="attributevalue">#VBARA</span>"></span><br /> <span class="element"><label></span>V'<span class="element"></label></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>V'<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">VB</span>" <span class="attribute">copyOf</span>="<span class="attributevalue">#VA</span>"></span><br /> <span class="element"><label></span>V<span class="element"></label></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">SPEC1B</span>" <span class="attribute">copyOf</span>="<span class="attributevalue">#SPEC1A</span>"></span><br /> <span class="element"><label></span>Spec<span class="element"></label></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">NBAR2B</span>" <span class="attribute">copyOf</span>="<span class="attributevalue">#NBAR2A</span>"></span><br /> <span class="element"><label></span>N'<span class="element"></label></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">PPB</span>" <span class="attribute">copyOf</span>="<span class="attributevalue">#PPA1</span>"></span><br /> <span class="element"><label></span>PP<span class="element"></label></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /><span class="element"></eTree></span></div></div><p>A <span class="term">derivation</span> in a generative grammar is often thought of as a set of trees. To encode such a derivation, one may use the <a class="gi" title="provides for groups of rooted trees." href="ref-forest.html">forest</a> element, in which the trees may be marked up using the <a class="gi" title="encodes a tree, which is made up of a root, internal nodes, leaves, and arcs from root to leaves." href="ref-tree.html">tree</a>, the <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a>, or the <a class="gi" title="(underspecified embedding tree, so called because of its characteristic shape when drawn) provides for an underspecified eTree, that is, an eTree with information left out." href="ref-triangle.html">triangle</a> element. The <span class="att">type</span> attribute may be used to specify what kind of derivation it is. Here is an example of a two-tree forest, involving application of the ‘wh-movement’ transformation in the derivation of <span class="mentioned">what you do</span> (as in <span class="mentioned">this is what you do</span>) from the underlying <span class="mentioned">you do what</span>.<span id="Note119_return"><a class="notelink" title="The symbols e and t denote special theoretical constructs (empty category and trace respectively), which need not concern us here." href="#Note119"><sup>82</sup></a></span></p><div class="p"><img src="Images/graph14.jpg" alt="" class="graphic" style=" width:80%;" /> <div id="index-egXML-d52e136918" class="pre egXML_valid"><span class="element"><forest <span class="attribute">n</span>="<span class="attributevalue">ex5</span>" <span class="attribute">type</span>="<span class="attributevalue">derivation-syntactic</span>"></span><br /> <span class="element"><eTree <span class="attribute">n</span>="<span class="attributevalue">Stage 1</span>" <span class="attribute">xml:id</span>="<span class="attributevalue">S1SBAR</span>"></span><br /> <span class="element"><label></span>S'<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S1COMP</span>"></span><br /> <span class="element"><label></span>COMP<span class="element"></label></span><br /> <span class="element"><eLeaf <span class="attribute">xml:id</span>="<span class="attributevalue">S1E</span>"></span><br /> <span class="element"><label></span>e<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S1S</span>"></span><br /> <span class="element"><label></span>S<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S1NP1</span>"></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>you<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S1VP</span>"></span><br /> <span class="element"><label></span>VP<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S1V</span>"></span><br /> <span class="element"><label></span>V<span class="element"></label></span><br /> <span class="element"><eLeaf></span><br /> <span class="element"><label></span>do<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S1NP2</span>"></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"><eLeaf <span class="attribute">xml:id</span>="<span class="attributevalue">S1WH</span>"></span><br /> <span class="element"><label></span>what<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">n</span>="<span class="attributevalue">Stage 2</span>" <span class="attribute">xml:id</span>="<span class="attributevalue">S2SBAR</span>"<br /> <span class="attribute">corresp</span>="<span class="attributevalue">#S1SBAR</span>"></span><br /> <span class="element"><label></span>S'<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S2COMP</span>" <span class="attribute">corresp</span>="<span class="attributevalue">#S1COMP</span>"></span><br /> <span class="element"><label></span>COMP<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">copyOf</span>="<span class="attributevalue">#S1NP2</span>" <span class="attribute">corresp</span>="<span class="attributevalue">#S1E</span>"></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S2S</span>" <span class="attribute">corresp</span>="<span class="attributevalue">#S1S</span>"></span><br /> <span class="element"><label></span>S<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S2NP1</span>" <span class="attribute">copyOf</span>="<span class="attributevalue">#S1NP1</span>"></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S2VP</span>" <span class="attribute">corresp</span>="<span class="attributevalue">#S1VP</span>"></span><br /> <span class="element"><label></span>VP<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S2V</span>" <span class="attribute">copyOf</span>="<span class="attributevalue">#S1V</span>"></span><br /> <span class="element"><label></span>V<span class="element"></label></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">S2NP2</span>" <span class="attribute">corresp</span>="<span class="attributevalue">#S1NP2</span>"></span><br /> <span class="element"><label></span>NP<span class="element"></label></span><br /> <span class="element"><eLeaf <span class="attribute">corresp</span>="<span class="attributevalue">#S1WH</span>"></span><br /> <span class="element"><label></span>t<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /><span class="element"></forest></span></div></div><p>In this markup, we have used <span class="att">copyOf</span> attributes to provide virtual copies of elements in the tree representing the second stage of the derivation that also occur in the first stage, and the <span class="att">corresp</span> attribute (see section <a class="link_ptr" href="SA.html#SACS" title="Correspondence and Alignment"><span class="headingNumber">16.5 </span>Correspondence and Alignment</a>) to link those elements in the second stage with corresponding elements in the first stage that are not copies of them.</p><p>If a group of forests (e.g. a full grammatical derivation including syntactic, semantic, and phonological subderivations) is to be articulated, the grouping element <a class="gi" title="provides for lists of forests." href="ref-listForest.html">listForest</a> may be used.</p></div><div class="teidiv1" id="GDstem"><div class="miniTOC miniTOC_right"><ul class="subtoc"><li class="subtoc"><span class="previousLink"> « </span><a class="navigation" href="GD.html#GDAT"><span class="headingNumber">19.3 </span>Another Tree Notation</a></li><li class="subtoc"><span class="nextLink"> » </span><a class="navigation" href="GD.html#index-body.1_div.19_div.5"><span class="headingNumber">19.5 </span>Module for Graphs, Networks, and Trees</a></li><li class="subtoc"><a class="navigation" href="index.html">Home</a></li></ul></div><h3><span class="bookmarklink"><a class="bookmarklink" href="#GDstem" title="link to this section "><span class="invisible">TEI: Representing Textual Transmission</span><span class="pilcrow">¶</span></a></span><span class="headingNumber">19.4 </span><span class="head">Representing Textual Transmission</span></h3><p>A <span class="term">stemma codicum</span> (sometimes called just <span class="term">stemma</span>) is a tree-like graphic structure that has become traditional in manuscript studies for representing textual transmission. Consider the following hypothetical stemma: </p><figure class="figure"><figcaption class="caption">Figure 19.1. Example stemma</figcaption><img src="Images/stemma.png" alt="Example stemma" class="graphic" style=" width:80%;" /></figure><p>The nodes in this stemma represent manuscripts; each has a label (a letter) which identifies it and also distinguishes whether the manuscript is extant, lost, or hypothetical. Extant manuscripts are identified by uppercase Latin letters or words beginning with uppercase Latin letters, e.g., <span class="val">L</span>, shown as aqua in this example; manuscripts no longer existing, but providing readings which are attested e.g. by note or copy made before their disappearance, are identified by lowercase Latin letters, e.g., <span class="val">t</span>, shown as magenta in this example; hypothetical stages in the textual transmission, which do not necessarily correspond to real manuscripts, are given lowercase Greek letters, e.g., <span class="val">α</span> and shown as gold in this example. The stemma shown above thus suggests that (on the basis of similarities in the readings of the extant and lost manuscripts) <span class="val">L</span> and <span class="val">t</span> share textual material that is not shared with other manuscripts (represented in this case by <span class="val">δ</span>) even though no physical manuscript attesting this stage in the textual transmission has ever been identified.</p><p>Manuscripts are copied from other manuscripts. The preceding stemma represents the hypothesis that all manuscripts go back to a common ancestor (<span class="val">α</span>), that the tradition split after that stage into two (<span class="val">β</span> and <span class="val">γ</span>), etc. Descent by copying is indicated with a solid line. According to this model, <span class="val">α</span> is the earliest common hypothetical stage that can be reconstructed, and all nodes below <span class="val">α</span> have a single parent, that is, were copied from a single other stage in the tradition.</p><p>This familiar tree model is complicated because manuscripts sometimes show the influence of more than one ancestor. They may have been produced by a scribe who checked the text in one manuscript of the same work whilst copying from another, or perhaps made changes from his memory of a slightly different version of the text that he had read elsewhere. Alternatively, perhaps scribe A copied a manuscript from one source, scribe B made changes in it in the margins or between the lines (either by consulting another source directly or from memory), and another scribe then copied that manuscript, incorporating the changes into the body. Whatever the specific scenario, it is not uncommon for a manuscript to be based primarily on one source, but to incorporate features of another branch of the tradition. This mixed result is called <span class="term">contamination</span>, and it is reflected in a stemma by a dotted line. Thus, the example above asserts that <span class="val">A</span> is copied within the <span class="val">ε</span> tradition, but is also contaminated from the <span class="val">γ</span> tradition.</p><p>The utility of a stemma as a visualization tool is inversely proportional to the degree of contamination in the manuscript tradition. A tradition completely without contamination (called a <span class="term">closed tradition</span>) yields a classic tree, easily represented graphically by a stemma. An <span class="term">open tradition</span>, with substantial contamination, yields a spaghetti-like stemma characterized by crossing dotted lines, which is both difficult to read and not very informative.</p><div class="p">The <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> element introduced in this chapter can be used to represent a closed tradition in a straightforward manner. Each non-terminal node is represented by a typed <a class="gi" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> element and each terminal node by an <a class="gi" title="(leaf or terminal node of an embedding tree) provides explicitly for a leaf of an embedding tree, which may also be encoded with the <eTree> element." href="ref-eLeaf.html">eLeaf</a>. A <a class="gi" title="contains any label or heading used to identify part of a text, typically but not exclusively in a list or glossary." href="ref-label.html">label</a> element provides a way of identifying each node, complementary to the global attributes <span class="att">n</span> and <span class="att">xml:id</span> attributes. For example, the closed part of the tradition headed by the label δ may be encoded as follows: <div id="index-egXML-d52e137568" class="pre egXML_valid"><span class="element"><eTree <span class="attribute">type</span>="<span class="attributevalue">hypothetical</span>"></span><br /> <span class="element"><label></span>δ<span class="element"></label></span><br /> <span class="element"><eLeaf <span class="attribute">type</span>="<span class="attributevalue">extant</span>"></span><br /> <span class="element"><label></span>L<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"><eLeaf <span class="attribute">type</span>="<span class="attributevalue">lost</span>"></span><br /> <span class="element"><label></span>t<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /><span class="element"></eTree></span></div> To complete this representation, we need to show that the node labelled A is not derived solely from its parent node (labelled ε) but also demonstrates contamination from the node labelled γ. The easiest way to accomplish this is to include an appropriately-typed <a class="gi" title="(pointer) defines a pointer to another location." href="ref-ptr.html">ptr</a> element within the node in question, the <span class="att">target</span> of which points to the node labelled γ. This requires that this latter node be supplied with a value for its <span class="att">xml:id</span> attribute. The complete representation is thus: <div id="index-egXML-d52e137588" class="pre egXML_valid"><span class="element"><eTree <span class="attribute">type</span>="<span class="attributevalue">hypothetical</span>"></span><br /> <span class="element"><label></span>α<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">type</span>="<span class="attributevalue">hypothetical</span>"></span><br /> <span class="element"><label></span>β<span class="element"></label></span><br /> <span class="element"><eTree <span class="attribute">type</span>="<span class="attributevalue">hypothetical</span>"></span><br /> <span class="element"><label></span>δ<span class="element"></label></span><br /> <span class="element"><eLeaf <span class="attribute">type</span>="<span class="attributevalue">extant</span>"></span><br /> <span class="element"><label></span>L<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"><eLeaf <span class="attribute">type</span>="<span class="attributevalue">lost</span>"></span><br /> <span class="element"><label></span>t<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">type</span>="<span class="attributevalue">hypothetical</span>"></span><br /> <span class="element"><label></span>ε<span class="element"></label></span><br /> <span class="element"><eLeaf <span class="attribute">type</span>="<span class="attributevalue">extant</span>"></span><br /> <span class="element"><label></span>R<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"><eLeaf <span class="attribute">type</span>="<span class="attributevalue">extant</span>"></span><br /> <span class="element"><label></span>A<span class="element"></label></span><br /> <span class="element"><ptr <span class="attribute">type</span>="<span class="attributevalue">contamination</span>"<br /> <span class="attribute">target</span>="<span class="attributevalue">#gamma</span>"/></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /> <span class="element"></eTree></span><br /> <span class="element"><eTree <span class="attribute">xml:id</span>="<span class="attributevalue">gamma</span>" <span class="attribute">type</span>="<span class="attributevalue">hypothetical</span>"></span><br /> <span class="element"><label></span>γ<span class="element"></label></span><br /> <span class="element"><eLeaf <span class="attribute">type</span>="<span class="attributevalue">extant</span>"></span><br /> <span class="element"><label></span>I<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"><eLeaf <span class="attribute">type</span>="<span class="attributevalue">extant</span>"></span><br /> <span class="element"><label></span>X<span class="element"></label></span><br /> <span class="element"></eLeaf></span><br /> <span class="element"></eTree></span><br /><span class="element"></eTree></span></div></div><p>In any substantial codicological project, it is likely that significantly more data will be required about the individual witnesses than indicated in the simple structures above. These Guidelines provide a rich variety of additional elements for representing such information: see in particular chapters <a class="link_ptr" href="MS.html" title="Manuscript Description"><span class="headingNumber">10 </span>Manuscript Description</a>, <a class="link_ptr" href="PH.html" title="18"><span class="headingNumber">11 </span>Representation of Primary Sources</a>, and <a class="link_ptr" href="TC.html" title="19"><span class="headingNumber">12 </span>Critical Apparatus</a>.</p></div><div class="teidiv1" id="index-body.1_div.19_div.5"><div class="miniTOC miniTOC_right"><ul class="subtoc"><li class="subtoc"><span class="previousLink"> « </span><a class="navigation" href="GD.html#GDstem"><span class="headingNumber">19.4 </span>Representing Textual Transmission</a></li><li class="subtoc"></li><li class="subtoc"><a class="navigation" href="index.html">Home</a></li></ul></div><h3><span class="bookmarklink"><a class="bookmarklink" href="#index-body.1_div.19_div.5" title="link to this section "><span class="invisible">TEI: Module for Graphs, Networks, and Trees</span><span class="pilcrow">¶</span></a></span><span class="headingNumber">19.5 </span><span class="head">Module for Graphs, Networks, and Trees</span></h3><p>The module described in this chapter makes available the following components: </p><dl class="moduleSpec"><dt class="moduleSpecHead"><span lang="en">Module</span> nets: Graphs, networks, and trees</dt><dd><ul><li><span lang="en">Elements defined</span>: <a class="link_odd" title="encodes an arc, the connection from one node to another in a graph." href="ref-arc.html">arc</a> <a class="link_odd" title="(leaf or terminal node of an embedding tree) provides explicitly for a leaf of an embedding tree, which may also be encoded with the <eTree> element." href="ref-eLeaf.html">eLeaf</a> <a class="link_odd" title="(embedding tree) provides an alternative to the <tree> element for representing ordered rooted tree structures." href="ref-eTree.html">eTree</a> <a class="link_odd" title="provides for groups of rooted trees." href="ref-forest.html">forest</a> <a class="link_odd" title="encodes a graph, which is a collection of nodes, and arcs which connect the nodes." href="ref-graph.html">graph</a> <a class="link_odd" title="(intermediate (or internal) node) represents an intermediate (or internal) node of a tree." href="ref-iNode.html">iNode</a> <a class="link_odd" title="encodes the leaves (terminal nodes) of a tree." href="ref-leaf.html">leaf</a> <a class="link_odd" title="provides for lists of forests." href="ref-listForest.html">listForest</a> <a class="link_odd" title="encodes a node, a possibly labeled point in a graph." href="ref-node.html">node</a> <a class="link_odd" title="(root node) represents the root node of a tree." href="ref-root.html">root</a> <a class="link_odd" title="encodes a tree, which is made up of a root, internal nodes, leaves, and arcs from root to leaves." href="ref-tree.html">tree</a> <a class="link_odd" title="(underspecified embedding tree, so called because of its characteristic shape when drawn) provides for an underspecified eTree, that is, an eTree with information left out." href="ref-triangle.html">triangle</a></li></ul></dd></dl><p> The selection and combination of modules to form a TEI schema is described in <a class="link_ptr" href="ST.html#STIN" title="Defining a TEI Schema"><span class="headingNumber">1.2 </span>Defining a TEI Schema</a>. </p></div></div><nav class="left"><span class="upLink"> ↑ </span><a class="navigation" href="index.html">TEI P5 Guidelines</a><span class="previousLink"> « </span><a class="navigation" href="FS.html"><span class="headingNumber">18 </span>Feature Structures</a><span class="nextLink"> » </span><a class="navigation" href="NH.html"><span class="headingNumber">20 </span>Non-hierarchical Structures</a></nav><!--Notes in [div]--><div class="notes"><div class="noteHeading">Notes</div><div class="note" id="Note115"><span class="noteLabel">78 </span><div class="noteBody">The treatment here is largely based on the characterizations of graph types in <a class="citlink" href="BIB.html#GD-BIBL-1">Chartrand and Lesniak (1986)</a></div> <a class="link_return" title="Go back to text" href="#Note115_return">↵</a></div><div class="note" id="Note116"><span class="noteLabel">79 </span><div class="noteBody">The family tree is that of the mathematician and philosopher Bertrand Russell, whose third wife was commonly known as Peter. The information presented here is taken from <a class="link_ref" href="BIB.html#GDFT-eg-12" title="Partial family tree for Bertrand Russell based on an example in Pereira Fernando C.N. and Stuart M. Shieber Prolog and Natural ...">Pereira and Shieber (1987)</a>.</div> <a class="link_return" title="Go back to text" href="#Note116_return">↵</a></div><div class="note" id="Note117"><span class="noteLabel">80 </span><div class="noteBody">That is, the three syntactic interpretations of the clause are mutually exclusive. The notion that the pertinents are in Argyll is clearly not inconsistent with the notion that both the land in Gallachalzie and the pertinents are in Argyll. The graph given here describes the possible interpretations of the clause itself, not the sets of inferences derivable from each syntactic interpretation, for which it would be convenient to use the facilities described in chapter <a class="link_ptr" href="FS.html" title="16"><span class="headingNumber">18 </span>Feature Structures</a>.</div> <a class="link_return" title="Go back to text" href="#Note117_return">↵</a></div><div class="note" id="Note118"><span class="noteLabel">81 </span><div class="noteBody"><a class="citlink" href="BIB.html#GD-BIBL-2">Jackendoff (1977)</a></div> <a class="link_return" title="Go back to text" href="#Note118_return">↵</a></div><div class="note" id="Note119"><span class="noteLabel">82 </span><div class="noteBody">The symbols <code>e</code> and <code>t</code> denote special theoretical constructs (<span class="term">empty category</span> and <span class="term">trace</span> respectively), which need not concern us here.</div> <a class="link_return" title="Go back to text" href="#Note119_return">↵</a></div></div><div class="stdfooter autogenerated"><p>
[<a href="../../en/html/GD.html">English</a>]
[<a href="../../de/html/GD.html">Deutsch</a>]
[<a href="../../es/html/GD.html">Español</a>]
[<a href="../../it/html/GD.html">Italiano</a>]
[<a href="../../fr/html/GD.html">Français</a>]
[<a href="../../ja/html/GD.html">日本語</a>]
[<a href="../../ko/html/GD.html">한국어</a>]
[<a href="../../zh-TW/html/GD.html">中文</a>]
</p><hr /><div class="footer"><a class="plain" href="http://www.tei-c.org/About/">TEI Consortium</a> | <a class="plain" href="http://www.tei-c.org/About/contact.xml">Feedback</a></div><hr /><address><br />TEI Guidelines <a class="link_ref" href="AB.html#ABTEI4">Version</a> <a class="link_ref" href="../../readme-3.1.1.html">3.1.1a</a>. Last updated on <span class="date">10th May 2017</span>, revision <a class="link_ref" href="https://github.com/TEIC/TEI/commit/bd8dda3">bd8dda3</a>. This page generated on 2017-05-12T12:30:09Z.</address></div></div></body></html>