Проблема с графиком навигации

Question

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

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

Теперь в случае циклического цикла между компонентами мне сложно выбрать поддерево. Для простоты я выбираю порядок, в котором они были расширены. Таким образом, если A расширяется до B, а C, свернувшись, A скрывает созданные им узлы и ребра. Теперь рассмотрим следующий сценарий.

[-] означает расширенное состояние, а [+] означает еще не расширенное. A расширяется, чтобы показать B и C. А затем B расширяется, чтобы показать D. C расширяется, что создает связь между C и выходящим узлом D, а также создает узел E. Теперь пользователь решает свернуть B. Поскольку по порядку расширения D является потомком B, он свернется и скроет D. Это оставит граф в несогласованном состоянии, так как C имеет ребро к D, но D больше не будет, если я удалю край CD, он все равно будет несовместимым. Если я сверну C. И E снова является циклической связью, например, с A, возникнет та же проблема.

    /-----B[-]-----\   
A[-]                D[+]
    \-----C[-]-----/
              \
               E[+]

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

Answer 1

Если дочерний узел знает, сколько с ним связано родителей, вы можете разрешить дочернему узлу сворачиваться только тогда, когда подключен только один родитель. Экстраполировано к вашему примеру

• При сворачивании B узел D будет разрушен.
• Узел D не разрушается, потому что у него есть два родителя
• B удаляет ссылку на D (оставляя D только с одним родителем)
• Если теперь узел C просит D свернуть, он свернется сам.

Answer 2

Забавно, я столкнулся с ситуацией (и проблемой циклических ссылок) в области приложения, совершенно не связанной.

Решение, которое я реализовал, очень просто, но мне потребовалось несколько раз, чтобы достичь его. Есть 2 вопроса:

• ты не хочешь быть непоследовательным
• Вы не хотите зацикливаться бесконечно

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

def Expand(node):
  for c in node.childs:
    c.parents.insert(node)
    Display(node, c)
    if len(c.parents) == 1: Display(c)

def Collapse(node):
  for c in node.childs:
    del node in c.parents
    Hide(node, c)
    if len(c.parents) == 0: Collapse(c)

  Hide(node)

Где Display и Hide - графические методы, используемые как для ребер, так и для узлов.

Answer 3

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

Реальный вопрос в том, что вы подразумеваете под "рухнул". Какая операция будет естественной, полностью зависит от того, для чего предназначен график.

Answer 4

Я думаю, что закрытие B должно закрывать только B.

Поскольку A является ведущим, A не следует закрывать, и от D оно также ведет к A над C, поэтому D также остается открытым.

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