anchor.diff: -; Dijkstra's algorithm for finding the shortest path between nodes in a weighted graph
  -
  +;;; dijkstra's algorithm 
  +;;; find the shortest path between nodes in a weighted graph
   (defun dijkstra (graph start)
     (init-path-costs graph)
     (update-path-cost start 0)
     (init-predecessors graph)
     (init-visited)
     (init-candidates start)
  +  ;; current is a name
     (loop while candidates do
           (let ((current (min-candidate)))
             (add-visited current)
  -          (loop for neighbour in (set-difference (neighbours current) visited :test #'equal) do
  -                (cond (< (+ (path-cost (name current)) 
  -                            (cost-to-neighbour neighbour))
  -                         (path-cost neighbour)) 
  -                      ((update-path-cost (name neighbour)
  -                                         (+ (path-cost (name current)) 
  -                                            (cost-to-neighbour neighbour)))
  -                       (update-predecessor (name neighbour)
  -                                           (name current)))
  -                      ((not (member (name neighbour) visited))
  -                       (add-visited (name neighbour)))))
  -          finally predecessors)))
  +          ; fix visited is only names, neighbours is node type
  +          ; rewrite cost-to
  +          (loop for neighbour in (set-difference (list-nodes (neighbours current)) 
  +                                                 visited 
  +                                                 :test #'equal)
  +                do 
  +                (cond 
  +                  ((< (+ (path-cost current)
  +                         (cost-to-neighbour neighbour))
  +                      (path-cost neighbour))
  +                   (update-path-cost neighbour
  +                                     (+ (path-cost current) 
  +                                        (cost-to-neighbour neighbour)))
  +                   (update-predecessor neighbour current))
  +                  ((not (member neighbour visited))
  +                   (add-visited neighbour)))
  +                finally predecessors))))
   
  -; keep track of the smallest cost to get to each node found by dijkstra
  -; note that all paths start at the start node called in dijkstra
  +(defun only-names (list-nodes))
  +
  +;;; keep track of the smallest cost to get to each node found by dijkstra
  +;;; note that all paths start at the start node called in dijkstra
   (defun init-path-costs (graph)
  -  (let ((impossible (+ 1 (apply '+ (remove-if-not #'integerp (flatten graph))))))
  -    (setq path-path-costs (mapcar #'(lambda (node) (list node impossible)) (list-nodes graph)))))
  +  (let ((impossible (+ 1 (apply '+ (remove-if-not #'integerp 
  +                                                  (flatten graph))))))
  +    (setq path-costs 
  +          (mapcar #'(lambda (node) (list node impossible)) 
  +                  (list-nodes graph)))))
   
   (defun flatten (llist)
     (cond ((null llist) nil)
  
positive.code:         (t (append (flatten (car llist)) (flatten (cdr llist))))))
  
  (defun update-path-cost (end path-cost)
    (setq path-costs (append (remove-if #'(lambda (node) (equal (car node) end)) path-costs) (list (list end path-cost)))))
  
  ; takes the name of a node
  (defun path-cost (target)
    (cadar (remove-if-not #'(lambda (node) (equal (car node) target)) path-costs)))
  
  ; keep track of the predecessor of each node on the shortest path to the start node
  (defun init-predecessors (graph)
    (setq predecessors (mapcar #'(lambda (node) (list node nil)) (list-nodes graph))))
  
  ; end and predecessor are names of a nodes
  (defun update-predecessor (end predecessor)
    (setq predecessors (append (remove-if #'(lambda (node) (equal (car node) end)) predecessors) (list (list end predecessor)))))
  
  (defun init-visited ()
    (setq visited nil))
  
negative.code:   (setq candidates (list start)))
  
  (defun add-candidate (node)
    (setq candidates (append candidates (list node)))  
    (setq candidates (sort candidates 
                           (lambda (left right) (< (path-cost left) 
                                                   (path-cost right))))))
  
  (defun min-candidate ()
    (pop candidates))
  
  ;;; nodes are stored as (name cost)
  (defun cost-to-neighbour (node)
    (cadr node))
  
  