dolist in a circular list

[filete]

I'm programming a lisp app that searches the shortest path between two train stations in Berlin.

Code: Select all

(defstruct station name)
(defstruct line name stations)
(defstruct karte linien)
(defstruct point station line)
(defstruct route points)

Stations

Code: Select all

(setq Oranienburg (make-station  :name "Oranienburg"))
(setq Lehnitz (make-station  :name "Lehnitz"))
(setq Borgsdorf (make-station  :name "Borgsdorf"))
(setq Birkenwerder (make-station  :name "Birkenwerder"))
(setq HohenNeuendorf (make-station  :name "Hohen Neuendorf"))
(setq Frohnau (make-station  :name "Frohnau"))
(setq Hermsdorf (make-station  :name "Hermsdorf"))
[...]

Lines

Code: Select all

(setq a (list Gesundbrunnen Wedding BeusselStr
	Westhafen Jungfernheide Westend
	MesseNordICC Westkreuz Halensee
	Hohenzollemdamm HeidelbergerPlatz
	Bundesplatz Schoneberg Sudkreuz
	Tempelhof Hermannstr Neukolln Sonnenallee
	TreptowerPark Ostkreuz FrankfurterAllee
	StorkowerStr LandsbergerAllee GreifswalderStr
	PrenzlauerAllee ShonhauserAllee)
)

(setq b (nconc a a))

(setf S41 (make-line   :name "S41" :stations b)) 
(setq S42 (make-line   :name "S42" :stations b))

Here comes my first question:

As you see, both S41 and S42 are circular lines, so I'm creating them as shown above. If i switch to:

Code: Select all

(setf S41 (make-line   :name "S41" :stations (nconc a a)))

I just doesn't work. Why?

And my second question:
In order to find reachable stations, I have to loop throught every line in the map, and then look for the current station within them using member as follows:

I'm currently just printing the station and line when found

Code: Select all

(defun nextpoint (apoint)
  (dolist (aline (karte-linien mapa))
    ;; Si la estación de la situación actual está en la línea
    (if (member (point-station apoint) (line-stations aline))
      ;; Su predecesor y sucesor están entre los alcanzables
      (printpoint apoint)
    )
  )
)

This function is never returning as long as the map has any circular list on it. ¿How to use dolist in this case?

[ramarren]

Where are you learning Common Lisp from? Using circular lists is rather unusual in practice. Practical Common Lisp is a good introduction to idiomatic Lisp programming.

You are using undeclared variables, which has undefined behaviour. Create global variables using DEFPARAMETER or DEFVAR. Conventionally names of global variables are surrounded by stars.

I just doesn't work. Why?

NCONC is destructive and side-effecting. If you execute it twice, it will hang or error out, since it would not be able to find the end of circular list. Mutating lists in general is not a very good idea, since the do not form a full abstract data type in Common Lisp.

This function is never returning as long as the map has any circular list on it. ¿How to use dolist in this case?

Do not use circular lists. I do not see exactly what you are trying to achieve here, but I doubt that circular lists are a good idea.

[filete]

I'm trying to represent this map. Where there are a couple of circular lines. I want to find both preceding and next station from a given one.

http://wgdw.minuskel.de/wp-content/uplo ... lin_01.png

So thankful for the links. I'm supposed to be teached at university, but the just gave me an assignment and told me get your life...

[ramarren]

The map is not the territory. Just because the line is circular doesn't have to mean that your data structure has to be as well. For fairly static data like this I would suggest using arrays. Note that MOD is specified to work on negative numbers, which means that you can use it to compute absolute indexes from relative ones:

Code: Select all

