I'm trying to figure out an approach to rendering a DAG in a clean, strict grid based way, and coming up very short.
I'd like to render something that looks like this:
┌───────────┐ ┌───────────┐
┌───│ b │─────▶│ d │
│ └───────────┘ └───────────┘
│
┌───────────┐ │ ┌───────────┐ ┌───────────┐
│ a │◀─┼──▶│ c │──┬──▶│ e │
└───────────┘ │ └───────────┘ │ └───────────┘
│ │
│ │ ┌───────────┐
└──────────────────┴──▶│ f │
└───────────┘
This would be a graph representation of the following dependencies: d(b), b(a), e(c), f(c), c(a). (box(depends on)).
I've researched the "force directed" graphs extensively, but that seems unnecessary as I have a couple of constraints, they should be strictly on a grid and it's not strictly hierarchical.
Alternative approaches for which I have been unable to find adequate documentation on the design of the layout algorithm include various takes on "tree layout", "process layout", "decision layout" (see here)
My ultimate goal is to make a layouting engine for d3 (or similar) which will lay something out that is interactive:
My best working theory so far is:
Walk the graph and find out how many columns there can be, if there are too many for the viewport, consider collapsing items on the leftmost.
Start placing things in columns, place things with the longest chains further right, and smaller or no chains further left.
If something in column has a dependency in the same column, move everything column to the left and allow the dependent to take its place.
Draw the lines, this should be easy if the algorithm only considers broad "grid positions" and not absolute pixel values, it should be easy to draw a connecting line from
A1(cella) toB1(cellc);
A B C
│ │
│ │
┌───────────┐ ┌───────────┐
0 ├───│ b │──┼──▶│ d │
│ └───────────┘ └───────────┘
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─│─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
┌───────────┐ │ ┌───────────┐ ┌───────────┐
1 │ a │◀─┼──▶│ c │──┼──▶│ e │
└───────────┘ │ └───────────┘ │ └───────────┘
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ─ ─ ─ ─│─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
│ │ ┌───────────┐
2 ├──────────────────┼──▶│ f │
└───────────┘
│ │
│ │
Is my approach basically sound? Is there something I'm missing about how to approach this? What reading could anyone recommend on writing layout engines such as this?
