ELKJS exception when using partitioning

[petermoogk]

Hello, our product uses ELK to do layouts for our graphs. One of our clients reported an issue where the graph didn't render. We narrowed the problem down to an exception being thrown when ELK is doing a layout of some customer graph data. We use the ELK partitioning feature to indicate to ELK which column in the graph we would like nodes to be placed. When this feature is turned on the ELK exception occurs. However, if we turn it off(ie. "org.eclipse.elk.partitioning.activate": "false") there is no exception. We would prefer to keep partitioning turned on so I have opened this issue to resolve this exception issue. I have reduced the customer graph data to a very small example so that you can reproduce the issue easily. I have attached a zip file to this issue which contains two files package.json and test.mjs. To reproduce this issue download this zip file to a directory. In the directory where you downloaded this zip file run the following commands: 1) unzip the downloaded zip file 2) npm install 3) node test.mjs

Step 2 just installs elk 0.8.2 Step 3 creates the graph data and runs the ELK layout command.

Here is a summary of the nodes and edges Nodes = N1(partition 1), N2(partition 2), N3(partition 3) Edges= N1->N1, N2->N2, N1->N2, N2->N1, N2->N3

Note: the nodes and edges in this example are very simple, but they are derived from real customer data.

Here is a snippet of the exception that is being throw: exception Error: java.util.NoSuchElementException at utb.$y [as Wd] (C:\Users\PETERMoogk\projects\elkbug\node_modules\elkjs\lib\elk.bundled .js:6353:88251) at utb.ez [as _d] (C:\Users\PETERMoogk\projects\elkbug\node_modules\elkjs\lib\elk.bundled .js:6353:88512) at utb.Xy (C:\Users\PETERMoogk\projects\elkbug\node_modules\elkjs\lib\elk.bundled.js:2124 :38) at utb.gz (C:\Users\PETERMoogk\projects\elkbug\node_modules\elkjs\lib\elk.bundled.js:1253 :18) at new utb (C:\Users\PETERMoogk\projects\elkbug\node_modules\elkjs\lib\elk.bundled.js:126 4:19) at sCb (C:\Users\PETERMoogk\projects\elkbug\node_modules\elkjs\lib\elk.bundled.js:2189:34 ) at SJc (C:\Users\PETERMoogk\projects\elkbug\node_modules\elkjs\lib\elk.bundled.js:6151:53 6) at RJc (C:\Users\PETERMoogk\projects\elkbug\node_modules\elkjs\lib\elk.bundled.js:2063:21 ) at rLc.sLc [as Ce] (C:\Users\PETERMoogk\projects\elkbug\node_modules\elkjs\lib\elk.bundle d.js:6353:278625)

elkbug.zip

[soerendomroes]

Hi, the exception does not occur because of partition but because of the NETWORK_SIMPLEX node placement strategy, as seen in the example. Since this is not an elkjs issue, I will create an issue in ELK.

Since it was previously claimed in #179 that partition is the problem, let me clarify how partition works. It just makes sure that edges are reversed in such a way that edges go from a low partition to a higher one. Moreover, nodes are assigned to layers such that they are in the same partition if possible. You can find out whether partition is the problem by recreating the cycle breaking partition does with the MODEL_ORDER cycle breaking strategy, which makes sure that edges from the beginning of the node list to some node behind it go forward and the other ones backward, e.g. like this.

[soerendomroes]

If you need to solve the problem now, I suggest changing the node placement strategy back to BRANDES_KOEPF.

[petermoogk]

Hey Soren, thanks so much for the speedy response on this issue!. I will try out the changes that you suggested.

[petermoogk]

Hi Soren, thanks for the example that you created on the elklive site. I added a few extra nodes to this example. In this updated example you can see that N6 and N5 are not horizontally aligned.(ie. there is a kink in the edge that connects them) As well N1 is not horizontally aligned with N2 and N3. When we ran into these line kink problems in the past it was suggested that we use the NETWORK_SIMPLEX node placement strategy. Is there a way to get this line straightening behavior without using the NETWORK_SIMPLEX node placement strategy? I tried using nodePlacement.bk.edgeStraightening: IMPROVE_STRAIGHTNESS, but this didn't remove the line kinks. Thanks!

[soerendomroes]

You have not linked the changed model (the previous link worked by encoding the model in the url). But there is no easy way to replicate the NETWORK_SIMPLEX functionality without using network simplex. The fix might take a while since I am quite busy in September and October but maybe I will find time to fix the issued (if it is not that complicated) and make a service release.

[soerendomroes]

Does https://www.eclipse.org/elk/reference/options/org-eclipse-elk-layered-priority-straightness.html work for this example? Note that this is not a general solution but rather used to enhance specific drawings or for edges that you know should be straight.

[petermoogk]

Hey Soren, thanks for the info on priority straightness. I'll check that out.
Thanks for letting me know about your September/October schedule. Hopefully, you will have a fix for this in November. Once, this issue is resolved and NETWORK_SIMPLEX is working again would you recommend that we use cycleBreaking.strategy: MODEL_ORDER instead of using partitioning? What we were trying to achieve with the partitioning was to have ELK put nodes in a particular order horizontally from lower partitions to higher partitions. As well we wanted all nodes in a partition to be stacked one on top of each another vertically. ELK did this vertical stacking most of the time. However, there were cases where it would put two nodes at the same partition level side by side horizontally. If we go with cycleBreaking.strategy: MODEL_ORDER it sounds like this would give us the horizontal layout we want. However, is there anything additional that we would need to do to get the vertical stacked behavior that we are looking for? Thanks!