Next: 6.3 縦型，横型探索
Up: 6 探索プログラム例
Previous: 6.1 グラフの表現
探索木を作るメソッドを:find-all-pathsとしてgraphクラスに定義する．self
変数に:find-all-pathsを送ることで再帰定義がなされている．
(defun new-nodes (path)
(remove-if
#'(lambda (n) (member n path))
(send (first path) :neighbors)))
(defun new-paths (new-nodes path)
(mapcar
#'(lambda (n) (cons n path))
new-nodes))
(defmethod graph
(:find-all-paths
(start &optional (path-queue (list (list start))))
(if
(null path-queue) nil
(let* ((path (first path-queue))
(new-nodes (new-nodes path)))
(if
(null new-nodes)
(cons (reverse path)
(send self :find-all-paths
start
(rest path-queue)))
(send self :find-all-paths
start
(append (new-paths new-nodes path)
(rest path-queue)))))
))
)
実行結果は以下のようになります．
eus$ (send *graph* :find-all-paths
(send *graph* :find-node "s"))
((#<node #X104e5600 "s" >
#<node #X104e596c "a" >
#<node #X104e61ac "b" >
#<node #X104e6728 "c" >)
(#<node #X104e5600 "s" >
#<node #X104e596c "a" >
#<node #X104e61ac "b" >
#<node #X104e74cc "e" >
#<node #X104e72f8 "d" >)
(#<node #X104e5600 "s" >
#<node #X104e596c "a" >
#<node #X104e61ac "b" >
#<node #X104e74cc "e" >
#<node #X104e7c88 "f" >)
(#<node #X104e5600 "s" >
#<node #X104e596c "a" >
#<node #X104e72f8 "d" >
#<node #X104e74cc "e" >
#<node #X104e61ac "b" >
#<node #X104e6728 "c" >)
(#<node #X104e5600 "s" >
#<node #X104e596c "a" >
#<node #X104e72f8 "d" >
#<node #X104e74cc "e" >
#<node #X104e7c88 "f" >)
(#<node #X104e5600 "s" >
#<node #X104e72f8 "d" >
#<node #X104e596c "a" >
#<node #X104e61ac "b" >
#<node #X104e6728 "c" >)
(#<node #X104e5600 "s" >
#<node #X104e72f8 "d" >
#<node #X104e596c "a" >
#<node #X104e61ac "b" >
#<node #X104e74cc "e" >
#<node #X104e7c88 "f" >)
(#<node #X104e5600 "s" >
#<node #X104e72f8 "d" >
#<node #X104e74cc "e" >
#<node #X104e61ac "b" >
#<node #X104e596c "a" >)
(#<node #X104e5600 "s" >
#<node #X104e72f8 "d" >
#<node #X104e74cc "e" >
#<node #X104e61ac "b" >
#<node #X104e6728 "c" >)
(#<node #X104e5600 "s" >
#<node #X104e72f8 "d" >
#<node #X104e74cc "e" >
#<node #X104e7c88 "f" >))
generated through LaTeX2HTML. M.Inaba 平成18年5月6日