Graph Traversal
By Robert Laing
Traversing trees comes up a lot in coding. For intance, I needed to write a recursive HTML template to generate the table of the contents on the left of this web page using Hugo, and I posted my solution to Hugo’s discourse group for anyone interested.
The pattern I followed is called a transitive closure. Whenever I need some computer science theory, I turn to a textbook written by Turing Award winners Al Aho and Jeff Ullman which they have kindly made freely available online. They introduce transivitive closures in chapter 7, The Set Data Model, and expand on it in chapter 9, The Graph Data Model.
To illustrate ways of doing graph traversal in Prolog, I’ll initially use the following directed acyclic graph (DAG) before introducing a cycle to complicate things a little later.
After dabbling with the various JavaScript diagraming tools such as d3 and vis, I’ve fallen back on Graphviz’s DOT because its syntax for describing graphs is very prologish, and that’s what I’ve used here.
Dot unfortunately is not in the huge list of languages Hugo’s syntax highlighter supports.
digraph G {
a -> b;
a -> c;
a -> d;
b -> e;
b -> f;
c -> g;
c -> h;
c -> i;
d -> j;
e -> k;
f -> l;
f -> m;
h -> n;
i -> o;
i -> p;
j -> q;
j -> r;
j -> s;
m -> t;
}
Running dot -T svg -o tree.svg tree.dot
produces the following diagram:
The above diagram can be turned into Prolog code as below. You could either make that a file, called say tree.pl which can be loaded in a the swipl repl as consult(tree)., or you could simply cut ’n paste it into the left-hand box of the SWISH browser-based version of SWI Prolog.
arc(a, b).
arc(a, c).
arc(a, d).
arc(b, e).
arc(b, f).
arc(c, g).
arc(c, h).
arc(c, i).
arc(d, j).
arc(e, k).
arc(f, l).
arc(f, m).
arc(h, n).
arc(i, o).
arc(i, p).
arc(j, q).
arc(j, r).
arc(j, s).
arc(m, t).
tc(X, Y) :-
arc(X, Y).
tc(X, Z) :-
arc(X, Y),
tc(Y, Z).
At this stage we are just concerned about visiting every descendent of a given starting node in our tree, not so much the order.
For the arcs ordered as above, the query tc(a, X)
produces Xs in in the following order
b, c, d, e, f, k, l, m, t, g, h, i, n, o, p, j, q, r, s
This works fine provided we don’t introduce any cycles such as the small modification below:
Now our path is going to be
b, c, d, e, f, k, e, k, e, k, e,...
Various techniques for avoiding a graph traverser going into an endless loop are available and will be discussed in the coming sections.
- Transitive Closures
- CyclesWithTabling
- BreadthDepthFirst
Typically, we want to use graph traversal for PathFinding. To keep things simple here, we’ll cover that in a separate section later which expands on the examples here.
Combined with tabling which I’ll introduce in the next section. this gives a very succinct way of visiting all linked nodes in a graph. The snag is, we don’t have much control over the order in which the nodes are visited.
As I relearnt transversing the directories I’d split these notes into to create a table of content, order is usually very important in graph traversal applications. For instance, Hugo offers a variety of ways to order pages. The one I’ve used is giving each of my content files a weight attribute, but it could also be done alphabetically by title or by the time the file was last edited.