Hi,
We are encountering problems with the layered digraph layout that is too slow in some cases.
We must clearly know the limitations because we must be very contractual with our customers (some cannot open their projects).
Is there any results of autolayout benches?
I’d like to have approximate times according to the number of nodes and the number of links, with best and worst scenario of complexity.
Our biggest projects are actually about 200 nodes for 700 links and cannot be opened.
Thanks
That sounds like it should take a while but should not be too bad. Perhaps there are a lot of links that cross layers, which will distinctly slow things down.
Trying to characterize the performance is difficult. It really depends a lot on the kinds of graphs that are being laid out. How long is that graph of 200+700 taking?
My 200+700 takes 12 seconds (1.5Ghz) which is not so bad.
I’ve made some tests. My conclusion is that we must use subgraphs at maximum.
I’d like now to determine the correct number of groups to optimize the time : If I have n nodes and I auto arrange n1 subgraphs of n2 nodes so that n1+n2=n. Which is the correct value for n1 and n2? SQRT(n)?
Here are the results of my bench:
1 object linked to the others:
Objects | Links | Time | Obj/Sec |
51 | 50 | 0.34 | 150 |
101 | 100 | 1.07 | 94 |
151 | 150 | 2.44 | 62 |
201 | 200 | 4.98 | 40 |
251 | 250 | 8.40 | 30 |
301 | 300 | 13.10 | 23 |
351 | 350 | 20.16 | 17 |
401 | 400 | 27.22 | 15 |
451 | 450 | 36.92 | 12 |
500 | 499 | 48.84 | 10 |
Objects | Links | Time | Obj/Sec |
102 | 200 | 1.33 | 77 |
202 | 400 | 6.27 | 32 |
302 | 600 | 16.23 | 19 |
402 | 800 | 32.92 | 12 |
No links:
Objects | Links | Time | Obj/Sec |
100 | 0 | 0.82 | 122 |
200 | 0 | 3.16 | 63 |
400 | 0 | 16.99 | 24 |
same as first situation but with groups of 50 nodes:
Objects | Links | Time | Obj/Sec |
101 | 100 | 3.53 | 29 |
201 | 200 | 7.72 | 26 |
301 | 300 | 11.11 | 27 |
401 | 400 | 12.39 | 32 |
501 | 500 | 17.79 | 28 |
You can clearly see that this is exponantial (try an excel chart)
If your graph is naturally decomposable into subgraphs, that would be reasonable to do. The typical case of this is where you are actually using GoSubGraphs (which are nodes) to hold graphs nested inside. The Layout User Guide describes how to do this, and the SubGraphApp demonstrates the code. But you need not be using GoSubGraphs to use this technique.
However, it only works when you can assume there is no interaction between nodes in the separate layouts. I have no idea if that applies to your situation.