(let ((line (vector 'a 'b 'c)))
           (print (aref line (mod (1- (position 'a line)) (length line))))
           (print (aref line (mod (1+ (position 'a line)) (length line)))))

[filete]

I've thought about this approach but, since not every line is circular, and therefore head and tale are not subsequent on those that are lineal. That imples that I would have to mark those who are, and then avoid the usage of negative indexes on those that aren't.

Rather than doing this, I'm wondering wheter it would be a good idea just to dupplicate stations on circular lines like this:

station1 station2 station3 station1 station2 station3

So I get the link from station3 to station1 represented, but this doesn't seem to be a good nor clean way to do it... Any suggestion?

[ramarren]

That imples that I would have to mark those who are, and then avoid the usage of negative indexes on those that aren't.

This is probably the best idea. As a separate accessor function this is fairly trivial. It is usually better to think in terms of verbs and protocols than objects.

[nuntius]

FWIW, there are times when a circular list is awesome. Certain ring buffers come to mind. That said, circular lists in CL are locally the same as terminating lists; so the default tools either loop infinitely on them (as you saw) or require special flags (e.g. *PRINT-CIRCLE*). If you know a list is circular, you can save the first CONS as the "head" and then iterate until you reach a CONS which is EQ to it. Or you may iterate based on the list's length if it is known.

As for representing links, a common technique uses a "sparse array". The data structure is an array of true/false values. Rows and columns are both indexed by the station. An entry is true if there is a link between the row/column stations; otherwise it is false. So (aref links station1 station2) -> t means there is a link from station1 to station2; the other direction is stored in (aref links station2 station1). If all links are bidirectional, you can save time and storage by only using the upper or lower triangle of the array (e.g. entries where station1<station2).

Another common technique is as you describe; use a list of the links.

[gugamilare]

To work with circular lists, either circular starting from the first term

Code: Select all

'#1=(1 2 3 . #1#)

or from a middle term

Code: Select all

'(1 . #1=(2 3 . #1#))

one common method is to use two pointers, one fast and one slow. It is guaranteed to stop whatever the form of the list, but it might go throw some elements more than once.

One example of use of this method is this function, from swank (lisp part of slime):

Code: Select all

(defun safe-length (list)
  "Similar to `list-length', but avoid errors on improper lists.
Return two values: the length of the list and the last cdr.
Return NIL if LIST is circular."
  (do ((n 0 (+ n 2))                    ;Counter.
       (fast list (cddr fast))          ;Fast pointer: leaps by 2.
       (slow list (cdr slow)))          ;Slow pointer: leaps by 1.
      (nil)
    (cond ((null fast) (return (values n nil)))
          ((not (consp fast)) (return (values n fast)))
          ((null (cdr fast)) (return (values (1+ n) (cdr fast))))
          ((and (eq fast slow) (> n 0)) (return nil))
          ((not (consp (cdr fast))) (return (values (1+ n) (cdr fast)))))))

[Warren Wilkinson]

Thats a tricky problem. Lets see if I have this right:

You have several lines --- and some are circular.
A line is a series of station names.
You are going to find routes through the city by finding the stations that intersect both lines.

You could use circular lists, but you can't use dolist with them. You would have to write a circle-aware do construct. Record where you started, and use that knowledge to determine when you have come full circle.

This type of problem is traditionally solved by search. Rather than store the lines, store stations and connections. For example

Store Heiligensee connects to hennigsdorf and Schulzendorf

I've given some example code... the problem is recursive. To find the best connection of A to Z, find the best of the connections of (A's neigbor 1) to Z, and (A's neighor 2) to Z. Each recursion does a similar computation, until you reach the point where your neighbor is the target destination. This brute force approach works if you maintain a seen list (otherwise you're search will recurse to the left neighbor, which recurses back to the right neighbor --- and you're stack gets blown).

Code: Select all

(defvar *stations* nil)
(defun station (name &rest connections)
  (let ((station (assoc name *stations*)))
    (if station 
	(rplacd station (reduce #'adjoin connections :from-end t :initial-value (cdr station)))
	(push (cons name connections) *stations*))))

(defun rot-forward  (things) (append (cdr things) (list (car things))))
(defun rot-backward (things) (cons (car (last things)) (butlast things)))
  
(defun circle (&rest names) (mapcar #'station names (rot-forward names) (rot-backward names)))
(defun line (&rest names)
  (station (first names) (second names))
  (station (car (last names)) (car (last names 2)))
  (mapcar #'station (cdr names) names (cddr names)))

(circle 'westend 'messe-nord 'westkruz 'halensee 'hohenzollendamm 'heidelberger-platz 'bundesplatz 'schonenberg 
	'sudkreuz 'tempelhof 'hermannstabe 'neukollin 'sonnenalee 'treptower-park 'ostkreuz
	'frankfurter-allee 'storkower-stabe 'landsberger-allee 'greifswalder-stabe 'prenzlauer-allee 
	'schonhauser-allee 'gesundbrunnen 'wedding 'westhafen 'beusselstabe 'jungfemheider)
(line 'spandu 'stresow 'pichelsberg 'olympiastadion 'heerstrabe 'messe-sud 'westkruz)

(defun papply (fn &rest values) #'(lambda (&rest more-args) (apply fn (append values more-args))))
(defun path-inner (seen-list dest start)
  (let ((links (cdr (assoc start *stations*))))
    (if (member dest links)
	(list start dest)
	(cons start (car (sort (mapcar (papply #'path-inner (cons start seen-list) dest)
				       (set-difference links seen-list)) #'< :key #'length))))))

(defun path (start dest)
  (path-inner nil dest start))

(path 'westhafen 'spandu)
;; Produces (WESTHAFEN BEUSSELSTABE JUNGFEMHEIDER WESTEND MESSE-NORD WESTKRUZ MESSE-SUD
;;                HEERSTRABE OLYMPIASTADION PICHELSBERG STRESOW SPANDU)