Repeated renderings of edges and O(n²) complexity when rendering multiple Bezier edges

[YinDongFang]

Environment info

• Cytoscape.js version : 3.30.4
• Browser/Node.js & version : Chrome 131.0.6778.140

Current (buggy) behaviour

• There are repeated renderings of edges, causing unnecessary re-renders and performance degradation.
• When rendering multiple Bezier edges, the calculation time increases exponentially as O(n²), causing slow rendering and poor performance when handling large graphs.

Desired behaviour

• Edges should not be repeatedly rendered unnecessarily.
• The rendering of Bezier edges should have optimized computation, avoiding the O(n²) complexity.

Minimum steps to reproduce

https://output.jsbin.com/puyafes

1. click "Add 100 edges"
2. open console panel, drag "cat" node, the lastRedrawTime is about 50ms
3. click "Add 100 edges" multi times, the lastRedrawTime will be more than 1000ms when edges count more than 500

Reason

1. For repeated rendering: The BRp.registerCalculationListeners has already recalculateRenderedStyle for all nodes and edges to update, but without update of bbCachePosKey. So in render function, recalculateRenderedStyle execute again with useCache = false.

2. For O(n^2) when rendering multiple Bezier edges: in render function, recalculateRenderedStyle execute for single node or edge, but in recalculateEdgeProjections, it will loop all parellel bezier edges without cache. When updating 100 edges, it will execute findBezierPoints 100*100 times.

For reviewers

Reviewers should ensure that the following tasks are carried out for incorporated issues:

• Ensure that the reporter has included a reproducible demo. They can easily fork this JSBin demo: http://jsbin.com/fiqugiq
• The issue has been associated with a corresponding milestone.
• The commits have been incorporated into the corresponding branches. Bug-fix patches go on
  • master,
  • unstable, and
  • the previous feature release branch (e.g. 1.1.x if the current release is 1.2).
• The issue has been labelled as a bug, if necessary.

[maxkfranz]

@YinDongFang would you repost your jsbin demo? The link isn't working for me.

[YinDongFang]

https://output.jsbin.com/sekirar

[maxkfranz]

Thanks, @YinDongFang. That's giving a 404. Is it public?

In the meanwhile, I'll note this: There are several things that can invalidate a bundled group of beziers. When one edge in the bundle is changed (e.g. style), the others may also need to be updated.

One example is when one of the edges in the bundle is moved out of the bundle by changing the edge type from bundled bezier to something else (like unbundled bezier). In this example, changing one edge changes all the other edges in the bundle, because the bundle size has changed -- and so it needs to be rebalanced.

At first glance, it looks like your PR takes into account the case where one or more of the source and target node move. Would your changes still allow for changes in style, like the example I gave, to invalidate the cached style data (e.g. points)?

[YinDongFang]

In my project, I only use Bezier curves, so I haven't tested other cases. I will modify the code. Also, your example helped me discover another bug, which I will fix as well. If there are any other scenarios or cases that need to be considered, please let me know. Thank you!

Minimum steps to reproduce

https://ivis-at-bilkent.github.io/cytoscape.js-fcose/demo/demo-constraint.html

1. open DevTools Console panel
2. input code

cy.add({data:{id:'e1', source:'n1', target:'n3'}});
cy.edges().style('curve-style', 'bezier');
cy.$('#e1').style('curve-style', 'unbundled-bezier');

3. drag node n1 or n3 and release

Current (buggy) behaviour

The other edge between n1 and n3 switch between a straight line and a curve

[YinDongFang]

New commit 2add561 fixed this bug. In function findEdgeControlPoints, put the bezier and unbundled curves into different pairInfo for processing, so that when calculating the bundle bezier index, the unbundled curves will not be considered.

[YinDongFang]

https://output.jsbin.com/sekirar

I don't know how to make JSBin link permanent, try this CodeSandbox https://4jm8zw.csb.app/

[maxkfranz]

cy.$('#e1').style('curve-style', 'unbundled-bezier');

This is expected behaviour. In your example, moving out one edge from the two-edge bundle should make the remaining edge straight. A bundle of odd size has one of the edges as straight to keep things balanced. It also makes it so that bezier edges work well out-of-the-box for multiple use cases, e.g. multigraphs (where edges naturally should be bundled) and simple graphs (where you expect the single edge to be straight).

[maxkfranz]

https://output.jsbin.com/sekirar

I don't know how to make JSBin link permanent, try this CodeSandbox https://4jm8zw.csb.app/

I'll take a look at the demo on CodeSandbox

[YinDongFang]

cy.$('#e1').style('curve-style', 'unbundled-bezier');

This is expected behaviour. In your example, moving out one edge from the two-edge bundle should make the remaining edge straight. A bundle of odd size has one of the edges as straight to keep things balanced. It also makes it so that bezier edges work well out-of-the-box for multiple use cases, e.g. multigraphs (where edges naturally should be bundled) and simple graphs (where you expect the single edge to be straight).

2025-01-09.194231.mp4

The buggy behaviour is the curve is flickering when drag node

[maxkfranz]

@YinDongFang, I don't see anything new in your Code Sandbox demo. It just shows the base images demo without any changes.

[YinDongFang]

there is a button "Add 100 edges" at left top.

1. click "Add 100 edges"
2. open console panel, drag "cat" node, the lastRedrawTime is about 50ms
3. click "Add 100 edges" multi times, the lastRedrawTime will be more than 1000ms when edges count more than 500

@maxkfranz

This is CodeSandbox demo (500 edges):

codesanbox.mp4

This is my local environment (500 edges) (with my MR):

local.mp4

log number is cy.renderer().lastRedrawTime

[maxkfranz]

Let's handle one thing per issue. The parallel edge bug is specified in:

• Edge points not calculated properly for bundled beziers when an unbundled edge exists between the same source and target #3322

[maxkfranz]

I have a much simpler patch that addresses the issue. It can be merged in some time over the next week or so, in conjunction with other patches.

[YinDongFang]

@maxkfranz Hi, is there any new progress regarding this performance issue?

[maxkfranz]

@YinDongFang, try the latest code on the unstable branch

[maxkfranz]

Since the latest code doesn't exhibit this behaviour for me, I'm closing this for now. It can be reopened if it becomes an issue in future.