11
$\begingroup$

When one has the output of a function like TreeForm, for instance:

Can this be turned into a Graph object? I would like to be able to apply functions like VertexList, VertexDegree, AdjacencyList, and so on.

$\endgroup$
  • $\begingroup$ See my this post $\endgroup$ – yode Jul 11 '17 at 8:29
  • $\begingroup$ I am attempting to use the answer from Wjx, but I am running into a problem. I cannot apply the function Graphics2Graph directly to TreeForm, only to the output of TreeForm. For example, Graphics2Graph[TreeForm[{{a, a}, {a, {a, a}}}]] does not work. I would also be happy with a method to take such a list and make the corresponding graph. $\endgroup$ – M. Brandt Jul 11 '17 at 9:18
  • $\begingroup$ See this answer $\endgroup$ – yode Jul 11 '17 at 9:23
7
$\begingroup$

You can use halirutan's makeTree function from this answer. Your purpose is slightly different than the purpose in that question, so the function can be simplified a bit in this context:

makeTree[nodes_] := Module[{counter = 0},
  traverse[h_[childs___]] := With[{id = counter},
    {DirectedEdge[id, ++counter], traverse[#]} & /@ {childs}
    ];
  traverse[_] := Sequence[];
  TreeGraph[#, GraphLayout -> "LayeredDigraphEmbedding"] &@Flatten[traverse[nodes]]
  ]

Use it like this:

expr = TreeForm[{a, {a, {a, a, a}}}];
{expr, makeTree @@ expr}

Mathematica graphics

$\endgroup$
  • $\begingroup$ This method will lose all vertices information $\endgroup$ – yode Jul 11 '17 at 10:57
  • $\begingroup$ @yode You can use this Graph object with VertexDegree, AdjacancyList etc. I do not store the the labels (List, a), but it could be added. Other than that I don't lose any information. $\endgroup$ – C. E. Jul 11 '17 at 11:00
4
$\begingroup$
TreeFormToGraph[treeForm_] := 
 Module[{tree = ToExpression@ToBoxes@treeForm, order, pos, label},
  label = Cases[tree, Inset[name_, n_] :> Rule[n, Placed[name, Center]],Infinity];
  {order, pos} = Catenate /@ Cases[tree, 
     Line[order_] | GraphicsComplex[pos_, ___] :> {order, pos}, Infinity];
  Graph[UndirectedEdge @@@ order, VertexLabels -> label, 
   VertexCoordinates -> MapIndexed[Rule[First[#2], #] &, pos]]]

Note the result of TreeFormToGraph is Graph object.

Example 1:

Mathematica graphics

Example 2:

Mathematica graphics

$\endgroup$
4
$\begingroup$

Update: We can use GraphComputation`ExpressionGraph to get a one-liner that converts a TreeForm object to a Graph object:

treeFormToGraph = Apply[GraphComputation`ExpressionGraph];

treeFormToGraph @ TreeForm[{{{a,b},c},d}]

enter image description here

We can add styling to get a Graph that looks like TreeForm:

ClearAll[treeFormToGraph ]
treeFormToGraph[t_TreeForm, o : OptionsPattern[]] := 
   Module[{g = GraphComputation`ExpressionGraph[t[[1]], o, 
           VertexSize -> {"Scaled", .1}, VertexStyle -> LightYellow, 
           VertexShapeFunction -> "Rectangle"]}, 
      SetProperty[g, VertexLabels -> (PropertyValue[g, VertexLabels] /. 
              Rule[a_, b_] :> Rule[a, Placed[b, Center]])]];

treeFormToGraph[TreeForm[{{{a,b},c},d}], VertexStyle->Pink]

enter image description here

Original answer:

We can use, instead of TreeForm, GraphComputation`ExpressionGraph which produces a Graph object accepting all the options of Graph.

g1 = GraphComputation`ExpressionGraph[{{{a, b}, c}, d}, 
   VertexSize -> {"Scaled", .1}, VertexStyle -> LightYellow, 
   VertexShapeFunction -> "Rectangle"];

SetProperty[g1, VertexLabels -> (PropertyValue[g1, VertexLabels] /. 
    Rule[a_, b_] :> Rule[a, Placed[b, Center]])]

enter image description here

$\endgroup$
  • $\begingroup$ As my understand,this topic is about how to convert a Graphics into Graph. :) $\endgroup$ – yode Jul 11 '17 at 20:39
  • $\begingroup$ @yode, i assume you meant "convert a TreeForm into Graph". Apply[GraphComputation`ExpressionGraph]@TreeForm[{{{a,b}, c}, d}] does it:) $\endgroup$ – kglr Jul 11 '17 at 21:14
  • $\begingroup$ @kglr thank you for introducing me to this function! :) $\endgroup$ – ubpdqn Jul 12 '17 at 1:33
2
$\begingroup$

This is not ideal. It requires the tree to be output. The object elements are collected and reused for a graph:

func[ex__] := (e = {}; vn = {};
  TreeForm[ex, 
   EdgeRenderingFunction -> ({Blue, (AppendTo[e, #]; 
        Arrow[#, .3])} &), 
   VertexRenderingFunction -> ((AppendTo[vn, {#1, #2}]; 
       Text[#2, #1]) &)])
f[x_, y_] := 
 Module[{el = DeleteDuplicates[UndirectedEdge @@@ x], vl, rules},
  vl = VertexList[Graph[el]];
  rules = MapIndexed[#1 -> #2[[1]] &, vl];
  Graph[el /. rules, VertexLabels -> Rule @@@ (y /. rules)]]

An example:

func[{a, b, {c, d}, {w, r}}] (* tree must be rendered*)
graph = f[e, vn]

enter image description here

$\endgroup$
1
$\begingroup$

IGraph/M now includes a function to convert a Mathematica expression into a Graph similar to what TreeForm would display. It is faster than GraphComputation`ExpressionGraph, especially if you turn off vertex labelling.

IGExpressionTree[{{{a, a}, a}, a}]

enter image description here

tree = IGExpressionTree[expr = {{{a, a}, a}, a}, VertexLabels -> None, 
 GraphLayout -> {"LayeredEmbedding", "RootVertex" -> {}}]

enter image description here

The vertex names of this tree are the positions of the corresponding subexpressions. Above, the root vertex was set to {}, which is the position specification of the entire expression.

VertexList[tree]
(* {{1, 1, 1}, {1, 1, 2}, {1, 1}, {1, 2}, {1}, {2}, {}} *)

Extract[expr, VertexList[tree]]
(* {a, a, {a, a}, a, {{a, a}, a}, a, {{{a, a}, a}, a}} *)

We could also have labelled the vertices with these subexpressions:

IGExpressionTree[expr, VertexLabels -> "Subexpression", 
 GraphLayout -> {"LayeredEmbedding", "RootVertex" -> {}}]

enter image description here

Should you need the vertex names to be just integers, use IndexGraph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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