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