- 1
-
Observe that we have lost an explicit representation of the
left-to-right order of our nodes. This can be recovered in one of
two ways: either from the tree addresses assigned to each node, or,
if we have been careful about the order in which nodes are entered
in the list, we can recover it from there as well. Otherwise, we
must have one graph for the dominance relation and another for the
precedence relation; i.e., a graph with one set of nodes, but two
types of arc.
- 2
- Well, actually it will work. Prolog does allow programs to modify
themselves. But you're not supposed to know about that yet!
- 3
- This is related to the fact that changing the order of records in
the graph structure does not change which ``real'' graph it
denotes. Put another way, the order in which nodes are visited in a
recursion on the node list does not reflect any essential property
of the graph that that list represents.
- 4
-
As a useful ``boundary case'' consider the graph with an empty
arc-relation: no
node is connected to any other! Or the other end of the scale, where
every pair of nodes are symmetrically connected to each other, i.e.,
where the arc relation equals N× N. Here any node at all
could serve as a root, and there are loops everywhere. We will need
to handle both of these cases with one solution.
- 5
- Note that if we make the selection of the starting node
deterministic, say by always choosing the head of the current graph
structure, then the sequence of starting nodes is now fully
determined by any particular graph structure. Note further, however,
that any given graph can be represented by several different
graph structures, that is, lists of adjacency lists.
For example, randomly permuting the list of adjacency records does
not in any way affect which graph it represents.