Luke Persola
08/20/2022, 11:20 PMThe second pass sets the vertex order within ranks by an iterative heuristic incorporating a novel weight function and local transpositions to reduce crossingsSo you’re able to override their ordering with your timestamp ordering?
The algorithm makes good drawings and runs fast.😂
Scott Antipa
08/20/2022, 11:30 PMgraph = 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.Luke Persola
08/21/2022, 1:04 AMThe 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?
Scott Antipa
08/21/2022, 4:43 AMa -> 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.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.