Hacker News Reader

Hacker News

Comment by gilleain | Hacker News Reader

Parent Full thread

gilleain

What do you mean by "textual graph literal"?

View on HN

Textual array literal: [1,2,3]

Textual dict literal: {"a": 1}

Textual graph literal: ???

Heh, one possibility is:

AB 0:1(C),0:2(D)

For a three node graph with edges between vertex 0 and 1, and vertex 0 and 2, vertex labels 'A' and 'B' and edge labels 'C', and 'D'. Not great to parse (as I sadly found), but possible to read.

Textual graph literal: {"a->b", "b->c", "c->a"}

Thinking about the programming language DOT https://en.wikipedia.org/wiki/DOT_(graph_description_languag...

This may be an effective way to express these graphs.

I like DOT a lot. Way back in the day we had a semi-serious proposal to use it in the Puppet configuration language to describe dependencies

Same - DOT is a great way to go from zero to functional in near minimal time. It's also pretty trivial to generate since it's not order dependent, which is great for lightweight automation.

Fine-tuning layout can be a real hassle though, sadly. I haven't found any quick tools for that yet.

The way I approach fine-tuning DOT layout is to add subgroups where it seems appropriate, add a 1px border for the subgroup and see where the layout engine is situating it next to other nearby vertices/edges. Sometimes I may have to put a border around a few subgroups, then attempt to adjust size of vertices and entire area to nudge it to a local minima. Note: I don't attempt to adjust the size of the subgroups, I'm not sure that even works anyway, but maybe it depends on the choice of layout algorithm, too. Padding and other style on the vertex-box may help, too. It's been a few years for me, tbh.

Deciding where the appropriate subgroups are is a bit of an art. Sometimes it's obvious, as in bipartite graphs that are intentionally bipartite. Or, if there is a staged layout like for pipeline architectures. Sometimes it's not obvious even when it seems it should be, like when graphviz really wants to make a certain edge really short. Be ready to backtrack sometimes. Then I usually remove the subgroup border after I'm done, but a few times they have been useful to leave there.

One thing I really like about DOT is that adding hyperlinks to the vertices and edges that translate decently into the compiled output is really nice. I had an oncall dashboard that made liberal use of this feature that I still think back on fondly sometimes.

Can you point to where I can learn more about this ? E.G. an example and explanation exists for hyper link embedding ?

I am especially interested in syntax suitable to be used in creating something to input into https://www.viz-js.com and creation of SVGs with embedded hyperlinks.

If you're using subgraphs, with an edge across subgraph boundaries, it is slightly order dependent - a node will appear in the area it was first mentioned in. If you define all the nodes/subgraphs first and all the edges at the bottom you'd never notice this though.

We've got a couple common graph literals today: Graphviz's "dot" language [0] and the Mermaid language (in part inspired from "dot") [1]. Mermaid is increasingly common in documentation today, given Github supports it almost everywhere Markdown is supported. Parsing dot or Mermaid as embedded literals in another language doesn't seem that complicated (Mermaid's parser is written in JS and already runs anywhere you can run a JS parser).

Though one interesting thing to note here is that both languages are edge list languages and are optimized for algorithms that are useful for edge lists, particularly display/diagramming. That gets back to the article's point that there are other useful representations and those can matter for efficiency of algorithms.

They also can matter for efficiency of a graph literal in a source document. Edge lists are great for sparse graphs, but if you have a dense graph it might be easier to write as a literal with a massive spreadsheet of an adjacency graph. Especially if it can just be a spreadsheet with modern affordances like scrolling and sticky rows/columns and such. There's no perfect answer for "every" graph.

[0] https://graphviz.org/doc/info/lang.html

[1] https://mermaid.js.org/intro/#flowchart

  array{ 1 2 3 }
  dict{ { "a" 1 } }
  graph{ { "a" "b" } { "b" "c" } { "c" "a" } }
  AVL{ { "a" 1 } { "b" 2 } }

Factor has some syntax like this. All you have to do is pass the `{...}` to the prefix (array/dict/graph/AVL) and it knows how to construct one.

https://github.com/factor/factor/blob/master/extra/trees/avl...

Datalog is a strong contender: https://www.learndatalogtoday.org/chapter/1

Reply on news.ycombinator.com