microsoft / automatic-graph-layout

A set of tools for graph layout and viewing
Other
1.36k stars 304 forks source link

LayeredLayout ignoring layout constraints #226

Closed rwvens closed 4 years ago

rwvens commented 4 years ago

First of all, I absolutely love MSAGL, y'all did a great job on this library, and I can say so with great confidence having previously used GraphSharp on the exact same dataset and achieving objectively inferior results.

I'm having a bit of an issue though with the constraints. While the results are great with the procedurally generated tech trees as seen in that video up there, when I try to run the layout code on an actual tech tree from my game, I run into some issues.

Here's what the layout looks like without constraints: Unity_tvgq6BKfY8

Which looks great, with one exception. Some techs that are meant to be in a linear chain get moved rather far away from their parents, such as the one labeled d0, which in my database is "Destroyer IV" (you can imagine what the other techs in the chain are). I tried to fix it by attaching all pairs of such techs using UpDownLinearConstraints. Unfortunately that doesn't have the expected result, instead causing such chains to cross over each other: Unity_MPgijeYuxy

Just for kicks, I also tried the same layer neighbor on the same set of techs, and ended up with the best result so far: Unity_um8VUjGtxn

While that's fine though, the objective really is to generate something close to the first layout, but with linear chains constrained to stay connected. Is there something I'm missing?

levnach commented 4 years ago

@rwvens , thank your for the kind words! I would not go with constraints. In general, the layouts with constraints do not look very natural because, well, of the constraints, the optimization algorithms do not do the best job. Instead I'd try to increase SugiyamaSettings.BrandesThreshold to some very large number. By default, when the number of the nodes in the graph is in hundreds, MSAGL switches to the algorithm described here : https://www.semanticscholar.org/paper/Fast-and-Simple-Horizontal-Coordinate-Assignment-Brandes-K%C3%B6pf/69cb129a8963b21775d6382d15b0b447b01eb1f8. It works fast, but creates these long edges that you complained about. If you set SugiyamaSettings.BrandesThreshold to a very large number, then the more accurate algorithm kicks in. It would take more time but the results should be better.

rwvens commented 4 years ago

Hey @levnach thanks for coming to the rescue. Unfortunately, the Brandes Threshold is not coming into play here, I set it to 9999 and it's still generating the same layout. Only reason it doesn't look exactly the same is because Destroyer II (0b) wasn't correctly depending on Destroyer I (d6), but the end of that chain, Destroyer IV (d0) still gets moved below its dependent chain (Dreadnought, depending on both Destroyer IV and Ironsides III) Unity_gUkoheBLbN

levnach commented 4 years ago

How large your graph is? Maybe it is the default layout working anyway. Another trick to use is the following one: if you want to keep an edge short assign a larger weight to it, Egde.Weight *= 10, or something like that. It might improve the situation. Also please notice, that if d0 is moved to the left, 8f->d0 becomes shorter, then the edge b4->59 becomes longer!

rwvens commented 4 years ago

Thanks, man, that did exactly what I was hoping for! Unity_2E1mgy6mOW