Go Layout limitations

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
2 objects linked to the others:
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.