Graphical representations are widely used for displaying relations
among informational units because they help readers to visualize those
relations and hence to understand them better. Two general types of
graphical representations may be distinguished.
Graphs, in the strictly mathematical sense, consist
of points, often called nodes or
vertices, and connections among them, called
arcs, or under certain conditions,
edges. Among the various types of graphs are
networks and trees. Graphs
generally and networks in particular are dealt with
directly below. Trees are dealt with separately in
sections and .
The treatment here is largely based on the
characterizations of graph types in Gary Chartrand and
Linda Lesniak, Graphs and Digraphs
(Menlo Park, CA: Wadsworth, 1986).Charts, which typically plot data in two or more
dimensions, including plots with orthogonal or radial axes, bar charts,
pie charts, and the like. These can be described using the elements
defined in the additional tag set for figures and graphics; see
chapter .
The following DTD fragment shows the overall organization of the
tag set discussed in the remainder of this chapter.
]]>
This tag set is made available as described in ; in
a document which uses the markup described in this chapter, the document
type declaration should contain the following declaration for the entity
tei.nets:
]]>
The entire document type declaration for a document using this
additional tag set together with the prose base might look like this:
]>
]]>
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.
Graphs and Digraphs
Broadly speaking, graphs can be divided into two types:
undirected and directed. An undirected graph
is a set of nodes (or vertices) together with
a set of pairs of those vertices, called arcs or
edges. Each node in an arc of an undirected graph is said
to be incident with that arc, and the two vertices which
make up an arc are said to be adjacent. An directed graph
is like an undirected graph except that the arcs are ordered
pairs of nodes. In the case of directed graphs, the term
edge is not used; moreover, each arc in an directed graph
is said to be adjacent from the node from which the arc
emanates, and adjacent to the node to which the arc is
directed. We use the element graph to encode graphs as a
whole, node to encode nodes or vertices, and arc to
encode arcs or edges; arcs can also be encoded by attributes on the
node element. These elements have the following descriptions
and attributes:
encodes a graph, which is a collection of nodes, and arcs
which
connect the nodes.
Attributes include:
describes the type of graph.
Suggested values include:
undirected graphdirected grapha directed graph with distinguished initial and final nodesa transition network with up to two labels on each arcgives a label for a graph.states the order of the graph, i.e., the number of its
nodes.states the size of the graph, i.e., the number of its arcs.encodes a node, a possibly labeled point in a graph.
Attributes include:
gives a label for a node.gives a second label for a node.provides the value of a node, which is a feature structure
or other analytic element.provides a type for a node.
Suggested values include:
initial node in a transition networkfinal node in a transition networkgives the IDs of the nodes which are adjacent from the
current node.gives the IDs of the nodes which are adjacent to the
current node.gives the IDs of the nodes which are both adjacent to and
adjacent from the current node.gives the in degree of the node, the number of nodes which
are adjacent from the given node.gives the out degree of the node, the number of nodes which
are adjacent to the given node.gives the degree of the node, the number of arcs with which
the node is incident.encodes an arc, the connection from one node to another in
a graph.
Attributes include:
gives a label for an arc.gives a second label for an arc.gives the ID of the node which is adjacent from this arc.gives the ID of the node which is adjacent to this arc.
Before proceeding, some additional terminology may be helpful. We
define a path in a graph as a sequence of nodes n1, ..., nk
such that there is an arc from each ni to ni+1 in the sequence. A
cyclic path, or cycle is a path leading from a
particular node back to itself. A graph that contains at least one
cycle is said to be cyclic; otherwise it is
acyclic. We say, finally, that a graph is
connected if there is a path from some node to every other
node in the graph; any graph that is not connected is said to be
disconnected.
Here is an example of an undirected, cyclic disconnected graph, in
which the nodes are annotated with three-letter codes for airports, and
the arcs connecting the nodes are represented by horizontal and vertical
lines, with 90 degree bends used simply to avoid having to draw diagonal
lines.
Next is a markup of the graph, using arc elements to encode
the arcs.
]]>
The label attribute on the graph element records
a
label for the graph; similarly, the label attribute on
the node elements records the labels of those nodes. The
order and size attributes on the graph
element record the number of nodes and number of arcs in the graph
respectively; these values are optional (since they can be computed from
the rest of the graph), but if they are supplied, they must be
consistent with the rest of the encoding. They can thus be used to help
check that the graph has been encoded and transmitted correctly. The
degree attribute on the node elements record the
number of arcs that are incident with that node. It is optional
(because redundant), but can be used to help in validity checking: if a
value is given, it must be consistent with the rest of the information
in the graph. Finally, the from and to attributes
on the arc elements provide pointers to the nodes connected by
those arcs. Since the graph is undirected, no directionality is implied
by the use of the from and to attributes; the
values of these attributes could be interchanged in each arc without
changing the graph.
The adj, adjFrom, and adjTo
attributes of the node element provide an alternative method of
representing unlabeled arcs, their values being pointers to the nodes
which are adjacent to or from that node. The adj attribute
is to be used for undirected graphs, and the adjFrom and
adjTo attributes for directed graphs. It is a semantic error
for the directed adjacency attributes to be used in an undirected graph,
and vice versa. Here is a markup of the preceding graph, using the
adj attribute to represent the arcs.
]]>
Note that each arc is represented twice in this encoding of the
graph. For example, the existence of the arc from LAX to LVG can be
inferred from each of the first two node elements in the graph.
This redundancy, however, is not required: it suffices to describe an
arc in any one of the three places it can be described (either adjacent
node, or in a separate arc element). Here is a less redundant
representation of the same graph.
]]>
Although in many cases the arc element is redundant (since
arcs can be described using the adjacency attributes of their adjacent
nodes), it has nevertheless been included in the tag set, in order to
allow the convenient specification of identifiers, display or
rendition information, and labels for each arc (using the attributes
id, rend, and label).
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.
---PHX--->---TUS CIB
| |
+----<----+
Selected Airline Routes in Southwestern USA
]]>
Here is an encoding of this graph, using the arc element to
designate the arcs.
]]>
Here is another encoding of the graph, using the adjTo and
adjFrom attributes on nodes to designate the arcs.
]]>
If we wish to label the arcs, say with flight numbers, then
arc elements must be used to carry the label
attribute, as in the following example.
]]>
The formal declarations of the graph, node and
arc elements are as follows.
]]>
Transition Networks
For encoding transition networks and other kinds of directed graphs
in which distinctions among types of nodes must be made, the
type attribute is provided for node elements. In
the following example, the initial and final
nodes (or states) of the network are distinguished. It can
be understood as accepting the set of strings obtained by traversing it
from its initial node to its final node, and concatenating the labels.
-+ +-->----o---->---+
| | | |
\ / | |
THE \ / | |
(8) o-->----o-----+ o
| |
| |
| |
+-->----o---->---+
MEN COME
]]>
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.
---1------->-----4--->---+
| L' | HOMME VIENT |
| | |
| OLD|VIEIL |
| | |
| THE | |
(8) 0-->----2 6
| LE / \ |
| / \ |
| / \ |
| | OLD | |
| +-->--+ |
| VIEIL |
| THE MEN COME |
+--->---3------>----5---->----+
LES / \ HOMMES VONT
/ \
/ \
| OLD |
+-->--+
VIEUX
]]>
Family Trees
The next example provides an encoding a portion of a
family tree, in which nodes are used to represent
individuals, and parents of individuals, and arcs are used to
represent common parentage and descent links. Let us suppose,
further, that information about individuals is contained in feature
structures, which are contained in feature-structure libraries
elsewhere in the document (see ). We can use the
value attribute on node elements to point to those
feature structures. Assume that, in some particular representation of
the graph, nodes representing females are framed by circles, nodes
representing males are framed by boxes, and nodes representing parents
are framed by diamonds.
--K+A--<-Amberley
|
So | Da
+----<-------+----->----+
| | So |
Bertrand +->-+ Rachel
| |
| Frank
Mo Fa | Fa Mo
Peter->--P+B--<-+->--D+B--<-Dora
| |
So | Da | So
+-<-+ +--<--+-->--+
| | |
Conrad Kate John
]]>
Historical Interpretation
For our final example, we represent graphically the relationships
among various geographic areas mentioned in a
seventeenth-century Scottish document. The document itself is
a sasine, which records a grant of land
from the earl of Argyll to one Donald McNeill, and reads in part
as follows (abbreviations have been expanded silently,
and [...] marks illegible passages):
Item instrument of Sasine given the said Hector
Mcneil confirmed and dated 28 May 1632
[...] at Edinburgh upon the 15 June 1632
Item ane charter granted by Archibald late earl
of Argyle and Donald McNeill of Gallachalzie wh
makes mention that ...
the said late Earl yields and grants
to the said Donald MacNeill ...
All and hail the two merk land of old extent
of Gallachalzie with the pertinents by and in
the lordship of Knapdale within the sherrifdome
of Argyll
[description of other lands granted follows ...]
This Charter is dated at Inverary the 15th May 1669
In this example, we are concerned with the land and pertinents (i.e.
accompanying sources of revenue) described as the two merk land of
old extent of Gallachalzie with the pertinents by and in the lordship of
Knapdale within the sherrifdom of Argyll.
The passage concerns the following pieces of land:
the Earl of Argyll's land (i.e. the lands granted by this clause
of the sasine)
two mark of land in Gallachalzie
the pertinents for this land
the Lordship of Knapdale
the sherrifdom of Argyll
We will represent these geographic entities as nodes in a graph.
Arcs in the graph will represent the following relationships among
them:
containment (INCLUDE)
location within (IN)
contiguity (BY)
constituency (PART OF)
Note that these relationships are logically related: include
and in, for example, are inverses of each other: the Earl of
Argyll's land includes the parcel in Gallachalzie, and the parcel is
therefore in the Earl of Argyll's land. Given an explicit set of
inference rules, an appropriate application could use the graph we are
constructing to infer the logical consequences of the relationships we
identify.
Let us assume that feature-structure analyses are available which
describe Gallachalzie, Knapdale, and Argyll. We will link to those
feature structures using the value attribute on the nodes
representing those places. However, there may be some uncertainty as to
which noun phrase is modified by the phrase within the sheriffdome of
Argyll: perhaps the entire lands (land and pertinents) are in
Argyll, perhaps just the pertinents are, or perhaps only Knapdale is
(together with the portion of the pertinents which is in Knapdale). We
will represent all three of these interpretations in the graph; they
are, however, mutually exclusive, which we represent using the
excl attribute defined in
chapter .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 .
We represent the graph and its encoding as follows, where
the dotted lines in the graph indicate the mutually exclusive arcs; in
the encoding, we use the exclude attribute to indicate those
arcs.
-INCLUDE---> Pertinents
| : : | |
Gallachalzie IN ...<..IN..<.....: | |
: : | |
: : INCLUDE INCLUDE
: : | |
: : (part of pertinents) (part)
: : | |
: : BY PART OF
: : | |
: : Lordship of Knapdale
: : :
: : ...<.IN..<.......:
: : :
Sherrifdom of Argyll
]]>
The graph formalizes the following relationships:
the Earl of Argyll's land includes (the
parcel of land in) Gallachalzie
the Earl of Argyll's land includes the
pertinents of that parcel
the pertinents are (in part) by the
Lordship of Knapdale
the pertinents are (in part) part of the
Lordship of Knapdale
the Earl of Argyll's land, or the pertinents, or the Lordship of
Knapdale, is in the Sherrifdom of Argyll
We encode the graph thus:
]]>
Trees
A tree is a connected acyclic graph. That is, it is
possible in a tree graph to follow a path from any vertex to any other
vertex, but there are no paths that lead from any vertex to itself. A
rooted tree is a directed graph based on a tree; that is, the arcs in
the graph correspond to the arcs of a tree such that there is exactly
one node, called the root, for which there is a path from
that node to all other nodes in the graph. For our purposes, we may
ignore all trees except for rooted trees, and hence we shall use the
tree element for rooted trees, and the root element
for its root. The nodes adjacent to a given node are called its
children, and the node adjacent from a given node is called
its parent. Nodes with both a parent and children are
called internal nodes, for which we use the iNode
element. A node with no children is tagged as a leaf. If the
children of a node are ordered from left to right, then we say that that
node is ordered. If all the nodes of a tree are ordered,
then we say that the tree is an ordered tree. If some of
the nodes of a tree are ordered and others are not, then the tree is a
partially ordered tree. The ordering of nodes and trees
may be specified by an attribute; we take the default ordering for trees
to be ordered, that roots inherit their ordering from the trees in which
they occur, and internal nodes inherit their ordering from their
parents. Finally, we permit a node to be specified as following other
nodes, which (when its parent is ordered) it would be assumed to
precede, giving rise to crossing arcs.
The elements used for the
encoding of trees have the following descriptions and attributes.
encodes a tree, which is made up of a root, internal nodes,
leaves, and arcs from root to leaves.
Attributes include:
gives the maximum number of children of the root and
internal nodes of the tree.indicates whether or not the tree is ordered, or if it is
partially ordered.
Legal values are:
indicates that all of the branching nodes of the tree are
ordered.indicates that some of the branching nodes of the tree are
ordered and some are unordered.indicates that all of the branching nodes of the tree are
unordered.gives the order of the tree, i.e., the number of its nodes.represents the root node of a tree.
Attributes include:
gives a label for a root node.provides the value of the root, which is a feature
structure or other analytic element.provides a list of IDs of the elements which are the
children of the root node.indicates whether or not the root is ordered.
Legal values are:
indicates that the children of the root are ordered.indicates that the children of the root are unordered.gives the out degree of the root, the number of its
children.represents an intermediate (or internal) node of a tree.
Attributes include:
gives a label for an intermediate node.provides the value of an intermediate node, which is a
feature structure or other analytic element.provides a list of IDs of the elements which are the
children of the intermediate node.provides the ID of the element which is the parent of this
node.indicates whether or not the internal node is ordered.
Legal values are:
indicates that the children of the intermediate node are
ordered.indicates that the children of the intermediate node are
unordered.provides an ID of the element which this node follows.gives the out degree of an intermediate node, the number of
its children.encodes the leaves (terminal nodes) of a tree.
Attributes include:
gives a label for a leaf.provides the value of a leaf, which is a feature structure
or other analytic element.provides the ID of parent of a leaf.provides an ID of an element which this leaf follows.
Here is an example of a tree. It represents the order in which the
operators of addition (symbolized by +), exponentiation
(symbolized by **) and division (symbolized by
/) are applied in evaluating the arithmetic formula
((a**2)+(b**2))/((a+b)**2) . In drawing the graph, the root is
placed on the far right, and directionality is presumed to be to the
left.
]]>
In this encoding, the arity attribute represents the
arity of the tree, which is the greatest value of the
outDegree attribute for any of the nodes in the tree. If, as
in this case, arity=2, we say that the tree is a
binary tree.
Since the left-to-right (or top-to-bottom!) order of the children of
the two + nodes does not affect the arithmetic result in
this case, we could represent in this tree all of the arithmetically
equivalent formulas involving its leaves, by specifying the attribute
ord=N on those two iNode elements, the attribute
ord=Y on the root and other iNode elements,
and the attribute ord=partial on the tree element,
as follows.
]]>
This encoding represents all of the following:
((a**2)+(b**2))/((a+b)**2)((b**2)+(a**2))/((a+b)**2)((a**2)+(b**2))/((b+a)**2)((b**2)+(a**2))/((a+b)**2)
Linguistic phrase structure is very commonly represented by trees.
Here is an example of phrase structure represented by an ordered tree
with its root at the top, and a possible encoding.
]]>
Finally, here is an example of an ordered tree, in which a particular
node which ordinarily would precede another is specified as following
it. In the drawing, the xxx symbol indicates that the arc
from VB to PT crosses the arc from VP to PN.
]]>
The formal declarations of the tree, root,
iNode and leaf elements are as follows.
]]>
Another Tree Notation
In this section, we present an alternative to the method of
representing the structure of ordered rooted trees that is given in
section , 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
eTree, for embedding tree. Whereas in a
tree, the relationship among the parts is indicated by the
children attribute, and by the names of the elements
root, iNode and leaf, the relationship among
the parts of an eTree is indicated simply by the arrangement of
their content. However, we have chosen to enable encoders to
distinguish the terminal elements of an eTree by means of the
empty eLeaf element, though its use is not required; the
eTree element can also be used to identify the terminal nodes
of eTree elements. We also provide a triangle
element, which can be thought of as an underspecifiedeTree, that is an eTree in which certain information
has been left out. In addition, we provide a forest element,
which consists of one or more tree, eTree or
triangle elements, and a forestGrp element, which
consists of one or more forest elements. The elements used for
the encoding of embedding trees and the units containing them have the
following descriptions and attributes.
provides an alternative to tree element for
representing
ordered rooted tree structures.
Attributes include:
gives a label for an embedding tree.provides the value of an embedding tree, which is a feature
structure or other analytic element.provides for an underspecified eTree, that is,
an
eTree with information left out.
Attributes include:
gives a label for an underspecified embedding tree.provides the value of a triangle, which is the SGML
identifier of a feature structure or other analytic
element.provides explicitly for a leaf of an embedding tree, which
may also
be encoded with the eTree element.
Attributes include:
gives a label for a leaf of an embedding tree.provides the value of an embedding leaf, which is a feature
structure or other analytic element.provides for groups of rooted trees.
Attributes include:
identifies the type of the forest.provides for groups of forests.
Attributes include:
identifies the type of the forest group.
Like the root, iNode and leaf of a
tree, the eTree, triangle and
eLeaf elements may also have label and
value attributes.
To illustrate the use of the eTree and eLeaf
elements, here is an encoding of the second example in section , repeated here for convenience.
]]>
Next, we provide an encoding, using the triangle element, in
which the internal structure of the eTree labeled
NP is omitted.
]]>
Ambiguity involving alternative tree structures associated with the
same terminal sequence can be encoded relatively conveniently using a
combination of the exclude and copyOf attributes
described in sections and . In
the simplest case, an eTree may be part of the content of
exactly one of two different eTree elements. To mark it up,
the embedded eTree may be fully specified within one of the
embedding eTree elements to which it may belong, and a
virtual copy, specified by the copyOf attribute, may appear
on the other. In addition, each of the embedded elements in question
is specified as excluding the other, using the exclude
attribute. To illustrate, consider the English phrase see the
vessel with the periscope, which may be considered to be
structurally ambiguous, depending on whether the phrase with
the periscope is a modifier of the phrase the
vessel or a modifier of the phrase see the
vessel. This ambiguity is indicated in the sketch of the
ambiguous tree by means of the dotted-line arcs. The markup using the
copyOf and exclude attributes follows the
sketch.
]]>
To indicate that one of the alternatives is selected, one may specify
the select attribute on the highest eTree as
either select=ppa or select=ppb; see section .
Depending on the grammar one uses to associate structures with
examples like see the man with the periscope, the
representations may be more complicated than this. For example,
adopting a version of the X-bar theory of phrase structure
originated by JackendoffR. Jackendoff,
X-Bar Syntax, 1977, 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.
]]>
A derivation in a generative grammar is often thought
of as a set of trees. To encode such a derivation, one may use the
forest element, in which the trees may be marked up using the
tree, the eTree or the triangle element.
The type 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 what you do (as in
this is what you do) from the underlying
you do what The symbols
e and t denote special theoretical constructs
(empty category and trace respectively), which
need not concern us here..
]]>
In this markup, we have used copyOf 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
corresp attribute (see section ) to link
those elements in the second stage with corresponding elements in the
first stage that are not copies of them.
If a group of forests (e.g. a full grammatical derivation including
syntactic, semantic and phonological subderivations) is to be
articulated, the grouping element forestGrp may be used.
The formal declarations of the eTree, triangle,
eLeaf, forest and forestGrp elements are as
follows.
]]>