46

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).
false
  • 10,264
  • 13
  • 101
  • 209
  • Is path/5 tail recursive? – pasaba por aqui May 30 '15 at 21:58
  • 1
    @pasa: only if the goal `call(R_2, X0,X1)` is determinate. – false May 30 '15 at 22:18
  • 3
    You should figure out a way to accept an answer for this question to increase its visibility on search results. I know it is there so I usually search for "[prolog] path trail" but it does not show up as high as it should in less specific searches, esp. considering how many votes the question itself has. –  May 27 '17 at 05:39
  • 1
    @Boris: So far, [8̶0̶0̶ 850](/posts/30328433/timeline) have been spent for increased visibility. I only invest my points above 10k – false May 27 '17 at 10:39
  • To be fair, I cannot easily imagine an "answer" that would obviously improve on what is already in the question. –  May 27 '17 at 11:16
  • In this situation, the bounty-reason "Draw attention" is most appropriate. – false May 27 '17 at 11:18
  • @XXX: anything wrong? – false Jun 02 '17 at 18:20
  • @XXX, boris: Is it because of -325? Seems some more people did not like this, although their upvoting was reversed... – false Jun 06 '17 at 10:11
  • @false I am just not interesting in contributing to Stackoverflow for many reasons; this was not the reason, just a symptom ;-). You would not believe how difficult it is to have your account removed/deleted, I wonder what kind of rule I would have to break to finally achieve it.... –  Jun 07 '17 at 10:52
  • 2
    @XXX: That's a pity in any case. – false Jun 07 '17 at 11:36

3 Answers3

12

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?

Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
11

I want to focus on naming the predicate.

  • Unlike maplist/2, the argument order isn't of primary importance here.

  • The predicate name should make the meaning of the respective arguments clear.

So far, I like path_from_to_edges best, but it has its pros and cons, too.

path_from_to_edges(Path,From,To,Edges_2) :-
    path(Edges_2,Path,From,To).

Let's pick it apart:

  • pro: path is a noun, it cannot be mis-read a verb. To me, a list of vertices is implied.

  • pro: from stands for a vertex, and so does to.

  • con: edges is somewhat vague, but using lambdas here is the most versatile choice.

  • con: According to Wikipedia, a path is a trail in which all vertices (except possibly the first and last) are distinct. So that would need to be clarified in the description.

Using lambdas for a lists of neighbor vertices Ess:

?- Ess  = [a-[b],b-[c,a]], 
      From = a,
      path_from_to_edges(Path,From,To,\X^Y^(member(X-X_neibs,Ess),member(Y,X_neibs))).
   Ess = [a-[b],b-[c,a]], From = a, To = a, Path = [a]
;  Ess = [a-[b],b-[c,a]], From = a, To = b, Path = [a,b]
;  Ess = [a-[b],b-[c,a]], From = a, To = c, Path = [a,b,c]
;  false.

Edit 2015-06-02

Another shot at better naming! This leans more on the side of maplist/2...

graph_path_from_to(P_2,Path,From,To) :-
   path(P_2,Path,From,To).

Here, graph, of course, is a noun, not a verb.

Regarding the meaning of "path": paths definitely should allow From=To and not exclude that by default (with pairwise term inequalities). It is easy to exclude this with an additional dif(From,To) goal, but not the other way round.

false
  • 10,264
  • 13
  • 101
  • 209
repeat
  • 18,496
  • 4
  • 54
  • 166
  • `Edges` suggests a list of edges. – false Jun 02 '15 at 13:21
  • 1
    Con: Goes against Richard O'Keefe's argument ordering which puts meta arguments very early. Also, chances are, that there is no variation on the meta argument, so one would never do `call(path_from_to_edges(Path,From,To), P_2)` like in `maplist(path_from_to_edges(Path,From,To),P_2s)` – false Jun 02 '15 at 13:25
  • 1
    And `Edges` means list of `Edges` - although we do not have some – false Jun 02 '15 at 13:32
