Next: 練習問題
Up: 13 探索木
Previous: 13.3 親子関係を表す木表現の生成
*tree2*から*tree1*を作るには，以下のような関数tree-pathsを定義する．
考え方は，*tree2*の頂点におけるcdr部の各要素に対してtree-pathsを再帰的
に呼び，返ってきたものはパスのリストのリストになっているから，それら
をすべてappendして，パスのリストとして集める．そして，集まったパスの
リストのそれぞれのパスに対して現在の頂点を付け加えるということを行なう．
再帰的に呼ばれた場合，子どもがなくなったところが末端条件になるが，
子どもがなにもなければその頂点ひとつからなるパスとみなしてリター
ンします．
(defun tree-paths (tree)
(cond
((null (cdr tree)) (list tree))
(t (mapcar
#'(lambda (x)
(cons (car tree) x))
(apply
#'append
(mapcar
#'(lambda (p)
(tree-paths p))
(cdr tree)))))))
これを走らせると，下のようになる．
> (tree-paths *tree2*)
((s d e b a) (s d e b c) (s d e f)
(s d a b e f) (s d a b c) (s a d e b c)
(s a d e f) (s a b e f) (s a b e d) (s a b c))
> (tree-paths (graph-tree *graph2* 's))
((s a d e f) (s a d e b c) (s a b e f)
(s a b e d) (s a b c) (s d e f)
(s d e b a) (s d e b c) (s d a b e f)
(s d a b c))
> *graph2*
((f e) (e b) (e d) (d s) (d a) (c b) (b a) (a s))
> (find-all-paths *graph2* 's)
((s a d e f) (s a d e b c) (s a b e f)
(s a b e d) (s a b c) (s d e f) (s d e b a)
(s d e b c) (s d a b e f) (s d a b c))
逆に*tree1*から*tree2*へ変換する関数を考えると，ひとつの解決方法として，
pathからedge-listを作り，それをグラフとみなして，graph-treeを呼ぶとい
う方法が考えられる．
generated through LaTeX2HTML. M.Inaba 平成18年5月7日