hierarchical directed layout: edge crossing

[whme]

The edge crossing bug 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.

Maybe this is to some degree related to https://github.com/visjs/vis-network/issues/83.

[Thomaash]

Is it always possible to organize a hierarchy without any edges crossing? I think there will be cases where it's simply impossible in 2D space.

[whme]

@Thomaash I do agree, in case of cross references between nodes, edges will have to cross each other. So there is not always a possibilty to organize a hierarchy without any edges crossing.

In some cases crossing can be avoided if "no edge crossing" is prioritised over "keeping the configured space between nodes". (first graph of this fiddle shows what i mean http://jsfiddle.net/huwp23bz/) This fiddle http://jsfiddle.net/m56qtkcu/ also shows "edge with node crossing" where on the top graph, node 3 overlaps with edge from 1 to 5.

[dawidchodura]

I try to render a tree with hierarchical directed layout, but the edges get crossed. Would it help if it was possible to specify in the options that the graph is a tree (ie. no cross references), so that the algorithm could take a hint, while laying out the nodes?

[Thomaash]

Hi @UnicornDeluxe and @dawidchodura,

I was thinking about this and I think we should add a new option which could look like this:

interface HorizontalLayout {
  algorithm?:
    // the way it is now and would be the default
    | 'none'
    // fast O(N) and perfect for trees, will fail on multiple paths to the same node
    | 'tree'
    // some heuristics to get a reasonably good layout for a generic graph
    // no idea how to implement this ATM, maybe not a part of the first PR
    | 'best-effort'
  propNameOrGetter?:
    // name of the property that will be used for ordering the nodes
    // would default to id (just to make it stable as ids generally don't change)
    | string
    // node comparator (like Array.sort callback for given nodes descendants)
    | ((a: NodeOptions, b: NodeOptions) => number)
}

Do you think this would satisfy your needs? Do you have any objections or improvements?

PS: If you can come up with better more descriptive names for the properties or string literals I'm all ears. PPS: @mojoaxel do you want to join this discussion?

[whme]

Looks good to me.

Concerning the "best-effort" algorithm, I guess the Reduction of the Number of Edge Crossings part of the Sugiyama-Algorithm can help.

[deepanshu11madan]

@UnicornDeluxe were you able to achieve no edge crossing? i looked into Sugiyama, and Dagre layout implements it so i am using dagre to calculate coordinates for nodes and edges. With visjs i can set the nodes at those coordinates determined by dagre but no way to tell vsjs edges point coordinates

[whme]

@deepanshu11madan no, I wasn't able to achieve no edge crossing. What do you mean by

no way to tell vsjs edges point coordinates

? Can you share a screenshot of the resulting graph?

[deepanshu11madan]

So dagre is a layered graph layout algorithm based on sugiyama, it calculates coordinates for nodes and control points for edges. With Visjs I can place the nodes on the coordinates generated by dagre, which works perfectly, but the edges are rendered by Visjs and they cross and overlap. I have the control points for edges generated by the dagre algorithm, but no way to tell visjs to use those array of points to draw edges instead. Does that make sense?

I do have a enhancement issue created which Thomaash plans to work on at some point. Meanwhile I was wondering if you were able to figure the edge crossing issue.

[whme]

That does indeed make sense. Have you tried placing 'fake nodes' at the mentioned control points for the edges to force visjs to draw the edges as you want? So for example: Dagre gives you the coordinates of nodes a, b, c and d and a control point e for the edge from b to d you can simply set a node at e and split the edge from b to d into b to e and e to d. Make the node e invisible and you kind of told vis to use this specific point to draw the edge from b to d. Which is what you/we want. Does this work?

[deepanshu11madan]

yeah actually that's I am doing right now, but i have edge properities like dragging edges, edge hovers, clicks, arrows, labels which doesn't work well, will need to dirty hacks and the corners are also not very smooth, for example , in the image below, do you know if it can be made smooth somehow, the connection point of dummy node

[whme]

you can try to reduce the size of dummy nodes, but otherwise I have no idea

[wyleyr]

Wondering if any progress has been made on this issue. I am running into edge crossing problems when using vis to visualize WordNet networks. I don't have much new information to add to this issue, but could provide some further examples of networks where edge crossing occurs even though the graph can be laid out without edge crossing. Would that be helpful?

[Jmedders]

I've been utilizing this example https://visjs.github.io/vis-network/examples/network/other/configuration.html to easily recreate this issue. I've tried playing with all of the options to no avail. To add some visuals to this issue, here is an image of the result when to arrows are added, layout is set to hierarchal, sortMethod is directed, and shakeTowards: roots

By moving the nodes around manually was able to produce the ideal solution, but it'd be amazing if there was a way to achieve something similar to this without the manual process of moving nodes around

[whme]

Hi @Thomaash, I was wondering if you have made any progress concerning this issue 🙃

[Thomaash]

Hi @whme, unfortunately no.

[Xerusial]

The problem is, that edge pulling force is less than node repulsion. What if node repulsion is disabled till the network is stable for the first time and edges have minimal length and then node repulsion kicks in and seperates the nodes from eachother?

[wyleyr]

@Xerusial can you elaborate on this? How did you determine that that was the problem? Do you have some sense of what would be required to code up the solution you propose?

[Thomaash]

Hi @Xerusial,

your solution makes no sense to me but, as always, that doesn't mean it's wrong (I don't understand everything). Could you open a PR so that we can discuss the code? I don't have the time to fix this myself right now but I will definitely find some time to review and hopefully merge a solution.

Thanks.

[pascalbetz]

Hi

I'm struggling with this as well. Is there a way to influence the ordering on the cross axis? Assuming I have a "UD" hierarchical layout, I could solve my "edges crossing" problem by specifying not only the level (Y-Axis) but also the cross-axis-level (X-Axis) (or vice verca for LR/RL direction)

[DurkoMatko]

Havinf the same issue...with sortMethod: "directed", edges get crossed on initial render. Manually, I'm able to create a graph with 0 edge crosses while preventing the hierarchy

[Ronnocerman]

@Thomaash

I'm dealing with this too.

I think @Xerusial is basically pointing out that the spring force can't overcome the repulsive force to un-cross the nodes in a hierarchical layout. Is it possible for nodes to "pull past" each other in a hierarchical layout if the spring force of the "parent" nodes is greater than the repulsive force between children?

[rolffank]

@Thomaash

Is it always possible to organize a hierarchy without any edges crossing? I think there will be cases where it's simply impossible in 2D space.

You can test if the graph is planar. If so, it is possible to draw it without edge crossings (but I don't know if a hierarchical layout is always possible in planar cases). The dot layout engine of Graphviz minimizes edge crossings very well. I think they use Sugiyama algorithm. I used it to get the coordinates of the nodes because in viz.js (JavaScript version of Graphviz created with emscripten) it's not possible to move the nodes manually. Cytoscapejs also use dagre's layout.

[dimitriz09]

Subscribing to this as it can truly break the reading experience. This 3 nodes graph is rendered flat.

https://jsfiddle.net/uadc4n05/

Edit: for anyone having the problem, temp fix would be to revert to https://cdnjs.cloudflare.com/ajax/libs/vis/4.21.0/vis.min.js