4 Replies - 7135 Views - Last Post: 26 July 2011 - 02:45 PM Rate Topic: -----

#1 bharatkr   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 19-December 10

Finding distance between nodes of a graph in prolog

Posted 24 July 2011 - 04:19 PM

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 is 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.

Thank you.

Is This A Good Question/Topic? 0
  • +

Replies To: Finding distance between nodes of a graph in prolog

#2 sepp2k   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2756
  • View blog
  • Posts: 4,416
  • Joined: 21-June 11

Re: Finding distance between nodes of a graph in prolog

Posted 25 July 2011 - 05:03 AM

First of all I don't see the point of the third argument of hd and tl. You should remove it.

Also using tl isn't necessary at all - B already is the tail of the list.

Now the most important problem in your code is how you use hd and tl: They aren't functions, they don't have return values - so you can't use them as if they had a value, i.e. you can't do foo(hd(...)). The way you use hd (after removing the third argument) is, you write hd(MyList, H), ... and after that H has the value of the head of the list.

So your code becomes:

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



Now there's still a couple of improvements I would do to this code:

1. You don't need to define your own hd predicate, you could just pattern match on the first two elements of the list, i.e. dist([A,B | Tail], Length) :- ... and then use [B | Tail] as the list in the recursive call.

2. I would chose dist([_], 0). as the base case instead of dist([A, B], X) :- connected(A, B, X).. This way you remove the code duplication of calling connected(A, B, X) twice and it also works correctly for lists with a single element.

This post has been edited by sepp2k: 25 July 2011 - 05:04 AM

Was This Post Helpful? 2
  • +
  • -

#3 bharatkr   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 19-December 10

Re: Finding distance between nodes of a graph in prolog

Posted 25 July 2011 - 09:47 AM

Thanks for the reply sepp2k!
As you said I don't need to explicitly define head. The pattern matching the first 2 elements & having the base case you have mentioned does the job.
I need to read more of prolog code to get into the grove of thinking in prolog.
Was This Post Helpful? 0
  • +
  • -

#4 bharatkr   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 19-December 10

Re: Finding distance between nodes of a graph in prolog

Posted 25 July 2011 - 01:21 PM

sepp2k,with the suggestions you mentioned I have this to find the distance .
dist([_], 0).            
dist([A, B | T], L) :-
    connected(A, B, L1), 
    dist([B|T], L2),     
    L is L1 + L2.


Applying the same logic to feed it with a list of nodes & to get a list of distances, I've done the following.

distlist([[_],[_]], [0,0]). 
distlist([[A,B|T1],[X,Y|T2]],L):- 
	connected(A,B,N1),  % trying to separately get the distance of each sub list
	connected(X,Y,N2),
	distlist([[B|T1],[Y|T2]],L1),
	L is [N1,N2]. % here I want it to return a list of the total distance


The way I've done works only for the case where only 2 elements are there in each list.
What I am trying to do is this:

?- distlist[[a,b,e],[b,d,l],X)
X=[3,12] 

I am going wrong in the recursive call to distlist and the calculation of L.

This post has been edited by bharatkr: 25 July 2011 - 01:25 PM

Was This Post Helpful? 0
  • +
  • -

#5 bharatkr   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 19-December 10

Re: Finding distance between nodes of a graph in prolog

Posted 26 July 2011 - 02:45 PM

I figured out how to do that. I just had to call dist predicate to do the task instead of trying to repeat the same stuff.

distlist([[_],[_]], [0,0]).
distlist([[A,B|T1],[X,Y|T2]],L):- 
         dist ([A,B|T1],L1),
         dist([X,Y|T2],L2),
         L = .(L1,.(L2,[])).



Thanks!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1