WOLFRAM

News, Views & Insights

Related Topics
Related Posts
View All 13.0 Features

New in 13: Trees

Stephen Wolfram

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:

&#10005

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:

&#10005

RulesTree[a -> {b, c -> {d, e}, f, g}]

And TreeRules goes the other way, converting a tree to a nested collection of rules:

&#10005

TreeRules[%]

ExpressionTree creates a tree from the structure of an expression:

&#10005

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

&#10005

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

&#10005

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:

&#10005

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:

&#10005

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:

&#10005

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:

&#10005

GraphTree[KaryTree[20]]

RandomTree produces a random tree of a given size:

&#10005

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:

&#10005

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:

&#10005

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:

&#10005

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:

&#10005

TreeExtract[CloudGet["http://wolfr.am/VAsbnJeT"], {2, 2}]

TreeSelect lets you select subtrees in a given tree:

&#10005

TreeSelect[CloudGet["http://wolfr.am/VAsbnJeT"], TreeDepth[#] > 2 &]

TreeData picks out payloads, by default for the roots of trees (TreeChildren picks out subtrees):

&#10005

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:

&#10005

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

&#10005

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:

&#10005

Entity["Person", "QueenElizabethII::f5243"][
 EntityProperty["Person", "Children"]]

This constructs a 2-level family tree:

&#10005

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

&#10005











This adds options for styling elements, with one particular element specified by its tree position being singled out as blue:









					
				



					&#10005












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:









					
				



					&#10005












Now show in which order the nodes are visited by TreeScan:









					
				



					&#10005












This explicitly labels the nodes in the order they are visited:









					
				



					&#10005












This order is by default depth first. But now TreeTraversalOrder allows you to ask for other orderings. Here’s breadth-first order:









					
				



					&#10005












Here’s a slightly more ornate ordering:









					
				



					&#10005












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.








Download your 13.0 now! »  (It’s already live in the Wolfram Cloud!)




                                            

                


                                    

                   					
				
 

                                                
                    

                
                                                                

        


        
                    

                

                    


    
Comments



    
Join the discussion

    

        

                                                        
            

                

                    

                        
                        
                        
!Please enter your comment (at least 5 characters).

                    

                


                

                    

                        
                        
                        
!Please enter your name.

                    

                    

                        
                        
                        
!Please enter a valid email address.