From: Mattheos Papavasiliou Subject: Help with short path algorithm Date: 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 allready recorded in (A) 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... thanks in advance. please email any responce to ········@entasis.hellas.net

From: Donald H. Mitchell Subject: Re: Help with short path algorithm Date: 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) Bethel Park, PA 15102 http://home.earthlink.net/~smartproject