8.6 隣接点リストを得る関数

Next: 9 グラフの比較 Up: 8 グラフの記述 Previous: 8.5 構造体によるグラフの表現

8.6 隣接点リストを得る関数

どのような記述形式であろうともそのグラフと頂点（

）シンボルを与えるとその頂点の隣接点リストを返す関数を以下に定義します．


(defun vertex-adjacency-list
  (vertex graph)
  (if
      (listp graph)
      (case (car graph)
       (elist
        (vertex-adjacency-list-from-elist
         vertex (cadr graph)))
       (alist   
        (cdr (assoc vertex (cdr graph))))
       (plist
        (get vertex 'neighbors))
       (hash
        (gethash vertex (cadr graph)))
       (amatrix
        (vertex-adjacency-list-from-amatrix
         vertex graph)))
    (if
        (graph-p graph)
        (mapcar
          #'vertex-name
          (vertex-alist
             (find vertex (graph-vlist graph)
               :key #'(lambda (x) (vertex-name x))))))))
  )


(defun vertex-adjacency-list-from-elist
  (vertex edge-list
          &key (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)
     :adjacency-list
        (union (car edge-list) adjacency-list)))
   (t (vertex-adjacency-list-from-elist
       vertex
       (cdr edge-list)
       :adjacency-list adjacency-list))))
;;;
(defun amatrix-vlist (amatrix) (caddr amatrix))
(defun amatrix-matrix (amatrix) (cadr amatrix))
(defun vertex-adjacency-list-from-amatrix
      (vertex graph)
  (let* ((vlist (amatrix-vlist graph))
         (amatrix (amatrix-matrix graph))
         (index (position vertex vlist))
         (len (length vlist))
         (result nil))
    (dotimes (i len)
             (if (aref amatrix index i) 
                 (push (elt vlist i) result)))
    result))

caseというのはマクロです．PascalやC言語のswitch文のような働きをします．ちなみにマクロ展開した形を見てみると，


<cl>  (macroexpand '(case (car '(a b c))
        (a 1) (b 2) (c 3)))

(LET ((#:G3 (CAR '(A B C))))
   (DECLARE (IGNORE-IF-UNUSED #:G3))
       (COND ((EQL 'A #:G3) 1)
             ((EQL 'B #:G3) 2)
             ((EQL 'C #:G3) 3))) 
T

となっています．このマクロ定義で注意しておくことは，caseの第一引数が letの局所変数に一旦代入されていることです．これを行なっておかないと，第一引数の関数が副作用を持った場合に，その関数が何度も実行された時に，予定外の副作用をよけいに及ぼすことになります．

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