Possible layout bug in edge originating from parent and targeting child node

[jbeard4]

I am migrating from klayjs to elkjs@0.3.0 and noticed a possible regression laying out an edge that originates from a parent node and targets a child node. Please consider the following reduced example.

Expected layout:

Actual layout:

The expected layout was derived from klay@0.4.1.

Here is the kgraph before running layout:

 {
    "id": "$generated-scxml-0",
    "labels": [
        {
            "text": ""
        }
    ],
    "edges": [
        {
            "id": "A:transition:0",
            "source": "A",
            "target": "a1",
            "labels": [
                {
                    "text": "e",
                    "width": 1.765625,
                    "height": 4.53125
                }
            ],
        },
        {
            "id": "$generated_A_initial_0:transition:0",
            "source": "$generated_A_initial_0",
            "target": "a1",
            "labels": []
        },
        {
            "id": "$generated_$generated-scxml-0_initial_0:transition:0",
            "source": "$generated_$generated-scxml-0_initial_0",
            "target": "A",
            "labels": []
        }
    ],
    "properties": {
        "borderSpacing": 6
    },
    "children": [
        {
            "id": "A",
            "labels": [
                {
                    "text": "A"
                }
            ],
            "edges": [],
            "properties": {
                "borderSpacing": 6
            },
            "children": [
                {
                    "id": "a1",
                    "labels": [
                        {
                            "text": "a1"
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "x": 0,
                    "y": 0,
                    "width": 8.765625,
                    "height": 9.53125
                },
                {
                    "id": "a2",
                    "labels": [
                        {
                            "text": "a2"
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "x": 0,
                    "y": 0,
                    "width": 8.765625,
                    "height": 9.53125
                },
                {
                    "id": "$generated_A_initial_0",
                    "labels": [
                        {
                            "text": "◉ $generated_A_initial_0"
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "x": 0,
                    "y": 0,
                    "width": 4,
                    "height": 4
                }
            ],
            "x": 0,
            "y": 0,
            "width": 7.875,
            "height": 9.53125
        },
        {
            "id": "$generated_$generated-scxml-0_initial_0",
            "labels": [
                {
                    "text": "◉ $generated_$generated-scxml-0_initial_0"
                }
            ],
            "edges": [],
            "properties": {
                "borderSpacing": 6
            },
            "x": 0,
            "y": 0,
            "width": 4,
            "height": 4
        }
    ],
    "width": 5,
    "height": 5
}

Here is the kgraph after running layout for elk@0.3.0:

{
    "id": "$generated-scxml-0",
    "labels": [
        {
            "text": "",
            "x": 0,
            "y": 0,
            "width": 0,
            "height": 0
        }
    ],
    "edges": [
        {
            "id": "A:transition:0",
            "source": "A",
            "target": "a1",
            "labels": [
                {
                    "text": "e",
                    "width": 1.765625,
                    "height": 4.53125,
                    "x": 0,
                    "y": 0
                }
            ],
            "sections": [
                {
                    "id": "A:transition:0_s0",
                    "startPoint": {
                        "x": 0,
                        "y": 0
                    },
                    "endPoint": {
                        "x": 0,
                        "y": 0
                    }
                }
            ]
        },
        {
            "id": "$generated_A_initial_0:transition:0",
            "source": "$generated_A_initial_0",
            "target": "a1",
            "labels": [],
            "sections": [
                {
                    "id": "$generated_A_initial_0:transition:0_s0",
                    "startPoint": {
                        "x": 16,
                        "y": 32.296875
                    },
                    "endPoint": {
                        "x": 36,
                        "y": 32.296875
                    }
                }
            ]
        },
        {
            "id": "$generated_$generated-scxml-0_initial_0:transition:0",
            "source": "$generated_$generated-scxml-0_initial_0",
            "target": "A",
            "labels": [],
            "sections": [
                {
                    "id": "$generated_$generated-scxml-0_initial_0:transition:0_s0",
                    "startPoint": {
                        "x": 16,
                        "y": 36.53125
                    },
                    "endPoint": {
                        "x": 36,
                        "y": 36.53125
                    }
                }
            ]
        }
    ],
    "properties": {
        "borderSpacing": 6
    },
    "children": [
        {
            "id": "A",
            "labels": [
                {
                    "text": "A",
                    "x": 0,
                    "y": 0,
                    "width": 0,
                    "height": 0
                }
            ],
            "edges": [],
            "properties": {
                "borderSpacing": 6
            },
            "children": [
                {
                    "id": "a1",
                    "labels": [
                        {
                            "text": "a1",
                            "x": 0,
                            "y": 0,
                            "width": 0,
                            "height": 0
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "x": 36,
                    "y": 27.53125,
                    "width": 8.765625,
                    "height": 9.53125,
                    "$H": 281
                },
                {
                    "id": "a2",
                    "labels": [
                        {
                            "text": "a2",
                            "x": 0,
                            "y": 0,
                            "width": 0,
                            "height": 0
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "x": 12,
                    "y": 12,
                    "width": 8.765625,
                    "height": 9.53125,
                    "$H": 284
                },
                {
                    "id": "$generated_A_initial_0",
                    "labels": [
                        {
                            "text": "◉ $generated_A_initial_0",
                            "x": 0,
                            "y": 0,
                            "width": 0,
                            "height": 0
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "x": 12,
                    "y": 30.296875,
                    "width": 4,
                    "height": 4,
                    "$H": 287
                }
            ],
            "x": 36,
            "y": 12,
            "width": 56.765625,
            "height": 49.0625,
            "$H": 278
        },
        {
            "id": "$generated_$generated-scxml-0_initial_0",
            "labels": [
                {
                    "text": "◉ $generated_$generated-scxml-0_initial_0",
                    "x": 0,
                    "y": 0,
                    "width": 0,
                    "height": 0
                }
            ],
            "edges": [],
            "properties": {
                "borderSpacing": 6
            },
            "x": 12,
            "y": 34.53125,
            "width": 4,
            "height": 4,
            "$H": 290
        }
    ],
    "width": 104.765625,
    "height": 73.0625,
    "$H": 12,
    "x": 0,
    "y": 0
}

You can see that edge A:transition:0_s0 has startPoint 0,0, and endPoint 0,0, which is unexpected.

                    "id": "A:transition:0_s0",
                    "startPoint": {
                        "x": 0,
                        "y": 0
                    },
                    "endPoint": {
                        "x": 0,
                        "y": 0
                    }
                }

I would greatly appreciate your help with this. Thank you.

[uruuru]

Please try to set the layout option hierarchyHandling to INCLUDE_CHILDREN.

It is necessary to lay out hierarchical edges. In klayjs this was the default behavior; in elkjs the default value is SEPARATE_CHILDREN (to be consistent with the java version of elk).

[jbeard4]

Thank you, I will try this.

[jbeard4]

I tried setting hierarchyHandling to INCLUDE_CHILDREN using the defaultLayoutOptions option of the ELK constructor. This resolved the issue of parents targeting children, but created an issue of children targeting parents. Please consider the following reduced example.

Expected behavior (generated with klay):

With hierarchyHandling unset (default behavior), I get the following graph, which matches the expected output:

With hierarchyHandling set to INCLUDE_CHILDREN, I get the following graph:

The edge from A1 to A is misaligned.

Here is the kgraph before layout:

{
    "id": "$generated-scxml-0",
    "labels": [
        {
            "text": ""
        }
    ],
    "edges": [
        {
            "id": "a1:transition:0",
            "source": "a1",
            "target": "A",
            "labels": [
                {
                    "text": "e",
                    "width": 1.765625,
                    "height": 4.53125
                }
            ],
            "targetPort": "A_exit:1",
            "$type": "hyperlink"
        },
        {
            "id": "$generated_A_initial_0:transition:0",
            "source": "$generated_A_initial_0",
            "target": "a1",
            "labels": []
        },
        {
            "id": "$generated_$generated-scxml-0_initial_0:transition:0",
            "source": "$generated_$generated-scxml-0_initial_0",
            "target": "A",
            "labels": []
        }
    ],
    "properties": {
        "borderSpacing": 6
    },
    "$type": "scxml",
    "children": [
        {
            "id": "A",
            "labels": [
                {
                    "text": "A"
                }
            ],
            "edges": [
                {
                    "id": "A_exit:1_A_enter:0",
                    "source": "A",
                    "target": "A",
                    "sourcePort": "A_exit:1",
                    "targetPort": "A_enter:0",
                    "labels": [],
                    "$hyperlink": "a1:transition:0"
                }
            ],
            "properties": {
                "borderSpacing": 6
            },
            "$type": "state",
            "children": [
                {
                    "id": "a1",
                    "labels": [
                        {
                            "text": "a1"
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "$type": "state",
                    "x": 0,
                    "y": 0,
                    "width": 8.765625,
                    "height": 9.53125
                },
                {
                    "id": "a2",
                    "labels": [
                        {
                            "text": "a2"
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "$type": "state",
                    "x": 0,
                    "y": 0,
                    "width": 8.765625,
                    "height": 9.53125
                },
                {
                    "id": "$generated_A_initial_0",
                    "labels": [
                        {
                            "text": "◉ $generated_A_initial_0"
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "$type": "initial",
                    "x": 0,
                    "y": 0,
                    "width": 4,
                    "height": 4
                }
            ],
            "ports": [
                {
                    "id": "A_enter:0"
                },
                {
                    "id": "A_exit:1"
                }
            ],
            "x": 0,
            "y": 0,
            "width": 7.875,
            "height": 9.53125
        },
        {
            "id": "$generated_$generated-scxml-0_initial_0",
            "labels": [
                {
                    "text": "◉ $generated_$generated-scxml-0_initial_0"
                }
            ],
            "edges": [],
            "properties": {
                "borderSpacing": 6
            },
            "$type": "initial",
            "x": 0,
            "y": 0,
            "width": 4,
            "height": 4
        }
    ],
    "width": 5,
    "height": 5
}

Here is the kgraph after layout with hierarchyHandling set to INCLUDE_CHILDREN:

{
    "id": "$generated-scxml-0",
    "labels": [
        {
            "text": "",
            "x": 0,
            "y": 0,
            "width": 0,
            "height": 0
        }
    ],
    "edges": [
        {
            "id": "a1:transition:0",
            "source": "a1",
            "target": "A",
            "labels": [
                {
                    "text": "e",
                    "width": 1.765625,
                    "height": 4.53125,
                    "x": 105.53125,
                    "y": 58.53125
                }
            ],
            "targetPort": "A_exit:1",
            "$type": "hyperlink",
            "sections": [
                {
                    "id": "a1:transition:0_s0",
                    "startPoint": {
                        "x": 85.53125,
                        "y": 55.53125
                    },
                    "endPoint": {
                        "x": 119.296875,
                        "y": 55.53125
                    }
                }
            ]
        },
        {
            "id": "$generated_A_initial_0:transition:0",
            "source": "$generated_A_initial_0",
            "target": "a1",
            "labels": [],
            "sections": [
                {
                    "id": "$generated_A_initial_0:transition:0_s0",
                    "startPoint": {
                        "x": 20.765625,
                        "y": 43.53125
                    },
                    "endPoint": {
                        "x": 40.765625,
                        "y": 43.53125
                    }
                }
            ]
        },
        {
            "id": "$generated_$generated-scxml-0_initial_0:transition:0",
            "source": "$generated_$generated-scxml-0_initial_0",
            "target": "A",
            "labels": [],
            "sections": [
                {
                    "id": "$generated_$generated-scxml-0_initial_0:transition:0_s0",
                    "startPoint": {
                        "x": 16,
                        "y": 24
                    },
                    "endPoint": {
                        "x": 36,
                        "y": 24
                    }
                }
            ]
        }
    ],
    "properties": {
        "borderSpacing": 6
    },
    "$type": "scxml",
    "children": [
        {
            "id": "A",
            "labels": [
                {
                    "text": "A",
                    "x": 0,
                    "y": 0,
                    "width": 0,
                    "height": 0
                }
            ],
            "edges": [
                {
                    "id": "A_exit:1_A_enter:0",
                    "source": "A",
                    "target": "A",
                    "sourcePort": "A_exit:1",
                    "targetPort": "A_enter:0",
                    "labels": [],
                    "$hyperlink": "a1:transition:0",
                    "sections": [
                        {
                            "id": "A_exit:1_A_enter:0_s0",
                            "startPoint": {
                                "x": 119.296875,
                                "y": 55.53125
                            },
                            "endPoint": {
                                "x": 36,
                                "y": 34
                            },
                            "bendPoints": [
                                {
                                    "x": 129.296875,
                                    "y": 55.53125
                                },
                                {
                                    "x": 129.296875,
                                    "y": 86.0625
                                },
                                {
                                    "x": 26,
                                    "y": 86.0625
                                },
                                {
                                    "x": 26,
                                    "y": 34
                                }
                            ]
                        }
                    ]
                }
            ],
            "properties": {
                "borderSpacing": 6
            },
            "$type": "state",
            "children": [
                {
                    "id": "a1",
                    "labels": [
                        {
                            "text": "a1",
                            "x": 0,
                            "y": 0,
                            "width": 0,
                            "height": 0
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "$type": "state",
                    "x": 40.765625,
                    "y": 38.765625,
                    "width": 8.765625,
                    "height": 9.53125,
                    "$H": 284
                },
                {
                    "id": "a2",
                    "labels": [
                        {
                            "text": "a2",
                            "x": 0,
                            "y": 0,
                            "width": 0,
                            "height": 0
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "$type": "state",
                    "x": 12,
                    "y": 12,
                    "width": 8.765625,
                    "height": 9.53125,
                    "$H": 287
                },
                {
                    "id": "$generated_A_initial_0",
                    "labels": [
                        {
                            "text": "◉ $generated_A_initial_0",
                            "x": 0,
                            "y": 0,
                            "width": 0,
                            "height": 0
                        }
                    ],
                    "edges": [],
                    "properties": {
                        "borderSpacing": 6
                    },
                    "$type": "initial",
                    "x": 16.765625,
                    "y": 41.53125,
                    "width": 4,
                    "height": 4,
                    "$H": 290
                }
            ],
            "ports": [
                {
                    "id": "A_enter:0",
                    "x": 0,
                    "y": 22,
                    "width": 0,
                    "height": 0
                },
                {
                    "id": "A_exit:1",
                    "x": 83.296875,
                    "y": 43.53125,
                    "width": 0,
                    "height": 0
                }
            ],
            "x": 36,
            "y": 12,
            "width": 83.296875,
            "height": 64.0625,
            "$H": 278
        },
        {
            "id": "$generated_$generated-scxml-0_initial_0",
            "labels": [
                {
                    "text": "◉ $generated_$generated-scxml-0_initial_0",
                    "x": 0,
                    "y": 0,
                    "width": 0,
                    "height": 0
                }
            ],
            "edges": [],
            "properties": {
                "borderSpacing": 6
            },
            "$type": "initial",
            "x": 12,
            "y": 22,
            "width": 4,
            "height": 4,
            "$H": 293
        }
    ],
    "width": 141.296875,
    "height": 98.0625,
    "$H": 12,
    "x": 0,
    "y": 0
}

Does hierarchyHandling need to be set at an individual node level, rather than globally? If so, what are the conditions for which hierarchyHandling it must be set?

Thank you very much for your help with this.

[uruuru]

If you set hierarchyHandling for the top-level node, the behavior is propagated to all children automatically. Setting it for the top-level node should thus yield the same behavior as specifying it as part of the defaultLayoutOptions.

The results you get do not immediately make sense to me. I won't be able to look at it more closely before next weekend though. Maybe @le-cds finds time to check it in elk itself in the meantime.

[jbeard4]

Sounds good. Thank you @uruuru

[jbeard4]

@le-cds Please let me know if I can provide additional information to help reproduce this

[le-cds]

Sorry, I totally neglected this ticket. I'll be sure to take a look at it over the next few days.

[jbeard4]

No problem. Thank you for your help with this.

[le-cds]

Right, I've spent a few minutes looking into this and have a few comments.

Hierarchy handling should only be necessary for long hierarchical edges. What you seem to have here, however, are short hierarchical edges: edges that connect a node with one of its direct children. ELK Layered should support those right out of the box. There are a few catches, however.

First, short hierarchical edges are a bit particular when it comes to ports. They usually need to be connected to an explicit port of their hierarchical node. When I didn't do so while reproducing your example, this is when I got your initial result.

Second, you need to be careful as to where you define your edges. The exact rules are at the bottom of this page (where it says Edge Containment). In short, if you have an edge that connects two children of A, that edge needs to be defined in A, not in the surrounding graph. Similarly, if you have an edge that connects A to one of its children, that too needs to be defined in A. That may explain the strange offsets you're experiencing.

As I already mentioned in #48, this may be different for graphs defined using JSON, but @uruuru will have to shed some light on that question.

However, even with all of these problems solved, there seems to be a layout bug hidden in what remains. This is what I got when I tried to reproduce your graph:

I created eclipse/elk#369 to track that.

[jbeard4]

Thank you for looking into this.

[uruuru]

The idea is that the json format behaves the same wrt edge containments.

[uruuru]

@le-cds have you had a look at this lately? Maybe any of your latest changes fixes this?

[le-cds]

According to my last comment here, this was related to eclipse/elk#369, which has since been fixed. Is there anything else I need to look at?

[uruuru]

I reduced the original example a bit and (hopefully) moved the edges to correct containment: see here.

The result is still odd in that the hierarchical edge A:transition:0 breaks the layout. Removing the edge gives a proper layout.

Make sure to select 0.6.1 when trying it.

[jbeard4]

Thank you for continuing to investigate this.

[le-cds]

I reduced the original example a bit and (hopefully) moved the edges to correct containment

As I mentioned in my previous comment, proper edge containment is just one half of the solution; using ports is the other. Having A:transition:0 connect to A through an explicit port should solve the issue.

[uruuru]

Shouldn't the ports (dummies) be added automatically?

You wrote:

They usually need to be connected to an explicit port of their hierarchical node.

Is that something we documented?

[le-cds]

Shouldn't the ports (dummies) be added automatically?

With INCLUDE_CHILDREN, they in fact are. Without that option, they are not, but should be. There's a ticket about that, namely eclipse/elk#60.

I took your corrected JSON file again and tried to reproduce the issue with the following ELKT code (I'm using ELKT because I find it easier to read):

algorithm: layered
hierarchyHandling: INCLUDE_CHILDREN

node A {
    node a1
    node a2
    edge a2 -> a1
    edge A -> a1
}
node B
edge B -> A

ELK Layered produces this result on my machine:

I don't see where the problem should come from. 😕