CODEWITHSUNDEEP
prolog
Yuumi
Yuumi

Reputation: 11

How to write all paths in a directed graph with no cycles? (Prolog)

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.

Upvotes: 1

Views: 225

Answers (1)

Yannai Alter
Yannai Alter

Reputation: 11

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.

Upvotes: 1

Related Questions