;;; DFS
;;; Takes graphs in adjacency list form
;;; maintain as state:
;;; the graph,
;;; the traversal so far (in reverse order, for easy augmentation)
;;; the stack of lists of neighbors to see
;;; the current list of neighbors-to-see
;;;
;;; Using the abbreviation: neighbors-to-see = nts

(load "p84.lisp")

(defun dfs (graph node)
  (dfs-aux graph (list node) nil (neighbors node graph))
  )

(defun dfs-aux (graph traversal stack nts)
  (cond
   ;; case 1: next neighbor to see has already been visited
   ((and nts (member (car nts) traversal))
    ;; just disregard this neighbor
    (dfs-aux graph traversal stack (cdr nts)))
   ;; case 2: next neighbor to see not yet visited
   (nts
    ;; pushd remaining list of neighbors to see, start a new one
    (dfs-aux graph 
	     (cons (car nts) traversal)
	     (cons (cdr nts) stack)
	     (neighbors (car nts) graph)))
   ;; case 3: no more neighbors to see, but stack not empty
   (stack
    ;; pop a list of neighbors to see from stack
    (dfs-aux graph traversal (cdr stack) (car stack)))
   ;; case 4: no more neighbors to see, empty stack
   (t
    ;; return traversal; remember it is built reversed
    (reverse traversal))
   )
  )