Performance of Force Directed Layout?

GoDiagram (6 and previous)
1

What is the performance of the GoLayoutForceDirected class in 2.6 relative to 2.1? I’m specifically considering the cases of 1,000+ nodes and 10,000+ nodes. It’s my understanding that the performance of 2.1 and earlier was poor on graphs of this size. Has it been improved in 2.6?

2

It got noticeably faster in version 2.5.

However, I think the performance limitations are typically due to starting off with all of the nodes at the same overlapping location. This is normally the case when loading some graph without any position information for the nodes.

We are improving GoLayoutForceDirected to be smarter about pre-positioning the nodes in this case, after which the rest of the computations will produce reasonable results in a much shorter time. This work will be released as part of version 3, which might start alpha testing soon.

3

Thanks for the information. If I’m understanding you correctly, I may still see some performance issue on large graphs (1,000+ nodes) if I start with all of the nodes at the same location? If that’s true, could it be improved if I simply spaced out the nodes without regard to their links (say, make sure each node is x units away from every other node both vertically and horizontally, where x is the width of a constant bounding rectangle of similarly sized nodes) and then performed a force directed layout operation?

4

Yes, that could be better if you can be smart about how the nodes are positioned, so that nodes that “should” be close to each other are not too far from each other.

One way to achieve some locality, if appropriate, is to use GoLayoutTree to do a tree layout, even if the graph is not really tree structured. Then you can do a GoLayoutForceDirected for a significantly shorter time, and probably get a better result, than if you had started with all of the nodes at the same location.

5

So I tried doing a tree layout first, but I’m getting two refreshes on my view (one after the tree layout and one after the force directed layout). Here’s what I’m doing in my GoView derived class:

this.Document.BeginTransaction();
....

this.Document.BeingUpdateViews();

GoTreeLayout treeLayout = new GoTreeLayout();
treeLayout.Document = this.Document;
treeLayout.PerformLayout();

GoLayoutForceDirected layout = new GoLayoutForceDirected();
layout.Document = this.Document;
layout.PerformLayout();

this.Document.EndUpdateViews();
this.Document.FinishTransaction("auto layout");

Is there a way to stop the double repaint?

6

You have a bunch of typos in your excerpt, so I assume you have typed it in instead of copy/pasting it from your actual code. Here’s what I would do:

GoDocument doc = myView.Document;
doc.StartTransaction();
//doc.BeginUpdateViews();

GoLayoutTree treeLayout = new GoLayoutTree();
treeLayout.Document = doc;
treeLayout.LayerSpacing = (float)Math.Sqrt(doc.Count/2)*10;
treeLayout.PerformLayout();

GoLayoutForceDirected layout = new GoLayoutForceDirected();
layout.Document = doc;
layout.MaxIterations = 10;
layout.PerformLayout();

//doc.EndUpdateViews();
doc.FinishTransaction("auto layout");

I don’t get double repaints when I execute this code, even without those calls to BeginUpdateViews and EndUpdateViews. Those calls are not necessary, since PerformLayout does not force any Refresh’es.

Perhaps you have implemented GoLayout.Progress event handlers or OnProgress overrides that call Control.Refresh()?