LISP - breadth first search

[snivek]

have an implementation of BFS I got elsewhere and modified slightly, but I am having problems with its input.
It takes a graph, and will take it as '((a b c) (b c) (c d)) But my input I am giving it is a weighted graph... I know it's not useful for the BFS, but I use the weights farther down the line later. This input looks like
'(
(a (b 3) (c 1))
(b (a 3) (d 1))
(c (a 1) (d2) (e 2))
)
And so on.

My Code:

(defun shortest-path (start end net)
 (BFS end (list (list start)) net))

(defun BFS (end queue net)
  (if (null queue)
      nil
      (expand-queue end (car queue) (cdr queue) net)))
 
(defun expand-queue (end path queue net)
  (let ((node (car path)))
    (if (eql node end)
        (reverse path)
        (BFS end (append queue (new-paths path node net)) net)
    )
  ))

(defun new-paths (path node net)
  (mapcar #'(lambda (n)
              (cons n path))
          (cdr (assoc node net))))

I'm just not sure where I need to most likely modify it to accept the new style list, or make a help function to format it correctly?

[pyTony]

For me looks simple case of applying car to cdr of each sublist before calling the BFS. As it is one debuged group of code I would leave it alone as I understnd that the result would suffice to you without the weights.

[snivek]

Yea I agree. Just not sure how to implement. I know I'll have to take the car of each individual list (a (b 1) (c 3)), to get the 'a', then take the car of the sublists and append it. I'm just not sure of the most efficient way to do it.

[pyTony]

I am little rusty (about 20 years) in Lisp but in basic functions MAPCAR could be helpfull:

(MAPCAR 'CDR '((A B) (C D)))                 

((B) (D))

[pyTony]

Got it? This my post could interest you: : Norvig: (An ((Even Better) Lisp) Interpreter (in Python)) Linked to second message where I give my version of the Norvigs first and second lisp interpreters.