# Converting expressions to "edges" for use in TreePlot, Graph

This question is similar to this: Nested list to graph. How to "flatten" an arbitrary expression, eg

expr = a[b[c, d[e][f], g], h]


to a list of key-value pairs representing Graph edges of the expression tree: These can be extracted by applying WReach's exception-based method --> Can TreeForm be displayed “sideways”?:

Block[{TreePlot},
t_TreePlot := Throw@Hold@t;
Catch@MakeBoxes@TreeForm[expr]
][[1, 1]]


Giving:

{{"a", "0", "a[b[c, d[e][f], g], h]"} -> {"b", "1",
"b[c, d[e][f], g]"}, {"b", "1", "b[c, d[e][f], g]"} -> {"c", "2",
"c"}, {"b", "1", "b[c, d[e][f], g]"} -> {"d[e]", "3",
"d[e][f]"}, {"d[e]", "3", "d[e][f]"} -> {"f", "4", "f"}, {"b", "1",
"b[c, d[e][f], g]"} -> {"g", "5", "g"}, {"a", "0",
"a[b[c, d[e][f], g], h]"} -> {"h", "6", "h"}}


(Why are they cast to String?) Note non-atomic sub-expressions replaced with their Head. Based on the above, and the rule: ({h_, _, _} -> {a_, _, _}) :> ToExpression@h -> ToExpression@ a gives:

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


TreeForm is a wrapper around TreePlot. TreePlot[%, VertexLabeling -> True] gives: Since the layout is different, TreePlot must be making use of the other components of the output of the Block above.

EDIT:

How do TreeForm and SparseArayExpressionToTree (see below) extract these pairs of vertices? "Proof of work" is to extract the position (in the expression) of each vertex along with the edges.

Previously, I asked how to extract these "edges" based on a more restricted example Alternatives ordering affects pattern matching in Cases?. Also tried ReplaceList but don't know how to map it consistently across all levels.

• Related: (11458) Jun 3, 2016 at 3:50

Although kguler posted an answer using a nice internal function that does this (almost) directly I find this kind of expression manipulation interesting in itself so I wanted to see what could be done without it.

expr = a[b[c, d[e][f], g], h];

edges =
Reap[
Cases[expr, h_[___, c_[___] | c_?AtomQ, ___] /; Sow[h -> c], {0, -1}]
][[2, 1]];

TreePlot[edges, VertexLabeling -> True] Or for the different layout:

TreePlot[edges, Automatic, Head @ expr, VertexLabeling -> True] tree[expr_] :=
edges = Reap[
Sow[Annotation[h, x] ->
Annotation[c, If[{z} === {}, {a}, {z}]]], {0, -1}]][[2, 1]];
edges = edges /. head -> Annotation;
TreePlot[edges, Automatic, edges[[-1, 1]], VertexLabeling -> True]
]

a[b[c, d[e][f], g, b, d[e][b]], h] // tree This very likely has bugs that will need to be addressed as I did it in a hurry and tired, but I think it at least gives us a place to start.

• Thanks, nice use of Sow/Reap, and inner Alternatives. One issue, how to specify Head[expr] as RootVertex? Maybe using a function of Position[expr, h] (in Sow)? Jun 27, 2014 at 21:09
• @alancalvitti I'm glad this helps. Regarding "RootVertex" does this do what you want? TreePlot[%, Automatic, Head@expr, VertexLabeling -> True] Jun 28, 2014 at 1:11
• this answer, as the others here, relies on the nodes being all different. it's not easy to see how to extend it to the case where e.g. b appears twice at different places. one would probably need some temporary node numbering? Sep 12, 2017 at 18:14
• @user3240588 Good question! I'll have to think about that. Sep 12, 2017 at 20:47
• @user3240588 Please see my update, and look for cases where it fails so I can try to fix those. Sep 12, 2017 at 21:25

An alternative method to WReach's method is to use SparseArrayExpressionToTree which produces the same output without string wrappers:

expr = a[b[c, d[e][f], g], h];
ett = SparseArrayExpressionToTree[expr]
(* {{a,0,a[b[c,d[e][f],g],h]}->{b,1,b[c,d[e][f],g]},
{b,1,b[c,d[e][f],g]}->{c,2,c},
{b,1,b[c,d[e][f],g]}->{d[e],3,d[e][f]},
{d[e],3,d[e][f]}->{f,4,f},
{b,1,b[c,d[e][f],g]}->{g,5,g},
{a,0,a[b[c,d[e][f],g],h]}->{h,6,h}} *)

edges = ett[[All,All,1]] (* thanks: @Mr.Wizard *)
(* or edges = ett /. Rule[a_, b_] :> Rule[First[a], First[b]];*)
(* {a->b,b->c,b->d[e],d[e]->f,b->g,a->h} *)

Graph[edges, VertexLabels -> Placed["Name", {Center, Center}],
VertexSize -> .3, VertexLabelStyle -> Directive[Red, Italic, 20],
ImagePadding -> 20, ImageSize -> 400,
GraphLayout -> {"LayeredEmbedding", "RootVertex" -> edges[[1,1]]}] Update: You can also use GraphComputationExpressionGraph:

eg = GraphComputationExpressionGraph[expr, VertexSize -> Large,
VertexLabelStyle -> Directive[Red, Italic, 20]];
SetProperty[eg,  VertexLabels -> {v_ :>
Placed[PropertyValue[{eg, v}, VertexLabels], Center]}] • More directly: SparseArrayExpressionToTree[expr][[All, All, 1]]. Also, thanks for showing me ExpressionToTree! (Again?) Jun 27, 2014 at 1:24
• @kguler, +1 - btw ETT --> ReleaseHold. But I'm asking how TreeForm (and ETT) convert the expr. I edited my Q to reflect this. Jun 27, 2014 at 18:40
• @alancalvitti Is my answer of no interest to you? Are you only interested in the details of the internal implementation and not an equivalent method in top-level code? Jun 27, 2014 at 19:37
• Yes that works, thank you, I had to test on some expressions of interest. Jun 27, 2014 at 21:06

IGraph/M now includes IGExpressionTree:

<<IGraphM
IGExpressionTree[expr] GraphQ[%]
(* True *)


Is this what you are seeking?

expr = a[b[c, d[e][f], g], h]
boxes = ToBoxes@TreeForm[expr]
positions = Cases[boxes, LineBox[{x__}] -> x, Infinity]
nodes =
Cases[
boxes,
StyleBox[x_, __] :> ToExpression@x, Infinity] /.
{t_Times :> First@t, Verbatim[HoldForm][x_] -> x}
Rule @@@ Extract[nodes, List /@ positions]
`

{a -> b, a -> h, b -> c, b -> d, b -> g, d -> f}

• No, for example that doesn't match d[e]. But also, How to extract it directly without using TreeForm? Jun 26, 2014 at 23:15