GProlog reachable elements in a graph

Question

I have an easy problem that I'm having trouble with although I think the answer is quite easy. Here it goes:

Assume a weighted directed graph is described by means of a predicate edge/3, such that edge(X,Y,C) is true is there is an edge from vertex X to vertex Y of cost C. For instance, to the right is a graph and its description using edge/3:

edge(a, c,1).
edge(a,d,3).
edge(b,d,2).
edge(c,e,5).
edge(e, c,2).
edge(e,f,2).
edge(d,f,10).

I have to . Define a predicate reachable/2 that computes the list of nodes that can be reached from a given node. For instance, to the query reachable(a, L) Prolog should answer L=[c,e,d,f] (in any order). (Remember findall.)

Here is what I wrote for the moment

path(X,Y):-edge(X,Y,_).
path(X,Y):-edge(X,Z,_),path(Z,Y).

reachable(X,L):-findall(Y,path(X,Y),L).

I can't see what is wrong but it's going in circles and stopping because of a memory issue. Any ideas how to solve that?

Please that would creatly help!

user_67579 · Answer

If your graph has an edge, like c → e → c → e → …, then there is nothing that stops path from each time walking from e to c and back. Unless we add something to prevent this.

We can make use of a list that contains all the elements already visited, and prevent from visiting these another time:

path(X, Y) :-
    path(X, Y, [X]).

path(X, Y, V) :-
    edge(X, Y, _),
    \+ member(Y, V).
path(X, Y, V) :-
    edge(X,Z,_),
    \+ member(Z, V),
    path(Z, Y, [Z|V]).

we thus start with a list that contains only X. Each time when we take an edge, we check if the target (Y or Z) is not a member of V, and in case of recursion, we add Z to the list.

For the given graph:

this thus produces:

?- path(X, Y).
X = a,
Y = c ;
X = a,
Y = d ;
X = b,
Y = d ;
X = c,
Y = e ;
X = e,
Y = c ;
X = e,
Y = f ;
X = d,
Y = f ;
X = a,
Y = e ;
X = a,
Y = f ;
X = a,
Y = f ;
X = b,
Y = f ;
X = c,
Y = f ;
false.

GProlog reachable elements in a graph

1 Answers