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.

The following nested list can be regarded as a representation of a (tree) graph:

li = {"fig", {"date", {"kumquat"}, {"papaya", {"peach"}, {"apple"}}},
             {"mango", {"orange", {"pear"}, {"avocado"}}}, 
             {"banana"}}

In the above, a string is a node in the tree, and any lists that follow it are subtrees rooted at that node.

What are some of the ways by which this can be converted into a graph (or more concretely, a list of DirectedEdges)? I've come up with one way, listed below. But I wanted to learn about other interesting approaches - for instance, pattern replacements might be used?

This is what I came up with:

h[{str_String}] := Sequence[];
h[{str_String, ls__List}] := {DirectedEdge[str, #[[1]]], h@#} & /@ {ls};

edges = Flatten@h@li

(* 
{"fig" \[DirectedEdge] "date", "date" \[DirectedEdge] "kumquat", 
 "date" \[DirectedEdge] "papaya", "papaya" \[DirectedEdge] "peach", 
 "papaya" \[DirectedEdge] "apple", "fig" \[DirectedEdge] "mango", 
 "mango" \[DirectedEdge] "orange", "orange" \[DirectedEdge] "pear", 
 "orange" \[DirectedEdge] "avocado", "fig" \[DirectedEdge] "banana"}
*)

TreePlot[Rule @@@ edges, Automatic, "fig", DirectedEdges -> True, 
 VertexLabeling -> True]

Don't you wish this were an actual tree?

share|improve this question
add comment

3 Answers 3

up vote 7 down vote accepted
edges = Cases[li,
   {node_String, subtrees__List} :> (
     node \[DirectedEdge] #[[1]] & /@ {subtrees}),
   {0, ∞}] // Flatten

Note the level specification within Cases.

Graph[edges,
 VertexLabels -> "Name",
 ImagePadding -> 30,
 GraphLayout -> {
   "LayeredEmbedding",
    "RootVertex" -> "fig"}]
share|improve this answer
    
+1, nice use of level specs. –  rasher Mar 13 at 10:34
add comment

Here's another way I think is interesting:

Flatten@Rest@
  Reap@Scan[Sow[Thread[First@# \[DirectedEdge] First /@ Rest@#]] &, 
    li, {0, -3}]
share|improve this answer
add comment
li //. {{x_, rest__} :> x[rest], {x_} :> x} // 
 TreeForm[#, DirectedEdges -> True] & 

enter image description here

A similar rule can be used to parse JSON data and display with TreeForm

share|improve this answer
    
If the goal was just produce a visual tree, then this would do fine... but the question was about converting the nested list representation to a "true" graph. –  Aky Jun 23 at 19:13
add comment

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.