1

I'm testing out graph-searching for paths in prolog using information from https://www.irit.fr/~Jerome.Mengin/teaching/prolog/prolog-search_a4.pdf and ran into some issues with writing from recursive func.

My code can find all possible paths from node1 to node2 however the results(paths) are printed out in reverse order.

edge(a, c).
edge(a, d).
edge(c, e). 
edge(e, f).
edge(d, f).

paths(Curr,Stop) :- 
    Curr==Stop -> write(Curr);
    edge(Curr,Next),
    paths(Next,Stop),
    write(Curr).

For example paths(a,f) yields: feca true ; fda true.

However I want the results in the correct order acef and adf written without the use of lists.

false
  • 10,264
  • 13
  • 101
  • 209
Yuumi
  • 11
  • 1
  • `path(edge, Path, Start, Stop)` using [this definition](https://stackoverflow.com/q/30328433/772868). – false Sep 29 '19 at 10:51

1 Answers1

1

Just remember that you are finding the path through backtracking, so the last node you arrive to, will be the first one who printed out. This forces you to write a predicate that prints the start node at the end, which means you need to solve this problem "upside down". The idea is to use edge(Previous,Stop) instead of edge(Curr,Next).

edge(a, c).
edge(a, d).
edge(c, e).
edge(e, f).
edge(d, f).


paths(Start,Stop) :-
    Start==Stop -> write(Start);
    edge(Prev,Stop),
    paths(Start,Prev),
    write(Stop).

as you can see now, we are starting from the end and recursively trying to get to the start, when we are reaching the start the whole path is printed from start to end.

Yannai Alter
  • 11
  • 2