Fix edge containment issue

soerendomroes commented 1 year ago

See https://github.com/kieler/elkjs/issues/177, https://github.com/kieler/elkjs/issues/204, and others.

soerendomroes commented 1 year ago

Further investigation revealed that this is only a problem in elkjs. In the Java tests that the edge will actually be contained in the desired node. Testing the same graph in elkjs does not update the containment. Since bendpoints positions are always relative to the contained node, which is wrong in elkjs, the edge routes look as described in the issues.

soerendomroes commented 1 year ago

elkjs branch with test https://github.com/kieler/elkjs/tree/sdo/test177 elk branch with test https://github.com/soerendomroes/elk/tree/sdo/elkjs177

soerendomroes commented 1 year ago

@skieffer when implementing this fix, did you use elkjs to test it or did you import a JSON graph in Java?

skieffer commented 1 year ago

Pretty sure I was testing in elkjs. (It was a long time ago, but I found an old workspace that shows some elkjs build steps.)

In any case, elkjs 0.8.1 is working perfectly in my application, and in that sense I am testing it all the time. I routinely generate JSON graphs in which hierarchy-crossing edges are defined in locations other than their true containing node. I pass these graphs to elkjs, and when it returns I use the container property that has been written into each edge to tell me how to interpret the route points. The diagrams look beautiful.

skieffer commented 1 year ago

Is the online demo page just not using the container property?

Here is an example graph that gets a very nice layout in my application, but has messed up edges in the online demo page.

skieffer commented 1 year ago

Okay, so, what to do about hierarchical edges in JSON graphs, for ELK and elkjs?

I've gone back and reviewed the issue, and I write up my thoughts. I'm happy to help with coding, updating docs, etc, in resolving this.

Definitions

For purposes of this discussion:

"h-edge": short for "hierarchical edge", i.e. one whose endpoints belong to different levels of the hierarchy
the "owner" of an edge: the node in the JSON graph where the user has chosen to define the edge
the "container" of an edge: the true, proper container of the edge, according to the docs, namely the lowest common ancestor (LCA) of the endpoints, or the parent node in the special case of a self-loop
an "ancestor" of a node: either the node itself, or a node that it lies inside of (recursively)

Background

It seems to be generally agreed that it is inconvenient to force users to figure out for themselves what is the true container for an h-edge, and to always define the edge only there, i.e. to always make owner == container.

As the docs say, at the very end, under "Edge Containment" (emphasis added):

Unless one uses one of the create methods to create edges, finding the node an edge should be contained in may be annoying (thus, don’t). The updateContainment(ElkEdge) method automatically computes the best containment and puts the edge there.

While computing the containment is a little intricate (hence the utility method)...

Indeed, as cases like kieler/elkjs#177 demonstrate, it is normal for users to want to define edges under owners that make more sense to them conceptually, or that work more naturally with their way of generating graphs.

For example, in response to the burden of having to move edge definitions to their true container, this comment says:

If I use insideSelfLoops.yo I need to detect all these edges, transfer them to parent node and keep some info about the transfer.

Problem is that I am using elkjs for interactive visualization and I need 1:1 mapping between displayed graph and original circuit. Every change like this is also breaking analysis functions which are searching and marking something in the graph.

So, some solution is needed, so that users can define JSON graphs in a way that makes sense, and that will also work with ELK/elkjs.

However, unlike users of ELK, who have a chance to call updateContainment() manually, users of elkjs have no such opportunity. Instead, they build their graph in the form of JSON, pass this to elkjs, and receive back the same graph in JSON format, only with layout information filled in. They must then interpret this information according to the rules of containment, which are currently given in the docs here.

ELK v0.7.x

In ELK v0.7.x, we had the following behavior:

if owner == container:
    layout completes, with correct coords
else:
    if owner is ancestor of edge's source endpoint:
        layout completes, but with incorrect coords
    else:
        layout crashes

ELK v0.8.x

In 0.8.1 we:

added a step where updateContainment() is called on each edge defined in the JSON graph, and
added a container property to each edge in the returned layout, so that the user could know how to interpret the coordinates of the edge.

This means that

owner can be anything
layout always completes, with correct coords, as long as you interpret those coords relative to the provided container property

Current problems

elk-live

elk-live has (I think) not been updated to use the container property. The transfer from elk graph to Sprotty seems to happen here.

