LayeredDigraphLayout Performance Suggestions

Are there any suggested methods for increasing the performance of a LayeredDigraphLayout? This seems to be the only layout I can use due to the fact that the nodes in our diagrams can have lots of loops back to previous nodes. I have tried using TreeLayout and setting the routing to Orthagonal or AvoidsNodes to fix the way the links appear, but the links are still very confusing and overlap other nodes. The way that LayeredDigraphLayout lays out the diagram is very clean comparatively. The problem we are experiencing is that some of our diagrams are getting into 200+ nodes and growing. These diagrams can take nearly a minute to finally render. The same diagram in TreeLayout loads in about 4 seconds.

I am not currently using coordinates with my nodes. Would storing those and using them on render help out the performance in any way (keep the algorithm from having to determine where to position the nodes)? Any suggestions would be greatly appreciated.

Thanks

What properties have you set on the LayeredDigraphLayout? I assume you have not overridden any methods.

{
      'toolManager.mouseWheelBehavior': go.ToolManager.WheelZoom,
      'draggingTool.dragsTree': !disableDragTree,
      initialAutoScale: go.Diagram.Uniform,
      'linkingTool.direction': go.LinkingTool.ForwardsOnly,
      initialContentAlignment: go.Spot.Center,
      autoScrollRegion: 50,
      allowClipboard: canCopyPaste,
      allowCopy: canCopyPaste,
      allowDragOut: false,
      allowInsert: canCopyPaste,
      hasHorizontalScrollbar: false,
      hasVerticalScrollbar: false,
      padding: 300,
      layout: $(go.LayeredDigraphLayout,
        {
          angle: (isVertical) ? 90 : 0,
          isOngoing: false,
          layerSpacing: 50
        }
      ),
      'undoManager.isEnabled': true
    }

Also disabled the dragSelectionTool and animationManager.

And no, nothing is being overridden.

That looks OK. You could try experimenting with setting LayeredDigraphLayout | GoJS API and/or LayeredDigraphLayout | GoJS API to different values.

I had already tried changing the pack option because I saw it recommended in another forum post. Unfortunately, the links are terrible in any pack option except for the default. I just tried playing with he layeringOption but that seems to make it take longer to render.

Well, you could try setting other options. But I’m not confident that anything can be improved.

We do intend some day to re-implement the layout to be faster and to have more features. But that day won’t be any day soon.

Is there any chance that you could partition the graph reasonably? Probably not, but I had to ask. Or remove some or all of the edges that form “cycles”, which leaving the Links in the Diagram?

Unfortunately no, it can’t be partitioned and those edges forming cycles can’t be removed. Our clients use it to create decision trees, and the outcome of one decision may need to “loop back” to a previous point in the tree.

Oh, no, I wasn’t suggesting removing the Links that go backwards, but the LayoutEdges, and then depend on AvoidsNodes routing to make sure that those backward Links do not cross over any Nodes.

Do you have a screenshot that shows what a very slow layout produces?

This is the way that LayeredDigraphLayout generates it. This is zoomed in pretty far. I selected a link (in blue) that loops back to a previous node.

I’m not sure I understand what you mean by removing the LayoutEdges. Do you have an example?

Yes, I can create a sample for you.
Can you tell before the layout operates which Links go “backwards”?

Yes, we should be able to determine that.

OK, I’ll work on this when I get a chance later this morning.

Try using this layout instead:

  function BackIgnoringLayeredDigraphLayout() {
    go.LayeredDigraphLayout.call(this);
  }
  go.Diagram.inherit(BackIgnoringLayeredDigraphLayout, go.LayeredDigraphLayout);

  //BackIgnoringLayeredDigraphLayout.prototype.makeNetwork = function(coll) {
  //  var net = go.LayeredDigraphLayout.prototype.makeNetwork.call(this, coll);
  //  net.findAllParts().each(function(link) {
  //    if (!(link instanceof go.Link)) return;
  //    if (isBackwards(link)) {
  //      net.deleteLink(link);
  //      link.routing = go.Link.AvoidsNodes;
  //      link.curve = go.Link.None;
  //    }
  //  })
  //  return net;
  //}

  BackIgnoringLayeredDigraphLayout.prototype.assignLayers = function() {
    go.LayeredDigraphLayout.prototype.assignLayers.call(this);
    var net = this.network;
    net.findAllParts().each(function(link) {
      if (!(link instanceof go.Link)) return;
      var fv = net.findVertex(link.fromNode);
      var tv = net.findVertex(link.toNode);
      if (fv.layer < tv.layer) {
        net.deleteLink(link);
        link.routing = go.Link.AvoidsNodes;
        link.curve = go.Link.None;
      }
    })
  }

There are two options:

  1. the override of assignLayers should work generally, but is slower, or
  2. if you can provide a definition for isBackwards, then use the override of makeNetwork instead (and comment out the override of assignLayers)

I was able to go the “assignLayers” route and it cut the initial render time in half…which is a great. The diagram I am testing with now loads in about 30 seconds as opposed to a minute. Thanks for all your help on this. If you have any other ideas or ways I can squeeze some better performance out of this, please let me know.