# How to automatically draw a graph in LaTeX

clarification: when I say "graph", I mean the computer science term.

I want to draw a full binary tree of h height. It means that there's one root with two sons, each son has two sons and so forth.

Is there a way to make LaTeX (with tikZ for example, but any other way will do) draw a full binary tree of a given h height without manually drawing each node? This should also allow me to write on the edges and on the leaves.

Thanks.

-
Is there a reason that you tagged this with lyx? Because your question doesn't mention LyX at all. (Also, it somewhat hurts to hear that 'graph' is a 'computer science term'. Graph theory goes at least back to Euler.) –  Caramdir Nov 30 '10 at 18:42
I'm using LyX, it might be relevant - I have no idea. –  Amir Rachum Nov 30 '10 at 19:08
Lyx does not seem relevant here, so I've removed the tag –  Joseph Wright Nov 30 '10 at 19:18
a beautiful tree can be made by the package ctan.org/tex-archive/graphics/tree .It is aimed at linguists, but I guess both computer scientists as well as mathematicians can be permitted to use it! With John's full denunciation of himself in the sample! –  Yiannis Lazarides Nov 30 '10 at 19:49
@Yiannis: I'd recommend qtree, along with tikz-qtree‌​, instead of that; I demonstrated it in another answer. Its biggest advantage is that you don't have to preprocess your LaTeX source (ick); it also generalizes to TikZ if you want it to. Again aimed at linguists, but really should be more widely known and used. I don't think it's as automatic as what Amir wants, though. –  Antal S-Z Nov 30 '10 at 20:18

Here's an admittedly hackish solution I just whipped up using TikZ:

\makeatletter
\def\bt@parent@index#1{\count0=#1\typeout{c01: \the\count0}\advance\count0 by -1\typeout{c02: \the\count0}\divide\count0 by 2\typeout{c03: \the\count0}\the\count0}
\newenvironment{binarytree}[1]{
\begingroup
\newcount\totaldepth\totaldepth=#1
\def\edge##1##2{\expandafter\edef\csname bt@edge##1\endcsname{##2}}
\def\leaf##1##2{\expandafter\edef\csname bt@leaf##1\endcsname{##2}}
}{
\newcount\rowlength % The number of nodes in the current generation of the tree
\rowlength=1
\newcount\numnodes\numnodes=0
\pgfmathparse{2^(\the\totaldepth)}
%% Each node will be labeled as node#', where # is its index.  The nodes are indexed as if they were in an Ahnentafel list.
\newcount\parent
\begin{tikzpicture}
\foreach \depth in {1,...,\the\totaldepth} {
\foreach \i in {1,...,\the\rowlength} {
\pgfmathparse{(\the\numnodes - 1) / 2}
\parent=\pgfmathresult
\ifnum\parent=\numnodes
%% Special case for the root node of the tree
\node[fill,circle,inner sep=2pt] at (0,0) (node\the\numnodes) {};
\else\pgfmathparse{int(mod(\i,2))}\ifnum\pgfmathresult=1
%% This is the first node of a subtree's generation
\node[fill,circle,inner sep=2pt] at ([yshift=-1cm,xshift=-0.7\nodespread] node\the\parent) (node\the\numnodes) {};
\else
%% This is a node in the middle of a generation
\count0=\the\numnodes
\fi\fi
\ifnum\parent<\numnodes
%% Draw the edge to the parent
\draw (node\the\parent) -- node[sloped,above] {\csname bt@edge\the\numnodes\endcsname} (node\the\numnodes);
\fi
\ifnum\depth=\totaldepth
%% We are drawing a leaf, so see if it has a label
\node[below of=node\the\numnodes] (leaf\the\numnodes) {\csname bt@leaf\the\numnodes\endcsname};
\fi
}
\global\multiply\rowlength by 2
}
\end{tikzpicture}
\endgroup
}
\makeatother


You'll have to tweak it a bit to get the desired spacing between nodes.

Just stick that code that the top of your document (or in a new .sty). Then you can use it like this:

