New in Tree Data & Computation

Ian Ford, Wolfram Research

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

ABSTRACT

Tree is a new fundamental construct in the Wolfram Language added in Version 12.3 used to represent rooted, ordered, labeled trees. In this talk, we will present a variety of new features added in Version 13.1, including support for associations between keys and children, new ways of constructing tree data such as XML and JSON, options for detailed control of labeling and styling, and new functional programming operations.

Tree Representation

Tree represents rooted, ordered labeled trees with leaves.

This represents a tree with three leaves:

Tree[{1,2,3}]

Non-leaf nodes can also be labeled by supplying the data:

Tree[0,{1,2,3}]

Tree expressions can be nested to represent hierarchies:

Tree[0,{Tree[1,{2,3}],Tree[4,{5,6}]}]

Associations

Version 13.1 added support for naming branches by giving an association between keys and children:

Tree[<|a->1,b->2,c->3|>]

ExpressionTree can construct a Tree from nested lists and associations:

ExpressionTree[ExampleData[{"Dataset","Planets"}],"Dataset",MaxDisplayedChildren->All->4,ImageSize->Full]

Keys can be used to specify positions in a tree of associations:

TreeExtract[%,{All,"Mass"}]

Expression Trees

In Version 13.1, the option Heads can be given to specify whether to include heads of expressions as subtrees:

Table[ExpressionTree[Unevaluated[Today+(Quantity[1, "day", day, "Days"])],struct,Heads->heads,PlotLabel->struct],{heads,{False,True}},{struct,{"Heads","HeldHeads","Subexpressions","HeldSubexpressions","Atoms","HeldAtoms",Null}}]//Grid

XML

XML documents are represented in the Wolfram Language as symbolic XML objects and elements:

ImportString["<?xml version='1.0'?>
<PAINTINGS>
 <SALE>
  <TITLE>No.5, 1948</TITLE>
  <ARTIST>Jackson Pollock</ARTIST>
  <YEAR>1948</YEAR>
  <PRICE>$140,000,000</PRICE>
 </SALE>
 <SALE>
  <TITLE>Woman III</TITLE>
  <ARTIST>Willem de Kooning</ARTIST>
  <YEAR>1953</YEAR>
  <PRICE>$137,500,000</PRICE>
 </SALE>
 <SALE>
  <TITLE>Portrait of Adele Block-Bauer I</TITLE>
  <ARTIST>Gustav Klimt</ARTIST>
  <YEAR>1907</YEAR>
  <PRICE>$135,000,000</PRICE>
 </SALE>
 <SALE>
  <TITLE>Portrait of Dr. Gachet</TITLE>
  <ARTIST>Vincent van Gogh</ARTIST>
  <YEAR>1890</YEAR>
  <PRICE>$82,500,000</PRICE>
 </SALE>
 <SALE>
  <TITLE>Bal au moulin de la Galette, Montmartre</TITLE>
  <ARTIST>Pierre-Auguste Renoir</ARTIST>
  <YEAR>1876</YEAR>
  <PRICE>$78,100,000</PRICE>
 </SALE>
</PAINTINGS>","XML"]

In Version 13.1, ExpressionTree can convert symbolic XML into the tree representation defined by the DOM:

xmlTree=ExpressionTree[%,"XML"]

Use TreeOutline to display an interactive outline view:

TreeOutline[xmlTree,{2,1|2,1|3,_}]

JSON

JSON objects can be represented in the Wolfram Language as nested lists of rules:

json="{\"Hydrogen\":{\"AtomicNumber\":1,\"AtomicWeight\":1.00793},\"Helium\":{\"AtomicNumber\":4.00259,\"AtomicWeight\":2},\"Lithium\":{\"AtomicNumber\":3,\"AtomicWeight\":6.94141}}"

ImportString[json,"JSON"]

In Version 13.1, ExpressionTree can convert nested rules into the tree of names and values of JSON objects:

ExpressionTree[%,"JSON"]

RawJSON

JSON objects can also be represented as nested associations:

ImportString[json,"RawJSON"]

ExpressionTree can convert nested associations into the tree of JSON names and values:

jsonTree=ExpressionTree[%,"RawJSON"]

Both forms support JSON objects and JSON arrays:

Table[ExpressionTree[ImportString["{\"a\":[1,2],\"b\":{\"x\":3,\"y\":4}}",struct],struct],{struct,{"JSON","RawJSON"}}]

Labeling & Styling

The TreeElementLabel and TreeElementStyle options control labeling and styling:

Tree[xmlTree,TreeElementStyle->{TreeCases[{"SALE",_}]->LightRed}]

Tree[jsonTree,TreeElementLabel->{{"Hydrogen"}->"H",{"Helium"}->"He",{"Lithium"}->"Li"}]

Version 13.1 added detailed control of labeling and styling for both nodes and edges in a tree:

SeedRandom[2];
funcs=ResourceData["VertexShapeFunction"];
tree=RandomTree[Length[funcs]];
Tree[tree,TreeElementShapeFunction->Thread[TreePosition[tree,_]->funcs],
ParentEdgeStyleFunction->{All->(Hue[#/100]&)},TreeElementStyleFunction->{x_:>(Hue[#/(Length[x]+1)]&)},TreeElementLabelFunction->{All->RomanNumeral}]

UnlabeledTree shows the overall structure of a tree without displaying labels:

UnlabeledTree[xmlTree]

Elision

Trees with more than 10 children elide the remaining children by default:

Tree[Range[15]]

Version 13.2 adds the MaxDisplayedChildren option to specify a different number of children:

Tree[Range[15],MaxDisplayedChildren->Infinity]

The default number of children is now given by the $MaxDisplayedChildren global variable:

$MaxDisplayedChildren=2;
xmlTree

$MaxDisplayedChildren=.

Properties & Measurements

RootTree returns the root node of a tree with its children removed:

RootTree[xmlTree]

When given a positive level, RootTree gives a tree containing the nodes from the root down to that level in a breadth-first TreeTraversalOrder:

RootTree[xmlTree,2]

A negative level yields the nodes from the root down to that level in a leaves-first order:

RootTree[xmlTree,-2]

TreeLeafCount gives the number of leaves of a tree:

TreeLeafCount[xmlTree]

Element Specifications

By default, TreeMap and TreeScan apply an operator to the data of subtrees when traversing a tree:

TreeMap[f,]

Version 13.1 added eleven new elements.

TreeScan[Echo@*f,,All->"OriginalSubtree"]

Multiple elements can be supplied using a list:

TreeMap[Replace[#,{tag_,_}:>{tag,#2}]&,xmlTree,All->{"Data","Index"}]

Future of Trees

More structure conversions (notebooks, text elements, parse trees, ...)

Queries and transformation rules

New and improved visualization and interactivity

Compiler integration

New in Tree Data & Computation

Ian Ford, Wolfram Research

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf