next up previous
Next: 10.2.2 全パスの探索 Up: 10.2 探索木の生成 Previous: 10.2 探索木の生成

10.2.1 パスの展開

グラフの探索においては，探索中の現在いる頂点（$v_n$）をもとに，$v_n$に 隣接している頂点を調べます．そこで，探索プログラムで必要となるも のとして，$v_1$から$v_n$までの path を与えて，$v_n$に隣接する頂点を求 めるという関数があげられます．この関数をnew-nodesと定義することにしま す． 次に，new-nodesで得られる頂点群へパスを伸ばして得られる新しいパス群を 作る関数をnew-pathsとして定義することにします． まず，new-nodesによりpathの最後の頂点$v_n$を展開するためには， (vertex-adjacency-list $v_n$ graph) として，頂点のリストを返す vertex-adjacency-list を用います． 

(defun new-nodes (path graph)
  (remove-if
   #'(lambda (n) (member n path))
   (vertex-adjacency-list (first path) graph)))

(defun new-paths (new-nodes path)
  (mapcar
   #'(lambda (n) (cons n path))
   new-nodes))
new-nodesはpathをもらってpathの先頭の頂点（現在探索中の頂点） の隣接点リストを取りだし，隣接点リストの各頂点のうちpathに すでに含まれているものを取り除きます．つまり，すでに通って来た 道にある頂点を除いた点のみを返します． new-pathsは，new-nodesとpathをもらって，新しいpathを 生成します．new-nodesに含まれる頂点の数だけの新しいpathの リストが返されます． vertex-adjacency-listは， 
(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))

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