search

erikbrinkman / d3-dag

Layout algorithms for visualizing directed acyclic graphs
https://erikbrinkman.github.io/d3-dag/
MIT License
1.45k stars 87 forks source link

Specific key order appears to cause decrossOpt to hang #107

Closed g-sam closed 1 year ago

g-sam commented 1 year ago

Please see this pen: https://codepen.io/g-sam/pen/abqMqbg

There are two json objects, fast and slow, containing the same nodes in a different order. If you construct the layout on line 1871 with fast, everything renders fine. If you construct it with slow the browser will freeze. In our app the calculation does actually finish after 5-10 minutes although codepen appears to refresh before this happens.

The problem does not occur when using decrossTwoLayer.

erikbrinkman commented 1 year ago

This is really interesting, but I think out of scope. decrossOpt just uses an ILP solver on the backend. Due to the nature of the problem it is easier to verify a good solution than to find one, so if the optimizers heuristics aren't problem invariant (I'm not sure this is possible, although maybe) this can and will happen. The solution is always to use decrossTwoLayer for problems like this.

It does raise two potential types of solutions:

  1. decrossTwoLayer starts with an initial "good" ordering created by decrossDfs. This is still ultimately dependant on the order of nodes, because decrossDfs uses edges in order without some total ordering to edge or node iteration, but running decrossDfs before decrossOpt might help. I tried combining decrossTwoLayer before decrossOpt and it didn't help, so the issue must be related more to edge order than node order.
  2. This is a strange graph in that one layer is very difficult to optimize, but the rest are pretty easy. I imagine you don't really care about how that ugly layer looks, but want the number of crossings minimized on the rest of the graph (There's the one extra edge cross that this stuck in a local minima an so decrossTwoLayer will never remove it.). It potentially suggests a hybrid approach, where we first run decrossTwoLayer on the whole graph, then run a modified decrossAlmostOpt that is identical to decrossOpt but leaves complicated layers in order.
g-sam commented 1 year ago

It's beyond my expertise to comment on your suggestions but I have a tangential suggestion: since it's so hard to predict when decrossOpt might run into difficulties it really shouldn't be used without being wrapped in a timeout mechanism. I didn't really appreciate this as it was finishing very quickly on our other graphs of similar size/complexity. Perhaps a way to gracefully timeout and fall back to decrossTwoLayer should be included in the lib.

erikbrinkman commented 1 year ago

it actually does have a timeout mechanism! Unfortunately I think in the current version the heuristic is off. In an update version it should be better able to predict timeout issues.

Sorry that you had to be hit with a case that bypassed the check. I will use this an example to make sure it appropriately errors on this as input.

Ideally for graphs like this, an exception will be raised, and if you wanted to backoff, you could catch this exception and switch to a different layout, or even write a custom decross operator that tried opt, and used twolayer if it times out.

erikbrinkman commented 1 year ago

The prerelease version updates this codes to check the actual number of variables, which should be better at catching this inconsistency:

https://github.com/erikbrinkman/d3-dag/blob/f3f0f20dfc0b658bfcd09225667e2da68d2f19b2/src/sugiyama/decross/opt.ts#L378-L384

The downside is is creates the program which might be very large. It's possible to compute these sizes in advance, but the code was quite messy, so I opted for this simpler version.

Don't hesitate to reopen if it's not addressed.