Cycli c подключенный граф против acycli c подключенный граф сценарий использования

Question

У меня есть граф с такой структурой и правилами:

Графическое изображение

1. Это направленный связанный циклический c граф (направление сверху вниз нижние узлы).
2. Любой родительский узел может иметь 0, 1 или 2 дочерних элемента.
3. Дочерний элемент может иметь 1 или 2 родителя (root узел n_id_1 не имеет родителей).
4. Есть левый ребенок и правый ребенок. Родитель может иметь правого ребенка и не иметь левого ребенка или наоборот (см. n_id_9 и n_id_2).
5. Если родитель (n_id_9) покинул ветвь (n_id_3 - n_id_8) и нет правой ветви, она всегда становится родительской дочерней для левой ветви (n_id_11).

На данный момент я вижу 2 решения для структуры данных:

Вариант 1. Сделать направленный связанный циклический c график, подобный этому (наиболее очевидный способ):

parent            children
   1                 2
   2                 3, 11
   3                 5, 6
   5                 9
   6                 4
   9                 10, 12
   4                 7
   12                8
   7                 8
   8                 11

Я думаю, что обратная сторона этого - трудно рендерить и поддерживать. График подключенного ациклического c, в котором каждый родитель может иметь 3 детей: левого, правого и третьего (не знаю, как это лучше назвать). Так, например, n_id_2 имеет левого ребенка n_id_3, нет правого ребенка и третьего ребенка n_id_11. Для пропавших детей мы должны указать null.

parent            children (left, right, third)
   1                 2, null, null 
   2                 3, null, 11
   3                 5, 6, 8
   5                 9, null, null
   6                 4, null, null
   9                 null, 10, 12
   4                 7, null, null
   12                null, null, null
   7                 null, null, null
   8                 null, null, null

Гораздо проще рендерить и просматривать данные, поскольку теперь у нас есть дерево без циклов. Недостатком этого я вижу - если по какой-то причине спецификации будут изменены - это может быть сложнее изменить. Я предпочитаю этот.

Итак, вопросы:

1. Есть ли другие решения?

2. Что вы думаете о моих предоставленных решениях?

Спасибо за обзор.

Answer 1

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

Лично я бы go предложил бы ваше второе решение, которое кажется более естественным для графа с такими свойствами, я бы описал его немного иначе: График может быть представлен в виде последовательности узлов , каждый узел может иметь левую и правую дочернюю ветвь и преемник (который это то, что вы назвали третий ). Обе дочерние ветви являются необязательными; нет преемника означает конец последовательности. Дочерняя ветвь снова представляет собой последовательность узлов того же типа.

Это дает вам простую рекурсивную структуру, о которой я легко нахожу (YMMV, конечно).

Как примечание: этот график не является циклическим c, только его ненаправленный аналог.