How to update dag without re-creation and also minimize layout shifts?

[coconutlad]

Hi @erikbrinkman,
Hope I'm posting this question in the right place.
I'm using d3-dag for an application where the graph is updated frequently.
It has been very helpful, thank you for creating it and maintaining it so well!
If possible, could you please verify if I'm using d3-dag the right way?

Overview

The app I'm working on displays a DAG to users. They can click on any node and all of the node's children and parents will be added to the graph (if they aren't already in the graph).

In a little more detail:

• An array of edges and an array of nodes are available.
• A dag is created using ConnectOperator (StratifyOperator could be used instead if needed)
• The dag is passed through the Sugiyama layout function
• Using dag.descendants and dag.links, nodes and edges are displayed onto the screen using d3

The issue

Now the issue is with the interaction part:

• Upon clicking a node, ids of its children and parents are fetched via an API call
• The children and parent nodes are created and they're added to the global array of nodes
• Edges connecting the node to its children and parents are added to global array of edges
  // checks are done to avoid duplicates
• A whole new dag is created with this new array of edges
• The dag is passed through the layout function and so on...

Now all of this works fine but I feel like there might be a better way to update the dag without re-creating it. I've tried:

• Storing references to dag.descendants() and dag.links(), appending to those arrays and then passing the dag to the layout function but subsequent calls to dag.descendants don't have the appended elements. Makes sense, it looks like something called proot is being used to store the nodes internally (haven't tried editing that because it's not publicly accessible according to typescript)
• Checking out how other people are creating interactive dags, e.g. https://observablehq.com/@giorgi-ghviniashvili/interactive-d3-dag and https://observablehq.com/@curiouserrandy/initial-interactive-graph-explorer but looks like they're re-creating the dag for every interaction

Why?

I'm looking for an alternative way to update because:

• sometimes there's a significant difference in layout between updates which confuses users (this is the main issue)
• the arrays returned by dag.descendants before and after re-creating the dag don't maintain any particular order between them. This makes it hard to use d3's enter-update-exit philosophy (because the nodes which go to the enter selection aren't the new nodes which were added to the dag).
• there might be some overhead that could be saved by not re-creating the entire graph (I think?)

Minimal example

Here's a small example which mimics a part of the application:
https://codesandbox.io/s/d3-dag-update-graph-6b68gn?file=/src/index.ts
I can add you as an editor if you'd like.

Would it be possible to update the dag without re-creating it? I'm assuming it is one step towards minimizing layout shifts (pardon me if that's an incorrect relation).
I'm open to modifying my copy of the source code if required to tailor it for the application.

Thanks once again for all your work!

[erikbrinkman]

@coconutlad Tanks for the detailed write up and discussion. Sorry it's taken so long for me to respond.

Overall, d3-dag is not well set up for dynamic dags. That was by design to keep things simple, and because without a use case in mind, I didn't want to make design decisions that would harm how it would actually be used. However, I've always wanted to support those use cases. Eventually #79 was posted and that's got us thinking about what dynamic should entail.

After a lot of playing around, there was more emphasis on improving the layout than improving how it generated things dynamically. So far I think every dynamic user does exactly what you describe. They recreate the dag, call sugiyama on it again, and update things.

I encourage you to read through what's been discussed in #79. It may be of specific interest to read though the stuff on dynadag. I'm generally open to implementing and supporting anything that makes sense. By that I mean, if you can propose an API and what it would do, it should be feasible. dynadag is probably a good place to start.

As far as what you're asking about / requesting:

1. layout differences: this will unfortunately take a different layout algorithm, hence why I suggest looking into dynadag to see if that satisfies what you're thinking. If so, we can work to build an api / algorithm around it.
2. They arrays do have an order, it's depth-first search by default, but yes after adding an element, that can change slightly. More importantly, by reconstructing the dags you're going to get new nodes each time. You should be able to fix this by using a key function pointing to the original data. Alternatively, having an api that allows adding nodes to the dag should fix this. Also note you can pass a string to descendants to change the ordering. This doesn't affect data binding though.
3. It should save some overhead, but compared to computing the layout, constructing the dag doesn't really matter.

What that means for next steps:

1. Since the most important thing to you is a stable layout, then an incremental update like dynadag is probably the right way. This should also save resources since it doesn't involve doing a full update. That will probably also require a mutable dag structure, but it will probably make sense to think about that relative to implementing dynadag rather than implementing it on it's own first.

Addressing the things you mentioned in the short term:

1. proots stores all nodes without parents, and only exists if there's more than one node. By design everything necessary for structure is readonly currently.
2. I made dags static so that users couldn't screw up the dag-ness. Since dag properties are more complicated than trees, adding nodes in a way that preserves the dag nature is non-trivial. d3-hierarchy generally recommended the practice of constructing the full tree and then "hiding" pathways. That notion is more complicated for dags, and also not possible for you if you have to make a request each time. That said, if you want to ignore the private typings, then modifying proots for a dag root is how to add a new node with no parents. If you modify a node's children, you want to modify dataChildren and set cachedChildCounts to undefined. I don't recommend this in general, but if you want to get around random ordering in the short term, that should allow you to.

[coconutlad]

Thanks for the detailed answer!
I understand now that re-creating the dag isn't a necessity for a stable layout across interactions.
Using a key function, as you mentioned, has been helpful. With that out of the way I've shifted focus towards layout stability rather than updating the dag.

Looks like dynadag has taken up the same problem and has solved it (there are still a few things in the paper that I feel like could have been elaborated further such as "insert/modify/delete subgraphs", what exactly are they?). They have specified the variables and constraints for each of their optimization problem but somehow none of them make use of previous layout positioning or actually minimize position differences between the previous and current layouts (I think).

In any case, I thought the source code should have answers. I'll have a closer look at it and see what can be used.

There have been other attempts at making stable dynamic graphs. I found this paper that references dynadag and other implementations "Visualizing Evolving Trees". Haven't read through the paper yet but I was going through their GitHub repo which referenced dagre. dagre has an interesting dynamic example linked in their wiki, whose source code seems to be similar to this. I should see how they're handling it too.

Long story short, I'm looking at how other people have solved this problem and how those solutions could be ported to d3-dag. Please do share any resources you think might be interesting!
I realize layout stability is a subset of what's being discussed #79 so I'll try to pitch in there if I'm able to get something working.

What next?

This is a very rough idea and somewhat naive. It could be entirely wrong since I have no experience in linear programming.

• Create custom layering, decross, and coord functions for sugiyama.
• Each function stores a "past state", i.e. whatever it output during the previous call. (e.g. the layers it assigned to nodes in the previous call)
• For future calls they make use of the past state to create an optimized current state that has minimal differences with the past state.
• To do that maybe they could make use of the simplex functions and add extra variables (e.g. layer/position within layer in prev run) and constraints (layerPrev - layerCurrent is minimized) before the solver is called

Not sure how effective it would be. I'll give it a shot if you think it could work. Please feel free to suggest changes!

[erikbrinkman]

Sorry for the radio silence! I think I might have said this a few places, but want to make sure my bases are covered. Thanks for doing all this research. I'll be honest in that I've only skimmed dynadag, so I can't comment about the details, but I can't imagine the steps are too much more complicated than the original layout. My feeling is that the best implementation is going to be something separate that supports manual options like, "add node" and "delete node", however your idea is an interesting one. The original design was not for any of the methods to store state, but the idea of caching the previous call and updating accordingly is an interesting way to fit dynamism into the layout, and should work reasonably well.

I will say, though, that when I looked back at the code to construct the LP it took a long time for me to figure out what was going on, so best of luck with tweaking it the way you want. If you're having trouble, I'm happy to help dive in.

Before I commit too much to this path though, I want to look at dynadag more seriously. Originally I held off because @curiousandy didn't see it as the biggest blocker, and there was an interesting question of why nothing happened to it. That said, it seems worthwhile, so might as well jump in.

[erikbrinkman]

Also, some of the dynamic layouts you reference seem to just be doing a static layout, and then choosing what nodes and links to highlight, which you should be able to do with d3-dag as is.