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