Title
#devlog-together
l

Luke Persola

08/20/2022, 11:20 PM
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?
11:22 PM
Also that abstract ends on:
The algorithm makes good drawings and runs fast.
😂
s

Scott Antipa

08/20/2022, 11:30 PM
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.
l

Luke Persola

08/21/2022, 1:04 AM
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?
s

Scott Antipa

08/21/2022, 4:43 AM
Knotend supports directed graphs (cycles are ok). It doesn't do compound/nested graphs. There aren't really any restrictions otherwise.
4:48 AM
Dagre doesn't promise this, but from looking at the paper the idea is that dagre mostly cares about setting the rank of the node (in a left to right graph, the rank would be which column the node is placed in). It sets the order (which column the node is in) based on trying to minimize edge crossings. But by default it would just order the nodes vertically in the order that you added them to the graph. I do think a complete solution is possible. I really just need to help dagre determine the vertical ordering since the horizontal ordering is determined by the dependencies. So I'm thinking of maintaining an ordering as a list, probably a doubly linked list, based on how nodes are added/deleted. Then I'd use that graph just in the context of ordering sibling nodes vertically. For example if we have a graph:
a -> b1
a -> b2
c -> d
e -> f
Then say we add a new node
b3
to the right of
a
. The main bit of information we would need is the ordering of [b1, b2, b3] so that the new
b3
node is placed at the bottom vertically of those children.
4:50 AM
That's a pretty simple case. It gets more complex when you start deleting nodes in the middle of the graph and then have to decide how to stitch the graph together and also update that ordering. But I think overall since the only requirement is to properly maintain the order for nodes that are siblings, it should be doable.
10:40 PM
I ended up using a list to represent relative ordering between nodes. You can see it printed in the console. Basically, the position in that list is what determines vertical ordering of siblings in the graph. Every graph edit then needs to update this list as well. So adding a new child do node
A
means you find
A
in the list and insert the new node after it. Deleting nodes removes from the order list, etc. A huge benefit of this is now I can support adding nodes in between others, whereas previously they would be added to the bottom of the set of siblings. Eg the
between 1 and 2
node is added with the shortcut to add a sibling.