;;;  Depth-first search of a directed acyclic graph (DAG)
;;;  
;;;  Author:  Philip Resnik, 16 September 1997
;;;  
;;;  
;;;  Graph is specified as a set of nodes and edges, e.g.
;;;  
;;;  (defvar *graph*
;;;    '((Nodes (a b c d e f g))
;;;      (Edges ((a c) (a b) (c d) (c e) (d f) (e f) (e g)))))
;;;  
;;;  To run
;;;  
;;;     (search start-node target)
;;;  
;;;  For example,
;;;  
;;;     (search 'A 'G)

(defun get-outward-edges (node)
  "Returns a list of all edges coming out of the given node"
  (let ((edges (second (assoc 'Edges *graph*))))
    (remove-if #'(lambda (pair) (not (eq (first pair) node))) edges)))

(defun search (start-node target)
  (do
   ;; THINGS TO DO BEFORE THE LOOP STARTS, INCLUDING DECLARING LOCAL VARIABLES
   ((possibilities (list start-node))
    (current-node)
    (visited))

   ;; UNDER WHAT CONDITIONS TO STOP THE LOOP, AND WHAT TO RETURN WHEN DONE
   ;; If the possibilities list is empty, we didn't find the target.
   ((null possibilities)
    'FAILURE)

   ;; WHAT TO DO REPEATEDLY WHILE EXECUTING THE LOOP
   (format t "~%~%Current possibilities: ~S, " possibilities)
   (setf current-node (pop possibilities))
   (push current-node visited)

   ;; If we've found the target, break out of the loop and accept.
   (format t " now exploring node ~A" current-node)
   (if (eq current-node target)
       (return 'SUCCESS))

   (dolist (pair (get-outward-edges current-node))
	   (if (not (member (second pair) visited))
	       (push (second pair) possibilities)))))