Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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:

enter image description here

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:

enter image description here

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 SparseAray`ExpressionToTree (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.

share|improve this question

3 Answers 3

up vote 4 down vote accepted

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'm going to see what can be done without it.

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

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

TreePlot[edges, VertexLabeling -> True]

enter image description here

Or for the different layout:

TreePlot[edges, Automatic, Head @ expr, VertexLabeling -> True]

enter image description here

share|improve this answer
    
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)? –  alancalvitti Jun 27 at 21:09
    
@alancalvitti I'm glad this helps. Regarding "RootVertex" does this do what you want? TreePlot[%, Automatic, Head@expr, VertexLabeling -> True] –  Mr.Wizard Jun 28 at 1:11

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

expr = a[b[c, d[e][f], g], h];
ett = SparseArray`ExpressionToTree[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]]}]

enter image description here

share|improve this answer
2  
More directly: SparseArray`ExpressionToTree[expr][[All, All, 1]]. Also, thanks for showing me ExpressionToTree! (Again?) –  Mr.Wizard Jun 27 at 1:24
    
Thank you indeed @Mr.Wizard. –  kguler Jun 27 at 1:35
    
@kguler, +1 - btw ETT --> ReleaseHold. But I'm asking how TreeForm (and ETT) convert the expr. I edited my Q to reflect this. –  alancalvitti Jun 27 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? –  Mr.Wizard Jun 27 at 19:37
    
Yes that works, thank you, I had to test on some expressions of interest. –  alancalvitti Jun 27 at 21:06

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}

share|improve this answer
    
No, for example that doesn't match d[e]. But also, How to extract it directly without using TreeForm? –  alancalvitti Jun 26 at 23:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.