Rendering performance for Directed Acyclic Graph

GoJS
1

I am currently rendering a directed acyclic graph (DAG) and running into performance issues as the number of nodes gets over 100. Here are some benchmarks:

Nodes

Render (secs)
10 0.25
21 0.5
45 1.4
82 3.6
112 6.9
261 24.3
327 46.8
628 163.8
722 216.7


For timing I have been using the following snippet:

start = new Date();
myDiagram.layout.isOngoing = false;
myDiagram.model = go.Model.fromJson(data);
myDiagram.layoutDiagram(true);
stop = new Date();
$(“#btn_test”).html(((stop.getTime()-start.getTime())/1000).toString());

I am currently using a tree layout with the following node and link template:

myDiagram.nodeTemplateMap.add(“NodeBuilt”,
$(go.Node, go.Panel.Horizontal,
{ selectionChanged: nodeSelectionChanged },
{ locationSpot: go.Spot.Center },
$(go.Panel, go.Panel.Auto,
$(go.Shape,
{ figure: “RoundedRectangle”, fill: bluegrad, stroke: ‘gray’}),
$(go.TextBlock,
{
font: “9pt Helvetica, Arial, sans-serif”,
stroke: ‘black’,
margin: 3,
textAlign: “center”,
maxSize: new go.Size(150, NaN),
wrap: go.TextBlock.WrapFit,
editable: false
},
new go.Binding(“text”, “text”).makeTwoWay())),
$(“TreeExpanderButton”)
));

myDiagram.linkTemplateMap.add(“LabeledLink”,
$(go.Link, // the whole link panel
{
routing: go.Link.Normal,
curve: go.Link.JumpGap,
corner: 5, toShortLength: 4,
relinkableFrom: false, relinkableTo: false, reshapable: false, selectable: false
},
$(go.Shape, // the link path shape
{
isPanelMain: true,
stroke: “gray”, strokeWidth: 1
}),
$(go.Shape, // the arrowhead
{
toArrow: “OpenTriangle”,
stroke: “gray”, strokeWidth: 1
}),
$(go.TextBlock, // the label
{
//textAlign: “center”,
font: “8pt helvetica, arial, sans-serif”,
stroke: “Black”,
//margin: 2,
editable: false,
segmentIndex: 1, segmentFraction: 0.55, segmentOffset: new go.Point(0, -5)
},
new go.Binding(“text”, “text”)
)
)
);

Here are the current additional diagram settings:
var bluegrad = new go.Brush(go.Brush.Linear);
bluegrad.addColorStop(0, “white”);
bluegrad.addColorStop(1, “#b2d9eb”);

myDiagram.layout = $(go.TreeLayout, { nodeSpacing: 12 });
myDiagram.layout.angle = 0.0;
myDiagram.undoManager.isEnabled = false;
myDiagram.isModelReadOnly = true;
myDiagram.allowDelete = false;
myDiagram.allowMove = false;
myDiagram.allowTextEdit = false;
myDiagram.toolManager.dragSelectingTool.isEnabled = false;
myDiagram.maxSelectionCount = 1;

We are trying to render DAGs with up to 1000 nodes. Currently, this is taking minutes. Since JavaScript is single-threaded it is also locking up the display. Is there something we can do to speed up the rendering and/or make the rendering code interruptable/resumable/incremental?


2

First, we know about the potential problems with freezing out user input during a long-running layout. That’s on the list of issues to address once all of the basic functionality is present.

Second, LayeredDigraphLayout is known to be very slow. Some of this is just JavaScript and array access, some of this is the non-optimal implementation of LayeredDigraphLayout.

BUT, you seem to be using TreeLayout, which is known to be very fast. I cannot explain why your timings are as slow as you report them to be. Unless maybe your graph is very non-tree-structured, which I suspect might cause quadratic performance (or worse?) because TreeLayout assumes that the graph is basically tree-structured.

For an example of TreeLayout with 12 thousand nodes: Virtualized Tree Layout.