I am not really familiar with Sprotty, but it seems that it will interpret edge route points relative to the node that owns the edge?

docs

The docs, specifically the pages on

have not been updated to say anything about the container property.

Possibilities

One way to move forward would be to keep the solution introduced in v0.8.1, and update both elk-live and the docs to reflect it.

However, since both ELK and elkjs are still at major version 0, I think it is also reasonable to reconsider whether the solution of v0.8.1 is the best one. As the person who offered that solution, I feel responsible to consider other possibilities.

I think there are various, competing desires, at least the following two:

D1: To have a consistent rule about edge coordinates, as currently given on the Coordinate System page.
D2: To make it easy for users to interpret and apply the results of a layout.

As I begin to look at what Sprotty expects, and what elk-live will have to do in order to support v0.8.1, I begin to wonder if the container property really serves desire D2.

I don't know what other graph drawing frameworks expect, but maybe the easiest thing for most users would be if the coordinates of an edge could be interpreted relative to the edge's owner, not its container (in the senses defined above).

`parentCoords` option

Maybe there could be a new option, called parentCoords. (I use parent instead of owner because the word "parent" is used on the Coordinate System page.)

For historical consistency, it would default to false.

When parentCoords=false (or undefined), and a user places an edge in a JSON graph anywhere other than in its true container, the layout immediately throws an error, with a helpful message along the lines of:

Edge {id} is defined in a node other than its proper container.
If you want to allow this, set `parentCoords=true`.

When parentCoords=true, then, as in v0.8.1, we automatically call updateContainment() on every edge, BUT, instead of the v0.8.1 solution of providing you with a container property, we adjust the edge's coordinates when writing the final output, so that they are relative to the parent/owner node, not the true container node.

`moveEdgesToContainers` option

This is an alternative possibility.

Again, the option defaults to false, in which case any edge defined elsewhere than its true container throws an exception, as above.

When true, edges are moved in the returned JSON so that they are now defined inside their true container node, regardless of where the user might have defined them in the input JSON. Coordinates then do not need to be adjusted at all.

Other ideas

While on the topic, I think it would be great to add a feedback window in elk-live, where the user could see things like

error messages
the JSON returned by elk

I would be happy to help develop this, as well as any of the options discussed above, updates to docs, etc.

soerendomroes commented 1 year ago

Thank you for the detailed answer. I am not quite sure whether we should prefer parentCoords or moveEdgesToContainers. If the coordinates are changed to based on the owner and not the container, this might be confusing. If the containment of the output graph changes this might again be confusing too. Currently, I would prefer the parentCoords option.

While on the topic, I think it would be great to add a feedback window in elk-live, where the user could see things like

error messages the JSON returned by elk

I would be happy to help develop this, as well as any of the options discussed above, updates to docs, etc.

Your help is appreciated. I think these will be good additions to elk-live. I will try to contact you next year when I find time to tackle this issue.

skieffer commented 1 year ago

If the coordinates are changed to based on the owner and not the container, this might be confusing. If the containment of the output graph changes this might again be confusing too.

I agree that any of these options could be confusing, but I think that if we carefully manage it so that it is always an "opt-in" situation, then, theoretically, the user has chosen the behavior they are seeing, and they are aware and ready to interpret it correctly.

Currently, I would prefer the parentCoords option.

I think I prefer this as well. Both options have the same net effect that edge coordinates can be interpreted relative to the edge's parent/owner node. But moveEdgesToContainers causes a disruption that is visible to the user, whereas under parentCoords the naive user really doesn't know that anything has changed, since they were never aware of the true, container-based coords, prior to their translation.

skieffer commented 3 months ago

In light of #1012, maybe the right thing is to have an edgeCoords option whose value is an enum, with CONTAINER, PARENT and ROOT as the possible values.

In other words, I imagine the entry in the reference might look like this:

Edge Coordinates

PROPERTY            VALUE
------------------------------------------------------------------

Identifier:         org.eclipse.elk.edgeCoords

Value Type:         org.eclipse.elk.core.options.EdgeCoords (Enum)

Possible Values:    CONTAINER
                    PARENT
                    ROOT

Default Value:      CONTAINER

What do you think?

soerendomroes commented 3 months ago

This might be a good idea. I think this might be better than having options that potentially move around an edge in the hierarchy or have a different coordinate.

eclipse / elk