Представление ориентированного ациклического графа в Common Lisp - PullRequest
Новая
       33

Представление ориентированного ациклического графа в Common Lisp

0 голосов
/ 06 сентября 2018

Обычно для представления базового неориентированного графа в Лиспе я могу создать список родительских узлов и их соответствующих дочерних узлов, как обсуждалось в этом вопросе (для удобства проиллюстрирован ниже).

enter image description here

этот график дает список ребер: 

(1 (2 6 7 8) 3 (4 (9 12)) 5 (10 11))

Это работает в случае дерева или любого другого неориентированного графа. Однако этот тип представления нарушается, когда мы хотим представить ориентированный ациклический граф, где у каждого узла может быть несколько родителей:

enter image description here

Теперь, у Узла 8 есть несколько родителей (2, 3), но когда мы пытаемся представить это, мы теряем способность определять, связан ли узел 8 с двумя родительскими узлами или есть два узла 8: 

(1 (2 6 7 8) (3 8) (4 (9 12)) (5 10 11))

В случае графа с уникальными узлами мы, безусловно, можем сделать это предположение, но, насколько мне известно, группы обеспечения доступности баз данных могут иметь дублированные узлы ... так как нам с этим бороться? Кроме того, как мы можем представить его как список в Лиспе?

Ответы [ 2 ]

0 голосов
/ 06 сентября 2018

Просто перечислите вершины с обоими идентификаторами узлов: 

((1 2) (1 3) (1 4) (1 5) (2 6) (2 7) (2 8) ... )

или используйте вектор: 

#((1 2) (1 3) (1 4) (1 5) (2 6) (2 7) (2 8) ... )

или используйте список узлов с их наследниками: 

((1 2 3 4 5) (2 6 7 8) (3 8) (4 9) ...)
0 голосов
/ 06 сентября 2018

Правильный способ представления DAG - это набор узлов (вершин): 

(defstruct node
  payload
  children)

Поскольку структура имеет только два слота, можно, конечно, использовать cons клеток вместо.

Представление списка дерева, которое вы даете полезная нагрузка сопоставляется с бездетным узлом и портит самую правую ветвь. Правильное представление 

(1 (2 (6) (7) (8)) (3) (4 (9 (12))) (5 (10) (11)))

Теперь DAG, разделяющий бездетный узел (8) между дочерними элементами. узлов (2 ...) и (3 ...) должны просто делиться ячейкой: 

(1 (2 (6) (7) #1=(8)) (3 #1#) (4 (9 (12))) (5 (10) (11)))

См. #n= и #n# для обозначения читателя. Конечно, вы не должны использовать их для создания DAG.

Вот как можно создать DAG: 

(defun make-node (&key payload children)
  (cons payload children))
(defparameter *my-dag*
  (let ((shared-mode (make-node :payload 8)))
    (make-node
     :payload 1
     :children
     (list (make-node :payload 2
                      :children (list (make-node :payload 6)
                                      (make-node :payload 7)
                                      shared-mode))
           (make-node :payload 3
                      :children (list shared-mode))
           (make-node :payload 4
                      :children (list (make-node :payload 9
                                                 :children (list (make-node :payload 12)))))
           (make-node :payload 5
                      :children (list (make-node :payload 10)
                                      (make-node :payload 11)))))))
(setq *print-circle* t)
*my-dag*
==> (1 (2 (6) (7) #1=(8)) (3 #1#) (4 (9 (12))) (5 (10) (11)))
...