Specific key order appears to cause decrossOpt to hang about d3-dag HOT 4 CLOSED

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.

from d3-dag.

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.

from d3-dag.

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.

from d3-dag.

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

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.

from d3-dag.