Next: 8.1 連想リスト Up: ソフトウェア特論　講義資料リスト，集合，グラフ，木の処理 Previous: 7.3 隣接点リスト(adjacency list)

8 グラフの記述

グラフは，リストデータを用いれば容易に表現できますが，グラフの頂点に付加的な情報を与えたい場合に構造体を用いる方法，辺の数がノードの数に比べて大きい場合に配列やハッシュ法を用いる方法などLisp処理系のデータを活用することが必要になる場合があります．図1に示すようなグラフに対して，辺のリスト (*graph1*)，隣接点リストのリスト(*graph2*)，隣接点リストの属性リスト表現(*graph3*)，隣接点リストのハッシュ表表現(*graph4*)，隣接行列表現 ( *graph5* )，構造体表現( *graph6* ) ，の例を示します．


(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) ５種類の表現をすべて同じ形のリストにすることでデータ変換を用意にするため，です．ある頂点の隣接点リストを得るための関数を *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)

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