unnecessary change to `pass1` and `pass2` methods in`lib/position/bk.js` file

[tylerlong]

Check the change history of lib/position/bk.js file: https://github.com/dagrejs/dagre/commits/3d538f0dbfe4ad5735c88efee22af0994441c898/lib/position/bk.js

1. Tried to migrate to lodash 4
2. Found a failed test, tried to fix it by editing pass1 and pass2 methods in lib/position/bk.js file
3. Fix bugs introduced in step 2, refactor code

I think things started to become wrong in step 2. If a test failed, we should check what was changed recently in step 1. And step 1 didn't change any logic of pass1 and pass2 methods. So we shouldn't change them in order to fix the failed test.

I think the bug was introduced in this commit of step 1: https://github.com/dagrejs/dagre/commit/590b155a32159412fe5f5de0e18df6b8d99d22b9#diff-02a83e5e964e624bd848264b9729e9bd

And we should try to edit findSmallestWidthAlignment method in order to fix it. The following works:

For a fully working project with passing tests, please check my fork of dagre: https://github.com/tylingsoft/dagre-layout

[lutzroeder]

@rustedgrail can you have a look?

[rustedgrail]

Hi @tylerlong

The issue that started this work is that pass1 and pass2 were making recursive calls. On large graphs, this would lead to a stack overflow. To the best of my knowledge, no issue was introduced with the lodash 4 changes.

My first commit removed the recursive calls and got all but 1 of the tests passing. It was a WIP commit at the end of the day. Changes we tried to fix the last test, ended up breaking more tests. The commits could have been squashed with a message explaining that it removed the recursive call, but instead that was captured in the PR.

Your fork might fix a different issue, but it still includes the recursive calls in pass1 & pass2, which should fail on graphs with thousands of highly connected nodes.

[cpettitt]

@tylerlong, if there is a bug, can you provide some more detail or a failing test case? Currently all tests are passing on master.

[tylerlong]

@rustedgrail Could you please provide the steps to reproduce the recursive calls issue?

@cpettitt I did NOT change pass1 and pass2 in https://github.com/tylingsoft/dagre-layout and all tests are also passing. So I don't know what the bug is. That's why I mentioned "unnecessary change" in the title of this issue.

So Let's figure out what the bug is. @rustedgrail please reply when you see this comment. It is even better if you can reproduce this issue with https://github.com/tylingsoft/dagre-layout which is a fork of this project. Thank you very much!

[tylerlong]

If CI says the code is OK, where did the failing test come from?

[cpettitt]

@tylerlong you can repro the stack overflow issue by creating a graph with a large number of nodes and edges.

I don't see anything actionable on this ticket. The merged commit does not include any changes to the test code. We could have squashed the merge and the original commit would not have shown up in the commit history. Rewriting history now would break clones.

[rustedgrail]

The graph that I had used to get the overflow had 1503 nodes with ids, A, B, C and 1-1500. A connected to B which is connected to C and each of those had an additional 500 outgoing nodes. I was running in a relatively recent version of Chrome.

A -> B -> C & A -> 1 through 500, B -> 501 through 1000, C -> 1001 through 1500

The failing test came from my own changes in the commit on Jan 24th. I tried to fix all the tests before making that commit, but that ended up being more work than I had expected.

[tylerlong]

@rustedgrail I don't quite understand the steps you described. It is appreciate if you can provide me with a test case or sample code.

The failing test came from my own changes in the commit on Jan 24th. I tried to fix all the tests before making that commit, but that ended up being more work than I had expected.

Before your commit on Jan 24th, all tests were passing according to Travis CI. So I don't know which test you are trying to fix. If you try to fix a bug which is not covered by existing tests, you should first create a failing test for that bug. I also don't see any new tests being created here: https://github.com/dagrejs/dagre/commit/755a0e9e445134195163d4fe557a2ea82bea7057 So I am still quite curious what the bug is. After I understand what it is, I am willing to write a test case for it.

Thanks :)

[gabrielgrant]

@tylerlong sounds like the failing case @rustedgrail is describing is something like this:

var g = new dagre.graphlib.Graph();
g.setGraph({});
g.setDefaultEdgeLabel(function() { return {}; });

let subNodes = 500;

['A', 'B', 'C'].forEach((c, i) => {
  g.setNode(c, { label: c});
  [...Array(subNodes).keys()].forEach(j => {
    let nodeName = (i * subNodes + j).toString();
    g.setNode(nodeName, { label: nodeName});
    g.setEdge(c,   nodeName);
  });
});

g.setEdge('A',   'B');
g.setEdge('B',   'C');

dagre.layout(g);