Enhancement: add virtual nodes and rank-by-rank edges after dagre has done layout

[jurgenvinju]

Thanks for making this plugin to cytoscape.js; it's really handy!

I'd like to exchange thoughts on the possiblity of adding a feature that would help make the graphs look even nicer, without stepping outside the scope of directly wrapping and reusing Dagre. I can help too if that's required/interesting.

This is how I read the current code:

1. the original graph nodes are positioned by the dagre layout algorithm and these positions are inherited by cytoscape nicely.
2. then the original edges are drawn between the original nodes

However, Dagre (like graphviz' dot) tries to untangle the edges between every rank by introducing new virtual (invisible) nodes on every rank level that is skipped, and breaking up edges that skip ranks up into segments: one new edge between every rank that is skipped.

This straightens up the edges between every rank (a lot), and also avoids unnecessary edge crossings. It really has a pacifying effect on the way the graph looks. It floats on the effect of a good rank assignment algorithm.

Another issue is that the edge-crossing minimization algorithms have the virtual nodes as an underlying assumption (edges are always between adjacent ranks). Without that assumption, the edge-crossing-minimizers make a mess of it. A node that is ideally positioned to avoid edge crossings with the virtual nodes, could easily be disastrous for edge-crossings without the virtual nodes.

Finally, the virtual nodes and the edges that go through them do have an effect on the horizontal positioning in the Dagre model, but since the edges aren't drawn through the virtual nodes by cytoscape.js, we get additional spacing in weird places, and no spacing where we need it for the edges that we are drawing. Fixing this would also have a positive effect on horizontal spacing.

A proposal would be to extract the new virtual nodes from Dagre and transfer them to the cytoscape model, and also extract the new edges and their bezier control points. And only then render the graph.

There might be better alternatives on how to implement this effect. Curious what you think!

[jurgenvinju]

CC @tvdstorm

[maxkfranz]

Details:

• Dagre already exposes mid points
• These points can be exposed to Cytoscape in something like scratch.dagre.points for each node
• The dev can then just use a style mapper to set the mid points for either segments or taxi -- whichever would be more appropriate

PRs welcome

[stale[bot]]

This issue has been automatically marked as stale, because it has not had activity within the past 14 days. It will be closed if no further activity occurs within the next 7 days. If a feature request is important to you, please consider making a pull request. Thank you for your contributions.

[jurgenvinju]

This is about more than midpoints for the bezier curves. I'll consider a PR. Thanks.

[maxkfranz]

The virtual nodes are a red herring. Only the points of the edges matter on the Cytoscape side.

[stale[bot]]

This issue has been automatically marked as stale, because it has not had activity within the past 14 days. It will be closed if no further activity occurs within the next 7 days. If a feature request is important to you, please consider making a pull request. Thank you for your contributions.

[jurgenvinju]

Thanks @maxkfranz