Radial layout only updates innermost radius

[rhpreston]

Radial layout only updates innermost radius

Expected behavior

Per the ELK documentation:

The radial layouter takes a tree and places the nodes in radial order around the root. The nodes of the same tree level are placed on the same radius.

The layout algorithm includes overlap removal (bold added):

The overlap removal intermediate processor can be started after the node placement. Due to the node sizes it is still not guaranteed that no overlaps occur, because the radius can be chosen too small. The processor starts with the innermost radius and widens it until no more overlaps on the radius occur. This is repeated for each radius.

My expectation is that the radius of all layers would be automatically adjusted to prevent overlaps, and that outer radii would always be larger than inner radii. For example, with only 1 layer, the radius expands as more nodes are added.

5 nodes:

10 nodes:

Actual behavior

Only the innermost radius is adjusted during overlap removal. This renders the layout unusable with large numbers of nodes and multiple layers.

5 nodes in first layer, 20 nodes in second layer:

15 nodes in first layer, 30 nodes in second layer:

Steps to reproduce

The following code generates elements that clearly show the issue when rendered with the radial algorithm:

var elements = { nodes: [{ data: { id: "root" } }], edges: [] }
for (i = 0; i < 15; i++) {
  elements.nodes.push({ data: { id: `/${i}` }})
  elements.edges.push({ data: { source: "root", target: `/${i}` }})
  for (j = 0; j < 2; j++) {
    elements.nodes.push({ data: { id: `/${i}/${j}` }})
    elements.edges.push({ data: { source: `/${i}`, target: `/${i}/${j}` }})
  }
}

Context

The examples above were created with a single HTML file using cytoscape-elk.

Ask

Are there settings I'm missing that could fix this? Is it a bug with elkjs? Could it be an issue with the Java kernel? Any help tracking down the source of this problem would be greatly appreciated :v:

[uruuru]

Thanks for the detailed analysis of the issue. My first guess would be that it's an issue in the actual Java implementation of the radial compaction part.

[rhpreston]

Could be, although the default compaction strategy is NONE [ref] so I would expect that there is no compaction done at all. Do you think it could be an issue with the overlap removal step?

[uruuru]

I somehow implied that you activated the compaction step, which obviously you didn't. Anyhow, yes it may well be a bug in the overlap removal step (or any other part of the layouter).

[liamlows]

@uruuru @rhpreston any update on a solution to this? We are facing the same issue when trying to render a large connected graph in a radial manner. We have one root node in the first layer, 3 nodes in the second layer, and then 150 in the third layer. Ideally, with that many we would see something like what you posted above (seen below)

[soerendomroes]

It looks fixed and should be available via elk(js) 0.8.X.

@liamlows Can you replicate your problem in elk-live?

[magnussentio]

Struggling with this same issue. Using react flow to generate a radial layout with Elkjs. All settings (except for radius) seem to only apply to the inner most radius, not the radius of other layers.

[soerendomroes]

@magnussentio Could you replicate the problem in elklive or elklive json (be careful to set the elk version to 0.8.x)?

As mentioned above, this issue should be fixed by https://github.com/eclipse/elk/pull/793.

[magnussentio]

Here is my replit that shows the error: replit link

Any help would be great!

[soerendomroes]

@magnussentio Anything other than a link to elklive does not help me to replicate the problem and takes time from actually getting anything done since I need to replicate the model myself.

I created a graph with a root node with five children that each again have five children and the result looks obviously wrong as seen here.

Is this the problem you are trying to show me?

[magnussentio]

Here is a link demonstrating the problem. Maybe I don't know how radial works but adjusting the node spacing only effects the inner radius, and does not update the overall radius. My impression is that if I adjust the node spacing, this node spacing would also apply to the nodes in the outer radius. By designating a node spacing that would apply to all nodes, then the overall radius should change. You can certainly increase the radius until the outer most nodes have sufficient spacing, but that's just a guessing game and not realistic or efficient.

Apologies on the not so useful example, I understand you are busy and I greatly appreciate your insight.

[magnussentio]

Just curious if there is a timeline on when this might get solved. Simply curious!

[magnussentio]

Hi just bumping this