Edge Containment Issues for JSON Graphs

skieffer commented 3 years ago

Hi folks, longtime klayjs user here. (Hey, @uruuru!) Thanks again for this awesome layout library!

After many years I am (grudgingly) trying to move from klayjs to elkjs/elk. : )

In my application I use a lot of hierarchy edges, and I ran into what seems to me to be a bug. I also want to raise a related usability issue. This pull request is my idea for how to solve both.

The pull request is only 2 lines long! These notes are a lot longer, but I wanted to be thorough on my thought process!

Abstract

Issue:

When constructing a graph from JSON, we don't call ElkGraphUtil.updateContainment() on any ElkEdges.
- Java users could call it afterward, with some effort.
- elkjs users have no chance to call it.
This can lead to a crash. (See example below.)
If not a crash, coords still might not conform to the spec, since edges might not have the right container.
Usability issue: Even if the above is patched, casual users would still benefit from a container property written into edges after layout, to help them interpret edge route points.

Proposed solution:

Modify JsonImporter to:

Call updateContainment() on each edge as it builds the graph.
During transferLayout, write a container property into each edge, giving the id of the node that was chosen as container.

Again, see the pull request.

Minimal Example for Crash

graph = {
    id: "root",
    layoutOptions: {
        'org.eclipse.elk.algorithm': 'org.eclipse.elk.layered',
        'org.eclipse.elk.hierarchyHandling': 'INCLUDE_CHILDREN',
    },
    children: [
        {
            id: "p", width: 10, height: 10
        },
        {
            id: "q", width: 40, height: 40,
            children: [
                { id: "r", width: 10, height: 10 }
            ],
            edges: [
                { id: "e", source: "p", target: "r" }
            ]
        }
    ]
}

Nodes p and q are siblings. Node q has child node r. The hierarchy edge from p to r is recorded under node q.

Why it crashes

In the existing code, if this graph is built from JSON, the edge from p to r will think that q is its container.

Therefore q will be noted as the origin in ElkGraphImporter.findCoordinateSystemOrigin(). But later, in ElkGraphLayoutTransferrer.calculateHierarchicalOffset(), currentGraph will be initialized as p, and we will then try to work our way through the ancestors of p in search of the origin q, and of course we can never find it, since q and p are siblings.

Finally there is a crash after we reach the root, and then representingNode is null, and yet we try to call its getGraph() method.

The problem is thus that we are trying to use q as the coordinate system for the hierarchy edge, when in fact we want to be using the lowest common ancestor (LCA) of its endpoints p and r, which is p itself.

Further Thoughts

The proposed solution still won't prevent the crash for users who built the graph directly, i.e. not from JSON.

However, you do advise use of updateContainment() here, in the section on Edge Containment. So maybe here the onus is on the user...? Arguably?

If you wanted to prevent the issue even in this case, you could revise the implementation of the ElkGraphImporter.findCoordinateSystemOrigin() method, changing the line

ElkNode origin = elkedge.getContainingNode();

to

ElkNode origin = ElkGraphUtil.findLowestCommonAncestor(source, target);

(And then you could delete the two assertions that follow.)

Please don't add restrictions on JSON format!

Of course one possible response would be to place new restrictions on where users were allowed to record hierarchy edges in the input graph, but I think this would be a bad solution, and I really hope you don't choose it! I think it would be bad to artificially limit users' freedom on this point, when it doesn't take much to make it just work.

There is no widely agreed upon "proper place" where hierarchy edges belong. They aren't really "owned" by any node. For different users, it can make sense to record them in different places when building a graph, e.g. by a recursive procedure.
There was no such restriction in klayjs. The example graph above works there.
The spec does not put any restrictions on where you define hierarchy edges. Again, I think this is a good thing! Please keep it this way!

On the need for a `container` property in the returned layout

For all the reasons discussed above, it is great if the user doesn't have to think about edge containment, lowest common ancestors, etc. ELK is good at that. Let ELK worry about it.

But if users are to remain "blissfully ignorant" of LCAs, then they need help interpreting the results of the layout. Therefore, in each edge element of the returned JSON, I want to see a container property so I know which node's coordinate system to use when I draw the edge.

Final Notes

I have tested my solution in elkjs, but I have not been able to run the unit tests of elk itself. I followed the steps given here but was stopped by:

[ERROR] Internal error: java.lang.RuntimeException: Could not resolve target platform specification artifact org.eclipse.elk:org.eclipse.elk.targetplatform:target:0.8.0-SNAPSHOT -> [Help 1]

uruuru commented 3 years ago

Hey Steve, thanks for the contribution and the - as always ;) - detailed description!

While I can certainly remember discussing it, I cannot fully remember the reason why we decided not to call updateContainment() automatically. Maybe because you'd need something along the lines of the container you propose to properly figure out coordinates.

Anyway, since the containment of the edges regularly causes confusion, I support your suggestion.

In order not to forget:

[ ] adjust documentation.

skieffer commented 3 years ago

Great! Well, I guess this is how bumbling users like myself can sometimes be helpful, by at least raising usability questions.

Re "as always detailed" -- LOL. Yes, being long-winded about design questions is one of my favorite hobbies! : )

kennethlombardi commented 1 year ago

As of 0.8.2 a node will have a container field which is the id of the container of the edge as determined by ELK. You then need to use that id to search the graph for the container id and use that as the parent transform. In my case I had to recurse graph children. A DFS worked fine.

eclipse / elk