```From: Mattheos Papavasiliou
Subject: Help with short path algorithm
Date: Sat, 15 Mar 1997 00:00:00 +0000
Message-ID: <332B2C29.7861@entasis.hellas.net>```
```I have a puzzling problem, that it seems that I cannot handle:
given a list
(setq mylist '((1 2) (2 1 3 4) (3 2 4) (4 2 3 5) (5 4))
given that the list reflects relations of the
items  1 : (2)      (with item 2)
2 : (1 3 4)  (with items 1 3 & 4)
3 : (2 4)	...		   (A)
4 : (2 3 5)      ...
and    5 : (4)          ...
How could I expand this list into a one that expands all the respective
relations that each item will give?
If I do this expansion by hand it should be:
as follows

1st expansion:
1 : ( 1 3 4)             when 1 could be ommited as it is itself  to
become --> ( 3 4)         }
2 : ( (2) (2 4) (2 3 5)) when 2 could be ommited
again                      --> ((4) (3 5))    }
3 : ( (1 3 4) (2 3 5))   when 3 could be
ommited                            --> ((1 4) (2 5))  } (B)
4 : ( (1 3 4) (2 4) (4)  when 4
goes                                        --> ((1 3) (2))    }
5 : ( (2 3 5) )          when 5
goes                                        --> ((2 3))        }

2nd expansion:
1 : ((2 4) (2 3 5))    when 2 could be ommited because is a relation
2 : ((2 3 5) ((2 4) (4))  when 2 couldbe ommited as itself, 3 as has
been recorded in (A), 4 and 5 recorded in (B)
hence ((4) (3 5)) would be the ultimate expansion
3 : (((2) (2 3 5)) ((1 3 4) (4)) and for the same reasons expansion (B)
is the ultimate
4 : and for similar reasons here the previous is the ultimate expansion
5 : ((1 3 4) (2 4))    here this is the ultimate because the relation
with 1 has not been previously recorded.

Trying to solve a path proximity algorithm any algorith that would
calculate the shortest path recording how many steps
one takes to go from A to B would be apreciated...

please email any responce to ········@entasis.hellas.net```
```From: Donald H. Mitchell
Subject: Re: Help with short path algorithm
Date: Sat, 15 Mar 1997 00:00:00 +0000
Message-ID: <332B570D.6A34@smartproject.com>```
```Mattheos Papavasiliou wrote:
>
> I have a puzzling problem, ... given a list ...

Here's one solution. Loop and standard tail recursion would also be
obvious implementations.

(defun transitive-neighbors (neighbors-alist)
;;neighbors-alist is an alist indicating for each node its
;;nearest neighbors.  This function must return an alist of the
;;neighbors (non-circular) just one removed grouped by their
;;transitive but unmentioned jumping point.  What's not clear in the
;;spec is whether there should be any further cleanup other than
;;strict circularity.
(mapcar
#'(lambda (entry)
(let ((this-node (car entry)))
(cons this-node
(delete nil
(mapcar
#'(lambda (neighbor)
(remove this-node
(cdr (assoc
neighbor
neighbors-alist))))
(cdr entry))))))
neighbors-alist))

(transitive-neighbors '((1 2) (2 1 3 4) (3 2 4) (4 2 3 5) (5 4)))
=> ((1 (3 4)) (2 (4) (3 5)) (3 (1 4) (2 5)) (4 (1 3) (2)) (5 (2 3)))

--
Donald H. Mitchell, PhD, PMP    ··········@smartproject.com
Proactive Solutions, Inc.       412.835.2410
5858 Horseshoe Dr.              412.835.2411 (fax)