4

I am trying to construct a function in Tex called \rootedtree, which takes in a a tree written in the notation of J. Butcher and then prints out the corresponding tree in TikZ.

For instance consider the trees here: http://alexander.lundervold.com/talks/ICMAT_oct2014/assets/grafting.jpg , just ignore the operations, we do not need them here. From left to right, the corresponding notation is

[*] 
[*,*]
[[*,*],*,*]

etc.

So the idea is that * corresponds to a node and the square brackets binds the nodes/trees inside to the same root. For the computer scientists out there, note that the root are downwards and the leaves are upwards.

So ultimately I want a something like this

\rootedtree([*,*])

which then draws the corresponding tree in TikZ, where the roots are evenly distributed upwards, e.g. if there is a single child, then it points directly up (90 degrees on both sides), if there are two childs then there are 60 degrees between them and 60 degrees to level on both sides.

I have close to none experience programming things in Tex myself and therefore have no idea how to get started. Any help is highly appreciated. Are there any other packages, where there is something like this and I do not have to start from scratch?

  • Does this help? – cfr Dec 16 '15 at 17:20
4

I made a package for this a while a go. See my blog. My solution uses PythonTeX. You can typeset forests and trees and the result will look like this:

Example forests and trees

The package is based on the following recursive definition of beautiful trees and forests (from my blog):

A forest is beautiful if:

  • Each subtree is beautiful.
  • The horizontal distance between two adjacent subtrees is one unit.
  • The roots of the subtrees are spaced out as evenly as possible.

A tree is beautiful if:

  • The forest you get by removing the root of the tree is beautiful.
  • The vertical distance between the root and the next level of nodes is one unit.
  • The horizontal position of the root is the median of the horizontal positions of the roots of the subtrees.

In addition:

  • The tree consisting of a single node is beautiful.

The format differs from what is specified in the question, but it is very compact and should be easy to use. For example, the last example in the picture above is generated by

\forest{b,b,b[b,b[b,b,b]],b,b[b,b,b[b,b]],b[b]}

Here, b is a black node, and b[...] means that all the forests in the bracket are connected to the black node in front of it, with the black node as parent. Forests are specified by simply separating them with commas.

Colour (as in the top-right example) can be added by using

\newnodecolor{r}{red}
\newnodecolor{w}{white}
\forest{b[w,r]}

The package is hosted on GitHub.

  • But the package is not on CTAN? Or is it? – cfr Dec 16 '15 at 18:01
  • 2
    This looks like a nice package. Perhaps you should consider submitting it to CTAN so that it will be available more widely. Could you also post the source code that you used to generate the image rather than just a link to your blog? Links die, and the StackExchange model strives to keep information for the longer term. – Alan Munn Dec 16 '15 at 18:02
  • No, the package is not on CTAN (yet). I'll consider submitting it, but for now, it's available on GitHub. I've updated the answer with a few code examples and usage information. – Håkon Marthinsen Dec 16 '15 at 18:24
  • This is a very nice solution! As you now add color, would it also be possible to add a number next to the node in the same manner as you know color to it? So \forest{1[3,4]} would generate a tree like your example but with the numbers next to node accordingly? – Nicky Mattsson Dec 16 '15 at 21:20
  • Labeled nodes is a nice idea, however, I think that the label text would become too large compared to the forest. At least for normal magnification of the trees and forest. I did some experiments, but even with \tiny labels, the label text becomes much larger than the nodes themselves. Take a look at this test PDF file. Here you can see that the forests themselves are already quite small compared to the surrounding text under standard magnification. – Håkon Marthinsen Dec 16 '15 at 22:51
4

Something like this?

rooted trees

Adaption from my earlier answer:

\documentclass{article}
\usepackage{forest}
\forestset{
  */.style={
    delay+={append={[]},}
  },
  rooted tree/.style={
    for tree={
      grow'=90,
      parent anchor=center,
      child anchor=center,
      s sep=2.5pt,
      if level=0{
        baseline
      }{},
      delay={
        if content={*}{
          content=,
          append={[]}
        }{}
      }
    },
    before typesetting nodes={
      for tree={
        circle,
        fill,
        minimum width=3pt,
        inner sep=0pt,
        child anchor=center,
      },
    },
    before computing xy={
      for tree={
        l=5pt,
      }
    }
  }
}
\usepackage{xparse}
\DeclareDocumentCommand\rootedtree{o}{\Forest{rooted tree [#1]}}
\begin{document}
\[
  \rootedtree
  [*]
  \,
  \rootedtree
  [*,*]
  \,
  \rootedtree
  [[*,*],*,*]
\]
\end{document}
  • Yes definitely, as Håkon Marthinsens answer is more general I have accepted his answer (as I can unfortunately not accept two answers). But still thank you so much for the help and +1. – Nicky Mattsson Dec 16 '15 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.