1. Top-down

Lets start with this acyclic tree introduced in GraphTraversal before handling cycles in HistoryFiltering.


The first way of doing this has as its base case two empty lists depthfirst([], []) and its recursive case copies the head of the frontier to the head of the visited list. This requires symmetry between the Frontier and Visited lists, which breaks when we introduce one or more cycles.

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

getchildren(Parent, Children) :-
    findall(Child, arc(Parent, Child), Unsorted),
    sort(Unsorted, Children).

depthfirst([], []).

depthfirst([Node|Frontier], [Node|Visited]) :-
    getchildren(Node, Children),
    append(Children, Frontier, NewFrontier),
    depthfirst(NewFrontier, Visited).

breadthfirst([], []).

breadthfirst([Node|Frontier], [Node|Visited]) :-
    getchildren(Node, Children),
    append(Frontier, Children, NewFrontier),
    breadthfirst(NewFrontier, Visited).

breadthfirst([a], Path) will return the nodes in alphabetical order whereas depthfirst([a], Path) returns Path = [a, b, e, k, f, l, m, t, c, g, h, n, i, o, p, d, j, q, r, s]

Next, in BottomUpRecursion, instead of copying nodes from the frontier to the visited list in the predicate head, we'll expand the visited list while depleting the frontier list by copying fresh nodes in the last, recursive statement. In Prolog, we need to keep an unused variable to return the final visited list, which then needs to be reversed to get it back into the expected depth or breadth first order. This allows us to filter out children already in the visited list as explained in HistoryFiltering.

TopDownRecursion (last edited 2021-09-09 08:33:34 by RobertLaing)