For example:
As described in
https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-15.html#%_sec_2.2
Look at record nodes. I found them handy while teaching data structures awhile back.
eg. here’s a 2-3 tree:
digraph tree {
node [shape=record,label="<L>|<R>"]
root [shape=none,label=""]
root -> x
x:L:s -> xL:n
x:R:s-> xR:n
xL:L:s -> xLL:n
xL:R:s-> xLR:n
xR:L:s -> xRL:n
xR:R:s -> xRR:n
}
}
There’s some caveats. Trying to force rank and compass points don’t seem to behave like you would expect with record node types. Maybe graphviz is buggy, or there could be some obscure details that I’m missing.
Here is a “pretty close” implementation. Fiddly and wordy, but simple structures look pretty close. Dot does pretty well on ranks (rows) but not so well on files (columns), so more complex structures like those found in section 3.3 of the book (https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-22.html) might be much more difficult.
digraph lisp {
graph [nodesep=.6 splines=line newrank=true] // nodesep will help & hurt
node [shape=plain ]
edge [tailclip=false ] // tail starts in the center
subgraph clusterA {
node [shape=plain ]
edge [tailclip=false ] // tail starts in the center
graph [label="figure 2.2" labelloc=b]
// begin1 - pointer from the left
begin1 [style=invis]
// pair w/ left & right pointers (filled circle in center)
a [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" port="l">●</TD>
<TD WIDTH="32" height="32" PORT="r">●</TD>
</TR>
</TABLE>>];
// terminal
1 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" HEIGHT="32" port="l">1</TD>
<TD WIDTH="32" HEIGHT="32" border="0"></TD>
</TR>
</TABLE>>];
// terminal
2 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" HEIGHT="32" port="l">2</TD>
<TD WIDTH="32" HEIGHT="32" border="0"></TD>
</TR>
</TABLE>>];
{ rank=same begin1 -> a }
a:l:c -> 1:l
{ rank=same a 2 a:r:c -> 2:w}
}
////////////////////////////////////////////////////////////////////
subgraph clusterB {
node [shape=plain ]
edge [tailclip=false ] // tail starts in the center
graph [label="figure 2.3 (part 1)" labelloc=b]
// begin2 - pointer from the left
begin2[style=invis]
// pair w/ left & right pointers (filled circle in center)
b1 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" port="l">●</TD>
<TD WIDTH="32" height="32" PORT="r">●</TD>
</TR>
</TABLE>>];
// pair w/ left & right pointers (filled circle in center)
b2 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" port="l">●</TD>
<TD WIDTH="32" height="32" PORT="r">●</TD>
</TR>
</TABLE>>];
// pair w/ left & right pointers (filled circle in center)
b3 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" port="l">●</TD>
<TD WIDTH="32" height="32" PORT="r">●</TD>
</TR>
</TABLE>>];
{ rank=same begin2 -> b1 }
{rank=same b1 b3}
b1:l:c -> b2
b1:r:c -> b3:w
// two terminals represented by "split" table
bp1 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"><TR>
<TD WIDTH="32" height="32" port="l">1</TD>
<TD WIDTH="8" height="32" border="0"></TD>
<TD WIDTH="32" height="32" PORT="r">2</TD></TR>
</TABLE>>];
b2:l:c -> bp1:l
b2:r:c -> bp1:r
// two terminals represented by "split" table
bp2 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"><TR>
<TD WIDTH="32" height="32" port="l">3</TD>
<TD WIDTH="8" height="32" border="0"></TD>
<TD WIDTH="32" height="32" PORT="r">4</TD></TR>
</TABLE>>];
b3:l:c -> bp2:l
b3:r:c -> bp2:r
}
////////////////////////////////////////////////////////////////////
subgraph clusterC {
node [shape=plain ]
edge [tailclip=false ] // tail starts in the center
graph [label="figure 2.3 (part 2)" labelloc=b]
// begin3 - pointer from the left
begin3[style=invis]
// pair w/ left & right pointers (filled circle in center)
c1 [group=CG1 label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" port="l">●</TD>
<TD WIDTH="32" height="32" PORT="r">●</TD>
</TR>
</TABLE>>];
c2 [group=CG1 label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" port="l">●</TD>
<TD WIDTH="32" height="32" PORT="r">●</TD>
</TR>
</TABLE>>];
c3 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" port="l">●</TD>
<TD WIDTH="32" height="32" PORT="r">●</TD>
</TR>
</TABLE>>];
// terminal - w/ 1 invisible cell
C1 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" HEIGHT="32" port="l">1</TD>
<TD WIDTH="32" HEIGHT="32" border="0"></TD>
</TR>
</TABLE>>];
// terminal
C4 [group=CG1 label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" HEIGHT="32" port="l">4</TD>
<TD WIDTH="32" HEIGHT="32" border="0"></TD>
</TR>
</TABLE>>];
{rank=same c1 C4}
{rank=same c2 c3}
c1:l:c -> c2:l
c1:r:c -> C4:w
c2:l:c -> C1:l
c2:r:c -> c3:w
// two terminals represented by "split" table
cp1 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"><TR>
<TD WIDTH="32" height="32" port="l">2</TD>
<TD WIDTH="8" height="32" border="0"></TD>
<TD WIDTH="32" height="32" PORT="r">3</TD></TR>
</TABLE>>];
c3:l:c -> cp1:l
c3:r:c -> cp1:r
{ rank=same begin3:e -> c1:l:w }
}
////////////////////////////////////////////////////////////////////
subgraph clusterD {
node [shape=plain ]
edge [tailclip=false ] // tail starts in the center
graph [label="figure 2.4" labelloc=b]
// begin4 - pointer from the left
begin4[style=invis]
// pair w/ left & right pointers (filled circle in center)
d1 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" port="l">●</TD>
<TD WIDTH="32" height="32" PORT="r">●</TD>
</TR>
</TABLE>>];
d2 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" port="l">●</TD>
<TD WIDTH="32" height="32" PORT="r">●</TD>
</TR>
</TABLE>>];
d3 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" port="l">●</TD>
<TD WIDTH="32" height="32" PORT="r">●</TD>
</TR>
</TABLE>>];
// black-out nil cdr
d4 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" port="l">●</TD>
<TD WIDTH="32" height="32" PORT="r" BGCOLOR="black"></TD>
</TR>
</TABLE>>];
// terminal
D1 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" HEIGHT="32" port="l">1</TD>
<TD WIDTH="32" HEIGHT="32" border="0"></TD>
</TR>
</TABLE>>];
// terminal
D2 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" HEIGHT="32" port="l">2</TD>
<TD WIDTH="32" HEIGHT="32" border="0"></TD>
</TR>
</TABLE>>];
// terminal
D3 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" HEIGHT="32" port="l">3</TD>
<TD WIDTH="32" HEIGHT="32" border="0"></TD>
</TR>
</TABLE>>];
// terminal
D4 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
<TR>
<TD WIDTH="32" HEIGHT="32" port="l">4</TD>
<TD WIDTH="32" HEIGHT="32" border="0"></TD>
</TR>
</TABLE>>];
{ rank=same begin4:e -> d1:l:w }
{rank=same d1 d2 d3 d4}
{rank=same D1 D2 D3 D4}
d1:l:c -> D1:l
d1:r:c -> d2:w
d2:l:c -> D2:l
d2:r:c -> d3:w
d3:l:c -> D3:l
d3:r:c -> d4:w
d4:l:c -> D4:l
}
}
Sometimes I wonder if we could benefit from making a “simple” grid-based layout engine.
Would you say more about your “simple” engine? Is it (approximately):
- User explicitly specifies row & column (rank & file)
- New feature that effectively does a “snap-to-grid” (https://www.techwalla.com/articles/what-is-snap-to-grid) to tweak a “normal” dot layout
- Something else entirely
Yes, User explicitly specifies row and column, but maybe allow some symbolic values and constraints.