高效跟踪有向图中的链接（Common Lisp）
Efficiently Following the Links in a Directed Graph (Common Lisp)
我想开发一种有效的策略，可以快速测试大型全连接有向标记图中是否存在预先指定的路径。例如，从某个节点开始，比如 node0，是否存在到另一个节点的路径，比如 node9，它遵循标记为 links 的序列，比如 node0 -> link3 -> link1 -> link4+ -> link1 -> node9，其中 link+ 表示 link 标签的一次或多次重复。该图是动态的，因此节点和 link 将不断添加和删除。唯一节点和 link 标签将是由基础语义信息构造的字符串。
我的第一个（最简单的）想法是将所有标记的图形节点和 link 作为符号存储在一个单独的包中。然后安装一个散列 table 作为每个节点的符号值。散列 table 将从该节点发出的所有 link 携带该节点的关联到它们各自的目标节点。测试链中的下一个 link 是否存在，然后是一个简单的 table 查找。查找总数取决于 link 链的长度。所有对节点和标签符号的编程引用都将通过包名称进行。
但是，我不确定使用符号和符号值作为数据结构是否可取。在这种情况下，将它们放在自己的包中是否可以减轻潜在的冲突？
如果你想使用符号，你不需要哈希表；您可以将数据存储在符号的 symbol-value 槽中，并将任何其他数据存储在其 symbol-plist 中。查找要么在读取时已经完成，要么在运行时使用 find-symbol 或 intern 完成。您可以使用 unintern 将符号与其主包分离，但其他节点仍然可以引用它，因此在删除节点时您需要删除对该符号的任何其他引用（这就是为什么有时您同时存储传入的和节点的出边）。
可以做到，据我所知，这曾经是历史上处理符号的常用方式。一个可能的缺点是当你创建一个包时你必须给它命名（所以没有即时的匿名包）。您可能必须选择当前未用作包名称的字符串，并将节点名称限制为特定包。
另一种实现方法是使用 node class 来保存 name，其中名称可以是用户选择的任何符号（在任何包中）。 graph class 维护所有节点和边缘等，您可以单独操作这些对象，而不会弄乱环境的包列表等。这可能会更干净一些。
它是最近推出的，所以我还想指出这本书的存在：Programming Algorithms Vsevolod Domkin，它使用 Common Lisp 来实现算法。
与其执着于实施，我会设计一个系统需要遵循的 协议 。这是一个这样的（注意我在这里做了一些假设，其中一些可能是隐含的，并且 none 可能与您希望事情如何工作一致）：
;;;; Protocol
;;;
;;; By assumption there is one link with each label, each link points
;;; at one other node.
;;;
;;; NODEs have identity and can be destructively modified but it is
;;; not specified whether node equality is object identity.
;;;
(defgeneric node-link-labelled (node label)
(:documentation "Return the node linked to NODE via LABEL, or NIL".))
(defgeneric (setf node-link-labelled) (target node label)
(:documentation "set the link with label LABEL of NODE to TARGET, replacing it if
it exists. Return TARGET."))
(defgeneric nodes-equal (n1 n2)
(:documentation "Are N1 and N2 the same node?"))
(defgeneric node-remove-link (node label)
(:documentation "Remove the link with label LABEL from NODE. Return NODE.
The link need not exist"))
(defgeneric mapc-node-links (fn node)
(:documentation "call FN with arguments NODE, LABEL TARGET for each link of NODE.
FN is allowed to delete the link corresponding to LABEL but should not otherwise
modify NODE"))
然后你可以为这个协议编写实现。这是一个简单的节点，其中节点是(<something> . <links>) 的conses。这对于大量链接来说会很慢，但对于少量链接可能非常快。它有一个很好的特性，你可以给节点命名，这在上面的协议中是不支持的。
;;;; Consy nodes are simple
;;;
(defun make-consy-node (&optional (label 'node))
(list label))
(defmethod node-link-labelled ((node cons) label)
(cdr (assoc label (cdr node))))
(defmethod nodes-equal ((n1 cons) (n2 cons))
(eql n1 n2))
(defmethod (setf node-link-labelled) (target (node cons) label)
(let ((found (assoc label (cdr node))))
(if found
(setf (cdr found) target)
(push (cons label target) (cdr node))))
target)
(defmethod node-remove-link ((node cons) label)
(setf (cdr node) (delete-if (lambda (link)
(eql (car link) label))
(cdr node)))
node)
(defmethod mapc-node-links (fn (node cons))
;; This is at least safe
(loop for (label . target) in (copy-list (cdr node))
do (funcall fn node label target))
node)
或者您可以将节点实现为哈希表，这对于具有许多每个节点链接的图来说会很快：
;;;; Hashy nodes
;;;
(defun make-hashy-node ()
(make-hash-table))
(defmethod nodes-equal ((n1 hash-table) (n2 hash-table))
(eql n1 n2))
(defmethod node-link-labelled ((node hash-table) label)
(values (gethash label node nil)))
(defmethod (setf node-link-labelled) (target (node hash-table) label)
(setf (gethash label node) target)
target)
(defmethod node-remove-link ((node hash-table) label)
(remhash label node)
node)
(defmethod mapc-node-links (fn (node hash-table))
(maphash (lambda (label target)
(funcall fn node label target))
node)
node)
或者您可以做任何其他事情。由于它们都遵循协议，您可以将它们混合使用：
(let ((n1 (make-hashy-node)))
(setf (node-link-labelled n1 'foo) (make-hashy-node)
(node-link-labelled n1 'bar) (make-consy-node 'n2))
n1)
如果需要，您可以将节点构建定义为协议的一部分：
(defgeneric make-node-of-sort (sort &key)
(:documentation "make a node whose sort is SORT. Methods on this GF should
use EQL specializers on SORT"))
...
(defmethod make-node-of-sort ((sort (eql 'consy)) &key (name 'node))
(list name))
...
我想开发一种有效的策略，可以快速测试大型全连接有向标记图中是否存在预先指定的路径。例如，从某个节点开始，比如 node0，是否存在到另一个节点的路径，比如 node9，它遵循标记为 links 的序列，比如 node0 -> link3 -> link1 -> link4+ -> link1 -> node9，其中 link+ 表示 link 标签的一次或多次重复。该图是动态的，因此节点和 link 将不断添加和删除。唯一节点和 link 标签将是由基础语义信息构造的字符串。
我的第一个（最简单的）想法是将所有标记的图形节点和 link 作为符号存储在一个单独的包中。然后安装一个散列 table 作为每个节点的符号值。散列 table 将从该节点发出的所有 link 携带该节点的关联到它们各自的目标节点。测试链中的下一个 link 是否存在，然后是一个简单的 table 查找。查找总数取决于 link 链的长度。所有对节点和标签符号的编程引用都将通过包名称进行。
但是，我不确定使用符号和符号值作为数据结构是否可取。在这种情况下，将它们放在自己的包中是否可以减轻潜在的冲突？
如果你想使用符号，你不需要哈希表；您可以将数据存储在符号的 symbol-value 槽中，并将任何其他数据存储在其 symbol-plist 中。查找要么在读取时已经完成，要么在运行时使用 find-symbol 或 intern 完成。您可以使用 unintern 将符号与其主包分离，但其他节点仍然可以引用它，因此在删除节点时您需要删除对该符号的任何其他引用（这就是为什么有时您同时存储传入的和节点的出边）。
可以做到，据我所知，这曾经是历史上处理符号的常用方式。一个可能的缺点是当你创建一个包时你必须给它命名（所以没有即时的匿名包）。您可能必须选择当前未用作包名称的字符串，并将节点名称限制为特定包。
另一种实现方法是使用 node class 来保存 name，其中名称可以是用户选择的任何符号（在任何包中）。 graph class 维护所有节点和边缘等，您可以单独操作这些对象，而不会弄乱环境的包列表等。这可能会更干净一些。
它是最近推出的，所以我还想指出这本书的存在：Programming Algorithms Vsevolod Domkin，它使用 Common Lisp 来实现算法。
与其执着于实施，我会设计一个系统需要遵循的 协议 。这是一个这样的（注意我在这里做了一些假设，其中一些可能是隐含的，并且 none 可能与您希望事情如何工作一致）：
;;;; Protocol
;;;
;;; By assumption there is one link with each label, each link points
;;; at one other node.
;;;
;;; NODEs have identity and can be destructively modified but it is
;;; not specified whether node equality is object identity.
;;;
(defgeneric node-link-labelled (node label)
(:documentation "Return the node linked to NODE via LABEL, or NIL".))
(defgeneric (setf node-link-labelled) (target node label)
(:documentation "set the link with label LABEL of NODE to TARGET, replacing it if
it exists. Return TARGET."))
(defgeneric nodes-equal (n1 n2)
(:documentation "Are N1 and N2 the same node?"))
(defgeneric node-remove-link (node label)
(:documentation "Remove the link with label LABEL from NODE. Return NODE.
The link need not exist"))
(defgeneric mapc-node-links (fn node)
(:documentation "call FN with arguments NODE, LABEL TARGET for each link of NODE.
FN is allowed to delete the link corresponding to LABEL but should not otherwise
modify NODE"))
然后你可以为这个协议编写实现。这是一个简单的节点，其中节点是(<something> . <links>) 的conses。这对于大量链接来说会很慢，但对于少量链接可能非常快。它有一个很好的特性，你可以给节点命名，这在上面的协议中是不支持的。
;;;; Consy nodes are simple
;;;
(defun make-consy-node (&optional (label 'node))
(list label))
(defmethod node-link-labelled ((node cons) label)
(cdr (assoc label (cdr node))))
(defmethod nodes-equal ((n1 cons) (n2 cons))
(eql n1 n2))
(defmethod (setf node-link-labelled) (target (node cons) label)
(let ((found (assoc label (cdr node))))
(if found
(setf (cdr found) target)
(push (cons label target) (cdr node))))
target)
(defmethod node-remove-link ((node cons) label)
(setf (cdr node) (delete-if (lambda (link)
(eql (car link) label))
(cdr node)))
node)
(defmethod mapc-node-links (fn (node cons))
;; This is at least safe
(loop for (label . target) in (copy-list (cdr node))
do (funcall fn node label target))
node)
或者您可以将节点实现为哈希表，这对于具有许多每个节点链接的图来说会很快：
;;;; Hashy nodes
;;;
(defun make-hashy-node ()
(make-hash-table))
(defmethod nodes-equal ((n1 hash-table) (n2 hash-table))
(eql n1 n2))
(defmethod node-link-labelled ((node hash-table) label)
(values (gethash label node nil)))
(defmethod (setf node-link-labelled) (target (node hash-table) label)
(setf (gethash label node) target)
target)
(defmethod node-remove-link ((node hash-table) label)
(remhash label node)
node)
(defmethod mapc-node-links (fn (node hash-table))
(maphash (lambda (label target)
(funcall fn node label target))
node)
node)
或者您可以做任何其他事情。由于它们都遵循协议，您可以将它们混合使用：
(let ((n1 (make-hashy-node)))
(setf (node-link-labelled n1 'foo) (make-hashy-node)
(node-link-labelled n1 'bar) (make-consy-node 'n2))
n1)
如果需要，您可以将节点构建定义为协议的一部分：
(defgeneric make-node-of-sort (sort &key)
(:documentation "make a node whose sort is SORT. Methods on this GF should
use EQL specializers on SORT"))
...
(defmethod make-node-of-sort ((sort (eql 'consy)) &key (name 'node))
(list name))
...