Open mmacfadden opened 6 years ago
More insight, in the order function https://github.com/dagrejs/dagre/blob/7e050f82852c0d1b3c07b914f683d108fa28938b/lib/order/index.js#L29
When the initial layering
matrix is created, the layers do not have undefined in them.
https://github.com/dagrejs/dagre/blob/7e050f82852c0d1b3c07b914f683d108fa28938b/lib/order/index.js#L34
However later on on line 52 the best
variable seems to have layers with undefineds:
https://github.com/dagrejs/dagre/blob/7e050f82852c0d1b3c07b914f683d108fa28938b/lib/order/index.js#L52
How are you building your graphlib.Graph
?
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.
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.
Some more debugging. In one of the calls to this method:
Several elements in the layering array go from string values to undefined.
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.
to clarify, SOME nodes in the graph are undefined and some are not? Or is it all-or-nothing per graph?
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
.
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.
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.
Looking here: https://github.com/dagrejs/dagre/blob/7e050f82852c0d1b3c07b914f683d108fa28938b/lib/rank/index.js#L29 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 https://github.com/dagrejs/dagre/blob/7e050f82852c0d1b3c07b914f683d108fa28938b/lib/layout.js#L35
The result is that several nodes do NOT have a rank defined. I think this is partially the cause of the above issue.
More information..
Prior to calling the nestedGraph method https://github.com/dagrejs/dagre/blob/7e050f82852c0d1b3c07b914f683d108fa28938b/lib/layout.js#L34 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.
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.
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 undefined
s into the copied array because it does not generate sparse arrays. So the question is how the array winds up being sparse.
Putting this all together here is what is going on in the layout method:
nestingGraph()
function creates nodes like {width: 1, height: 1, borderTop: "_bt109526", borderBottom: "_bb109527", minRank: 25, …}
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.order()
method:
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
.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.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.deepClone()
converts the missing indices to undefined values within the layering
matrix.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.
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.
After much work, I have been able to reproduce this issue in dagre directly. There is gist that demonstrates the issue. The graph structure is pretty simple. 23 total nodes, 8 of them are parents / containers, and 15 of them are children. There are only 7 edges. There is a source code file that reproduces the issue as well as a visualization of the graph structure in the gist.
https://gist.github.com/mmacfadden/2c923a6c7209308745296d489289f316
I hit a similar issue, but in my case v
has a value, but g.node(v)
returns undefined.
function assignOrder(g, layering) {
_.forEach(layering, function(layer) {
_.forEach(layer, function(v, i) {
g.node(v).order = i;
});
});
}
edit: I recall i saw that on my browser, but when running in cli, v is undefined. So maybe i looked it wrong.
@mmacfadden thanks to your reproducer and some guesswork i think i found out the problem.
Let me explain, the problems seems to be related to the way lodash
forEach
works, the method util.buildLayerMatrix
builds a matrix, but the orders assigned there (layering[rank][node.order] = v;
) are not always consecutive, so it ends up with a matrix with "holes" between orders.
forEach
methods seems to iterate over these undefined
values in the assignOrder
and thus the reported exception.
See a reproducer of what i mean:
var _ = require("lodash");
var arr = [];
arr[0] = 0;
arr[1] = 1;
arr[4] = 4;
arr[5] = 5;
console.log(arr);
console.log('for var i in arr:');
for (var i in arr) {
console.log(`arr[${i}] = ${arr[i]}`);
}
console.log('_forEach:');
_.forEach(arr, function(v, i) {
console.log(`arr[${i}] = ${v}`);
});
This yields:
[ 0, 1, <2 empty items>, 4, 5 ]
for var i in arr:
arr[0] = 0
arr[1] = 1
arr[4] = 4
arr[5] = 5
_forEach:
arr[0] = 0
arr[1] = 1
arr[2] = undefined
arr[3] = undefined
arr[4] = 4
arr[5] = 5
@j6k4m8 can you take a look at https://github.com/dagrejs/dagre/issues/234#issuecomment-399488074?
If what I say is correct and makes sense (if not, please let me know, thanks!), what do you think the best fix would be? To ignore the undefined in assignOrder
or to remove the gaps by lowering the order?
e.g.
from
arr[0] = 0
arr[1] = 1
arr[4] = 4
arr[5] = 5
to
arr[0] = 0
arr[1] = 1
arr[2] = 4
arr[3] = 5
I tried with forOwn
and forIn
because i saw lodash.forEach docs, but same results.
Note: As with other "Collections" methods, objects with a "length" property are iterated like arrays. To avoid this behavior use .forIn or .forOwn for object iteration.
forOwn:
arr[0] = 0
arr[1] = 1
arr[2] = undefined
arr[3] = undefined
arr[4] = 4
arr[5] = 5
forIn:
arr[0] = 0
arr[1] = 1
arr[2] = undefined
arr[3] = undefined
arr[4] = 4
arr[5] = 5
It seems that util.buildLayerMatrix
is used elsewhere, so it would be better to fix up there.
Hm. I'm not sure what the benefit of having undefined
s in the array is, but I imagine that it'd be better to pass to ranks and remove undefined
s rather than ignoring them; @mmacfadden?
I did something quick to remove the gaps and shifting the order, but other error appeared after that
Error: Not possible to find intersection inside of the rectangle
at Object.intersectRect (/home/josejulio/Documents/opensource/dagre/lib/util.js:107:11)
at /home/josejulio/Documents/opensource/dagre/lib/layout.js:315:30
at arrayEach (/home/josejulio/Documents/opensource/dagre/node_modules/lodash/lodash.js:537:11)
at Function.forEach (/home/josejulio/Documents/opensource/dagre/node_modules/lodash/lodash.js:9359:14)
at assignNodeIntersects (/home/josejulio/Documents/opensource/dagre/lib/layout.js:302:5)
at /home/josejulio/Documents/opensource/dagre/lib/layout.js:93:51
at notime (/home/josejulio/Documents/opensource/dagre/lib/util.js:258:10)
at runLayout (/home/josejulio/Documents/opensource/dagre/lib/layout.js:93:3)
at /home/josejulio/Documents/opensource/dagre/lib/layout.js:25:45
at notime (/home/josejulio/Documents/opensource/dagre/lib/util.js:258:10)
I'm not sure if this is related to the fact that we aren't using connected DAG's as needed by the rank algorithm.
Reproducer of @mmacfadden is:
and the (big) graph (using cose layout) that showed this bug to me is:
It might be related to the lack of connected DAGs, however, I have several other instances of not-connected DAGs that work. In fact, in my reproducer, removing any one node seems to allow it to work.
It might be related to the lack of connected DAGs, however, I have several other instances of not-connected DAGs that work. In fact, in my reproducer, removing any one node seems to allow it to work.
Yes, I have seen the same too, not really sure what the problem might really be, but the fact that the algorithm is for connected DAGs makes me think that it might fail on some non connected DAGs (not sure which ones). We might have to read to check why it needs connected DAGs
@josejulio, just an aside, but as lovely as that graph looks using a directed algorithm like dagre (like a dragon!), using a spring/force algorithm like webcola or d3-force will bring out more of the symmetry. There is so much repeated structure which is getting squished and tangled in order to put everything in ranks, and it doesn't look like the ranks add meaning. (To the contrary, a lot of edges are pointing upward?)
@josejulio, just an aside, but as lovely as that graph looks using a directed algorithm like dagre (like a dragon!), using a spring/force algorithm like webcola or d3-force will bring out more of the symmetry. There is so much repeated structure which is getting squished and tangled in order to put everything in ranks, and it doesn't look like the ranks add meaning. (To the contrary, a lot of edges are pointing upward?)
thanks for the suggestions @gordonwoodhull That's a graph used to test our istio mesh with Kiali, Dagre is giving nice results (we haven't decided for any layout yet, we are testing dagre, cola, cose and others) for our service mesh graph and I was hoping to find out and fix the issue.
Any fix for this yet??
Having the same issue.
Having the same issue.
Having the same issue, but only in a test environment. Not in my box. Can't help but wonder if it has to do with the minified file.
Fixed it on my end by removing the following options from my Uglify compression options:
//unsafe: true,
//unsafe_comps: true,
as well as enabling parallelization (but I don't think this would be related at all). One of the unsafe flags has to be doing something funny that doesn't play well with dagre.
Hopefully this helps someone else ✨ !!
I am also having this issue. I'm using react-create-app
, so it's not easy to adjust build settings per @xnt 's suggestion. Any word on a fix?
I'm using dagre 0.8.5
Thanks a bunch!
EDITS: grammar, included a version number
I am still having this issue in 2021, any progress on this?
I've been using this library for a bit and it was working fine, now i suddenly have this same error. Any progress here?
For people that come here later, at least in my case, I found the issue and it was a really easy fix. When I add a node, I track the host field associated with it and do grouping so that all nodes with the same host are grouped together.
g.setNode(node.id, {label: getLabel(node, view_config["label_components"]), node: node, style: nodeColor, labelStyle: nodeLabelStyle, shape: 'circle'});
g.setNode(node.host, {label: node.host, clusterLabelPos: 'top', style: 'fill:#d3d7e8', node: null});
g.setParent(node.id, node.host);
However, I was doing some dummy data and the host field was blank, i.e. ""
. For whatever reason, this caused that error. I go back and set the host field for my data to be a >0 length string, and everything is working again. Hopefully that'll be enough to help somebody since it doesn't seem like this library is every gonna be updated again :(
Why is there no solution in 2022 😭
@Revadike, it's likely because this project has no maintainer, as announced in the README.
We just ran into this problem (May 2024). I'm a bit surprised this has been an active issue for just over 6 years. Any chance the authoring team can make a decision to Won't Fix or hopefully put in the queue to address.
We just ran into this problem (May 2024). I'm a bit surprised this has been an active issue for just over 6 years. Any chance the authoring team can make a decision to Won't Fix or hopefully put in the queue to address.
we ended up using https://github.com/kieler/elkjs because of this and never looked back.
We moved over to elkjs yesterday.
+1, error happens
For anyone still interested in a workaround for this bug. I did a bit of digging, and it turns out that non-consecutive order
values appear when sorted vertices here do not contain all layer's vertices. As the result some of vertices are left with the indices from the previous sweep, thus breaking the ordering and sometimes creating holes. This happens when resolveConflicts is called from sortSubgraphs with a cyclic constraints graph. It loses some of the vertices in this case because doResolveConflicts
is called on constraints graph's source vertices without incoming edges and walks from there, which excludes vertices trapped in cycles. So one way to fix the problem is to improve addSubgraphConstraints such that it does not create cycles. Another is to simply ignore layerings with broken order, since they are just attempts to improve the layering:
diff --git a/lib/order/index.js b/lib/order/index.js
--- a/lib/order/index.js
+++ b/lib/order/index.js
@@ -41,6 +41,10 @@ function order(g) {
sweepLayerGraphs(i % 2 ? downLayerGraphs : upLayerGraphs, i % 4 >= 2);
layering = util.buildLayerMatrix(g);
+
+ const orderIsBroken = layering.some(layer => layer.length !== Object.keys(layer).length);
+ if (orderIsBroken) continue;
+
var cc = crossCount(g, layering);
if (cc < bestCC) {
lastBest = 0;
I believe this PR https://github.com/dagrejs/dagre/pull/304 proposed something similar to you @ul . Strange that nobody wants to fix this issue from the maintainers.
Also I tried applying your changes,
util.ts:46 Uncaught (in promise) TypeError: Cannot set properties of undefined (setting 'rank')
at r (util.ts:46:19)
at util.ts:39:14
at Array.map (<anonymous>)
at r (util.ts:34:42)
at util.ts:39:14
at Array.map (<anonymous>)
at r (util.ts:34:42)
at Array.forEach (<anonymous>)
at Ff (util.ts:49:15)
at Rn (network-simplex.ts:51:3)
This is still an issue.
@adminy Stack trace is different, it's likely a different issue that was hidden by this one. Do you have a minimal reproducible example? I'm keen to look into it.
Greetings. I am seeing the following error:
After doing some debugging I see the following:
In this function
layer
is an array, seemingly containing strings (maybe id's). When this error crops up, it seems that several items in thelayer
array areundefined
. Thereforeg.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.