Re: Need advice for path research

[Matthieu Labbé]

Gurvan,

A simple way to prevent cycle is to keep track of visited nodes.
Here is a way to do it:

path(From, To, [From, To], _) :- rel(From, To).
path(From, To, [From | Tail], Visited) :-
        rel(From, Intermediate),
        \+ member(Intermediate,Visited),
        path(Intermediate, To, Tail, [Intermediate|Visited]).

If I understand properly what you want to do, this isn't good enough:
This only avoid infinite recursion and loop in the path from the
recursive clause.
Below is an example where I think it doesn't do what you want.

Using this graph:
rel(a,b).
rel(a,d).
rel(b,c1).
rel(b,c2).
rel(c1,d).
rel(c2,d).
rel(d,e).
rel(d,b).

And calling the code above to find path from a to b:
| ?- path(a,b,P,[]).
P = [a,b] ?
P = [a,b,c1,d,b]
P = [a,b,c2,d,b]
P = [a,d,b]
no

My understanding is that you only want [a,b] and [a,d,b], not
[a,b,c1,d,b] and [a,b,c2,d,b].
You get a similar bug with path(a,d,P,[]).

Here is a possible fix:

path(From, To, [From, To], _) :- rel(From, To).
path(From, To, [From | Tail], Visited) :-
        rel(From, Intermediate),
        Intermediate \= To,
        \+ member(Intermediate,Visited),
        path(Intermediate, To, Tail, [Intermediate|Visited]).

I hope this help,
-Matt.

--
Matthieu Labbé
http://mattlabbe.com/