(defun init-graph-example nil (setq *graph-vertex-list* '(s a b c d e f)) (setq *graph-edge-list* '((s a) (s d) (a b) (a d) (b c) (b e) (d e) (e f))) (setq *graph1* (list 'elist *graph-edge-list*)) (setq *graph2* '(alist (s . (a d)) (a . (s b d)) (b . (a c e)) (c . (b)) (d . (s a e)) (e . (b d f)) (f . (e)))) (setq *graph3* (list 'plist *graph-vertex-list*)) (setf (get 's 'neighbors) '(a d)) (setf (get 'a 'neighbors) '(s b d)) (setf (get 'b 'neighbors) '(a c e)) (setf (get 'c 'neighbors) '(b)) (setf (get 'd 'neighbors) '(s a e)) (setf (get 'e 'neighbors) '(b d f)) (setf (get 'f 'neighbors) '(e)) (setq *graph4* (list 'hash (make-hash-table) *graph-vertex-list*)) (setf (gethash 's (cadr *graph4*)) '(a d)) (setf (gethash 'a (cadr *graph4*)) '(s b d)) (setf (gethash 'b (cadr *graph4*)) '(a c e)) (setf (gethash 'c (cadr *graph4*)) '(b)) (setf (gethash 'd (cadr *graph4*)) '(s a e)) (setf (gethash 'e (cadr *graph4*)) '(b d f)) (setf (gethash 'f (cadr *graph4*)) '(e)) (setq *graph5* (list 'amatrix (adjacency-matrix *graph-vertex-list* *graph-edge-list*) *graph-vertex-list*)) (setq *graph6* (graph-structure *graph-edge-list*)) t)すべてのデータをデータの種類を示すタグ (elist, alist, plist, hash, amatrix) を付けて表現します.このようにしておくのは,(1)辺を表すデータ の集合と隣接点リストの集合との見分けをはっきりつけるため,(2)隣接点行 列表現の場合に頂点リストの順番が重要でそのリストと合わせ持ったリストで 表現する必要があるため,(3) 5種類の表現をすべて同じ形のリストにするこ とでデータ変換を用意にするため,です. ある頂点の隣接点リストを得るための関数 を *graph-edge-list* を引数として, 得るための関数vertex-adjacency-list-from-elistを考えれば,
(defun vertex-adjacency-list-from-elist (vertex edge-list &optional (adjacency-list (list vertex))) (cond ((null edge-list) (remove vertex adjacency-list)) ((member vertex (car edge-list)) (vertex-adjacency-list-from-elist vertex (cdr edge-list) (union (car edge-list) adjacency-list))) (t (vertex-adjacency-list-from-elist vertex (cdr edge-list) adjacency-list))))
<cl> (vertex-adjacency-list-from-elist 's *graph-edge-list*) (D A) <cl> (vertex-adjacency-list-from-elist 'f *graph-edge-list*) (E)