2. Bottom-up, tail recursion using an accumulator

tree.svg

Here we introduce an auxiliary or helper function (good style is to give these trailing underscores), which return a reversed list. Though more lines of code, this often executes faster, and is more flexible for filtering out 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([Start], Path) :-
    depthfirst_([Start], [], RevPath),
    reverse(RevPath, Path).

depthfirst_([], Acc, Acc).

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

breadthfirst([Start], Path) :-
    breadthfirst_([Start], [], RevPath),
    reverse(RevPath, Path).

breadthfirst_([], Acc, Acc).

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

As with TopDownRecursion 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 HistoryFiltering, we'll handle cycle traps.

BottomUpRecursion (last edited 2021-09-12 21:10:54 by RobertLaing)