Common Lisp 中的反转有向图

Question

该函数的输入是一个有向图。例如，((A B C) (B C) (C D)) 表示存在从 A 到 B、A 到 C、B 到 C 和 C 到 D 的有向边。

我想做的是反转图中的所有边。因此，在上面的示例中，我试图获得类似 ((C B A) (B A) (D C)) 的输出。

这是我到目前为止编写的代码：

(defun reverse-net (net)
  (let (new-net)
    (dolist (obj net)
      (dolist (st (cdr obj))
        (let (cur (assoc st new-net))  
          (if cur
              (push (cons (car obj) cur) new-net)
            (push (list st (car obj)) new-net)))))
    new-net))

不幸的是，在代码中

assoc

（第5行）总是返回nil。我得到的输出是 ((D C) (C B) (C A) (B A))，它没有合并 (C B) 和 (C A)。 请帮我找出函数中的问题。

Answer 1

第一个问题是发布的代码缺少一些括号：

(let (cur (assoc st new-net))

-->

(let ((cur (assoc st new-net)))

。 SBCL 甚至不会编译发布的代码，而是发出错误消息：错误：LET 绑定规范 (ASSOC ST NEW-NET) 格式错误。

第二个问题是，当在

cur

中找到

new-net

时，会将扩大的节点列表推到

new-net

上，但旧的节点不会被删除。此问题的一种解决方案是在将更新后的列表推送到

new-net

之前删除找到的节点列表。

第三个问题是这一行：

(push (cons (car obj) cur) new-net)

将节点连接到节点列表的 front 上。您需要将它们附加到列表的back，因为列表中的第一个节点是源节点，而其他节点是目标节点。

(defun reverse-net (net)
  (let (new-net)
    (dolist (obj net)
      (dolist (st (cdr obj))
        (let ((cur (assoc st new-net)))  
          (cond (cur
                 (setf new-net (remove (car cur) new-net :key #'car))
                 (push (append cur (list (car obj))) new-net))
                (t
                 (push (list st (car obj)) new-net))))))
    new-net))

CL-USER> (reverse-net '((a b c) (b c) (c d)))
((D C) (C A B) (B A))