10.5 探索木表現のデータ変換

Next: 練習問題 Up: 10 探索木 Previous: 10.4 探索木表現のコンスセルを数える

10.5 探索木表現のデータ変換

*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)))))))

これを走らせると，下のようになります．

<cl> (tree-paths (graph-tree *graph2* 's))
((S A B C) (S A B E D) (S A B E F)
 (S A D E B C) (S A D E F) (S D A B C)
 (S D A B E F) (S D E B A)
 (S D E B C) (S D E F)) 

<cl> (find-all-paths *graph2* 's)
((S A B C) (S A B E D) (S A B E F)
 (S A D E B C) (S A D E F) (S D A B C)
 (S D A B E F) (S D E B A)
 (S D E B C) (S D E F))

逆に*tree1*から*tree2*へ変換する関数を考えると，ひとつの解決方法として， pathからedge-listを作り，それをグラフとみなして，graph-treeを呼ぶという方法が考えられます．


(defun paths-tree (paths)
 (graph-tree
   (list 'elist (paths-to-edge-list paths))
   (caar paths)))

(defun paths-to-edge-list (paths)
  (let ((result nil))
    (dolist
      (path paths)
     (setq result
          (union
            (mapcar #'list
                    (butlast path)
                    (cdr path))
            result
            :test #'edge-equal)))
    result))

butlastというのは，リストの最後の要素を取り除く組み込み関数です．

<cl> (butlast '(1 2 3))
(1 2)

butlastの定義はどのようになるでしょうか．

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