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

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

введите здесь описание изображения

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

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

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

введите здесь описание изображения

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

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

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


graph directed-acyclic-graphs graph-theory lisp common-lisp
person Chris Abbott    schedule 06.09.2018    source источник

Ответы (2)


arrow_upward
6
arrow_downward

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

(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= и _ 9_ для обозначения читателя. Конечно, вы не должны использовать их для создания групп 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)))
person sds    schedule 06.09.2018
comment
Спасибо! Похоже, это именно то, что я искал. Действительно ли это назначает ссылку на один и тот же узел 8? Имеет ли значение, какое целое значение я использую для # n =? Или это просто справочное значение? - person Chris Abbott; 07.09.2018
comment
Вы не должны сами использовать нотацию #n=, вы должны построить свой граф, создавая узлы и заполняя их дочерними элементами и полезными нагрузками. - person sds; 07.09.2018
comment
Идеально. Спасибо - person Chris Abbott; 07.09.2018

arrow_upward
2
arrow_downward

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

((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) ...)
person Rainer Joswig    schedule 06.09.2018
comment
Используя эту нотацию, если граф содержит дубликаты, как я могу быть уверен, что (2 6 7 8) и (3 8) на самом деле указывают на один и тот же узел 8? - person Chris Abbott; 07.09.2018
comment
@ChristianAbbott: два способа: а) использовать сами узлы, б) использовать идентификаторы узлов - person Rainer Joswig; 07.09.2018