Graph navigation problem

Question

I have a graph of components and relations between them. User start navigation with a root component. He click expand button on component to reveal new component that are related to current component.

The problem is when user decide to collapse a node. I have to choose a sub-tree to hide and at same time leave graph in consistent state so that there is no expanded node with missing relation to another node in graph.

Now in case of cyclic/loop between component i have difficult of choosing sub-tree. For simplicity i choose the order in which they were expanded. So if a A expand into B and C collapsing A will hide the nodes and edge that it has created. Now consider following scenario.

[-] mean expanded state and [+] mean not yet expanded. A is expanded to reveal B and C. And then B is expanded to reveal D. C is expanded which create a link between C and exiting node D and also create node E. Now user decide to collapse B. Since by order of expansion D is child of B it will collapse and hide D. This leave graph in inconsistent state as C has edge to D but D is not anymore there if i remove CD edge it will still be inconsistent. If i collapse C. And E is again a cyclic link e.g to A will produce the same problem.

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

So guys any idea how can i solve this problem. User need to navigate through graph and should be able to collapse but i am stuck with problem of cyclic nodes in which case any of node in loop if collapse will leave graph in inconsistent state.

Answer 1

I think closing B should close B only.

Since A is master A should not be closed and from D it also leads to A over C, so D also remains open.

One implementation might be, that each link should tell you mastering link which tells if can reach master waking in this direction (I suppose you store graph as doubly linked list). or you chek this rule each time you apply subgraph closing.

Answer 2

I think the answer for your question depends on what the graph is to be used for. Any subgraphp could potentially be collapsed, where you just replace that subgraph with a new node, with each edge connected to the subgraph re-connected to the new node instead. In this case the graph would never be inconsistent.

The real question is what you mean by "collapsed". What operation would be natural depends completely on what the graph is for.

Answer 3

If a child node knows how many parents are linked to it, you could let a child node only collapse itself when there's only one parent connected.

Extrapolated to your example

• Collapsing B would ask node D to collapse.
• Node D does not collapse because it has two parents
• B removes the link to D (leaving D with only one parent)
• If now node C asks D to collapse, it will collapse itself.

Answer 4

Funny, I've encountered the situation (and the problem of cyclic references) in an application domain totally unrelated.

The solution I have implemented is very simple, yet it took me some times to achieve it. There are 2 issues:

• you don't want to become inconsistent
• you don't want to loop indefinitely

I think it can be achieved easily here I think, because you relations are oriented so the second issue should not bother us:

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)

Where Display and Hide are graphics methods used for edges and nodes alike.