As a free-time activity in order to learn some Lisp I had to implement depth first directed graph search. Due to large graph size (800K nodes, 5M arcs) recursion-based approach I could devise didn't work.
Below is my stack-based implementation that I would like to improve in terms of readability if nothing else. Any comments on style, use of Lisp idioms, code smell are welcome.
(defun depth-first-search (adjacency-array visit-function &optional (init-function nil init-function-supplied-p)) (let* ((num-nodes (array-dimension adjacency-array 0)) (init most-negative-fixnum) (nodes-seen (make-array num-nodes :element-type 'fixnum :initial-element init)) (results (make-array num-nodes :element-type 'fixnum :initial-element init))) (labels ((visited-p (node) (not (eql init (aref results (1- node))))) (seen-p (node) (not (eql init (aref nodes-seen (1- node))))) (mark-seen (node) (setf (aref nodes-seen (1- node)) 1)) (mark-visited (node) (setf (aref results (1- node)) (funcall visit-function))) (visit (node) (unless (visited-p node) (when init-function-supplied-p (funcall init-function node)) (mark-seen node) (loop with stack = (list node) until (null stack) for head = (first stack) for tails = (aref adjacency-array (1- head)) for fresh-tails = (unless (visited-p head) (loop for tail in tails unless (or (visited-p tail) (seen-p tail)) collect tail)) do (if fresh-tails (progn (mapcar #'mark-seen fresh-tails) (setq stack (append fresh-tails stack))) (progn (pop stack) (unless (visited-p head) (mark-visited head)))))))) (loop for node from 1 to num-nodes unless (or (null node) (visited-p node)) do (visit node) finally (return results)))))
adjacency-arrayfor a graph
#((2 3) nil (1)).
visit-functionreturns a "visited" value for a node.
init-functionmakes necessary actions when new subgraph search starts.