Transitive Closures


A tree walking technique that's very quick and easy to write in Prolog is called a transitive closure which is a recursive algorithm with this basic structure:

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).

Then if I query tc(a, X)., the order of Xs shows this is as follows (mainly the same as breadth first search as covered in BreadthDepthFirst, but not exactly):

X = b
X = c
X = d
X = e
X = f
X = k
X = l
X = m
X = t
X = g
X = h
X = i
X = n
X = o
X = p
X = j
X = q
X = r
X = s

A good description of transitive closures is given in Al Aho's and Jeff Ullman's free online textbook Foundations of Computer Science, specifically Chapter 9 The Graph Data Model.

Those familiar with transitive closures, but not Prolog, tend to wonder why we don't just have our arc facts and one rule:

arc(X, Z) :-
  arc(X, Y),
  arc(Y, Z).

The next subsection, CyclesWithTabling, shows a way to achieve that. However, it's probably better style to write a separately named recursive rule such as tc. A common Prolog novice mistake is to write recursive rules something like this:

tc(X, Z) :-
    tc(X, Y),
    arc(Y, Z).

That often results in having to press Ctrl-C to break out of an endless loop. A good rule of thumb is to always put the recursive call as the final statement.

We'll complicate things by adding a cycle and show a simple way to avoid getting trapped in it next in CyclesWithTabling.

TransitiveClosures (last edited 2021-09-02 21:01:20 by RobertLaing)