Graph Traversal

To illustrate ways of doing graph traversal in Prolog, we'll use the following DAG before introducing a cycle to complicate things a little:

tree.svg

The above diagram can be written in Prolog like so:

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

Introducing a cycle as in the diagram below simply involved adding arc(k, e)

tree_cycle.svg

Graph Traversal has been split into the following subsections:

  1. TransitiveClosures

  2. CyclesWithTabling

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

GraphTraversal (last edited 2021-09-03 08:59:47 by RobertLaing)