Stack Overflow during tree layout

GoDiagram (6 and previous)
1

So I’m trying to do a tree layout (because tree is by far the fastest) and am encountering a System.StackOverflowException while inside PerformLayout. My data consists of the following:

  • ~6600 nodes
  • ~6600 links
It's randomly generated, so there's nothing particularly special about it.

The options I’ve given to the GoLayoutTree object are:

  • Angle = 90
  • Arrangement = Horizontal
  • SetsPortSpot = false
  • SetsChildPortSpot = false
  • Progress = a handler that updates a status bar
This is particularly troublesome since this is just a test run to find problems on the way to my target data set which is 1 order of magnitude larger for the nodes and 2 orders of magnitude larger for the links.

edit: This is using version 2.6.2.2 on WinXP SP 2.

2

Can you post the code you’re using to start the Layout? and a bit of the end of the stack dump if you can…

3

Slight correction: I have ~6600 nodes and ~18,000 links.

Here’s the code:

try
{
// Wait until this thread can grab the sync object.
this.threadSync.WaitOne();
this.threadSync.Reset();

GoLayouTree layout = new GoLayoutTree();
layout.Document = this.Document;
layout.Document.StartTransaction();
layout.Angle = 90;
layout.Arrangement = GoLayoutTree.Horizontal;
layout.Progress += this.layout_Progress;
layout.View = this;
layout.SetsPortSpot = false;
layout.SetsChildPortSpot = false;

layout.PerformLayout();

layout.Document.FinishTransaction(“Tree auto layout”);
}
catch (ThreadAbortException)
{
// Eat the exception that is generated when the user presses the cancel
// button. The cancel button handler performs any necessary cleanup.
}
finally
{
// Signal the sync object so other layout threads can execute.
this.threadSync.Set();
}

4

I hope you realize that the graph you have probably created, with about three times as many links as nodes, is far from being a tree.

GoLayoutTree does try to layer the nodes, but it’s almost certain to come up with very long chains – i.e. a very deep tree. And it will be very narrow. I suppose we could do a smarter job about this, but the design assumption was that the graph be tree-like with at most a small percentage of exceptions (multiple parents).

The tree layout is recursive, as you might expect. So with thousands of nodes, there are probably thousands of levels/layers of nodes. That would cause a stack overflow.

5

Well here’s the problem: if the tree layout were actually able to finish, it looks like it would probably complete in under 5 minutes. I tried a layered digraph layout with MaxIterations = 500 and it made no significant progress after 8 hours. I don’t event want to think about what a force directed layout would do.

So does your layout package support large data sets? The requirement I have from my customer is 35K nodes and 110K edges. I’d prefer to not have to integrate something like GraphViz if I can avoid it, but I’m not seeing much choice here. :(

6

35000 nodes and 110000 links? No. Our target is graphs that can be seen and edited, not read-only graph visualization.

In the kind of huge ball of spaghetti that you have, both the tree and the layered-digraph layouts are probably spending inordinate amounts of time trying to figure out the layers.

You can improve the speed of GoLayoutTree in this case by choosing a root node – initialize the GoLayoutTree.Roots collection.

You can improve the speed of GoLayoutLayeredDigraph by setting the LayeringOption to something other than OptimalLinkLength.

We can look into improving the behavior of GoLayoutTree when the graph is so not a tree. We also intend to write a new layered-digraph algorithm to be much faster than the existing one.