在 Common Lisp 中表示有向无环图

Question

通常，为了在 Lisp 中表示一个基本的无向图，我可以创建一个父节点列表及其对应的子节点，如 this question 中所讨论的（为方便起见，在下面进行了说明）。

此图生成边列表：

(1 (2 6 7 8) 3 (4 (9 12)) 5 (10 11))

这适用于树或任何其他无向图的情况。然而，当我们想要表示每个节点可以有多个父节点的有向无环图时，这种表示就失效了：

现在，节点 8 有多个父节点 (2, 3)，但是当我们试图表示这一点时，我们无法判断节点 8 是否连接到两个父节点，或者是否有两个节点 8：

(1 (2 6 7 8) (3 8) (4 (9 12)) (5 10 11))

在具有唯一节点的图的情况下，我们当然可以做出这个假设，但据我所知，DAG 可以有重复的节点......那么我们如何处理呢？此外，我们如何将其表示为 Lisp 中的列表？

Answer 1

表示 DAG 的正确方法是节点（顶点）的集合：

(defstruct node
  payload
  children)

既然struct只有两个slot，当然可以用一个， cons 个单元格。

你给出的树的列表表示将 payload 与无子节点 node 混为一谈并弄乱了最右边的分支。正确的表示是

(1 (2 (6) (7) (8)) (3) (4 (9 (12))) (5 (10) (11)))

现在，子节点之间共享无子节点的 DAG (8) 节点 (2 ...) 和 (3 ...) 应该只共享单元格：

(1 (2 (6) (7) #1=(8)) (3 #1#) (4 (9 (12))) (5 (10) (11)))

参见 #n= 和 #n# 用于 reader 表示法。当然，您不应该使用它们来创建 DAG。

创建 DAG 的方法如下：

(defun make-node (&key payload children)
  (cons payload children))
(defparameter *my-dag*
  (let ((shared-mode (make-node :payload 8)))
    (make-node
     :payload 1
     :children
     (list (make-node :payload 2
                      :children (list (make-node :payload 6)
                                      (make-node :payload 7)
                                      shared-mode))
           (make-node :payload 3
                      :children (list shared-mode))
           (make-node :payload 4
                      :children (list (make-node :payload 9
                                                 :children (list (make-node :payload 12)))))
           (make-node :payload 5
                      :children (list (make-node :payload 10)
                                      (make-node :payload 11)))))))
(setq *print-circle* t)
*my-dag*
==> (1 (2 (6) (7) #1=(8)) (3 #1#) (4 (9 (12))) (5 (10) (11)))

Answer 2

只需列出具有两个节点 ID 的顶点：

((1 2) (1 3) (1 4) (1 5) (2 6) (2 7) (2 8) ... )

或使用矢量：

#((1 2) (1 3) (1 4) (1 5) (2 6) (2 7) (2 8) ... )

或使用节点列表及其后继节点：

((1 2 3 4 5) (2 6 7 8) (3 8) (4 9) ...)

在 Common Lisp 中表示有向无环图

Representing a directed acyclic graph in Common Lisp

lisp

graph-theory

graph

common-lisp

directed-acyclic-graphs