Drawing an unbalanced infinite growing tree

forestoverleaftrees

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):

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:

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.

Best Answer

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

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");

Related Solutions

[Tex/LaTex] Unbalanced binary tree with forest

There are various things you might mean by 'missing nodes'. A Minimal Working Example of the kind of tree you have, together with an explanation of how you wish to adapt it would be invaluable.

The following example shows three things you might have in mind:

Missing nodes

Node 2 is missing in a first sense: the branch simply continues without stopping to make the node. This creates an 'unbalanced' tree - the angles of the left and right branches are different.

This effect is achieved by altering the distance of node 4's level using l*=2 which doubles it.

Node 6 is missing in a second sense: it is simply empty. It is treated in every way as a proper node but there is no content.

This is straightforward - {} just provides empty content.

Node 9 is missing in a third sense: it causes a gap in the entire structure of branches and nodes. This isolates its children, 17 and 18 from the remainder of the tree.

This uses .phantom style demonstrated in NightRa's answer.

The code:

\documentclass{standalone}
\usepackage{forest}

\begin{document}
\begin{forest}
  [1, for tree=draw
    [4, l*=2
      [7
        [13]
        [14]]
      [8
        [15]
        [16]]
    ]
    [3
      [5
        [,.phantom
          [17]
          [18]]
        [10
          [19]
          [20]]
      ]
      [{}
        [11
          [21]
          [22]]
        [12
          [23]
          [24]]
      ]
    ]
  ]
\end{forest}
\end{document}

[Tex/LaTex] Family tree with two different line style using forest package

You can use the edge key to change the default edge style for the desired childs. A little example:

\documentclass{standalone}
\usepackage[utf8]{inputenc}
\usepackage{palatino}
\usepackage{forest}
\begin{document}
\forestset{
  my tier/.style={% align all nodes on a given level
    tier/.wrap pgfmath arg={level##1}{level()},
  },
}
\begin{forest}
  for tree={
    grow'=0,
    child anchor=west,
    parent anchor=south,
    anchor=west,
    calign=first,
    s sep+=-5pt,
    inner sep=2.5pt,
    edge path={
      \noexpand\path [draw, \forestoption{edge}]
      (!u.south west) +(7.5pt,0) |- (.child anchor)\forestoption{edge label};
    },
    before typesetting nodes={
      if n=1{
        insert before={[, phantom, my tier]},
      }{},
    },
    my tier,
    fit=band,
    before computing xy={% change the value of l to alter the distance between levels
      l=30pt,
    },
  }
[Grandma+Steve. Steve later remarried with Betty
    [Child of Grandma+Steve
        [Grandchild]
        [Grandchild]
    ]
    [Child of Grandma+Steve,edge={densely dashed}
        [Grandchild of Grandma+Steve]
        [Half brother/sister,edge={densely dashed}]
    ]
    [Child of Steve+Betty]
]
    \end{forest}
\end{document}

The output:

enter image description here

Best Answer

Related Solutions

[Tex/LaTex] Unbalanced binary tree with forest

[Tex/LaTex] Family tree with two different line style using forest package

Related Question