News, Views & Insights
New in 13: Trees
Two years ago we released Version 12.0 of the Wolfram Language. Here are the updates in trees since then, including the latest features in 13.0. The contents of this post are compiled from Stephen Wolfram’s Release Announcements for 12.1, 12.2, 12.3 and 13.0.
Trees! (May 2021)
Based on the number of new built-in functions the clear winner for the largest new framework in Version 12.3 is the one for trees. We’ve been able to handle trees as a special case of graphs for more than a decade (and of course all symbolic expressions in the Wolfram Language are ultimately represented as trees). But in Version 12.3 we’re introducing trees as first-class objects in the system.
The fundamental object is Tree:
✕
Tree[a, {b, Tree[c, {d, e}], f, g}]
|
Tree takes two arguments: a “payload” (which can be any expression), and a list of subtrees. (And, yes, trees are by default rendered slightly green, in a nod to their botanical analogs.)
There are a variety of “*Tree” functions for constructing trees, and “Tree*” functions for converting trees to other things. RulesTree, for example, constructs a tree from a nested collection of rules:
✕
RulesTree[a -> {b, c -> {d, e}, f, g}]
|
And TreeRules goes the other way, converting a tree to a nested collection of rules:
✕
TreeRules[%] |
ExpressionTree creates a tree from the structure of an expression:
✕
ExpressionTree[Integrate[1/(x^2 - 1), x]] |
In a sense, this is a direct representation of a FullForm expression, as shown, for example, in TreeForm. But there are also ways to turn an expression into a tree. This takes the nodes of the tree to contain full subexpressions—so that the expressions on a given level in the tree are essentially what a function like Map would consider to be the expressions at that level (with Heads → True):
✕
ExpressionTree[Integrate[1/(x^2 - 1), x], "Subexpressions"] |
Here’s another version, now effectively removing the redundancy of nested subexpressions, and treating heads of expressions just like other parts (in “S-expression style”):
✕
ExpressionTree[Integrate[1/(x^2 - 1), x], "Atoms"] |
Why do we need Tree when we have Graph? The answer is that there are several special features of trees that are important. In a Graph, for example, every node has a name, and the names have to be unique. In a tree, nodes don’t have to be named, but they can have “payloads” that don’t have to be unique. In addition, in a graph, the edges at a given node don’t appear in any particular order; in a tree they do. Finally, a tree has a specific root node; a graph doesn’t necessarily have anything like this.
When we were designing Tree we at first thought we’d have to have separate symbolic representations of whole trees, subtrees and leaf nodes. But it turned out that we were able to make an elegant design with Tree alone. Nodes in a tree typically have the form Tree[payload, {child1, child2, …}] where the childi are subtrees. A node doesn’t necessarily have to have a payload, in which case it can just be given as Tree[{child1, child2, …}]. A leaf node is then Tree[expr, None] or Tree[None].
One very nice feature of this design is that trees can immediately be constructed from subtrees just by nesting expressions:
✕
Tree[{\!\(\*
GraphicsBox[
NamespaceBox["Trees",
DynamicModuleBox[{Typeset`tree = HoldComplete[
Tree[$CellContext`a, {
Tree[$CellContext`b, None],
Tree[$CellContext`c, {
Tree[$CellContext`d, None],
Tree[$CellContext`e, None]}]}]]}, {
{RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1], Opacity[0.7],
StyleBox[{
LineBox[{{0.4472135954999579, 1.7888543819998317`}, {0.,
0.8944271909999159}}],
LineBox[{{0.4472135954999579, 1.7888543819998317`}, {
0.8944271909999159, 0.8944271909999159}}],
LineBox[{{0.8944271909999159, 0.8944271909999159}, {
0.4472135954999579, 0.}}],
LineBox[{{0.8944271909999159, 0.8944271909999159}, {
1.3416407864998738`, 0.}}]},
GraphicsHighlightColor->RGBColor[
0.403921568627451, 0.8705882352941177,
0.7176470588235294]]},
{GrayLevel[0], EdgeForm[{GrayLevel[0], Opacity[0.7]}],
StyleBox[{InsetBox[
FrameBox["a",
Background->RGBColor[
0.9607843137254902, 0.9882352941176471,
0.9764705882352941],
FrameStyle->Directive[
RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {0.4472135954999579, 1.7888543819998317}],
InsetBox[
FrameBox["b",
Background->RGBColor[
0.9607843137254902, 0.9882352941176471,
0.9764705882352941],
FrameStyle->Directive[
RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {0., 0.8944271909999159}], InsetBox[
FrameBox["c",
Background->RGBColor[
0.9607843137254902, 0.9882352941176471,
0.9764705882352941],
FrameStyle->Directive[
RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {0.8944271909999159, 0.8944271909999159}],
InsetBox[
FrameBox["d",
Background->RGBColor[
0.9607843137254902, 0.9882352941176471,
0.9764705882352941],
FrameStyle->Directive[
RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {0.4472135954999579, 0.}], InsetBox[
FrameBox["e",
Background->RGBColor[
0.9607843137254902, 0.9882352941176471,
0.9764705882352941],
FrameStyle->Directive[
RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {1.3416407864998738, 0.}]},
GraphicsHighlightColor->RGBColor[
0.403921568627451, 0.8705882352941177,
0.7176470588235294]]}}]],
BaseStyle->{
FrontEnd`GraphicsHighlightColor ->
RGBColor[
0.403921568627451, 0.8705882352941177, 0.7176470588235294]},
FormatType->StandardForm,
FrameTicks->None,
ImageSize->{69.1171875, Automatic}]\), \!\(\*
GraphicsBox[
NamespaceBox["Trees",
DynamicModuleBox[{Typeset`tree = HoldComplete[
Tree[$CellContext`a, {
Tree[$CellContext`b, None],
Tree[$CellContext`c, {
Tree[$CellContext`d, None],
Tree[$CellContext`e, None]}]}]]}, {
{RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1], Opacity[0.7],
StyleBox[{
LineBox[{{0.4472135954999579, 1.7888543819998317`}, {0.,
0.8944271909999159}}],
LineBox[{{0.4472135954999579, 1.7888543819998317`}, {
0.8944271909999159, 0.8944271909999159}}],
LineBox[{{0.8944271909999159, 0.8944271909999159}, {
0.4472135954999579, 0.}}],
LineBox[{{0.8944271909999159, 0.8944271909999159}, {
1.3416407864998738`, 0.}}]},
GraphicsHighlightColor->RGBColor[
0.403921568627451, 0.8705882352941177,
0.7176470588235294]]},
{GrayLevel[0], EdgeForm[{GrayLevel[0], Opacity[0.7]}],
StyleBox[{InsetBox[
FrameBox["a",
Background->RGBColor[
0.9607843137254902, 0.9882352941176471,
0.9764705882352941],
FrameStyle->Directive[
RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {0.4472135954999579, 1.7888543819998317}],
InsetBox[
FrameBox["b",
Background->RGBColor[
0.9607843137254902, 0.9882352941176471,
0.9764705882352941],
FrameStyle->Directive[
RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {0., 0.8944271909999159}], InsetBox[
FrameBox["c",
Background->RGBColor[
0.9607843137254902, 0.9882352941176471,
0.9764705882352941],
FrameStyle->Directive[
RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1]],
ImageSize->Automatic,
RoundingRadius->4,
StripOnInput->False], {0.8944271909999159, 0.8944271909999159}],
InsetBox[
FrameBox["d",
Background->RGBColor[
0.9607843137254902, 0.9882352941176471,
0.9764705882352941],
FrameStyle->Directive[
RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {0.4472135954999579, 0.}], InsetBox[
FrameBox["e",
Background->RGBColor[
0.9607843137254902, 0.9882352941176471,
0.9764705882352941],
FrameStyle->Directive[
RGBColor[0.6588235294117647, 0.7294117647058823, 0.7058823529411765],
AbsoluteThickness[1]],
ImageSize->Automatic,
RoundingRadius->0,
StripOnInput->False], {1.3416407864998738, 0.}]},
GraphicsHighlightColor->RGBColor[
0.403921568627451, 0.8705882352941177,
0.7176470588235294]]}}]],
BaseStyle->{
FrontEnd`GraphicsHighlightColor ->
RGBColor[
0.403921568627451, 0.8705882352941177, 0.7176470588235294]},
FormatType->StandardForm,
FrameTicks->None,
ImageSize->{68.625, Automatic}]\),
Tree[{CloudGet["http://wolfr.am/VAsaSro1"]}]}]
|
By the way, we can turn this into a generic Graph object with TreeGraph:
✕
TreeGraph[%] |
Notice that since Graph doesn’t pay attention to ordering of nodes, some nodes have effectively been flipped in this rendering. The nodes have also had to be given distinct names in order to preserve the tree structure:
✕
Graph[CloudGet["http://wolfr.am/VAsb0AqA"], VertexLabels -> Automatic] |
If there’s a generic graph that happens to be a tree, GraphTree converts it to explicit Tree form:
✕
GraphTree[KaryTree[20]] |
RandomTree produces a random tree of a given size:
✕
RandomTree[20] |
One can also make trees from nesting functions: NestTree produces a tree by nestedly generating payloads of child nodes from payloads of parent nodes:
✕
NestTree[{f[#], g[#]} &, x, 2]
|
OK, so given a tree, what can we do with it? There are a variety of tree functions that are direct analogs of functions for generic expressions. For example, TreeDepth gives the depth of a tree:
✕
TreeDepth[CloudGet["http://wolfr.am/VAsbf4XX"]] |
TreeLevel is directly analogous to Level. Here we’re getting subtrees that start at level 2 in the tree:
✕
TreeLevel[CloudGet["http://wolfr.am/VAsbnJeT"], {2}]
|
How do you get a particular subtree of a given tree? Basically it has a position, just as a subexpression would have a position in an ordinary expression:
✕
TreeExtract[CloudGet["http://wolfr.am/VAsbnJeT"], {2, 2}]
|
TreeSelect lets you select subtrees in a given tree:
✕
TreeSelect[CloudGet["http://wolfr.am/VAsbnJeT"], TreeDepth[#] > 2 &] |
TreeData picks out payloads, by default for the roots of trees (TreeChildren picks out subtrees):
✕
TreeData /@ % |
There are also TreeCases, TreeCount and TreePosition—which by default search for subtrees whose payloads match a specified pattern. One can do functional programming with trees just like with generic expressions. TreeMap maps a function over (the payloads in) a tree:
✕
TreeMap[f, CloudGet["http://wolfr.am/VAsbCysJ"]] |
TreeFold does a slightly more complicated operation. Here f is effectively “accumulating data” by scanning the tree, with g being applied to the payload of each leaf (to “initialize the accumulation”):
✕
TreeFold[{f, g}, CloudGet["http://wolfr.am/VAsbCysJ"]]
|
There are lots of things that can be represented by trees. A classic example is family trees. Here’s a case where there’s built-in data we can use:
✕
Entity["Person", "QueenElizabethII::f5243"][ EntityProperty["Person", "Children"]] |
This constructs a 2-level family tree:
✕
NestTree[#[EntityProperty["Person", "Children"]] &, Entity["Person", "QueenElizabethII::f5243"], 2] |
By the way, our Tree system is very scalable, and can happily handle trees with millions of nodes. But in Version 12.3 we’re really just starting out; in subsequent versions there’ll be all sorts of other tree functionality, as well as applications to parse trees, XML trees, etc.
Trees Continue to Grow (December 2021)
We introduced Tree as a basic construct in Version 12.3. In 13.0 we’re extending Tree and adding some enhancements. First of all, there are now options for tree layout and visualization.
For example, this lays out a tree radially (note that knowing it’s a tree rather than a general graph makes it possible to do much more systematic embeddings):
✕
|
This adds options for styling elements, with one particular element specified by its tree position being singled out as blue:
✕
|
One of the more sophisticated new “tree concepts” is TreeTraversalOrder. Imagine you’re going to “map across” a tree. In what order should you visit the nodes? Here’s the default behavior. Set up a tree:
✕
|
Now show in which order the nodes are visited by TreeScan:
✕
|
This explicitly labels the nodes in the order they are visited:
✕
|
This order is by default depth first. But now TreeTraversalOrder allows you to ask for other orderings. Here’s breadth-first order:
✕
|
Here’s a slightly more ornate ordering:
✕
|
Why does this matter? “Traversal order” turns out to be related to deep questions about evaluation processes and what I now call multicomputation. In a sense a traversal order defines the “reference frame” through which an “observer” of the tree samples it. And, yes, that language sounds like physics, and for a good reason: this is all deeply related to a bunch of concepts about fundamental physics that arise in our Physics Project. And the parametrization of traversal order—apart from being useful for a bunch of existing algorithms—begins to open the door to connecting computational processes to ideas from physics, and new notions about what I’m calling multicomputation.
