图形导航问题

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[+]

大家有什么想法，如何解决这个问题。用户需要通过图形导航，并应该能够折叠，但我被循环节点的问题所困扰，在这种情况下，如果折叠循环中的任何节点，将使图形处于不一致状态。

- particle

---

@Matthieu M. 抱歉，我今天遇到了一些困难，我的反应有些过激，虽然我真的很难理解这个问题。 - Gabriel Ščerbák

@affan请接受我的道歉，我不想无礼。 - Gabriel Ščerbák

Answer 1

如果一个子节点知道有多少个父节点与其相连，那么你可以让一个子节点只在只有一个父节点连接时才折叠自己。

推广到你的例子

• 折叠B将要求节点D折叠。
• 节点D不会折叠，因为它有两个父节点
• B删除与D的链接（使D只剩下一个父节点）
• 如果现在节点C要求D折叠，它将折叠自己。

- Lieven Keersmaekers

Answer 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是用于边缘和节点的图形方法。

- Matthieu M.

Answer 3

我认为关闭B应该只关闭B。

由于A是主控，所以不应该关闭A，并且从D到A经过C，因此D也保持开放状态。

一种实现方法可能是，每个链接都应该告诉你主控链接，这样可以确定是否可以在这个方向上到达主控（我假设您将图形存储为双向链表）。或者每次应用子图关闭时都检查此规则。

- Luka Rahne

Answer 4

我认为你的问题的答案取决于图形的用途。任何子图都可能被折叠，只需将该子图替换为一个新节点，并将每个连接到子图的边重新连接到新节点即可。在这种情况下，图表永远不会不一致。

真正的问题在于你所谓的“折叠”是什么意思。什么操作自然取决于图形的用途。

- Jørgen Fogh