在Lisp中提高非递归深度优先搜索函数的可读性

Question

作为一项自由活动，为了学习一些Lisp，我必须实现深度优先有向图搜索。由于大图大小(800 K节点，5米弧)递归的方法，我可以设计不起作用。

下面是我的基于堆栈的实现，我想在可读性方面进行改进，如果没有其他的话。欢迎任何关于风格、使用Lisp习语、代码嗅觉的评论。

(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-array，1->2;1->3;3->1将是#((2 3) nil (1))。
• visit-function返回节点的“访问”值。
• 当新的子图搜索开始时，init-function会进行必要的操作。

Answer 1

ANSI不支持LOOP的这种用法。在UNTIL子句(变量子句)之前不能有FOR子句(仅在LOOP语法中的main子句中)。

见：宏回路。