Cannot set property 'order' of undefined

[mmacfadden]

Greetings. I am seeing the following error:

TypeError: Cannot set property 'order' of undefined
    at dagre.core.js:1395
    at arrayEach (lodash.js:1289)
    at Function.<anonymous> (lodash.js:3345)
    at dagre.core.js:1394
    at arrayEach (lodash.js:1289)
    at Function.<anonymous> (lodash.js:3345)
    at assignOrder (dagre.core.js:1393)
    at order (dagre.core.js:1371)
    at dagre.core.js:495
    at notime (dagre.core.js:2897)

After doing some debugging I see the following:

function assignOrder(g, layering) {
  _.each(layering, function(layer) {
    _.each(layer, function(v, i) {
        g.node(v).order = i;
    });
  });
}

In this function layer is an array, seemingly containing strings (maybe id's). When this error crops up, it seems that several items in the layer array are undefined. Therefore g.node(undefined) also returns undefined and produces the error.

I am currently going through our code to see what might be causing the issue, but was hoping that maybe the authors had some insight into what I might look for.

[mmacfadden]

More insight, in the order function

dagre/lib/order/index.js

Line 29 in 7e050f8

function order(g) {

When the initial layering matrix is created, the layers do not have undefined in them.

dagre/lib/order/index.js

Line 34 in 7e050f8

var layering = initOrder(g);

However later on on line 52 the best variable seems to have layers with undefineds:

dagre/lib/order/index.js

Line 52 in 7e050f8

assignOrder(g, best);

[j6k4m8]

How are you building your graphlib.Graph?

[mmacfadden]

Hi @j6k4m8, I am actually using the Directed Graph Layout from JointJS that uses Dagre. I am actually building a JointJS graph. JointJS is then building a GraphLib graph to pass to Dagre.

https://github.com/clientIO/joint/blob/master/plugins/layout/DirectedGraph/joint.layout.DirectedGraph.js

I am trying to figure out if the issue is with 1) us passing bad data to Joint JS, 2) a bug in JointJS translating into GraphLib, or 3) a bug in Dagre.

Mainly I am hoping to understand what could cause undefined to wind up in those arrays, so maybe i could trace backwards and figure it out. Or if there is some validation I can put at some step in the process to detect issues.

At the moment, most of the graphs work just fine, but several of them exhibit this behavior. But the error is buried so deeply in Dagre that it is not obvious what the issue might be and where to start looking.

[mmacfadden]

Some more debugging. In one of the calls to this method:

dagre/lib/order/index.js

Line 43 in 7e050f8

layering = util.buildLayerMatrix(g);

Several elements in the layering array go from string values to undefined.

[mmacfadden]

And finally... in this method:

function buildLayerMatrix(g) {
  var layering = _.map(_.range(maxRank(g) + 1), function() { return []; });
  _.each(g.nodes(), function(v) {
    var node = g.node(v),
        rank = node.rank;
    if (!_.isUndefined(rank)) {
      layering[rank][node.order] = v;
    }
  });
  return layering;
}

node.rank (e.g. rank) winds up being undefined in several nodes. So therefore, that element in the array layering matrix does not get set.

[j6k4m8]

to clarify, SOME nodes in the graph are undefined and some are not? Or is it all-or-nothing per graph?

[mmacfadden]

So in terms of the graph, I don't think the nodes are undefined at all. What is happening is that there is a matrix called layering that is used to do the layout in one of the files (mentioned above). At the beginning this matrix (2D array) is fully populated with strings. I assume these strings are node id's of some sort. At some point in the process, several slots (but not all) of the matrix become undefined. The assignOrder method does this:

function assignOrder(g, layering) {
  _.each(layering, function(layer) {
    _.each(layer, function(v, i) {
        g.node(v).order = i;
    });
  });
}

So because an element in the layering matrix is undefined, ultimately a value for v will be undefined (since this is the value in the matrix). Then g.node(v) will be essentially g.node(undefined) and the output of that is undefined. I assume the node() method is looking up a node by its id, and since the id is undefined, it returns undefined. At that point g.node(v).order throws and exception since you are trying to access the order property of undefined.

[j6k4m8]

Ah — so just some of the node-lookups are failing. That's what I meant! Sorry, I misspoke — but you still answered my question :)

I'm trying to figure out a similar problem right now; I think that there must be some discontinuity (incompatible version updates between libraries, perhaps?) where dagre expects a certain structure to the graph that isn't being fully satisfied by external libraries.

Have you tried making a graph of the same size as your real graph, but comprised of a bunch of the same repeated node (with a different ID)? That'll tell you if it's a structural problem with dagre/Joint or some weird corner-case having to do with the attributes of your graph.

[mmacfadden]

I will have to try that. I have been working on isolating the problem in the source data. I know for example if I take all the edges out of the graph it works just fine. There is a large amount of data so it is somewhat hard to isolate.

[mmacfadden]

Looking here:

dagre/lib/rank/index.js

Line 29 in 7e050f8

