Prolog: If Two Nodes Can Be Traversed To In A Graph

Question

Here's the Question I was given:

Define a Prolog predicate path(X,Y,G), where path(-,-,+), which is true when there is a path from node X to node Y in a directed graph G, where the graph is represented by a list of edges, each represented by a two-element list of the source and destination nodes.

Here's the sample output:

 ?- path(b,Y,[[a,b],[b,c],[b,d],[d,e]]).
 Y = c ;
 Y = d ;
 Y = e ;
 no
 ?- path(X,b,[[a,b],[b,c],[b,d],[d,e]]).
 X = a ;
 no
 ?- path(c,e,[[a,b],[b,c],[b,d],[d,e]]).
 yes

This is different to other examples I've seen online where the node traversals would be facts such as:

canTraverse(a,b).

canTraverse(b,c).

etc.

So I'm pretty stumped with it.

This is what I've gotten out so far:

path(X, Y, G) :-
    (
        G = [CurrentPair | EverythingElse],
        CurrentPair = [X1 , Y1| _],
        =(X, X1),
        =(Y, Y1)
    ) 
    ;
    path(X, Y, EverythingElse).

Which seemed to work if the two nodes X and Y were in a pair/list together. But I'm not sure how to get it to traverse across nodes.

You should have a couple of cases. One is the base case where you have, trivially, path(X, Y, [X,Y]) :- canTraverse(X, Y). (and perhaps path(X, Y, [X,Y]) :- canTraverse(Y, X). if it's not directional). Your other case should be the recursive case, which would look like path(X, Y, [X|G]) :- canTraverse(X, Z), path(Z, G). (and the symmetrical case, again, if it's not directional). — lurker
I see no particular syntactic benefit to =(X, X1) over X=X1, and after you make that change you wind up with no particular reason to break out all these variables at all: (G=[[X,Y]|EverythingElse]); path(X, Y, EverythingElse), which reveals that EverythingElse is unbound in your or-clause, which means you have unbounded recursion there. — Daniel Lyons
general breadth first search is always going to work for a graph traversal. find all possible "moves" from your current "position", stick them in the end of the TODO queue, pop one off it and continue. — Will Ness

rain1 rain1 · Accepted Answer · 2019-01-14T18:11:28

The graph is directed and doesn't have cycles.

The base case could be path(X, Y, G) :- member([X,Y],G). and the recursive case can say for there to be a path from X to Y, take a step from X to some middle note then find a path from middle to Y.

Prolog: If Two Nodes Can Be Traversed To In A Graph

1 Answers