dotmatrixis a graphviz layout engine for generating graphs from DOT files into text via monospaced unicode fonts. I’m proud to announce it here in it’s preview debut: today it finally crossed the rubicon on graphviz’s C repo’s test suite (~320 .gv files) with about ~170 rendering “perfectly” (i.e. all nodes and edges with correct topology). The remaining are due to gv embedding HTML or other invalid artifacts.
3 Likes
I’m pretty impressed by how it even handles tricky graphs like Unix tree reasonably
2 Likes
Neat
1 Like
Thank you, both of you! 
I’m pretty impressed by how it even handles tricky graphs like Unix tree reasonably
I am working on a small video/writeup, I will try to finish and post it this weekend
Had no time to write. too many failing test cases needed working through, so here are some notable highlights from the now newly passing test cases and improvements on prior unoptimal layout and routing. At the time of my first post, the repository’s 321 test cases were split between 163 pass / 158 fail.
Now they stand at:
225 success | 14 defect | 57 unsupported | 25 exhaustion
-
defect (14): a valid stock-Graphviz scene using documented-supported semantics fails. The input is fine, the feature is claimed, the render doesn’t happen. A key invariant I chose to establish this is that bounded exhaustion is not valid proof that a graph layout is impossible, i.e. a scene that runs out of a search mechanism. these remain until a genuine computational/representational boundary is proven
-
unsupported (57): the input is valid Graphviz and stock renders it, but the construct is outside dotmatrix’s current vocabulary. These include HTML-like labels, exotic arrowheads, styles beyond the vocabulary, gradient paint, labels that aren’t valid UTF-8, lhead naming a non-ancestor cluster, undocumented rankdir tokens. These are outside of scope.
-
exhaustion (25): exceeded the fixed 60-second per-test timeout, this is deliberately the weakest claim in the taxonomy, and is not proof of impossibility one way or the other. Most of these do have a valid representation.
To make sure I understand:
- is dotmatrix
- an output format (like png or svg)
- a spline type (like curved, true, polyline)
- a complete layout engine (like dot and neato)
- if it is a spline type or complete layout engine, what is the algorithm?
(C) - it is both a layout engine and renderer, registered through the standard plugin API. They are designed as a pair, invoked with -Kdotmatrix -Tdotmatrix. Neither half is a spline type.
The layout and routing space is discretized to the integer lattice ℤ² instead of ℝ² (it’s a cell grid). Nodes occupy cell rectangles, and an edge is simply its path. There’s no Bézier representation whatsoever at any point, as every possible cross/junction/etc. has to resolve to an element of the set of renderable glyphs.
The formatter renders the cell grid as one of 3 render types: either a utf string or truecolor ANSI, as well as a lossless JSON projection of the grid, with this schema:
{
"version": 1,
"columns": 42,
"rows": 17,
"cellAspect": {
"width": { "numerator": 1, "denominator": 1 }, // physical
"height": { "numerator": 5, "denominator": 2 }
},
"glyphs": ["│", "└", "─", "H", …],
"glyphWidths": [1, 1, 1, 1, …],
"colors": ["#fce8c3ff", "#121110ff", …],
"runs": [
{ "x": 3, "y": 0, "length": 7, "glyph": 2, "foreground": 0, "background": 1 },
…
]
}
The two halves are decoupled like the other formats are. -Tdotmatrix accept geometry from any layout engine (-Kdot -Tdotmatrix resamples the dot layout onto the cell grid), and -Kdotmatrix publishes ND_coord/ED_spl so stock renderers (-Tsvg etc.) work against its geometry:
For the routing algorithm: after placement, the grid is rasterized into an occupancy matrix with each element as a set of bit flags+values/refcounters for ports, junctions, crossing, bridges, lanes, etc. encoding:
- hard obstacles: node interiors, labels, and reserved arrow cells
- soft penalties: cluster borders, existing edges, and near-node cells
Edge routing is heading-aware A* over (x, y, heading) states, with step costs encoding monospaced font metrics: a width of 1, with height determined by a font’s em-square value (2.5 in the screenshots). Bends, crossings, color conflicts, and node proximity are fixed-point penalties with a per-axis lower-bound heuristic, and all routing arithmetic is rational/fixed-point for determinism. There are also several transactional specialist planners that handle port assignment, self-loops, parallel-edge lanes, bundling, label placement, crossing bridges, and rip-up-and-reroute.
I’m happy to answer more questions, they are a lot easier to put down in lieu of a writeup, if there’s anything else I can clarify please let me know!
