Feature Request: Standalone Edge Routing

[philip-alldredge]

Standalone edge routing was discussed on the forum at https://www.eclipse.org/forums/index.php/t/1086846/ as a possibility sometime in the future. It would be a great use for users who would like to manually position nodes and ports but have ELK layout the edges.
Is this something that is still being considered?

[le-cds]

It's still a feature we would very much like to have, but don't have any plans as to when someone might get around to implementing one.

[Nic30]

@le-cds the thesis label means that you have a student for this task or that you created the topic for student thesis?

[le-cds]

@Nic30 The latter. We're still looking for someone to work on this.

[khoshrou]

any news on this side?

[uruuru]

Unfortunately, no.

[Nic30]

It seems to me that it is only required to replace some parts of logic which generates a positions of nodes in columns. I did some proof of concepts but then I realized that I do not have time to write rest of app which would allow to drag components etc so I ended up using only upstream version of ELK.

[uruuru]

As you mention, the routing included in elk.layered makes heavy use of the fact that the nodes are partitioned into layers (including that edges spanning multiple layers are split by dummy nodes).

For a general standalone edge routing it is not always possible to properly create such a distribution for several reasons. An obvious one being that nodes may be "interweaved" in a way that prevents a partitioning.

Whenever it is allowed to slightly alter the positions of nodes (and the positions already roughly resemble what elk would come up with) but keep the overall topology, there are already processors included that would derive a corresponding partitioning.

[khoshrou]

is there any orthogonal layouting algorithm or library for javascript that we can use? seperating the responsibility, using elkjs for auto layouting and other library for dynamic layouting when user changes the place of nodes?

[uruuru]

There's an orthogonal edge router in libavoid/adaptagrams (cpp library).

Several years ago the KIELER project included a bride that made the cpp library available in Java. I couldn't see it on their current update-site though. Maybe @le-cds can elaborate on at what point in time support was dropped and point you to the sources in case you are interested.

[khoshrou]

Oo God, CPP library, I was hoping there is an npm package.
Years ago I did a little bit of search for layouting and as I know its a complex subject. Some times I am thinking maybe an AStart algorithm could do the job (It will be slow for large diagrams).
What do you think about this?

[Nic30]

https://github.com/Nic30/hwtIde/blob/master/hwtIde/static/hls/connections/a_star.js
Long story short:
I tried it and it worked somehow, but it was definitely bad idea (as there is endless number of corner cases..) so I deprecated the idea and moved to ELK.

[khoshrou]

Wow, really nice. yeh its complex
that's why I hope we can find a bullet proof solution.
ELK works very good the only thing is missing is layouting only edges.
Another idea what do you think about using Tensor Flow for this i.e Machine Learning

[Nic30]

I have tried genetic alg. (pagmo2) and it worked somehow, but it was bellow the expectations in terms of performance and quality.

i.e Machine Learning

It seems to me that graph data of unbounded size and random features are exactly the nightmare for neural nets (however I am not ML expert).

[khoshrou]

Seems its a long story. better to stick to elk for now.
If you found any thing new please let us now

[Nic30]

I did not want to say that nothing better exists. Feel free to search for a while, my knowledge of this agenda is 1y old... If you find something please let me know.

[khoshrou]

there should be a reliable solution, maybe not open sourced yet. if i get time i am going to check
AStart and ML. I will let you know about the results.

[le-cds]

A quick update on the current state of affairs. We finally, finally have a student working on standalone edge routing. Having said that, the thesis has only just started, so if there's going to be anything that can be released, that'll be at least six months away.

Several years ago the KIELER project included a bride that made the cpp library available in Java. I couldn't see it on their current update-site though. Maybe @le-cds can elaborate on at what point in time support was dropped and point you to the sources in case you are interested.

Just for future reference, we removed this just recently, on February 19th, 2020. See this page (look for Kiml libavoid and adaptergrams). It includes a commit hash from this repository.

[Vadorequest]

@le-cds Any feedback on this? It's been 8 months since the last update (I hope that student made some progress 😉)

Also, I'm not familiar with the complexity inherent to graphs, and I don't understand how this issue (Standalone edge routing) relates to kieler/elkjs#100 or kieler/elkjs#122 😅

---

Edit: I think I understand it means having the nodes be placed manually (or, not controlled/semi-controlled by ELK) but having the edges controlled by ELK.

[le-cds]

@Vadorequest Yep, it does mean leaving the node positions untouched and only routing the edges through the space that remains.

Sadly, the student did not finish the thesis, so this topic is out in the open again. @uruuru did some work on a prototypical implementation a while ago. Perhaps he can add a few words as to the status of that project. :)

[uruuru]

I'd say the basics are there, however, quite some parts are still missing or are simply not stable enough. If anybody feels that he or she has the toolbox to push on with the topic and has spare time at hand, feel free to contact me.

[nimobeeren]

This issue seems to be duplicated by #912, which is closed since the addition of Libavoid in ELK 0.9.0.

This issue can probably be closed as well.