reingold@emr.cs.uiuc.edu (Edward M. Reingold) (01/11/91)
I'm interested in tree drawing macros. I have a set that uses PiCTeX and Latex and I know about Bruggermann-Klein and Wood's work. Please respond by email; I do not ordinarily read these notes. -- Professor Edward M. Reingold reingold@cs.uiuc.edu Department of Computer Science (217) 333-6733 University of Illinois at Urbana-Champaign 1304 W. Springfield Ave. Urbana, IL 61801-2987 USA
reingold@emr.cs.uiuc.edu (Edward M. Reingold) (03/03/91)
Some time ago I asked for any existing tree-drawing macros to be sent to me.
The response was enthusiastic, but none of what I received filled the bill, so
a colleague and I cooked up our own set, based on PicTeX. Here they are; we'd
appreciate any comments.
--------------------tree.tex for use with PicTeX------------------------------
% Binary tree drawing in LaTeX using the PiCTeX macros.
%
% Edward M. Reingold (reingold@cs.uiuc.edu)
% Nachum Dershowitz (nachum@cs.uiuc.edu)
%
\typeout{Binary Tree Macros. Released 18 Jan 1991.}
%
% These macros are in the public domain. You may use them and copy them at
% will, provided you retain the authorship information.
%
%
% USAGE: \tree[optional root symbol]{left subtree}{right subtree}
%
% For example,
%
% \tree[X]
% {\setdots\tree[Z]
% {\setsolid\tree[Y]{a}{}}
% {\setsolid\tree{c}{d}}}
% {\tree
% {\tree{}{f}}
% {\tree{g}{h}}}
%
% The root symbol and leaves can be anything you can construct in LaTeX
% or PiCTeX. The trees constructed can be used in any context in LaTeX
% or PiCTeX. That is, you can have, say, tables of trees of equations.
%
%
% WARNINGS: Do not use the tilde (~) as the first character in any subtree!
% Load these macros BEFORE the PiCTeX macros in the documentstyle.
%
%
% PARAMETERS: Feel free to change the following tree drawing parameters;
% these parameters can be reset even in the middle of a tree.
%
\newdimen\subtreesep \subtreesep=10pt % Distance between nonempty subtrees
\newdimen\levelsep \levelsep=30pt % Distance between successive levels
\def\nodesymbol{$\bullet$} % Default symbol for an internal node
% Tree edges connecting to the default node symbol
% will go to it's center. Other tree edges will be
% chopped off at a node's bounding box.
%
%
% Here's an example that changes the parameters in the middle of the tree:
%
% \subtreesep=15pt\levelsep=40pt
% \tree[\fbox{\subtreesep=5pt\levelsep=13pt\tree[o]{a}{a}}]
% {b}{b}
%
%
% You can get triangular subtrees by using \triangle which has the format
%
% \triangle[optional apex label]{width}{height}
%
% For example,
%
% \tree{\triangle[A]{2\subtreesep}{2\levelsep}}
% {\tree{\triangle{\subtreesep}{\levelsep}}
% {\tree{\fbox{}}
% {\fbox{}}}}
%
%
% Don't fiddle with the stuff that follows; it's fairly delicate.
%
% Working variables
%
\newdimen\halfsubtreesep % half the subtree separation
%
\newdimen\leftwd % width of left subtree
\newdimen\rightwd % width of right subtree
%
\newcount\rootbullet % flag indicating if root is the default bullet
\newdimen\rootwd % width of root
\newdimen\rootht % height of root
\newdimen\rootdp % depth of root
%
\newcount\leftrootbullet % flag indicating if left root is the default bullet
\newdimen\leftrootht % height of left subtree's root
\newdimen\leftrootwd % width of left subtree's root
\newcount\rightrootbullet% flag indicating if right root is the default bullet
\newdimen\rightrootht % height of right subtree's root
\newdimen\rightrootwd % width of right subtree's root
%
\newdimen\root % distance of root midpointfrom left edge of tree
\newdimen\leftroot % distance of root midpoint of left subtree
% from left edge of tree
\newdimen\rightroot % distance of root midpoint of right subtree
% from left edge of tree
%
\newcount\leafnode % flag indicating if subtree just placed is a leaf
%
\newdimen\rootxpos % x-cooordinate of the root midpoint
\newdimen\leftrootpos % position of the root of the left subtree
\newdimen\rightrootpos % position of the root of the right subtree
\newdimen\leftpos % position of the NE corner of the left subtree
\newdimen\rightpos % position of the NW corner of the right subtree
%
\newbox\rootnode % the root node, as placed
\newbox\leftsubtree % the left subtree, as placed
\newbox\rightsubtree % the right subtree, as placed
%
\newdimen\xa % (\xa,\ya) = coordinates of the point on the root
\newdimen\ya % node at which to connect the line to a child
\newdimen\xb % (\xb,\yb) = coordinates of the point on the child
\newdimen\yb % at which to connect the line to the parent
%
\let\ifnextchar=\@ifnextchar%
\def\tree{\ignorespaces%
\def\tree{\ifnextchar[{\treey}{\treex}}%
%
\setdimensionmode%
\setlinear%
%
\@ifnextchar[{\treey}{\treex}%
}%
%
\long\def\treex#1#2{\itree{#1}{#2}{\nodesymbol}} % use default node symbol
\long\def\treey[#1]#2#3{\itree{#2}{#3}{#1}} % use specified node symbol
%
\long\def\itree#1#2#3{\ignorespaces % #1=left, #2=right, #3=root
%
\halfsubtreesep=\subtreesep % Do this calculation for each node so its...
\divide\halfsubtreesep by 2 % ...value can vary throughout the tree
%
\ignorespaces%
%
% Recursively draw nonempty left subtree
%
\ifx ~#1~\ignorespaces%
\else%
\leafnode=1 % Assume left subtree is a leaf
\setbox\leftsubtree=\hbox{#1}\ignorespaces
\leftwd=\wd\leftsubtree%
\leftroot=\root%
\leftrootbullet=\rootbullet%
\leftrootht=\rootht%
\leftrootwd=\rootwd%
\ifnum \leafnode=1%
\leftroot=\leftwd%
\divide\leftroot by 2%
\leftrootbullet=0%
\leftrootht=\ht\leftsubtree%
\advance\leftrootht by \dp\leftsubtree%
\leftrootwd=\leftwd%
\fi%
\fi%
%
% Recursively draw nonempty right subtree
%
\ifx ~#2~\ignorespaces%
\else%
\leafnode=1 % Assume right subtree is a leaf
\setbox\rightsubtree=\hbox{#2}\ignorespaces%
\rightwd=\wd\rightsubtree%
\rightroot=\root%
\rightrootbullet=\rootbullet%
\rightrootht=\rootht%
\rightrootwd=\rootwd%
\ifnum \leafnode=1%
\rightroot=\rightwd%
\divide\rightroot by 2%
\rightrootbullet=0%
\rightrootht=\ht\rightsubtree%
\advance\rightrootht by \dp\rightsubtree%
\rightrootwd=\rightwd%
\fi%
\fi%
%
% In the case of empty subtrees, give artificial values for those empty
% trees so that the later calculations are done properly.
%
\ifx ~#1#2~\ignorespaces % Both subtrees empty
\rightroot=0pt%
\leftroot=-\halfsubtreesep%
\leftwd=-\halfsubtreesep%
\else\ifx ~#1~\ignorespaces % Left subtree empty, right subtree not empty
\leftroot=\rightroot%
\advance\leftroot by -\subtreesep%
\leftwd=-\subtreesep%
\else\ifx ~#2~\ignorespaces % Right subtree empty, left subtree not empty
\rightroot=\leftroot%
\advance\rightroot by -\leftwd%
\fi\fi\fi%
%
% With the subtrees done, now do the root node
%
\setbox\rootnode=\hbox{#3}\ignorespaces%
\global\rootwd=\wd\rootnode%
\global\rootht=\ht\rootnode%
\global\advance\rootht by \dp\rootnode%
\ifx \nodesymbol#3\ignorespaces%
\global\rootbullet=1%
\else\ignorespaces%
\global\rootbullet=0%
\fi%
%
% Find distance of the root midpoint from left edge of the tree
%
\global\root=\leftroot%
\global\advance\root by \rightroot%
\global\advance\root by \leftwd%
\global\advance\root by \subtreesep%
\ifdim \root<\rootwd \global\root=\rootwd \fi%
\global\divide\root by 2%
%
% Indicate this root and all its ancestors are not a leaves
%
\global\leafnode=0%
%
% Find positions of the root and those of the roots of the subtrees
%
\leftrootpos=\leftroot%
\advance\leftrootpos by -\leftwd%
\advance\leftrootpos by -\halfsubtreesep%
%
\rightrootpos=\rightroot%
\advance\rightrootpos by \halfsubtreesep%
%
\rootxpos=\leftrootpos%
\advance\rootxpos by \rightrootpos%
\divide\rootxpos by 2%
%
\leftpos=0pt%
\advance\leftpos by \leftrootht%
\divide\leftpos by 2%
%
\rightpos=0pt%
\advance\rightpos by \rightrootht%
\divide\rightpos by 2%
%
% Now the root is a box of width \rootwd and total height \rootht, centered
% at (\rootxpos,\levelsep); the root of the left subtree is a box of
% width \leftrootwd and total height \leftrootht, centered at
% (\leftrootpos,0); the root of the right subtree is a box of width
% \rightrootwd and total height \rightrootht, centered at (\rightrootpos,0).
%
%
\beginpicture
%
\put {\box\rootnode} at {\rootxpos} {\levelsep} % Draw the root
%
\ifx ~#1~\else % Draw the left subtree
\put {\box\leftsubtree} [rt] at {-\halfsubtreesep} {\leftpos}
\xa=\rootxpos%
\ya=\levelsep%
\ifnum\rootbullet=0%
\chop{\rootxpos}{\levelsep}{-\rootwd}{\rootht}{\leftrootpos}{0}%
{\xa}{\ya}%
\fi%
\xb=\leftrootpos%
\yb=0pt%
\ifnum\leftrootbullet=0%
\chop{\leftrootpos}{0}{\leftrootwd}{-\leftrootht}{\rootxpos}{\levelsep}%
{\xb}{\yb}%
\fi%
\plot {\xa} {\ya} {\xb} {\yb} /%
\fi%
%
\ifx ~#2~\else % Draw the right subtree
\put {\box\rightsubtree} [lt] at {\halfsubtreesep} {\rightpos}
\xa=\rootxpos%
\ya=\levelsep%
\ifnum\rootbullet=0%
\chop{\rootxpos}{\levelsep}{\rootwd}{\rootht}{\rightrootpos}{0}%
{\xa}{\ya}%
\fi%
\xb=\rightrootpos%
\yb=0pt%
\ifnum\rightrootbullet=0%
\chop{\rightrootpos}{0}{-\rightrootwd}{-\rightrootht}{\rootxpos}%
{\levelsep}{\xb}{\yb}%
\fi
\plot {\xa} {\ya} {\xb} {\yb} /%
\fi%
%
% Draw the bottom of the triangle, when appropriate.
%
\ifx#1. \ifx#2. \plot {\leftrootpos} {0pt} {\rightrootpos} {0pt} / \fi\fi%
%
\endpicture%
}%
%
\long\def\triangle{\ifnextchar[{\triangley}{\trianglex}}%
\long\def\trianglex#1#2{\itriangle{#1}{#2}{}} % use empty apex symbol
\long\def\triangley[#1]#2#3{\itriangle{#2}{#3}{#1}} % use specified apex symbol
\long\def\itriangle#1#2#3{% A triangle #1 wide and #2 high, #3 at apex
\subtreesep=#1%
\levelsep=#2%
\tree[#3]{.}{.}%
}%
%
\newcount\x% Scratch counters used in the computations of \chop
\newcount\y% to find the location on the border of a node's bounding
\newcount\a% box at which to attach a line aimed at a target point
\newcount\b% from the center of the box.
\newcount\c%
\newcount\d% It would be better to do all these calculation in dimen's
\newcount\e% istead of counters, but so many dimen's are used above
\newcount\f% that to do so would make running out dimen's very probable.
\newcount\g%
\newcount\h% Forgive us for not explaining the following computations; they're
\newcount\l% based on elementary analytical geometry.
%
\def\chop#1#2#3#4#5#6#7#8{\ignorespaces%
% (#1,#2) = coordinates of center of bounding box
% #3 x #4 = width x height of bounding box
% (#5,#6) = coordinates of target point
% (#7,#8) = coordinates of computed intersection
% point
%
\a=#1\divide \a by 10000% Scale down to prevent arithmetic overflow.
\b=#2\divide \b by 10000%
\c=#3\divide \c by 10000%
\d=#4\divide \d by 10000%
\e=#5\divide \e by 10000%
\f=#6\divide \f by 10000%
%
\l=-\f\advance\l by \b%
%%
\y=-\d%
\divide \y by 2%
\advance\y by \b%
%%
\g=\c%
\divide \g by 2%
\advance\g by \a%
%%
\x=-\a%
\advance\x by \e%
\multiply\x by \d%
\divide\x by \l%
\divide\x by 2%
\advance \x by \a%
%%
\count255=-\a%
\advance\count255 by \e%
\multiply\count255 by 2%
\h=-\c%
\multiply \h by \l%
\divide \h by \count255%
\advance \h by \b%
%
\ifnum #5>#1%
\ifnum\x>\g\else\g=\x\h=\y\fi%
\else%
\ifnum\x<\g\else\g=\x\h=\y\fi%
\fi%
\multiply\g by 10000% Scale back up
\multiply\h by 10000%
\global#7=\g sp%
\global#8=\h sp%
}%
--
Professor Edward M. Reingold reingold@cs.uiuc.edu
Department of Computer Science (217) 333-6733
University of Illinois at Urbana-Champaign
1304 W. Springfield Ave.
Urbana, IL 61801-2987 USA