Maximum call stack size exceeded in $connectedComponentsDFS

[B3rn475]

I'm reporting here, even if I'm experiencing the problem with elkjs, as in https://github.com/eclipse/elk/issues/472 it was reported that this is the correct way to do it.

I'm encountering Maximum call stack size exceeded in function $connectedComponentsDFS, while running a layered layout.

The Java counterpart of this function is at https://github.com/eclipse/elk/blob/3630e23fa5abc253233296e2bdf5e18828e5dba7/plugins/org.eclipse.elk.alg.layered/src/org/eclipse/elk/alg/layered/p2layers/NetworkSimplexLayerer.java#L103-L133 and is, unfortunately, recursive.

[B3rn475]

Extra info: To reproduce it is enough to build a model with 100000 nodes connected in a line n0 => n1 => n2 => .... => n100000.

[uruuru]

Since this keeps re-occurring, it may be a good idea to replace the recursion by an iteration.

Further places:

• org.eclipse.elk.alg.layered.p2layers.CoffmanGrahamLayerer.dfs()
• org.eclipse.elk.alg.layered.p2layers.LongestPathLayerer.visit()
• org.eclipse.elk.alg.layered.p2layers.InteractiveLayerer.checkNode()
• org.eclipse.elk.alg.layered.components.ComponentsProcessor.dfs()
• NetworkSimplex.tightTreeDFS()

[B3rn475]

Thank you very much for these fixes.

Is there an idea of when these changes will get into a release?

[uruuru]

Note that they are not on master yet. Coffman graham is still missing as well.

There's no timeline for the next ELK release, however, I can assemble a dev release based on the current master for elkjs any time.

[B3rn475]

Just to fully understand.

The dev release you are suggesting would be for cherry picking the changes into elkjs and have a point release there?

[uruuru]

Yes.

[B3rn475]

That would be awesome

[B3rn475]

Friendly Ping.

Will you have time to assemble a dev release based on the current master for elkjs?

[uruuru]

@B3rn475, just published elkjs 0.7.3-dev which hopefully contains a fix.

[B3rn475]

Version 0.7.3-dev solved the problem with $connectedComponentsDFS, but it is triggering it again in $tightTreeDFS.

https://github.com/eclipse/elk/blob/3630e23fa5abc253233296e2bdf5e18828e5dba7/plugins/org.eclipse.elk.alg.common/src/org/eclipse/elk/alg/common/networksimplex/NetworkSimplex.java#L515-L537

Which is also recursive

[uruuru]

:/

Either my simple test didn't cover this or it's part of node placement? I.e. does changing nodePlacement.strategy resolve it?

[B3rn475]

I tried to change the strategy to any other value, e.g.:

layoutOptions: {
  // ...
  'elk.layered.nodePlacement.strategy': 'LINEAR_SEGMENTS',
}

But nothing changes. (let me know if I'm doing it wrong). I'm working on a model with 20K+ nodes and 25k+ edges.

I guess that, in general, all these recursive functions are there waiting to trigger a Maximum call stack size exceeded error, especially in elkjs, given the fact that there is no guarantee that the walk will not hit an edge case and manage one single node per stack frame.

[uruuru]

I guess that, in general, all these recursive functions are there waiting to trigger a Maximum call stack size exceeded error,

Yes. I tried to remove those that affected your graphs but obviously missed at least one.

[perenstrom]

Hello, any updates on this issue? I encountered it now with about 37k nodes, as well in ElkJS.

[soerendomroes]

Sadly there are no updates.

[daydayhappychao]

bump

[daydayhappychao]

Fixed by using the java version of elk. So the reason for the issue is that the elk-js has performance issues. Is it possible to implement elk in the browser using methods other than GWF?

[B3rn475]

@daydayhappychao the main problem is tail recursion. The Java version relies on tail recursion optimizations that do not exist when converted to JavaScript. The main option is to convert all of them into loops.