8.4 隣接行列の表現例

Next: 8.5 構造体によるグラフの表現 Up: 8 グラフの記述 Previous: 8.3 ハッシュ表を用いて隣接点リストを表す

8.4 隣接行列の表現例

頂点の数に比べて辺の数が多いグラフを表現する場合には，隣接行列表現がよい場合が多くなりますが，lispの配列データで隣接行列を表現する例を紹介します． CommonLispの配列は以下のように作make-arrayで作り，要素へのアクセスはarefを用います．

<cl> (make-array '(3 3))
#2a((NIL NIL NIL) (NIL NIL NIL) (NIL NIL NIL)) 
<cl> (make-array '(3 3)
    :initial-contents '((t nil nil) (t t t) (t nil t)))
#2a((T NIL NIL) (T T T) (T NIL T))

配列を用いてグラフを表現する場合に，配列のインデックスと頂点との対応を付けるための工夫が必要です．ここでは，頂点のリストにおけるインデックスに合わせた配置になるようにpositionという関数を用いて自動的に頂点の名前からインデックスを求めることを行なっています．

(defun adjacency-matrix 
  (&optional (gvl *graph-vertex-list*)
             (gel *graph-edge-list*))
  (let ((graph (make-array
                (list (length gvl) (length gvl)))))
    (dolist (el gel)
       (setf (aref graph (position (car el) gvl)
             (position (cadr el) gvl)) t)
       (setf (aref graph (position (cadr el) gvl)
             (position (car el) gvl)) t))
    graph))

<cl> (setq *graph5*
     (adjacency-matrix
        *graph-vertex-list* *graph-edge-list*))
#2a((NIL T   T   NIL NIL NIL NIL)
    (T   NIL T   T   NIL NIL NIL)
    (T   T   NIL NIL NIL T   NIL)
    (NIL T   NIL NIL T   T   NIL)
    (NIL NIL NIL T   NIL NIL NIL)
    (NIL NIL T   T   NIL NIL T  )
    (NIL NIL NIL NIL NIL T   NIL))

ここで用いているpositionはシーケンスデータに対して第一引数で渡したデータと同じ要素のある場所を返す関数です．:test, :key引数も使えます．

<cl> (position 'a '(a b c))
0 
<cl> (position 'c '(a b c))
2 
<cl> (position 'x '(a b c))
NIL 
<cl> (position '(b) '((a) (b) (c)))
NIL

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