Вместо того, чтобы зацикливаться на реализации, я бы разработал протокол , которому должна следовать система. Вот один из них (обратите внимание, что я сделал здесь некоторые предположения, некоторые из которых, вероятно, являются неявными, и ни одно из которых не может согласиться с тем, как вы хотите, чтобы все работало):
;;;; 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>). Это будет медленно для большого количества ссылок, но, вероятно, очень быстро для небольших номеров. У него есть приятная особенность, заключающаяся в том, что вы можете задавать имена узлов, которые не поддерживаются в вышеуказанном протоколе.
;;;; 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)
Или вы можете реализовать узлы в виде таблиц ha sh, которые будут быстрыми для графов со многими ссылки на узел:
;;;; 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))
...