16.1 グラフの表現

Next: 16.2 探索木の生成 Up: 16 探索プログラム例 Previous: 16 探索プログラム例

16.1 グラフの表現

graphとnodeというクラスを以下のように定義する．


(defclass graph :slots (nodes))
(defmethod graph
  (:init (nn)
         (setq nodes nn)
         self)
  )

(defclass node :slots (name neighbors))
(defmethod node
  (:init (&rest args &key ((:name n)) &allow-other-keys)
         (setq name n)
         self)
  )

以前示したグラフの初期化は次のようになる．


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


eus$ (init-graph)
#<graph #X104e0138>
eus$ *graph*
#<graph #X104e0138>
eus$ (describe *graph*)
nodes=(#<node #X104e5600 "s" >
       #<node #X104e596c "a" >
       #<node #X104e61ac "b" >
       #<node #X104e6728 "c" >
       #<node #X104e72f8 "d" >
       #<node #X104e74cc "e" >
       #<node #X104e7c88 "f" >)
nil

eus$ (send *graph* :find-route "s" "f" :depth-first)
route length from s to f is 5 in :depth-first method.
  route path is (s a b e f).
(#<node #X104e5600 "s" >
 #<node #X104e596c "a" >
 #<node #X104e61ac "b" >
 #<node #X104e74cc "e" >
 #<node #X104e7c88 "f" >)

eus$ (send *graph* :find-route "s" "f" :breadth-first)
route length from s to f is 4 in :breadth-first method.
  route path is (s d e f).
(#<node #X104e5600 "s" >
 #<node #X104e72f8 "d" >
 #<node #X104e74cc "e" >
 #<node #X104e7c88 "f" >)

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


(defun find-instance
      (item bag
            &key (key-method :name)
                 (test #'equal))
  (find item bag :test test
        :key #'(lambda (x) (send x key-method)))
  )

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

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