How to find direct path between two nodes in a graph in Prolog?

user_17588822 0
Viewed 208

I am new to Prolog and I'm trying to write a predicate that takes two nodes and a graph as it's arguments and then checks whether there exists a direct path between these two nodes in the graph.

For example, there is a direct path from n(1) to n(4) in the graph below, that goes from n(1) to n(3) and from n(3) to n(4):

g[n(1), n(4), g([n(1), n(2), n(3), n(4), n(5), n(6), n(7), n(8)],
[e(n(1), n(2)), e(n(1), n(3)), e(n(3), n(4)), e(n(4), n(5)), e(n(5), n(6)), e(n(5), n(7)), e(n(7), n(8))]))

In the end

?− dirPath(n(1), n(4), g[n(1), n(4), g([n(1), n(2), n(3), n(4), n(5), n(6), n(7), n(8)],
[e(n(1), n(2)), e(n(1), n(3)), e(n(3), n(4)), e(n(4), n(5)), e(n(5), n(6)), e(n(5), n(7)), e(n(7), n(8))]))

should return true.

My tentative code looks like this:

edge(n(1),n(2)).
edge(n(1),n(3)).
edge(n(3),n(4)).
edge(n(4),n(5)).
edge(n(5),n(6)).
edge(n(5),n(7)).
edge(n(7),n(8)).

dirPath(A,B, g) :-   % - graph argument still missing.
  move(A,B,[])       % - two nodes are connected,
  .                  % - if one can move from one to the other,

move(A,B,V) :-       % -  and one can move from A to B
  edge(A,X) ,        % - if A is connected to X, and
  not(member(X,V)) , % - one hasn't yet reached X, and
  (                  % - either
    B = X            % - X is the desired destination
  ;                  %   OR
    move(X,B,[A|V])  % - one can get to that destination from X
  )                  
  .

My main problem is that I can't figure out how make my dirPath predicate accepts a graph, as it's argument.

prolog graph
1 Answers

First of all, this:

g[n(1), n(4), g([n(1), n(2), n(3), n(4), n(5), n(6), n(7), n(8)],
[e(n(1), n(2)), e(n(1), n(3)), e(n(3), n(4)), e(n(4), n(5)), e(n(5), n(6)), e(n(5), n(7)), e(n(7), n(8))]))

is not valid syntax. A term cannot begin g[.... This should probably be g([... instead.

Second, the representation is not entirely intuitive. What are the special roles of n(1) and n(4)? Why is there an inner g(...) term?

Nevertheless, it's clear which part is supposed to be the edges. Let's define a predicate to access just the edges:

graph_edges(Graph, Edges) :-
    Graph = g(_Something, _SomethingElse, g(_Nodes, Edges)).

Selection of one edge from the graph is then:

graph_edge(Graph, Edge) :-
    graph_edges(Graph, Edges),
    member(Edge, Edges).

You can then incorporate this into your predicate like this:

dirPath(A, B, Graph) :-
    move(A, B, Graph, []).

move(A, B, Graph, Vs) :-
    graph_edge(Graph, e(A, X)),
    ...

Note that I changed your variable V to Vs. Single-letter variable names are often not great in general (From and To would in my opinion be clearer than A and B). Single-letter variable names for lists are especially unusual; the common convention is to add s (as in the English plural, visited nodes) for lists. For graphs this is especially recommended, since a simple V could very well be interpreted as a single "vertex".

(Solution not tested.)

user_43917430
Related