If I understand your problem statement, you
- Have a directed graph (a digraph) defined by
link(From,To).
- Wish to be able to traverse that digraph from some origin node to some destination node and identify the path[s] between the 2 nodes.
This is a pretty straightforward problem that doesn't require assert/1 or retract/1.
A common pattern in Prolog programming is the use of helper predicates that carry extra arguments that track the persistent state required to accomplish the task at hand.
Graph traversal, as an algorithm, is pretty easy (and nicely recursive):
- You can travel from node A to node B if nodes A and B are directly connected, or
- You can travel from node A to node B if node A is connected to some other node X such that you can travel from node X to node B.
The trick here is that you need to track what nodes you've visited (and their order), and you'd want to do that anyway, so that you can detect cycles in the graph. Trying to traverse a cyclic graph like this::
a → b → c → b
leads to infinite recursion unless you check to see whether or not you've already visited node b.
That leads pretty direction to an implementation like this:
- A
traverse/3 predicate, traverse(Origin, Destination,Path), and,
- A
traverse/4 helper predicate, traverse(Origin,Destination,Visited,Path).
You can fiddle with it at https://swish.swi-prolog.org/p/oZUomEcK.pl
link(1,2).
link(2,3).
link(3,4).
link(3,6).
link(6,7).
link(6,5).
% ---------------------------------------------------------------------------
%
% traverse( Origin, Destination, ReversePath )
%
% traverse/3 traverses a directed graph defined by link(From,To).
% The path taken is listed in reverse order:
% [Destination, N3, N2, N1 , Origin]
%
% ---------------------------------------------------------------------------
traverse(A,B,P) :- % to traverse a graph
traverse(A,B, [], P) % - invoke the helper, seeding the visited list with the empty list
. %
% ---------------------------------------------------------------------------
% traverse( Origin, Destination, Visited, ReversePath )
% ---------------------------------------------------------------------------
traverse( A , B , V , [B,A|V] ) :- % Traversal of a graph from A to B,
link(A,B) % - succeeds if there exists an edge between A and B.
. %
traverse( A , B , V , P ) :- % otherwise, we can get from A to B if...
link(A,X) , % - an edge exists between A and some node X
\+ member(X,V) , % - that we have not yet visited,
traverse(X,B,[A|V],P) % - and we can get from X to B (adding A to the list of visited nodes
. %
Once you have that, invoking traverse/3 with all arguments unbound
?- traverse(A,B,P) .
results in finding all paths in the graph via backtracking.
If you want to know all the paths in the graph, beginning at a specific origin node, invoke it with the origin argument bound:
?- traverse(1,B,P) .
And if you want to know if two specific nodes are connected, invoke it with both origin and destination bound:
?- traverse(1,5,P) .
Note: because we're building the list of visited nodes by prepending them to the list of visited nodes, the path thus build is in reverse (destination-first) order. If you want the path in proper (origin-first) order, just use reverse/2 in the main predicate:
traverse(A,B,P) :- traverse(A,B, [], RP ), reverse(RP,P) .
