# Drawing PQ-trees

I need to draw PQ-trees in LaTeX which look like these:

I tried trees in tikz but I had two problems:

• use vertical pointers from children to the parent, if the parent is a rectangle

I'm wondering whether tikz-trees is the easiest way to go or whether you would recommend using something else?

-
To partially shade the rectangles, check out the patterns library. See, for example: tex.stackexchange.com/questions/54358/…. For vertical pointers you want to use the |- syntax. See, for example: tex.stackexchange.com/questions/87454/… –  John Wickerson Jul 29 '13 at 12:00
Thanks, I managed to draw vertical pointers and I tried to define my own pattern - but I don't see how I can partially fill a node by defining my own pattern? –  user1305497 Aug 10 '13 at 20:40

This solution uses the forest package for the placement of the nodes. The advantage here is that they get automatically positioned so that they not overlap.

For the nodes I defined three styles:

• tria for the triangle node, it uses the isosceles triangle shape (you can specify width and height);
• rect for the rectangular node, as an argument, it needs the the number of children it has (including the … node) so that it can be stretched correctly covering its children widthwise;
• circ for the circular node;
• dots for the node with the \ldots in it, the \ldots are given via the content key (a forest key).

Furthermore,

• the patt key is used to pattern only a part of a shape via the path picture option; as I ran intro problems with the TikZ version (both coordinates @aux1 and @aux2 lie in the defaulting center) the (faster and more convenient) PGF version of this works. The argument is <start of the pattern>:<end of the pattern>, which are the horizontal ratio.

• The *| is used to draw only a vertical line to the parent node (this can actually be included in the rect style).

• The values of the normal width and the normal height key is used for the sizes of the nodes.

In the rect style one can find

minimum width=
(#1  )*(\pgfkeysvalueof{/forest/normal width})
+ (#1+1)*(\forestove{s sep})
- (#1  )*(\pgfkeysvalueof{/pgf/outer xsep})


which works very well, though I initially had a different setup

As the rect style gets the number of children #1, the width is set to #1 * width which takes up the total width of the children. So far so good. I initially had here #1 - 1 times the s sep (six children have five spaces between them), though #1 + 1 seems more correct, otherwise the children protrude more or less over the horizontal sides of the rectangle (or the rect is not as wide as its children).

There seems more to be about the spacing between nodes. If one sets different normal width and normal height values this spacing is thrown off. I suspect that the height of nodes somehow have an influence on the s sep, the horizontal spacing between nodes.

### Further improvement …

… can be achieved by automatizing the process. The triangular nodes only come in pairs with the dots between them and are then patterned the same way.

Also, forest has probably the ability to read the number of children in advance so that it can set the width of the rectangle automatically.

## Code

\documentclass[tikz,convert=false]{standalone}
\usepackage{forest}
\usetikzlibrary{shapes.geometric,patterns}
\forestset{
*|/.style={
parent anchor=south,
for descendants={
edge path={
\noexpand\path[\forestoption{edge}]
(!u.parent anchor-|.child anchor) -- (.child anchor)\forestoption{edge label};
}
}
},
normal width/.initial=.5cm,
normal height/.initial=.5cm,
every forest node/.style={
draw,
minimum width=\pgfkeysvalueof{/forest/normal width},
minimum height=\pgfkeysvalueof{/forest/normal height},
inner sep=+0pt,
anchor=south,
},
tria/.style={
every forest node,
shape=isosceles triangle,
shape border rotate=90,
isosceles triangle apex angle=60,
%    isosceles triangle stretches=true
},
rect/.style={
every forest node,
shape=rectangle,
minimum width=(#1)*(\pgfkeysvalueof{/forest/normal width})+(#1+1)*(\forestove{s sep})-(#1)*(\pgfkeysvalueof{/pgf/outer xsep}),
},
rect/.default=3,
circ/.style={
every forest node,
shape=circle
},
dots/.style={
no edge,
content=\ldots,
every forest node,
shape=rectangle,
draw=none,
},
patt/.style args={#1:#2}{
node options={
/tikz/path picture={
\pgfsetfillpattern{north east lines}{black}
\pgfpathrectanglecorners
{\pgfpointlineattime{#1}
{\pgfpointanchor{path picture bounding box}{north west}}
{\pgfpointanchor{path picture bounding box}{north east}}}
{\pgfpointlineattime{#2}
{\pgfpointanchor{path picture bounding box}{south west}}
{\pgfpointanchor{path picture bounding box}{south east}}}
\pgfusepath{fill}
%      \draw[green,ultra thick] (path picture bounding box.north west) -- coordinate[pos={#1}] (@aux1) (path picture bounding box.north east)
%                               (path picture bounding box.south west) -- coordinate[pos={#2}] (@aux2) (path picture bounding box.south east);
%      \fill[draw,pattern=north east lines] (@aux1) rectangle (@aux2);
%%      \fill[blue] (@aux1) circle (2pt);
%%      \fill[red] (@aux2) circle (1pt);
}
}
},
patt/.default=0:1
}
\begin{document}
\begin{forest} for tree={child anchor=north}
[,circ,
[, tria]
[, dots]
[, tria]
[, rect=6, patt=.5:1, *|, alias=XY
[, tria]
[, dots]
[, tria]
[, tria, patt]
[, dots]
[, tria, patt, alias=XX]
]
[, tria, patt]
[, dots]
[, tria, patt]
[, rect=6, patt=0:.5, *|
[, tria, patt]
[, dots]
[, tria, patt]
[, tria]
[, dots]
[, tria]
]
]
% just to show that they are aligned correctly
\draw[opacity=.5] (XY.south east) -- (XX.right corner);
\end{forest}
\end{document}


-