4

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:

path( some_rule, [start|Q], start ) :- 
  path ( some_rule, [start|Q ] ).

* 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:

n(a, b).
n(a, c).
n(a, d).

and trace algorithm execution for the query:

[trace]  ?- path( n, P, X, d ).
   Call: (6) path(n, _G1025, _G1026, d) ? creep
   Call: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Exit: (7) path(n, [], d, d, [d]) ? creep
   Exit: (6) path(n, [d], d, d) ? creep
P = [d],
X = d ;
   Redo: (7) path(n, _G1107, _G1026, d, [_G1026]) ? creep
   Call: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, b) ? creep

   Call: (8) non_member(b, [a]) ? creep
   Call: (9) dif:dif(b, a) ? creep
   Exit: (9) dif:dif(b, a) ? creep
   Call: (9) non_member(b, []) ? creep
   Exit: (9) non_member(b, []) ? creep
   Exit: (8) non_member(b, [a]) ? creep
   Call: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Call: (9) n(b, _G1118) ? creep
   Fail: (9) n(b, _G1118) ? creep
   Fail: (8) path(n, _G1113, b, d, [b, a]) ? creep
   Redo: (9) non_member(b, []) ? creep
   Fail: (9) non_member(b, []) ? creep
   Fail: (8) non_member(b, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, c) ? creep

   Call: (8) non_member(c, [a]) ? creep
   Call: (9) dif:dif(c, a) ? creep
   Exit: (9) dif:dif(c, a) ? creep
   Call: (9) non_member(c, []) ? creep
   Exit: (9) non_member(c, []) ? creep
   Exit: (8) non_member(c, [a]) ? creep
   Call: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Call: (9) n(c, _G1118) ? creep
   Fail: (9) n(c, _G1118) ? creep
   Fail: (8) path(n, _G1113, c, d, [c, a]) ? creep
   Redo: (9) non_member(c, []) ? creep
   Fail: (9) non_member(c, []) ? creep
   Fail: (8) non_member(c, [a]) ? creep
   Redo: (8) n(_G1026, _G1112) ? creep

   Exit: (8) n(a, d) ? creep

   Call: (8) non_member(d, [a]) ? creep
   Call: (9) dif:dif(d, a) ? creep
   Exit: (9) dif:dif(d, a) ? creep
   Call: (9) non_member(d, []) ? creep
   Exit: (9) non_member(d, []) ? creep
   Exit: (8) non_member(d, [a]) ? creep
   Call: (8) path(n, _G1113, d, d, [d, a]) ? creep
   Exit: (8) path(n, [], d, d, [d, a]) ? creep
   Exit: (7) path(n, [d], a, d, [a]) ? creep
   Exit: (6) path(n, [a, d], a, d) ? creep
P = [a, d],
X = a .

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.

pasaba por aqui
  • 3,446
  • 16
  • 40
  • 2
    Not providing the extra two arguments makes many queries cumbersome. Like: What paths exist from `a` to `b`? This would read as: `Path = [a|_], path(connex, Path), last(Path, b)` contrast this to `path(connex, Path, a,b)` – false May 31 '15 at 11:46
  • The example you provide shows that: a) start node is not necessary; end node is necessary only until a more efficient algorithm is used. – pasaba por aqui May 31 '15 at 14:10
  • End case, and in general any intermediate or final condition, needs a better algorithm than the one provided in the original message. On going. – pasaba por aqui May 31 '15 at 14:49
  • 2
    Fine! Then please provide some! – false May 31 '15 at 14:53
  • I'm absolutly sure you known more search algorithm theory than me. But, I will try, if free time. – pasaba por aqui May 31 '15 at 15:14
  • 2
    ad addendum 2: That is an accurate observation. In fact the end node is a *steadfast* argument. However, for a complete search, nothing else can be expected! – false May 31 '15 at 15:18