Menu
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.
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. :- 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). 
621
A trail is a walk with no repeated edge. A path is a walk with no repeated vertex. A u, v-walk, u, v-trail, u, v-path is a walk, trail, path, respectively, with first vertex u and last vertex v. If u = v then the u, v-walk and u, v-trail is closed.
A trail, also known as a path or track, is an unpaved lane or small road usually through a natural area. In the United Kingdom and the Republic of Ireland, a path or footpath is the preferred term for a pedestrian or hiking trail.
If the vertices in a walk are distinct, then the walk is called a path. If the edges in a walk are distinct, then the walk is called a trail. In this way, every path is a trail, but not every trail is a path.
A path is a sequence of vertices with the property that each vertex in the sequence is adjacent to the vertex next to it. A path that does not repeat vertices is called a simple path. A circuit is path that begins and ends at the same vertex. A circuit that doesn't repeat vertices is called a cycle.
If all the edges (but no necessarily all the vertices) of a walk are different, then the walk is called a trail. If, in addition, all the vertices are difficult, then the trail is called path. The walk vzzywxy is a trail since the vertices y and z both occur twice. The walk vwxyz is a path since the walk has no repeated vertices.
Path: A path is a simple graph whose vertices can be ordered so that two vertices are adjoint iff they are constitutive in the list. Walk: it is a list of vertices and edges v 0, e 1, v 1, …, e k, v k for 1 ≤ i ≤ k, e i has an endpoints v i − 1, v i. Trial: It is an walk with no repeated edge.
A trailis a walk that does not pass over the same edge twice. A trail might visit the same vertex twice, but only if it comes and goes from a different edge each time. A trail from U to V
Definition of a path/trail/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.)
How about defining path/4 like this?
path(R_2, Xs, A,Z) :- % A path `Xs` from `A` to `Z` is ... walk(R_2, Xs, A,Z), % ... a walk `Xs` from `A` to `Z` ... all_dif(Xs). % ... with no duplicates in `Xs`. To aid universal termination, we swap the two goals in above conjunction ...
path(R_2, Xs, A,Z) :- all_dif(Xs), % enforce disequality ASAP walk(R_2, Xs, A,Z). ... and use the following lazy implementation of all_dif/1:
all_dif(Xs) :- % enforce pairwise term inequality freeze(Xs, all_dif_aux(Xs,[])). % (may be delayed) all_dif_aux([], _). all_dif_aux([E|Es], Vs) :- maplist(dif(E), Vs), % is never delayed freeze(Es, all_dif_aux(Es,[E|Vs])). % (may be delayed)
walk/4 is defined like path/4 and path/5 given by the OP:
:- meta_predicate walk(2, ?, ?, ?). walk(R_2, [X0|Xs], X0,X) :- walk_from_to_step(Xs, X0,X, R_2). :- meta_predicate walk_from_to_step(?, ?, ?, 2). walk_from_to_step([], X,X, _). walk_from_to_step([X1|Xs], X0,X, R_2) :- call(R_2, X0,X1), walk_from_to_step(Xs, X1,X, R_2). IMO above path/4 is simpler and more approachable, particularly for novices. Would you concur?
56
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
