14.1 グラフの表現

Next: 14.2 探索木の生成 Up: 14 探索プログラムの実現 Previous: 14 探索プログラムの実現

14.1 グラフの表現

グラフは，Lispではノードをシンボルとしてリストデータを用いれば容易に表現できます．グラフの頂点に付加的な情報を与えたい場合にノードを構造体で表現することも有効です．辺の数がノードの数に比べて大きい場合には，配列やハッシュ法を用いる方法などLisp処理系のデータを活用することが必要になる場合もあります．ここでは，グラフ全体を表すクラスとノードを表すクラスを考え，それらでグラフを表現してみます． graphとnodeというクラスを以下のように定義します．


(defclass graph ()
  ((nodes :initarg :nodes :accessor nodes)))

(defclass node ()
  ((name :accessor node-name :initarg :name)
   (neighbors :accessor node-neighbors
              :initarg :neighbors :initform nil))
  )

**図 1:** 状態空間
$\includegraphics[width=7cm]{/home/inaba/eps/lecture/fig/searchspace.eps}$

図1のグラフの初期化は次のようになります．


(defun init-graph ()
  (setq s (make-instance 'node :name "s"))
  (setq a (make-instance 'node :name "a"))
  (setq b (make-instance 'node :name "b"))
  (setq c (make-instance 'node :name "c"))
  (setq d (make-instance 'node :name "d"))
  (setq e (make-instance 'node :name "e"))
  (setq f (make-instance 'node :name "f"))
  ;;
  (setf (node-neighbors s) (list a d))
  (setf (node-neighbors a) (list s b d))
  (setf (node-neighbors b) (list a c e))
  (setf (node-neighbors c) (list b))
  (setf (node-neighbors d) (list s a e))
  (setf (node-neighbors e) (list b d f))
  (setf (node-neighbors f) (list e))
  ;;
  (setq *graph* 
    (make-instance 'graph
      :nodes (list s a b c d e f)))
  )

このように，ノードを作り，各ノードに隣接しているノードのリストを与えて初期化します．


<cl> (init-graph)
#<GRAPH @ #x203c1e2a>

<cl> *graph*
#<GRAPH @ #x203c1e2a>

<cl> (describe *graph*)
#<GRAPH @ #x203c1e2a> is
      an instance of #<STANDARD-CLASS GRAPH>:
 The following slots have :INSTANCE allocation:
  NODES   (#<NODE @ #x203c1a92> #<NODE @ #x203c1ac2>
           #<NODE @ #x203c1af2> #<NODE @ #x203c1b22>
           #<NODE @ #x203c1b52> #<NODE @ #x203c1b82>
           #<NODE @ #x203c1bb2>)

<cl> (find-route *graph* "s" "f" #'depth-first)
route length from s to f is
       5 in #<STANDARD-GENERIC-FUNCTION
                          DEPTH-FIRST> method.
  route path is (s a b e f).
(#<NODE @ #x203c1a92> #<NODE @ #x203c1ac2>
 #<NODE @ #x203c1af2>
 #<NODE @ #x203c1b82> #<NODE @ #x203c1bb2>)

<cl> (find-route *graph* "s" "f" #'breadth-first)
route length from s to f is 4
         in #<STANDARD-GENERIC-FUNCTION
                         BREADTH-FIRST> method.
  route path is (s d e f).
(#<NODE @ #x203c1a92> #<NODE @ #x203c1b52>
 #<NODE @ #x203c1b82>
 #<NODE @ #x203c1bb2>)

というようになっています．ノードは名前を持っていて，グラフに対してある名前でノードを検索できるようにしておかないと後々使いにくいため，以下のように，find-nodeメソッドを定義します．


(defun find-instance
    (item bag
     &key (key 'node-name) (test #'equal))
  (find item bag :test test :key key)
  )

(defmethod find-node 
    ((self graph) item
     &key (key-method 'node-name) (test #'equal))
  (find-instance item (nodes self)
                 :test test :key key-method))

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