Gurvan, So, your predicates are actually returning just a list. We are calling that list a "path". Am I correct?
Then, a common way of preventing cycles is a "visited list". Your predicates become: path(From, To, _VisitedList, [From, To]) :- rel(From, To). path(From, To, VisitedAlready, [From | Tail]) :- rel(From, Intermediate), not( member(Intermediate, VisitedAlready) ), path(Intermediate, To, [Intermediate | VisitedAlready], Tail). The cost is that, for very long paths and especially for very highly-branching graphs, you will traverse the VisitedList many times when the recursive invocation of path/4 is only going to fail (which cannot be known ahead of time, when we invoke member/2). Note that you will have to call path/4 with an empty list for the VisitedList: ?- path( a, c, [], Path). Regards. Gregory Bourassa On Jun 6 , "Gurvan Le Guernic" <[EMAIL PROTECTED]> wrote: Hi, I have a graph described using predicates similar to: rel(node1,node2). For example, the graph a-b-c is described as follow: rel(a,b). rel(b,c). I want to code a predicate given all path without cycles from a given node to another one. A simple implementation (not taking care of cycles) would be: path(From, To, [From, To]) :- rel(From, To). path(From, To, [From | Tail]) :- rel(From, Intermediate), path(Intermediate, To, Tail). How would you prevent an element to appear twice in the path? I tried to play with \= and \== but I don't really know how to use them before having the final path. If I wait to check that elements do not appear twice in possible paths, gprolog goes out of memory. Thanks for your help, Gurvan Le Guernic _______________________________________________ Users-prolog mailing list [email protected] <a href='http://lists.gnu.org/mailman/listinfo/users- prolog'>http://lists.gnu.org/mailman/listinfo/users-prolog</a> _______________________________________________ Users-prolog mailing list [email protected] http://lists.gnu.org/mailman/listinfo/users-prolog
