successors() does not return the original order

[coli]

In the demo at http://cpettitt.github.io/project/dagre-d3/latest/demo/interactive-demo.html
The nodes are rendered with respect to the order the node/links are defined. Eg: if A -> D is defined before A -> B, then D will be to the left of B, and vise versa. So the order is stored in the graph(?)

However, graph.successors() does not seem to return the original order?

[cpettitt]

It's is just coincidence. Try adding a node "12345" before and after node A. In both cases on Chrome it ends up before the node A. There are no guarantees on returned order either for the nodes call or for the successors call right now.

[coli]

Hmm, that could be a problem for me, since I need ordering. Would adding it to the nodes() and successors() be all that is needed for ordering to work?

[cpettitt]

For the moment you can still do this on your end by either:

1. Adding an order attribute to your nodes and then sorting based on that attribute. OR...
2. If you need the sort frequently, precompute the order for successors and stash it on the node and for the total order of nodes, precompute and stash on the graph object.

However, even if we do get the nodes ordered it may not do what you want. Can you describe your use case in a little more detail. Superficially it sounds like it may benefit from #112.

[coli]

When I sort the nodes, how do I tell dagre layout the sort order?

For my use case see http://jsfiddle.net/fk2t8/

You can click on the nodes to show/hide the children (except the first child, which is always shown).
The idea is that the original order is preserved.

If you click on the root twice, you'll see the order is all mess up. Clicking on "b", the behavior is exactly what I want.

[coli]

Hey, changing successors to

Digraph.prototype.successors = function(u) {
  this._strictGetNode(u);
  var _outEdges = this._outEdges;
  var _edges = this._edges;
  return Object.keys(this._outEdges[u])
      .map(function(nodeId){return _outEdges[u][nodeId].keys()[0];}).sort()
      .map(function(edgeId){return _edges[edgeId].v })
};

Seems to preserve the order for my use case now.

[cpettitt]

There are a couple subtle issues with this approach, but it may be OK for your purposes:

1. This changes the time complexity of successors, which is potentially called several times, from O(n) to O(n log n)
2. The sort is lexicographical. It works if your nodes are ordered alphabetically, but it will start to behave oddly with anonymous edge ids (e.g. _1, _2, etc.). Once you get up to _10, you'd have [_1, _10, _2, etc...]

We can get away with better time complexity by maintaining a tree internally, but I need to see what kinds of lookups we're doing to see if that works out in our favor.

Also, I meant to reference dagrejs/dagre#112 which I believe would help for your case.

[coli]

So putting a order field on the node and edges should be what it takes? Let me try it

[coli]

Maybe I'm misunderstanding something but putting an order in the nodes seems to have no effect? http://jsfiddle.net/fk2t8/4/

[cpettitt]

Sorry, the comment about adding your own order does no good for dagre drawing. For that you probably need something like dagrejs/dagre#112. Sorry for causing confusion.