Prolog Cookbook

  1. Documenting, testing, and moduling
  2. Classical Logic
    1. Negation
      1. Not
      2. Difference
      3. Fill Values
      4. De Morgan's Law
    2. Conjunction
      1. And
      2. Intersection
      3. Inner Join
      4. Product
      5. Series
    3. Disjunction
      1. Or
      2. Union
      3. Outer Join
      4. Sum
      5. Parallel
    4. Implication
      1. Proofs
    5. Equivalence
  3. Automata
  4. Graph Traversal
    1. Depth First
    2. Breadth First
    3. Transitive Closures
  5. Route Finding
  6. Puzzle Solving

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.

Figure 1: Example tree with nodes labeled in alphabetical order by level

The above diagram can be turned Prolog code as below. You could either make that a file, called say 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

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.