Maximum call stack size exceeded

[seanzer]

The DFS implementation in longestPath is recursive, and fails for a large graph.

[seanzer]

I was able to change longestPath to use a stack, but then tightTree also blows up

[seanzer]

Also in dfsFAS - if i get a chance, i'll try to send a pr

[kevalbhatt]

@seanzer any solution you found.

I am getting an error in this function.

function horizontalCompaction(g, layering, root, align, reverseSep) {
  // This portion of the algorithm differs from BK due to a number of problems.
  // Instead of their algorithm we construct a new block graph and do two
  // sweeps. The first sweep places blocks with the smallest possible
  // coordinates. The second sweep removes unused space by moving blocks to the
  // greatest coordinates without violating separation.
  var xs = {},
      blockG = buildBlockGraph(g, layering, root, reverseSep);

  // First pass, assign smallest coordinates via DFS
  var visited = {};
  function pass1(v) {
    if (!_.has(visited, v)) {
      visited[v] = true;
      console.log("start",v);
      xs[v] = _.reduce(blockG.inEdges(v), function(max, e) {
        pass1(e.v);
        return Math.max(max, xs[e.v] + blockG.edge(e));
      }, 0);
    }else{
      return;
    }
  }
  _.each(blockG.nodes(), pass1);

  var borderType = reverseSep ? "borderLeft" : "borderRight";
  function pass2(v) {
    if (visited[v] !== 2) {
      visited[v]++;
      var node = g.node(v);
      var min = _.reduce(blockG.outEdges(v), function(min, e) {
       pass2(e.w);
        return Math.min(min, xs[e.w] - blockG.edge(e));
      }, Number.POSITIVE_INFINITY);
      if (min !== Number.POSITIVE_INFINITY && node.borderType !== borderType) {
        xs[v] = Math.max(xs[v], min);
      }
    }
  }
  _.each(blockG.nodes(), pass2);

  // Assign x coordinates to all nodes
  _.each(align, function(v) {
    xs[v] = xs[root[v]];
  });

  return xs;
}

[seanzer]

The only solution is to rewrite the library to avoid using recursive graph walks. Unfortunately, I haven't had time to make much progress.. there's more than one place where this blows up.

[kevalbhatt]

@seanzer I found the solution https://github.com/dagrejs/dagre/issues/223 , I have updated the version and it is working now.

After the version update, Huge data will take time but the good news is graph will be rendered.

I have one suggestion regarding performance, if we use Web worker for data manipulation or calculation I think performance whould be improved https://github.com/dagrejs/dagre/issues/295