2021-12-05

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

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.



from Recent Questions - Stack Overflow https://ift.tt/3Ie36ed
https://ift.tt/eA8V8J

No comments:

Post a Comment