Prolog printing all paths in one go

Question

To preface, I'm a beginner at prolog.

I'm trying to print all possible paths between two nodes in an acyclic graph in one go, and my code can find all the possible paths, just that the format of the result is wrong for my specific task.

What I got so far is:

?- always(a,e).
bce
true ;
bcde
true ;
ce
true ;
cde
true ;

But I'd like to get in the the format of:

?- always(a,e).
bce
bcde
ce
cde
true ;

Without the need of pressing ; And i need this to be done in the code rather then add something in the query. My current code is

edge(a,b).
edge(a,c).
edge(b,c).
edge(c,d).
edge(c,e).
edge(d,e).
edge(f,g).
edge(g,h).

always(X,Y) :- always(X,Y,[]).
always(X,Y,Path) :- edge(X,Y), append(Path, [Y], Path2), always_writelist(Path2).
always(X,Y,Path) :- edge(X,Next), append(Path, [Next], Path2), always(Next,Y,Path2).
always_writelist(Path) :- length(Path,0).
always_writelist([Node|Path]) :- write(Node), always_writelist(Path).

Note that I can't use any built-in predicates except is, setof, write, nl, integer and !, in order to follow my instructions.

Any tips on what I can do?

I've tried printing out the whole list but then i just get

[b,c,e][c,e][e]

Use a fail driven loop to print each solution. Finish with another clause that just succeeds — gusbro, Nov 09 '22 at 20:18
Can use `setof`, to perform the same essential task (creating a list of solutions) as done by the likes of `bagof` and `findall`. Or @gusbro's method :-) — brebs, Nov 09 '22 at 20:20
I don't see the graph definition (your edge/2 facts). Add them so that we can reproduce your program. — TA_intern, Nov 10 '22 at 11:37
@brebs yeah i'm thinking setof/3 is probably the way to go! :) — GruddenOprejuz, Nov 10 '22 at 12:27

score 0 · Answer 1 · answered Nov 11 '22 at 09:24

I am only answering because you are using write and append for absolutely no reason. Don't do it. If you know the path is acyclic, this is enough:

path(To, To, []).
path(From, To, [X|Path]) :-
    edge(From, X),
    path(X, To, Path).

That's it. Now you need setof to get all answers:

?- setof(P, path(a, e, P), Paths).
Paths = [[b, c, d, e], [b, c, e], [c, d, e], [c, e]].

If your path might have cycles in it this will loop (do you see why?). Here is the canonical "modern" solution to this: Definition of a path/trail/walk

This is "library code" so maybe the purpose is slightly obfuscated. The message is, you need to check the visited nodes to avoid loops.

Prolog printing all paths in one go

1 Answers1