2

選択したノードの子であるすべてのノードを見つける必要があります。グラフは次のように作成されます：（setq graf1'（（A（BC））（B（DE））（C（FG））（D（H））（E（I））（F（J））（G（ J））（H（））（I（J））（J（））））したがって、ノードBのすべての子は（第1レベルで）D、E、第2 H、I、第3Jです。コードは次のとおりです。最初のレベルの子供を見つけるためですが、私はLispの初心者なので、他の子供のためにそれを機能させることはできません。

(defun sledG (cvor graf obradjeni)
  (cond ((null graf) '())
        ((equal (caar graf) cvor)
                (dodaj (cadar graf) obradjeni))
        (t(sledG cvor (cdr graf) obradjeni)))
(defun dodaj (potomci obradjeni)
  (cond ((null potomci) '())
        ((member (car potomci) obradjeni)
         (dodaj (cdr potomci) obradjeni )
        (t(cons (car potomci)
                (dodaj (cdr potomci) obradjeni) ))))
(setq graf1 '((A(B C)) (B(D E)) (C (F G )) (D (H)) (E(I)) (F(J)) (G(J)) (H()) (I(J)) (J())))
4

2 に答える 2

2

私が読んでいるように、グラフは有向グラフです。したがって、グラフの子（有向エッジ）を見つけるには（例では）、

(defun children (node graph) (second (assoc node graph)))

それから

(children 'b graf1) ; with graf1 from the OP

（DE）を返します。その後、あなたがしなければならないのは、（非常に速くて汚い）のようなもののように、子供たちをループすることです

(defun all-children (node graph)
  (let ((c (children node graph)))
    (if (null c) nil
        (union c (loop for x in c appending (all-children x graph))))))

これは、Bの子として（JIHDE）を返します。

于 2013-03-27T10:37:09.723 に答える
2

alexandriaパッケージの使用：

(defvar *graf*
  '((a (b c)) (b (d e)) (c (f g)) (d (h)) (e (i)) (f (j)) (g (j)) (h nil) (i (j)) (j nil)))

(defun descendants (tree label)
  (let ((generation
         (mapcan #'cadr
                 (remove-if-not
                  (alexandria:compose (alexandria:curry #'eql label) #'car)
                  tree))))
    (append generation (mapcan (alexandria:curry #'descendants tree) generation))))

;; (D E H I J)

これがあなたがやりたかったことだと思います。これは非巡回グラフでは機能しますが、サイクルがある場合は「永久に」繰り返されます。深度カウンターを追加する場合は、深度カウンターを挿入することにより、結果のリストにもう1つの引数として追加するdescendantsか、最後のmapcan変換で追加できます。

深さを含む：

(defun descendants (tree label)
  (labels ((%descendants (depth label)
             (let ((generation
                    (mapcan #'cadr
                            (remove-if-not
                             (alexandria:compose
                               (alexandria:curry #'eql label) #'car)
                             tree))))
               (append (mapcar (alexandria:compose
                                #'nreverse
                                (alexandria:curry #'list depth))
                               generation)
                       (mapcan (alexandria:curry #'%descendants (1+ depth))
                               generation)))))
    (%descendants 0 label)))

;; ((D 0) (E 0) (H 1) (I 1) (J 2))
于 2013-03-27T17:12:20.853 に答える