hierarchical directed layout: wrongly directed arrows

[whme]

The fiddle below is using vis.js as vis-network seems to be not yet available on cdnjs, however this is not working on the current vis-network version either.

As you can see on this jsfiddle not strictly hierarchical networks do not very well with vis atm. It seems that the levels given to the diferent nodes by vis are not quite.. right.
The first network shows nodes without the level argument given, the second one below with level given. Without explicit level the result is just wrong: crossing edges and even wrong levels. (In up direction a child node should never be above its parent node ^^)

The edge crossing seems to be known but it still would be nice if it gets fixed or at least if one could toggle if he want "optimazation but crossing" or "no crossing but no optimization" mentioned here.
Concerning the wrong direction for some nodes I did not find any related issue.

Im not sure if it can help here, but it seems like for larger graphs without level given the order of edges does alter the resulting graph significantly. (I will update the issue with an example as soon as I got one or maybe better open another one, as it may be a totally different thing.)

Without having looked into the code, I assume the graph engine isnt sorting the edges it is given properly in order to assign them their final level in the graph, thus nodes are placed on wrong levels resulting in wrongly directed arrows/edges.

[whme]

Here is the above mentioned example where the order of the edges matters.
The top one of the 2 graphs has the edge array sorted differently each time one presses run which results in completly different trees each time.
It seems like this is due to the fact, that the way vis determines the max level of the tree is wrong.
The correct graph, the bot one, has 21 level. However vis comes up with a different number of levels each time going from 13 to 19.
There are basically two problems:

1. the order of the edges impacts the determination of the levels
2. the level determination is doing something wrong, which is why it never gets the correct number of levels.

Maybe this publication about the Sugiyama-Algorithm can help solving the level determination problem.

(The bottom graph although rightly "leveled" has node 35 overlapping with the edge from 32 to 42 which I assume is due to the fact, that vis prefers keeping the same nodespacing everywhere over having no "edge crossing" at all)

[ohsorry]

Is there any progress on this issue? My application scenario also needs to manually set the level of the node to layout. It seems that I can't help much, I just finished reading the documentation.

[Thomaash]

Hi @UnicornDeluxe and @ohsorry,

I tried to fix the wrong layout part of this issue. It's really slow at the moment but seems to work correctly. Could you test it with your apps and give some feedback please? I'm not sure whether it's bullet proof.

• MWE 1: http://jsfiddle.net/m56qtkcu/
• MWE 2: http://jsfiddle.net/huwp23bz/
• URL for MWEs: https://raw.githack.com/Thomaash/vis-network/issues/4/dist/vis-network.js

[whme]

Hi @Thomaash,

looks to me like there are no wrongly directed edges anymore, congrats!
And the randomness when altering the order of the edges is also gone.

The levels itself are a bit weird tho, I guess the problem is your determining the level based on the parent nodes, resulting in a lot of nodes beeing placed at level 0 which would fit better at for example level 6 (as their sole child is level 7).

I rendered the same graph in three different ways to make this a bit clearer:

This one beeing without explicit level given to the nodes and without your fix. (although given in the right order, which is why there are only 2 level 0 nodes):

At level 10 to 9 one can see wrongly directed edges, which is due to the lack of 1 additional level in the graph.

The next one is using your fix (without levels and with the same order of the nodes as the previous one ofc):

Here there are no wrongly directed arrows, however many nodes are placed at level 0 while they could be placed far below. Resulting in the graph beeing very broad.

The last one works with and without the use of your fix but requires the levels to be determined, leading to this:

There are no wrongly directed edges either, however there are not more nodes than absolutly necessary on level 0 and so on.

The way I avoid having nodes at level 0 that should not be there is by building the graph from the bottom to the top thus looking at the childs of the nodes instead of their parents. Which means in the worst case the number of levels in the graph is equal the number of nodes, thus I set the initial level of each node to the total amount of nodes. Then by using the edges I check for each node if their child node is on the same level as they are, if so the node level has to be reduced by one to get the node one level above its child. Repeat this for each node, number_of_nodes^2 times and you get the right levels. (As the lowest level may not be zero just substract it from all the other levels to get levels from 0 to x)
The performance of this is horrible but I'm sure it can be improved a lot by some smart people out there.

I hope this helps make your fix even better.

Thanks for the work your putting into this, keep it up!

[Thomaash]

@UnicornDeluxe Okay, so I've improved the performance and incorporated your advice. Could you check it out once more whether everything is alright please?

URL for MWEs: https://raw.githack.com/Thomaash/vis-network/issues/4/dist/vis-network.js

[ohsorry]

@Thomaash
No layout problems for me now! I used vis-network to visualize dynamic neural networks, everything works very well. 👍

[whme]

Hi @Thomaash it seems like it's not working anymore; the graph looks like the first one here #4 (comment) again. And the randomness is back in, as you can see here: http://jsfiddle.net/huwp23bz/

Can you please upload the vis-network.js from #4 (comment) separately again so I can check?

I fucked something up while testing, sorry.

The levels look perfectly fine for me now, good job! However there still is a randomness in layouting (http://jsfiddle.net/huwp23bz/) which leads to crossed edges (instead of beeing random every run, the layout is right in 3 out of 5 cases mostly, so there is some progress).

[Thomaash]

@UnicornDeluxe glad to read it works. The crossing edges are indeed not part of the PR, it's only about the messed up levels. Edge crossing is, at least in my opinion, an unrelated issue that should have it's own issue opened.

[whme]

@Thomaash you are right, I will open another issue for the crossing edges.
What about the random layouting? A new issue aswell or as part of the crossing edges one?

[Thomaash]

I would say 2 independent issues.