Fix bug where original order is not respected in some cases #335
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Fixes #336
This fix accomplishes two things:
This fixes a layout bug where some graphs will have an incorrect node ordering. This happens because the original ordering is already optimal (zero crosses) but the cross minimization in order/index.js will permute the nodes several times anyways even though it can't decrease the cross count.
This is a perf optimization. If cross count gets to 0 then we should stop the loop. I noticed that running
make bench
shows an increase in the ops/sec for the order phase of around 700 to 840.Note that this breaks atleast one case of compound graphs (the failing tests) and I'm not entirely sure why compound graphs are required to go through the sweepLayer pass in order to get a proper layout. It seems that the cross minimization should be separated from the compound graph layout. I did notice that moving the cross minimization check to within the for-loop (after sweepLayer) fixes the test. That may be one possible fix and I'll put up a separate PR. However, it does not fix the original bug that I was trying to fix.
Before:
After:
Perf before:
Perf after:
The main issue with this fix is that it breaks compound graph layout. It breaks a unit test, and I confirmed by rendering the graph from that unit test using
test/console.html
.The test is
layout-test.js: can layout subgraphs with different rankdirs
. And the graph looks like:I'm not familiar enough with the compound graph layout additions to order.js to know if its actually essential that we run the cross minimization iterations in order to layout compound graphs, or if there's a way to do what we need for compound graphs but still return early if cross count is 0 before doing all those iterations. I'm going to look at putting up another PR that tries to meet in the middle by returning early after 1 iteration, which I think fixes compound graph layout but also gives perf benefits of not running all the iterations.