5 ms·

Beautiful and impressively fast! I wonder if this could be adapted to work with [1] “dot” graphs through the terminal? [1] https://graphviz.org/doc/info/comman

by gitgud 3y ago

Beautiful and impressively fast! I wonder if this could be adapted to work with [1] “dot” graphs through the terminal? [1] https://graphviz.org/doc/info/command.html https://graphviz.org/doc/info/command.html

josephg 3y ago
I'd love that! For my CRDT work, I stare at a lot of graphs to figure out bugs and optimize. For example, here's the causal graph of changes made to git's Makefile: https://josephg.com/git-makefile.dt.svg https://josephg.com/git-makefile.dt.svg Having a nicer way to render these graphs (and especially show them in the browser) would be delightful!
- kqr 3y ago
  At work I also used to stare at a lot of graphs to figure out bugs. We reuse some of the graphs so we've gone through the effort of recording node positions in metadata and given the graphs a UI where people can drag nodes around and re-save. But it's clunky. I always wished I could invent some domain-specific heuristics to lay out the graph automatically but never took the time to. Manually moving nodes actually worked fairly well for our use case, but it made a mess of text diffs when e.g. nodes were inserted and the position of all subsequent nodes shifted, so as a consequence we had to invent ways to visually diff graphs. Maybe the improved automatic layout would have been easier after all.
- czx111331 3y ago
  Yes, I use a similar approach when debugging some parts of my CRDTs as well. It's very helpful. However, this algorithm is designed specifically for trees. I'm not sure whether I could manage to make it work on DAGs (Directed Acyclic Graphs). It would require some rewrites of the aesthetic rules and designing a new algorithm.
  - ygra 3y ago
    The way we do it at work is to have a separate step before a tree layout that removes non-tree edges, lays out the tree, and then re-insert the edges and calculates separate routes for them. You can play with this here by adding new edges and re-layouting: https://live.yworks.com/demos/layout/layoutstyles/index.html?layout=tree&sample=tree https://live.yworks.com/demos/layout/layoutstyles/index.html... That being said, those edges of course sometimes just won't fit nicely into the general layout. And which edges are "tree" edges and which are "non-tree" edges can of course be debatable. If a graph is very much not a tree, this can be somewhat random, but it works very well for graphs that are mostly trees.
    - czx111331 3y ago
      Thanks for sharing. I might be able to build upon this.
graphviz 3y ago
Nice work.
czx111331 3y ago
Probably not. This algorithm is specifically designed for trees, not graphs.
- gitgud 3y ago
  But trees are a subset of graphs, so it’s probably is possible, right?
jimmySixDOF 3y ago
I would choose Plotly or D3 subset of DAGs or something even like Meanim (3blue1brown) where you can have a proper depth dimension.

by gitgud 3y ago

josephg 3y ago

I'd love that! For my CRDT work, I stare at a lot of graphs to figure out bugs and optimize. For example, here's the causal graph of changes made to git's Makefile: https://josephg.com/git-makefile.dt.svg https://josephg.com/git-makefile.dt.svg Having a nicer way to render these graphs (and especially show them in the browser) would be delightful!

kqr 3y ago
At work I also used to stare at a lot of graphs to figure out bugs. We reuse some of the graphs so we've gone through the effort of recording node positions in metadata and given the graphs a UI where people can drag nodes around and re-save. But it's clunky. I always wished I could invent some domain-specific heuristics to lay out the graph automatically but never took the time to. Manually moving nodes actually worked fairly well for our use case, but it made a mess of text diffs when e.g. nodes were inserted and the position of all subsequent nodes shifted, so as a consequence we had to invent ways to visually diff graphs. Maybe the improved automatic layout would have been easier after all.
czx111331 3y ago
Yes, I use a similar approach when debugging some parts of my CRDTs as well. It's very helpful. However, this algorithm is designed specifically for trees. I'm not sure whether I could manage to make it work on DAGs (Directed Acyclic Graphs). It would require some rewrites of the aesthetic rules and designing a new algorithm.
- ygra 3y ago
  The way we do it at work is to have a separate step before a tree layout that removes non-tree edges, lays out the tree, and then re-insert the edges and calculates separate routes for them. You can play with this here by adding new edges and re-layouting: https://live.yworks.com/demos/layout/layoutstyles/index.html?layout=tree&sample=tree https://live.yworks.com/demos/layout/layoutstyles/index.html... That being said, those edges of course sometimes just won't fit nicely into the general layout. And which edges are "tree" edges and which are "non-tree" edges can of course be debatable. If a graph is very much not a tree, this can be somewhat random, but it works very well for graphs that are mostly trees.
  - czx111331 3y ago
    Thanks for sharing. I might be able to build upon this.

graphviz 3y ago

Nice work.

czx111331 3y ago

Probably not. This algorithm is specifically designed for trees, not graphs.

gitgud 3y ago
But trees are a subset of graphs, so it’s probably is possible, right?

jimmySixDOF 3y ago

I would choose Plotly or D3 subset of DAGs or something even like Meanim (3blue1brown) where you can have a proper depth dimension.