How to draw the box-and-pointer notation

Help
1

For example:

image

As described in
https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-15.html#%_sec_2.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
     }
}

https://bit.ly/3h9iCfo

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.

3

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.

lisp4_all
lisp4_all1865×315 4.57 KB 

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">&#9679;</TD>
    <TD WIDTH="32" height="32" PORT="r">&#9679;</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">&#9679;</TD>
    <TD WIDTH="32" height="32" PORT="r">&#9679;</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">&#9679;</TD>
    <TD WIDTH="32" height="32" PORT="r">&#9679;</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">&#9679;</TD>
    <TD WIDTH="32" height="32" PORT="r">&#9679;</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">&#9679;</TD>
    <TD WIDTH="32" height="32" PORT="r">&#9679;</TD>
    </TR>
  </TABLE>>];
  c2 [group=CG1 label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR>
    <TD WIDTH="32" port="l">&#9679;</TD>
    <TD WIDTH="32" height="32" PORT="r">&#9679;</TD>
    </TR>
  </TABLE>>];
  c3 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR>
    <TD WIDTH="32" port="l">&#9679;</TD>
    <TD WIDTH="32" height="32" PORT="r">&#9679;</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">&#9679;</TD>
    <TD WIDTH="32" height="32" PORT="r">&#9679;</TD>
    </TR>
  </TABLE>>];
  d2 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR>
    <TD WIDTH="32" port="l">&#9679;</TD>
    <TD WIDTH="32" height="32" PORT="r">&#9679;</TD>
    </TR>
  </TABLE>>];
  d3 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR>
    <TD WIDTH="32" port="l">&#9679;</TD>
    <TD WIDTH="32" height="32" PORT="r">&#9679;</TD>
    </TR>
  </TABLE>>];
  // black-out nil cdr
  d4 [label=<<TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR>
    <TD WIDTH="32" port="l">&#9679;</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
 }
}
4

Sometimes I wonder if we could benefit from making a “simple” grid-based layout engine.

5

Would you say more about your “simple” engine? Is it (approximately):

6

Yes, User explicitly specifies row and column, but maybe allow some symbolic values and constraints.