\begin{binarytree}{3} %% The "3" here is the depth of the tree
\edge{1}{First edge.}
\edge{5}{Edge 5.}
\leaf{3}{Leaf 1}
\leaf{4}{Leaf 2}
\leaf{5}{Leaf 3}
\end{binarytree}


The edges and leaves are indexed according to their order in the tree's associated Ahnentafel list. The result should look like this:

-
Amazing, thank you so much! –  Amir Rachum Dec 9 '10 at 12:21

This is more "proof of concept" than a fully working example; the point of it is as follows. Firstly, to show how to build up a tree recursively using a \foreach loop. Secondly, it uses the tree stuff already in TikZ. Thirdly, someone just mentioned the Htree to me and in figuring out how to draw that, I had an answer-in-search-of-a-question and it occurred to me that with a slight modification, the routine for drawing the H-tree could be adapted to a full binary tree. What's missing is the labelling facilities, though these could be added in without too much difficulty, I'm sure.

Here's the results, first the H-tree:

and then the binary tree:

And now the code:

\documentclass{standalone}
\usepackage{tikz}

\makeatletter

\tikzset{
htree leaves/.initial=2,
sibling angle/.initial=20,
htree level/.initial={}
}

\def\htree@growth{%
\pgftransformrotate{%
(\pgfkeysvalueof{/tikz/sibling angle})*(-.5-.5*\tikznumberofchildren+\tikznumberofcurrentchild)}%
\pgftransformxshift{\the\tikzleveldistance}%
\pgfkeysvalueof{/tikz/htree level}%
}
\tikzstyle{htree}=[
growth function=\htree@growth,
sibling angle=180,
htree level={
\tikzleveldistance=.707\tikzleveldistance
\pgfsetlinewidth{.707*\the\pgflinewidth}
}
]

\tikzstyle{btree}=[
growth function=\htree@growth,
sibling angle=60,
htree level={
\tikzleveldistance=.55\tikzleveldistance
\pgfsetlinewidth{.707*\the\pgflinewidth}
}
]

\begingroup
\toks@\expandafter\expandafter\expandafter{\expandafter#1#2}%
\xdef#1{\the\toks@}%
\endgroup}

\newcommand{\htree}[2][]{%
\def\htree@start{\noexpand\coordinate}
\def\htree@end{}
\foreach \l in {0,...,#2} {
\g@addto@macro\htree@start{child foreach \noexpand\x in {1,2} {\iffalse}\fi}
\global\let\htree@start\htree@start
\global\let\htree@end\htree@end
}
\edef\htree@cmd{\htree@start\htree@end;}
\begin{scope}[htree,#1]
\htree@cmd
\end{scope}
}
\makeatother

\begin{document}
\begin{tikzpicture}[
rotate=-90,
yscale=.5
]
\htree[
btree,
level distance=3cm,
line width=8pt,
]{7}
\end{tikzpicture}
\end{document}


It works by building up the appropriate {child foreach \x in {1,2} list. We have to be a bit sneaky about groupings (there may be a sneakier way). The rest is just modified from the trees library in TikZ. I added a hook in to the growth routine so that it was easy to define a style for each level as "some modification of the previous style", instead of having to define styles for each level specifically. Using a different growth function could result in something a little more like the example given in ESultanik's answer - the main point of this answer was to build up the tree using a loop.

-

You could use a combination of grahviz and dot2tex`, in order to generate nice graphs. This combination can produce nice graphs.

-

There is a new library for automatic (or algorithmic, as we call it in the manual) graph drawing in development in the CVS repository of PGF/TikZ. The first serious graph drawing algorithms are currently being worked on (including force-based algorithms, algorithms for layered drawings such as flow charts, and also algorithms for drawing trees).

I don't know about the status of the tree algorithms but let's hope that this feature (and the algorithms I mentioned) will become available with a new PGF/TikZ release sometime in 2011.

-
thanks for the interesting info! –  Amir Rachum May 11 '11 at 14:09