Autoarrange ( big problem )

Hi, Please help.

I have a big, big problem.

I have a GoDocument which contains aprox. 400 GoNode objects that are linked width GolabeledLink. In conclusion I have a graph of 400 elements linked wilth GoLabeledLinks.

I want to autoarrange these elements an for that I call the PerformLayout function of GoLayoutLayeredDigraph class on GoDOcument collection.

The big, big problem is that the time of autoarranging is up to 30 - 35 minutes on 2 GHz processor and 512 RAM.

How can i reduce the time of processing of this situation.

In my GoDocument i have many links ( high density ).

This is very very important … crucial for our application.

All setting of our class GoLayoutLayeredDigraph are default with exception of

base.LayeringOption = GoLayoutLayeredDigraphLayering.OptimalLinkLength;

Please help.

I just tried running a test with 400 nodes in LayoutDemo. It took about 30 seconds, not minutes, on a slower machine with the same amount of memory.
The performance is greatly dependent on the structure of the graph. It’s hard to characterise easily, but if you have a lot of links that cross layers, that will be slower than if the links connect adjacent layers. (I’m talking about layered-digraph layers, not GoLayers, of course!)


There I Have a lot of links … aprox 3000 links.

How can I reduce the time of processing??? ( Now I have there 20 minutes …)

Any idea?

Thanks a lot…

You might be able to override some methods as no-ops, for those steps that you can afford not to do. But you probably wouldn’t like the results.


I uderstand that …

Can you help me with some source code and documentation about autoarrange? This is crucial for our customers.

It is imperios necesarly to find a way more fast for autoarrange.

I need details and examples about how can I suppress some operation in GoDiagram algorithm for autoarrange for fast autoarrangr…

Thanks a lot …

It depends a lot on the nature of your graph.
You could try overriding several methods to see if they help.
For example, try overriding ShiftBendStraighten and AdjacentExchangeCrossingReductionBendStraighten to just call the base method and then return false.
And/or try overriding CountBends to just return zero.


I tried your recomandation and I obtaibed from 20 minutes to 8 minutes … but is not sufficient.

In your documentation you said in GoLayoutLayeredDigraph class …"This method can be overridden to customize the layout algorithm. "

But there I have the next functions:

protected virtual void RemoveCycles();

protected virtual void AssignLayers();

protected virtual void MakeProper();

protected virtual void InitializeIndices();

protected virtual void InitializeColumns();

protected virtual void ReduceCrossings();

protected virtual void StraightenAndPack();

protected virtual void LayoutNodesAndLinks();

Where can I find some examples on how this methods can be overriden because I don’t know how to modifiy them for faster processing …

Please give me a link or something else for help.

Thanks a lot …

With those overrides, were the results still reasonable looking?
I don’t know if we have any examples for overriding most of the methods you mention. Some of them are pretty fast, so you wouldn’t gain anything anyway.
I’m not sure there’s much more that you can do that would be easy.


Look for example at the method:

protected virtual void StraightenAndPack();

If I want to override this method I don’t know what to do it. In my results this method take a long time for processing ( because when I have commented it when I have overrode it the time will reduce from 8 minutes to 1-2 minutes ). If I comment it then the result of autoarrange is not very good. That why I want to do a combination between its presence an its absence.

Then if I know what to write I think I can put there some code for more reducing time.

Your advices it is very good … but if I can to override this method and to put the properly code ( for example the original code but a little modified ) then I think I can obtain a time reducing processing.

If you can give me the source code for this method I think I can modified it for fast processing. I don’t mind if the quality of autoarrange will be reduced a little.

Thanks a lot.

Thanks for imeddiatly response.

I’m running into a similar performance problem when laying out graphs with a large number of nodes.
Could you give some insight why you suggested to override the three methods you mentioned in your previous post? In your opinion, are these the methods which have the most impact on layout performance? Are there any other methods which you could recommend overriding in a similar manner?
If you could point me to any documentation you have about strategies for how to structure your graph to improve layout performance, I would really appreciate it.
Thanks for your help.

Yes, as a practical matter, there’s a limit to how many objects the layout algorithms can handle. Normally we suggest a limit of about a thousand, but that depends a lot on the nature of the graph. Sometimes several hundred can be too much, and sometimes a few thousand work well.
Unfortunately we don’t have a good characterization for different graphs and their respective performance depending on various parameters and overrides. This is all very complicated. Alas, that also means that providing the source code is unlikely to be helpful.
We’re working on additional layout algorithms that are more specialized and a lot faster. But they wouldn’t help vasilegrafu, with whom we are corresponding by e-mail.
I suggested overriding those particular methods because vasilegraphu’s graph seemed to have a lot of links, and the code to straighten links that cross layers is slower than it needs to be for a lot of cases.

Thanks for your response. I agree with you that this is a pretty complicated problem. :)
I am going to try some more tests overriding the various straighten functions since my graph has a combination of a large number links between a large number of nodes. If you’re interested, I’ll post any results here.

Hi iangoodsell

I am very interestred in any result that it will ameliorate the time of processing …