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/
_______________________________________________
Users-prolog mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/users-prolog
