Can trees be made into graphs?

Question

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.

Answer 1

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}

Answer 2

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:

Example 2:

Answer 3

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}]

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]

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

Answer 4

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]

Answer 5

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}]

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

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" -> {}}]

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