How to automatically draw a graph in LaTeX

Question

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.

Answer 1

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)}
  \newdimen\nodespread\nodespread=\pgfmathresult cm
  %% 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
            \advance\count0 by -1
            \node[right of=node\the\count0,right=\nodespread,fill,circle,inner sep=2pt] (node\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\advance\numnodes by 1
        }
        \global\multiply\rowlength by 2
        \global\nodespread=0.5\nodespread
    }
  \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:

Answer 2

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}
  }
]

\long\def\ge@addto@macro#1#2{%
  \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}
    \g@addto@macro\htree@end{\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.

Answer 3

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

Answer 4

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.