function rank(g) {

the rank method states that as a post condition:

 * Post-conditions:
 *
 *    1. Graph nodes will have a "rank" attribute based on the results of the
 *       algorithm. Ranks can start at any index (including negative), we'll
 *       fix them up later.

However after this method is called from the layout method

dagre/lib/layout.js

Line 35 in 7e050f8

time(" rank", function() { rank(util.asNonCompoundGraph(g)); });

The result is that several nodes do NOT have a rank defined. I think this is partially the cause of the above issue.

[mmacfadden]

More information..

Prior to calling the nestedGraph method

dagre/lib/layout.js

Line 34 in 7e050f8

time(" nestingGraph.run", function() { nestingGraph.run(g); });

All the nodes in the graph look something like this:

{
  "0b7c8847-5ad5-4115-b7a0-cee55295a23c": {width: 300, height: 300}
  "0b50f2ad-7697-4392-8a5d-9a2744b9deaa": {width: 300, height: 300}
}

After calling the nestingGraph method several new nodes are added to the graph, that look like this:

{
  "62c2d840-0375-4b24-baf2-4bddba883dbe": {width: 1, height: 1, borderTop: "_bt12391", borderBottom: "_bb12392"},
  "64bd51ba-a559-4b00-9c49-fe8a0d1d9212": {width: 1, height: 1, borderTop: "_bt12379", borderBottom: "_bb12380"}
}

It is these nodes that wind up with no rank after the rank() method.

{
  "cb00a654-4cb8-4bf0-b5c7-73509c33da77": {width: 300, height: 300, rank: -37},
  "cbd9fe77-e741-4ea7-a436-271478396aaa": {width: 1, height: 1, borderTop: "_bt23166", borderBottom: "_bb23167"},
  "cbd0306c-701d-4ff1-818d-1445f4ddef1f": {width: 300, height: 300, rank: -85},
  "cbe818d9-58c3-494d-9685-dd4b3dcbecb9": {width: 300, height: 300, rank: -67},
  "cc84afd3-b37b-4940-ab1d-07f48d148dc9": {width: 1, height: 1, borderTop: "_bt23186", borderBottom: "_bb23187"},
  "cc449908-b667-42b5-a17b-3917edd95d55": {width: 300, height: 300, rank: -1},
  "cd6c78da-b2a6-4b35-8121-ae3c0003fc04": {width: 300, height: 300, rank: -37}
}

Node sure if these are creating the problem directly but seems to be relevant.

[mmacfadden]

One more bit of oddness. In the order(g) {} method the following code exists:

  for (var i = 0, lastBest = 0; lastBest < 4; ++i, ++lastBest) {
    sweepLayerGraphs(i % 2 ? downLayerGraphs : upLayerGraphs, i % 4 >= 2);

    layering = util.buildLayerMatrix(g);
    var cc = crossCount(g, layering);
    if (cc < bestCC) {
      lastBest = 0;
      best = _.cloneDeep(layering);
      bestCC = cc;
    }
  }

On the first run, layering is populated but best is undefined. The first time best gets set is when _.cloneDeep(layering); is called. When setting a breakpoint right after provides some interesting results. layering does not have undefined values in the matrix. However, best does have undefined values. Putting the following watch expressions in the debugger shows this:

best.filter(layer => layer.indexOf(undefined) >= 0).length = 28
layering.filter(layer => layer.indexOf(undefined) >= 0).length = 0

So somehow the deepClone is resulting in arrays with undefined values.

[mmacfadden]

It turns out that they layer has indices that are not set.

[
...
63: "_d80132"
64: "_d80243"
65: "_d80267"
66: "_br85745"
78: "_d80668"
79: "_d80670"
80: "_d80672"
...
]

Lodash is inserting undefineds into the copied array because it does not generate sparse arrays. So the question is how the array winds up being sparse.

[mmacfadden]

Putting this all together here is what is going on in the layout method:

1. The nestingGraph() function creates nodes like {width: 1, height: 1, borderTop: "_bt109526", borderBottom: "_bb109527", minRank: 25, …}
2. There is a call to util.asNonCompoundGraph(g) which is passed to the rank() method. This seems to filter out the nodes added by the nestingGraph() method. Therefore the call to rank() adds a rank all of the nodes except those that look like those created in the nestingGraph() method.
3. Within the order() method:
   1. The initOrder() method creates the initial layering matrix. This matrix has values for all indices, it is not sparse, but it also does not contain the nodes created in nestingGraph.
   2. The first call to assignOrder() method adds an order field to all nodes with a rank. The nodes generated by nestingGraph() do not get an order. However since the layering matrix contains now undefined values, there are no exceptions.
   3. The buildLayerMatrix() iterates over the graph. This method winds up skipping several nodes because several of the nodes do not have ranks. For some reason, the resulting layering matrix is now sparse, missing several indices.
   4. The deepClone() converts the missing indices to undefined values within the layering matrix.
   5. The final call to assignOrder() fails due to the undefined values in the layering matrix. Ultimately on the g.node(v).order = i; call.

So the interplay of the nestingGraph(), rank(), and order() methods is throwing an exception.

[mmacfadden]

Upon further inspection, when initOrder() is called, it looks like all the nodes in the graph get put into ranks and orders, and the layering matrix is completely populated. However, when the sweepLayerGraphs method gets called, things get weird. We wind up with some nodes mapping to the same rank and order, and other rank / order combinations are empty. This is why when buildLayerMatrix is call things are missing.