Undesired overlapping edges

marcello3d commented 10 years ago

Not sure if this a bug or by design, but I'm getting overlapping edges in some of my graphs. I've pulled together a minimal test case.

The following graph:

digraph {
  A2 -> B1
  A1 -> B1
  A2 -> B2
}

Is rendering with crossed edges: screen shot 2014-09-16 at 3 06 55 pm http://cpettitt.github.io/project/dagre-d3/latest/demo/interactive-demo.html?graph=digraph%20{%0A%20%20A2%20-%3E%20B1%0A%20%20A1%20-%3E%20B1%0A%20%20A2%20-%3E%20B2%0A}%0A

But I'd like it to render like this:

digraph {
  A1 -> B1
  A2 -> B1
  A2 -> B2
}

screen shot 2014-09-16 at 3 07 02 pm http://cpettitt.github.io/project/dagre-d3/latest/demo/interactive-demo.html?graph=%2F*%20Example%20*%2F%0Adigraph%20{%0A%20%20A1%20-%3E%20B1%0A%20%20A2%20-%3E%20B1%0A%20%20A2%20-%3E%20B2%0A%20%20A3%20-%3E%20B2%0A}%0A

cpettitt commented 10 years ago

It's a limitation of ordering being a heuristic versus exact algorithm and the layout being deterministic. However, this is a pretty big fail: the graph could be translated into an undirected tree which should be easy to lay out with crossings. I'm in the process of making big changes to dagre (including some new functionality) and one of the things I fixed is better handling the tree case - regardless of the ordering of the edges it will layout this graph without crossings.

If you can wait a while you can pick up the new version of dagre when it is released. If you can't you could go down one of two paths:

Backport the work I did for trees to the mainline (from 0.5.0-dev). The tree handling code is in lib/order/init-order.js. It's not a lot of code. The main idea is to do a DFS starting from the smallest rank.
If you don't need stability between renders, setting orderRestarts to a non-zero value should fix this case most of the time. Unfortunately for more complicated graphs the value needs to be higher and the probability of minimal crossings goes down.

marcello3d commented 10 years ago

Thanks! I just tried the orderRestarts feature, but it isn't helping with some of our more advanced (non-tree) cases. It's not an urgent problem, so I can wait for the new release.

Let me know if you want more test cases! :-)

eparadis commented 10 years ago

Is orderRestarts still available? I don't see it causing any effect in the online demo, and it isn't helping my own case of overlapping edges.

example with my data and orderRestarts=1

eparadis commented 9 years ago

I dug through the commit history and found that orderRestarts was removed in the v0.5 rewrite. So you're out of luck if dagre is producing bad layouts for your data. If you re-order the list of edges, you can occasionally shuffle to a layout that has fewer or no edge crossings.

cpettitt commented 9 years ago

Yes, it needs to be added back.