next up previous
Next: 8.6 隣接点リストを得る関数 Up: 8 グラフの記述 Previous: 8.4 隣接行列の表現例

8.5 構造体によるグラフの表現

構造体でグラフを表現する例を示します． Lispでは，データの等しさを調べる関数には，=, eq, eql, tree-equal, equal, equalpがありますが，リストデータを要素にした構造体の等しさを調 べる関数にはequalpが使えます． 
<cl> (defstruct test a b)
TEST 
<cl> (setq a (list (make-test :a '(a) :b '(b))
                   (make-test :a '(a) :b '(b))))
(#s(TEST :A (A) :B (B)) #s(TEST :A (A) :B (B))) 
<cl> (setq b (make-test :a '(a) :b '(b)))
#s(TEST :A (A) :B (B)) 
<cl> (setq c (list b b))
(#s(TEST :A (A) :B (B)) #s(TEST :A (A) :B (B))) 
<cl> (eq (car a) (cadr a))
NIL 
<cl> (eq (car c) (cadr c))
T 
<cl> (eql (car a) (cadr a))
NIL 
<cl> (equal (car a) (cadr a))
NIL 
<cl> (equalp (car a) (cadr a))
T
一般に構造体でグラフを表現する場合に，頂点の構造体のコピーを作らなけれ ば，構造体の比較はeqで可能になります． そこで，以下のように構造体のコピーを作らないようにグラフを作りました． 
(defstruct graph  vlist elist)
(defstruct vertex name alist)
(defstruct edge vertex1 vertex2)
(defun graph-structure (&optional (gel *graph-edge-list*))
  (let ((gvl 
         (mapcar #'(lambda (v) (make-vertex :name v))
                 (graph-vlist gel)))
        (graph nil))
    (setq graph
          (make-graph
           :vlist gvl
           :elist
           (mapcar
            #'(lambda (e)
               (make-edge
                :vertex1 
                (find (car e) gvl :key #'vertex-name)
                :vertex2
                (find (cadr e) gvl :key #'vertex-name)))
            gel)))
    (dolist (vl (graph-vlist graph))
      (mapc
       #'(lambda (av)
          (push
           (find av (graph-vlist graph) :key #'vertex-name)
           (vertex-alist vl)))
       (vertex-adjacency-list-from-elist (vertex-name vl) gel)))
      graph))
以下のように実行すると，頂点sに対応する構造体のalistには，頂点dが入っ ていることがわかります．つまりdへのポインタが入っているわけで，コピー へのポインタが入っているわけではないということがわかります．コピーへの ポインタならば(find d (vertex-alist s) :test 'eq)はnilになってしまい， そのnotはTになってしまいます． 
<cl> (setq vl (graph-vlist *graph6*))
<cl> (setq s (find 's vl :key #'vertex-name))
<cl> (setq d (find 'd vl :key #'vertex-name))
<cl> (not (find d (vertex-alist s) :test 'eq))
NIL
今まで頂点として使ってきたシンボルはコピーが作られる心配がありませんで した．それは，Lispの処理系がシンボル名を読み込んだときに，すでに使われ たシンボルの登録表の中からそのシンボル名をもつシンボルを毎回探しだし， そのシンボルへのポインタを返すようにしているからです． 構造体データの生成がそのようにコピーを作らない生成方法になっていたなら ば，上のように作らずとも必要となったところでmakeをすればよいということ になります．しかし，Lispのオブジェクト空間の中から構造体の内部のequalp を調べるというのは大変な処理になってしまいます．また，コピーが必要な場 合に困ってしまうため，このような形になっています．

generated through LaTeX2HTML. M.Inaba 平成18年5月6日