CODEWITHSUNDEEP
prolog
daniel7558
daniel7558

Reputation: 397

Prolog: Order of clauses for finding path in graph

I have a cyclic graph with entry and exit nodes for which I want to find out all paths leading from any entry to any exit node.

entry(a).
exit(e).
exit(f).

next(a, b).
next(b, c).
next(b, d).
next(c, e).
next(d, f).

/* Cycle */
next(c, d).
next(d, b). 

/* path(entrynode, exitnode, pathtrace) */
path(X, Y, P)       :- entry(X), path2(X, Y, P).
path2(X, Y, [Y])    :- next(X, Y), exit(Y).
path2(X, Y, [P|PS]) :- next(X, P), path2(P, Y, PS).

My path2 predicate works great on a non cyclic graph. Now I want to extend it to cyclic ones. All I would have to do is check if a new possible node is already in my list of visited nodes. For this I would add not(member(X, PS)) to my last rule.

If I add it before the recursion, it always returns false. If I add it after the recursion Prolog tries to find the paths first and runs out of stack. It returns the correct answers but it tries to find more and gets stuck.

Therefore: Where should I add the check or what did I do wrong/what can I do better?

Upvotes: 1

Views: 273

Answers (1)

Paulo Moura
Paulo Moura

Reputation: 18663

You need an additional argument for your path2/3 predicate as your third argument is the path being constructed, not a list of visited nodes. I.e. you cannot simply add the \+ member(X,Ps) goal to the last rule of the predicate as Ps is bound by the recursive call. Try instead:

path(X, Y, P) :-
    entry(X),
    path2(X, Y, [], P).

path2(X, Y, _Visited, [Y]) :-
    next(X, Y),
    exit(Y).
path2(X, Y, Visited, [P|PS]) :-
    next(X, P),
    \+ member(P, Visited),
    path2(P, Y, [P| Visited], PS).

Sample calls:

| ?- path(X, Y, P).                        

P = [b,c,e]
X = a
Y = e ? ;

P = [b,c,d,f]
X = a
Y = f ? ;

P = [b,d,f]
X = a
Y = f ? ;

no

Upvotes: 2

Related Questions