10.3 親子関係を表す木表現の生成

Next: 10.4 探索木表現のコンスセルを数える Up: 10 探索木 Previous: 10.2.3 目標頂点までの全パスを探索する

10.3 親子関係を表す木表現の生成

頂点の親(parent)から子(child)への関係を(parent . children)で表すとした場合の探索木の記述を得るための関数は以下のgraph-treeのように定義できます．


(defun graph-tree (graph start)
  (graph-tree-aux graph (list start)))
(defun graph-tree-aux (graph path)
  (let ((children (new-nodes path graph)))
    (if
      (null children)
      (cons (car path) nil)
      (cons
       (car path)
       (mapcar
        #'(lambda (x)
           (graph-tree-aux graph (cons x path)))
        children)))))

graph-tree は補助関数graph-tree-auxを使う形にしています．graph-tree-aux は，pathをもらい，そのパスの先端の頂点

が新しい頂点をもたなければ，その頂点のリストを返し，新しい頂点を持てば，その新しい頂点を新たなpath として再帰的に呼びだし，

を先頭にした木として返します．

<cl> (setq *tree2* (graph-tree *graph1* 's))
(S (A (B (C) (E (D) (F)))
      (D (E (B (C)) (F))))
   (D (A (B (C) (E (F))))
      (E (B (A) (C)) (F)))) 
<cl> (equal (graph-tree *graph2* 's)
            (graph-tree *graph3* 's))
T 
<cl> (equal (graph-tree *graph4* 's)
            (graph-tree *graph4* 's))
T 
<cl> (equal (graph-tree *graph5* 'f)
            (graph-tree *graph6* 'f))
NIL 
<cl> (pprint (graph-tree *graph1* 'f))
(F (E (D (A (B (C)) (S))
         (S (A (B (C)))))
      (B (C) (A (D (S)) (S (D)))))) 
<cl> (pprint (graph-tree *graph6* 'f))
(F (E (B (A (S (D)) (D (S))) (C))
      (D (S (A (B (C)))) (A (S) (B (C))))))

という具合になります．

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