Path Finding

Continuing with the example introduced in GraphTraversal, instead of exploring the entire graph, we want to write a predicate route(Start, End, Path), which returns the nodes from Start to End. For instance, route(a, t, Path). returns Path = [a, b, f, m, t]

tree.svg

If the graph is known and available in a database, all we need is to refactor TransitiveClosures a bit.

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

route(Start, End, Path) :-
    tc(Start, End, [Start], RevPath),
    reverse(RevPath, Path).

tc(X, Y, Path, [Y|Path]) :-
    arc(X, Y).

tc(X, Z, Path, Acc) :-
    arc(X, Y),
    tc(Y, Z, [Y|Path], Acc).

Going in circles

tree_mcircle.svg

Adding arc(m, m) to the graph produces the snag that it isn't clear to the path finder how often to circle the m node on its way to t:

Path = [a, b, f, m, t]
Path = [a, b, f, m, m, t]
Path = [a, b, f, m, m, m, t]
Path = [a, b, f, m, m, m, m, t]
...

A trick similar to HistoryFiltering of ignoring nodes already visited helps.

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).
arc(m, m).

route(Start, End, Path) :-
    tc(Start, End, [Start], RevPath),
    reverse(RevPath, Path).

tc(X, Y, Path, [Y|Path]) :-
    arc(X, Y).

tc(X, Z, Path, Acc) :-
    arc(X, Y),
    \+memberchk(Y, Path), 
    tc(Y, Z, [Y|Path], Acc).

A snag with both the above is Path = [a, b, f, m, t] is repeatedly seen as an answer. As with CyclesWithTabling, the solution is to add :- table route/3. which removes duplicate results.

Alternative routes

Lets modify the graph to create two ways of getting from a to t

tree_nroute.svg

:- table route/3.

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).
arc(m, m).
arc(n, t).

route(Start, End, Path) :-
    tc(Start, End, [Start], RevPath),
    reverse(RevPath, Path).

tc(X, Y, Path, [Y|Path]) :-
    arc(X, Y).

tc(X, Z, Path, Acc) :-
    arc(X, Y),
    \+memberchk(Y, Path), 
    tc(Y, Z, [Y|Path], Acc).

Then route(a, t, Path). produces Path = [a, b, f, m, t] and Path = [a, c, h, n, t].

If the goal is unreachable, eg route(a, x, Path)., the above code returns false.

Often, as illustrated in PuzzleSolving, the graph has to be built dynamically, where TransitiveClosures with CyclesWithTabling won't work, and we need to turn to IterativeDeepening.

PathFinding (last edited 2021-09-14 07:45:49 by RobertLaing)