Advanced · Lesson 38 of 43

Graphs & search

Paths, cycles, shortest routes, and breadth-first search.

Graphs fit Prolog naturally: facts are edges, and finding a path is just a query. Here is a small directed graph, with a cycle (e → a) to keep us honest:

edge(a, b).
edge(a, c).
edge(b, d).
edge(c, d).
edge(d, e).
edge(e, a).

Reachability: and why a naive version loops

The obvious definition of "is there a path from X to Y" is:

naive(X, Y) :- edge(X, Y).
naive(X, Y) :- edge(X, Z), naive(Z, Y).

% a separate little loop, to see the problem: p and q point at each other
edge(p, q).
edge(q, p).

?- once(naive(a, d))

?- naive(p, r)

naive(a, d) is found at once. But a goal with no answer, naive(p, r), where r can't be reached, chases the cycle p → q → p → … for ever. In any graph with cycles, the fix is to remember where we've been.

Paths with a visited list

% path(From, To, Path): Path is a cycle-free route
path(X, Y, Path) :-
    walk(X, Y, [X], Rev),
    reverse(Rev, Path).

walk(X, X, Visited, Visited).
walk(X, Y, Visited, Path) :-
    edge(X, Z),
    \+ memberchk(Z, Visited),
    walk(Z, Y, [Z|Visited], Path).

?- path(a, e, P)

?- findall(P, path(a, e, P), Paths), length(Paths, N)

?- setof(Y, P^path(a, Y, P), Reachable)

Every recursive step adds the new node to Visited and refuses to revisit one. The cycle can no longer trap us.

Shortest path

With all paths available as a list, "shortest" is just a minimum:

?- aggregate_all(min(L, P), (path(a, e, P), length(P, L)), min(Len, Best))

That enumerates every path, which explodes on big graphs. Breadth-first search explores in layers and stops at the first hit, so it finds a shortest path directly. Keep a queue of partial paths:

bfs(Start, Goal, Path) :-
    bfs_([[Start]], Goal, [Start], Rev),
    reverse(Rev, Path).

bfs_([[Goal|Rest]|_], Goal, _, [Goal|Rest]).
bfs_([[Node|Rest]|Queue], Goal, Seen, Path) :-
    findall([Next, Node|Rest],
            ( edge(Node, Next), \+ memberchk(Next, Seen) ),
            Extended),
    findall(Next, member([Next|_], Extended), Nexts),
    append(Seen, Nexts, Seen1),
    append(Queue, Extended, Queue1),
    bfs_(Queue1, Goal, Seen1, Path).

?- bfs(a, e, P)

Weighted edges

Add a cost to each edge and accumulate it along the way:

road(a, b, 4).  road(a, c, 1).
road(c, b, 2).  road(b, d, 5).
road(c, d, 8).

route(X, Y, Cost, Path) :- travel(X, Y, [X], 0, Cost, Rev), reverse(Rev, Path).

travel(X, X, V, C, C, V).
travel(X, Y, V, C0, C, P) :-
    road(X, Z, W), \+ memberchk(Z, V),
    C1 is C0 + W,
    travel(Z, Y, [Z|V], C1, C, P).

?- findall(C-P, route(a, d, C, P), Routes), keysort(Routes, Sorted)

?- aggregate_all(min(C, P), route(a, d, C, P), min(Cost, Best))

Exercise: Reachable, safely

The graph edge(a,b). edge(b,c). edge(c,a). edge(c,d). is loaded (it has a cycle). Write reachable(X, Y): there is a path of one or more edges from X to Y. It must terminate for every query, keep a visited list.