Prolog for graph search: paths and cycle checking

Graphs as facts

State-space search (M3) and the Prolog assignments A1 and A2 all start the same way: represent the graph as a set of edge/2 facts, then write a recursive predicate that walks from a start node to a goal node. This lesson is the bridge from "Prolog lists" to "Prolog search".

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

The cycle problem

A naive path finder — "there is a path from X to Y if there is an edge X→Y, or an edge X→Z and a path Z→Y" — loops forever on any graph with a cycle, because nothing stops it from revisiting a node. The fix used throughout the assignments is to carry a visited list and forbid stepping onto an already-visited node with \+ member(Next, Visited) (negation-as-failure: succeed only if Next is *not* a member).

Worked example — the acyclic path finder (A1 pattern)

path(Goal, Goal, Visited, Path) :- reverse(Visited, Path).
path(Node, Goal, Visited, Path) :-
    edge(Node, Next),
    \+ member(Next, Visited),
    path(Next, Goal, [Next | Visited], Path).

acyclic_path(Start, Goal, Path) :- path(Start, Goal, [Start], Path).

Read it carefully:

- Base case — when the current node *is* the goal, we are done; Visited holds the path in reverse (we prepended each node), so reverse flips it to forward order. - Recursive step — pick an edge Node → Next, *check Next has not been visited* (the cycle guard), then recurse with Next prepended to Visited.

The accumulator trick — prepend to Visited, reverse at the goal — is idiomatic Prolog: prepending ([Next | Visited]) is O(1), whereas appending to the end each step would be O(n).

Tracing acyclic_path(a, e, Path): from a the first edge is a→b, then b→d, then d→e (goal) — so it returns [a, b, d, e]. Because Prolog tries edge(a, b) before edge(a, c) (clause order), the b-route is found first; backtracking would later yield the c-route [a, c, d, e].

The Python exercise below does the same DFS with a visited set, deterministic given the edge order.