# Finding distance between nodes of a graph in prolog

Page 1 of 1

## 4 Replies - 7135 Views - Last Post: 26 July 2011 - 02:45 PMRate Topic:     //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=240851&amp;s=486803f0d804ebab58c3a9d021896f57&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 bharatkr Reputation: 0
• 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 Reputation: 2756
• 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.

```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

### #3 bharatkr Reputation: 0
• Posts: 4
• Joined: 19-December 10

## Re: Finding distance between nodes of a graph in prolog

Posted 25 July 2011 - 09:47 AM

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.

### #4 bharatkr Reputation: 0
• 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

### #5 bharatkr Reputation: 0
• 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!

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }