Many predicates define some kind of an acyclic path built from edges defined via a binary relation, quite similarly to defining transitive closure. A generic definition is thus called for.
Note that the notions defined in graph theory do not readily match what is commonly expected. Most notably, we are not interested in the edges' names.
Worse, also graph theory has changed a bit, introducing the notion of walk, noting
Traditionally, a path referred to what is now usually known as an open walk. Nowadays, when stated without any qualification, a path is usually understood to be simple, meaning that no vertices (and thus no edges) are repeated. (The term chain has also been used to refer to a walk in which all vertices and edges are distinct.)
So my question is: How to name and define this functionality?
What I have done so far is to define:
path(Rel_2, Path, X0,X)
The first argument has to be the continuation of the relation which is an incomplete goal that lacks two further arguments. Then comes either the Path
or the pair of vertices.
Example usage
n(a, b).
n(b, c).
n(b, a).
?- path(n,Xs, a,X).
Xs = [a], X = a
; Xs = [a, b], X = b
; Xs = [a, b, c], X = c
; false.
Implementation
:- meta_predicate(path(2,?,?,?)).
:- meta_predicate(path(2,?,?,?,+)).
path(R_2, [X0|Ys], X0,X) :-
path(R_2, Ys, X0,X, [X0]).
path(_R_2, [], X,X, _).
path(R_2, [X1|Ys], X0,X, Xs) :-
call(R_2, X0,X1),
non_member(X1, Xs),
path(R_2, Ys, X1,X, [X1|Xs]).
non_member(_E, []).
non_member(E, [X|Xs]) :-
dif(E,X),
non_member(E, Xs).
I do not see the reason to define in path/4 the arguments "start node" and "end node". It seems that a simple path/2 with the rule and the list of nodes must be enough.
If the user wants a list starting with some node (by example, 'a'), he can query the statement as: path( some_rule, ['a'|Q] ).
A user could, by example, request for path that have length 10 in the way: length(P,10), path( some_rule, P).
* Addendum 1 *
Some utility goals can be easily added, but they are not the main subject. Example, path/3 with start node is:
* Addendum 2 *
Addition of last node as argument could give the false idea that this argument drives the algorithm, but it doesn't. Assume by example:
and trace algorithm execution for the query:
as you can see, in this case algorithm fails to brute force. For this reason, if algorithm is not improved, I suggest do not add "end node" as "path" argument.