5

I want to draw a tree that looks like this (disregarding the two boxes, info regarding the tree heights and the node coloring, only the tree itself):

enter image description here

I know I could draw this tree manually. Is there a way to automate this process? I have found a similar question that the accepted question is close to what I want. However, the tree is perfectly balanced and I would like that "randomness" of some nodes having children and others not, like in the image above. Also, the answer manually adds the node with for.

This is the toy code that was taken from the answer:

\documentclass{article}
\usepackage[utf8]{inputenc}

\usepackage[linguistics]{forest}
\usepackage{graphicx}

\begin{document}

\resizebox{\linewidth}{!}{%
\begin{forest}
symbol/.style={
    draw=black,
    text height=1.5ex,
    text depth=.25ex,
  },
operation/.style={
    symbol,
    rounded rectangle,
  },
  [{}, operation,
    repeat=2{
      append={
        [{},operation,repeat=2{
          append={[{}, operation]}
        }]
      },
    },
    before typesetting nodes={
      for children={
        for children={
          repeat=2{
            append={
              [{}, operation,repeat=2{
                append={[\dots]}
              }]
            },
          },
        }
      }
    }
  ]
\end{forest}
}
\end{document}

Which gives this tree:

enter image description here

Is the tree in the first image possible to be automated in Latex? I'm not looking for an exact replica of it, but similar in the unbalanced, random look of it.

3
  • 1
    Perhaps you could work on the random tree on the title page of the Forest manual. Nov 2, 2021 at 17:14
  • When you say the tree is perfectly "balanced", what properties are you talking about? Nov 7, 2021 at 0:25
  • @jessexknight all nodes at the same height have the same amount of children Nov 7, 2021 at 0:54

1 Answer 1

4
+50

This is an interesting problem. I decided to see what I could produce using asymptote and graphviz programs.

The following asymptote code will write an input file in the dot language (part of graphviz) and then perform a system call to the dot executable to compile the graph. You will need both of these open source programs installed.

Note that the defineChildren function is called recursively until the desired graph level is reached.

//srand(seconds());
int levels = 15;

int getWeightedRandom(int thisLevel) {
    int i = floor(0.5 + unitrand() * 25 - thisLevel/2.0);
    if (i <  4) return 0;
    if (i <  9) return 1;
    if (i < 14) return 2;
    if (i < 18) return 3;
    if (i < 22) return 4;
    return 5;
}

file fout=output("sample.dot");

void defineChildren(string parentName) {
    int thisLevel = length(parentName);
    if (thisLevel >= levels) { return; }
    for (int i = 1; i <= getWeightedRandom(thisLevel); ++i) {
        string childName = parentName + string(i);
        write(fout, parentName + " -> " + childName + ";", endl);
        defineChildren(childName);
    }
}

write(fout, "digraph G {", endl);
write(fout, "node [shape=circle, label=\"\"];", endl);
write(fout, "edge [arrowhead=none];", endl);
defineChildren("0");
write(fout, "}", endl);
system("dot -Tpdf sample.dot -o sample.pdf");

You call this asymptote code with the following command in a windows batch file. The -nosafe flag is required to use the system call that is at the end of the asymptote code.

asy -nosafe sample.asy

enter image description here

If you uncomment the first line, then the random number generator will be seeded with the computer clock and the graph will be different each time you process the code. Sometimes this will result in a blank output because the first node has no children.

I played around with the getWeightedRandom function to try to produce an appealing graph. I incorporated the level (row) of the graph in the random number function because otherwise the graph tends to get very wide at the bottom.

EDIT to give dashed lines at bottom per OP comment:

The following code is modified to make the lowest level of the tree have dashed edges. Also, the bottom row of nodes have a white border color to make them invisible.

//srand(seconds());

int levels = 15;

int getWeightedRandom(int thisLevel)
{
    int i = floor(0.5 + unitrand() * 25 - thisLevel/2.0);
    if (i <  4) return 0;
    if (i <  9) return 1;
    if (i < 14) return 2;
    if (i < 18) return 3;
    if (i < 22) return 4;
    return 5;
}

file fout=output("sample.dot");

void defineChildren(string parentName)
{
    int thisLevel = length(parentName);
    if (thisLevel >= levels) { return; }
    for (int i = 1; i <= getWeightedRandom(thisLevel); ++i)
    {
        if (thisLevel == levels - 1)
        {
            write(fout, "edge [style=dashed];", endl);
            write(fout, "node [color=white];", endl);
        }
        else
        {
            write(fout, "edge [style=solid];", endl);
            write(fout, "node [color=black];", endl);
        }
        string childName = parentName + string(i);
        write(fout, parentName + " -> " + childName + ";", endl);
        defineChildren(childName);
    }
}

write(fout, "digraph G {", endl);
write(fout, "node [shape=circle, label=\"\"];", endl);
write(fout, "edge [arrowhead=none];", endl);
defineChildren("0");
write(fout, "}", endl);
system("dot -Tpdf sample.dot -o sample.pdf");

enter image description here

2
  • 1
    Thanks for your answer, James! This is great. I have never worked with graphviz, do you know if it is possible to draw those dashed edges (preferrably without a node below) at the end of the tree, like in the image I posted? To give the sense of an infinite growing tree. Nov 10, 2021 at 15:16
  • 1
    @ihavenoidea: Thank you. I have added a modified code and image to my answer showing how to do this.
    – James
    Nov 10, 2021 at 15:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .