Re: Need advice for path research

[Gregory Bourassa]

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" <address@hidden> 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
address@hidden
<a href='http://lists.gnu.org/mailman/listinfo/users-
prolog'>http://lists.gnu.org/mailman/listinfo/users-prolog</a>