Node order problem when using hierarchical layout

[KimRasmussen]

When using hierarchical layout with 2 levels and > 10 items in the 2nd level, the sort order gets weird.

I have a simple example here: http://jsfiddle.net/sg27ycbn/

Here, you can see the order of nodes in the 2nd level is all wrong. If I comment out the line

edges.add({from: 1, to: 12});

then the remaining 9 nodes connected to the root gets shown sorted in the order they were inserted in, but as soon as there are 10 of them, the order gets weird.

I assume that is a bug and not intentional - is there any way I can fix this ? Any options that should have been set different ?

[wimrijnders]

It looks perfectly fine to me; perhaps there's some extra step I need to do to reproduce?

Having said that, there are known problems with the hierarchical ordering, see e.g. #3357. But for a simply connected network like this, there should not be any problem.

[KimRasmussen]

I am sorry that I was unclear in my description of the issue.

As it looks now, the nodes on the 2nd level is in this order:
2, 12, 4, 5, 6, 3, 8, 9, 10, 11, 7.

If I remove the last edges.add line, the appear in the order I inserted them (which is what I would expect them to do).
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

As soon as the last edge (from 1 to 12) is added, the order of all the nodes get messed up.

[wimrijnders]

No, sorry, I really don't see that happening.
Perhaps it's platform-specific? I'm doing this on linux+firefox. Want OS/browser are you using?

[KimRasmussen]

Ah, it seems to be browser specific. It works just fine on firefox on windows, but not on chrome.
Seems to work fine in internet explorer and edge as well - so it looks like it is only chrome that has the problem.

Didn't at all think about trying it on other browsers - sorry.

[wimrijnders]

Well, I'll be. Confirmed. This is truly weird.

Now, why on earth would chrome do it differently?

Okay, I have something to go on now. Will keep you posted.

[wimrijnders]

Found it. It has to do with the Array.sort() method, which I can imagine to be browser-specific.

The nodes are sorted, several times in fact, during the positioning of the nodes. Initially however, the per-level coordinates (y in the case above) are not filled in yet, for the simple reason that they have still to be determined. So you have the situation that the following is run:

        nodeArray.sort(function (a, b) {
          return a.y - b.y;
        })

...without the y-coordinates filled in. The sort method calculates undefined - undefined which translates to NaN.

I have no trouble at all imagining that the handling of NaN in the sorting is platform-specific. I suppose that the strategy in chromium for handling this, is different from the other browsers.

Very interesting. It looks like a small thing, but this might actually explain some of the problems we're having with the hierarchy layout.
Thanks for reporting. You deserve an internet beer: 🍺 .

[KimRasmussen]

Cheers for the 🍺 :)
I'm glad you found the problem.

What is the intention regarding sort order for items with the same level ? is it purely insertion order ?

[wimrijnders]

Right now, it's insertion order. There is a half-hearted attempt in the code to implement a custom sorting function, but it's not enabled.

However, there are requests open for that, see #528, #1927, #3240. So there is real demand for it and your voice only adds more weight to its importance. It's definitely going to get implemented some day, I just can't say when. Have more than plenty enough to do, here and elsewhere.

(I should also mention here that the order can change due to optimization of the hierarchical tree, the intention of which is to minimize edge overlaps and lengths)