I'm working on a way to better preserve order of sibling nodes in my directed graph editor. I'm wondering if anyone's familiar with common data structures for this kind of stuff. Maybe from the text editing world. I use a customized fork of dagrejs for auto layout. You can see the difference between videos 1/2 below where my first solution has made things better. I'm basically using time stamps to track the order in which nodes were added to the graph. And transfer those timestamps to adjacent nodes on deletions/edits.

Can you say a bit more about what capabilities dagrejs provides you with and how your timestamp solution relates to them? I haven’t seen dagrejs before, but it looks like their priority is more getting an individual graph rendering to have nice properties like minimizing edge crossings rather than consistency across renderings. From the abstract of the first paper they cite:

The second pass sets the vertex order within ranks by an iterative heuristic incorporating a novel weight function and local transpositions to reduce crossings

So you’re able to override their ordering with your timestamp ordering?

Thanks for taking a look! Yes you're right, dagre doesn't try to support incremental rendering, or interactive rendering. It just takes a DAG (graphlib) and assigns x,y coords to all the nodes. It also gives you splines for drawing the edges. It's widely used for these kinds of applications, despite it being no longer maintained (because it's feature complete). The order that you add nodes to your graph will determine part of the layout. For example if your code is:

graph = new dagre.Graph() // pseudo code
graph.setNode("a");
graph.setNode("b");
graph.setNode("c"):
graph.setNode("d");
graph.setEdge("c", "d");

Then your resulting graph will be rendered like:

a
b
c -> d

mermaid js uses the same layout algo so it can be handy to experiment there: mermaid.live. (And my tool exports to mermaid). Basically you can see the order of the nodes in mermaid since its a DSL, text to diagram thing. The issue I have is that I need to tell dagre the correct ordering of nodes in order to maintain the order of sibling branches. Like in the first video above you can see that deleting "D1" causes the whole D branch to be re-arranged at the bottom. This is because originally I was creating the dagre graph by ordering the nodes based on their created at time stamps, which is pretty naive but works most of the time. However the user never edits their graph by just always appending to it, top to bottom. So the created at time doesn't end up corresponding with the actual intent. For example in the a,b,c,d graph above, if after making that initial graph we added a node

e

from

a -> e

then e is going to have a late created at time, but conceptually it needs to be ordered at the very beginning of the graph so you would get a layout of:

a -> e
b
c -> d

So my attempt today is to move away from ordering by createdAt and find a different way. So far its a combination of two things: 1. I add the earliest nodes first in a depth first way by adding the node, then traversing the graph from that node and adding its predecessors/successors. Eg in the graph above we would add

a

and

e

nodes first because a is the earliest, and it's connected to e. This has been a lot better, but I think there's a better way that would capture more information than simple time stamp can. I'm thinking of using a tree (probably) structure to capture the ordering of nodes relative to other siblings. But I haven't come up with a design for this yet. Eventually I want to be able to support letting the user re-order nodes (vertically) or insert nodes above/below other nodes. Which right now isn't really possible with the timestamp approach.

I rolled it around in my head a bit but don’t have any suggestions at the moment. What graphs does/will knotend support? All DAGs?

The order that you add nodes to your graph will determine part of the layout.

Does dagre make any specific promises? And in general, do you think a complete solution is possible, or just looking for a good heuristic?

Knotend supports directed graphs (cycles are ok). It doesn't do compound/nested graphs. There aren't really any restrictions otherwise.