Finding distance between nodes of a graph in prolog

Question

I have a graph in Prolog represented by the edges & weights:

connected(a,b,2).
connected(b,e,1).
connected(b,l,5).
connected(b,g,2).
connected(c,s,2).
connected(d,a,2).
connected(d,k,4).
connected(d,l,7).
connected(e,m,2).

I need to write a predicate which takes a list of nodes & distance.

?- dist([a,b,e],X).
X=3

I've tried to write it, but it is very clumsy & doesn't give the intended result.

The basic idea I have is: If it is a list of 2 elements then see if they are connected. If more then 2 elements in the list: see if the 1st element & 2nd element are connected, recursively see if the next elements are connected. I have defined 2 auxiliary predicates for head & tail.

dist([A, B], X) :-
    connected(A, B, X).
dist([A|B], Length) :-
    connected(A, hd(B,H,N), X),  % sees if A & next element in the list are connected
    dist(tl(B,H,N), Length1),    % recursive call with the list excluding element A
    Length is X + Length1.       

hd([H|T],H,Q).
tl([H|T],T,Q).

I am very new to Prolog land and I am still trying to comprehend the language semantics. Please suggest an efficient way to go about this problem.

The hd and tl predicates don't make sense to me. The parameter Q isn't used, so it doesn't do anything. And predicates don't return values, so you can't write something like connected(A, hd(B,H,N), X). Or rather, you can, but it doesn't mean what you think. — svick
I was trying to use tail to denote the rest of the list after the first element. In your answer you've represented the list as '[A, B | T]'. Instead of that I was trying to get B by using head. The Q in the hd function was to return the value of head. I know it is all so clumsy :( Hoping to learn faster,the logical programming way of doing things. — Bharat

svick svick · Accepted Answer · 2011-07-24T23:56:28

dist([_], 0).            % path of length 0 has distance 0
dist([A, B | T], L) :-
    connected(A, B, L1), % A and B are connected directly, the distance is L1
    dist([B|T], L2),     % the distance between B and the last element is L2
    L is L1 + L2.

Finding distance between nodes of a graph in prolog

1 Answers