0
$\begingroup$

For demo, exploration and teaching purposes, I would like to be able (and asking you for help) to generate these special instances of trees:

For given:

  • N - number of nodes in the tree
  • D - depth of the tree (largest distance root-leaf)

I need to generate a random tree with all nodes labeled so that:

  • Root is labeled "Lorem"
  • First or other prominent child of the root is labeled "ipsum".
  • All other children are labeled randomly from words from following paragraph: "dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum."

Example from related question: (but this solution doesn't care about depth limitations)

vtx[] := Table[i <-> RandomInteger[{0, i - 1}], {i, 1, 50}];
Graph@vtx[]

Tree should look like this: (just imagine words instead of numbers)

enter image description here

Improve this question
$\endgroup$
7
  • $\begingroup$ Why not just generate the tree like in your second example and then label 1 -> "Lorem", 2 -> "Ipsum" and then thread the remaining integers with a RandomSample of the remaining words? $\endgroup$
    – rm -rf ♦
    Jan 26, 2014 at 18:57
  • $\begingroup$ @rm -rf You are right about the example, and the challenge is just to make sure the tree satisfies both "N" and "D" limitations. $\endgroup$
    – VividD
    Jan 26, 2014 at 19:01
  • 2
    $\begingroup$ Ok, if that's the case, then I would suggest rewording the question to indicate that the focus is on "creating a random graph/tree with a fixed number of nodes and depth"... the "Lorem ipsum" part is mostly irrelevant given your clarification, but the title suggests that you're looking for a "Lorem ipsum" tree. $\endgroup$
    – rm -rf ♦
    Jan 26, 2014 at 19:06
  • 2
    $\begingroup$ Naive iterative approach: Have all nodes in the graph be labelled with their level (depth). 1. Select a random node. 2. If its depth is $< D$, then attach a new node to it. Repeat this until you have $N$ nodes. When you're done, name the nodes with the words from the text using DepthFirstScan. You can try to code this in Mathematica. $\endgroup$
    – Szabolcs
    Jan 26, 2014 at 19:41
  • $\begingroup$ Also, do you have any requirements on the distribution that the trees are drawn from? For example, do you need all trees satisfying your requirements to be drawn with equal probability (i.e. have a uniform distribution on the set of allowed trees)? If yes, that makes the problem considerably more involved, and I'd suggest first figuring out a method (e.g. asking on Math.SE) and thinking about a Mathematica implementation only afterwards. The naive algorithm I described probably won't give you a uniform distribution. $\endgroup$
    – Szabolcs
    Jan 26, 2014 at 19:48

2 Answers 2

Reset to default
1
$\begingroup$

This should do what you want. 

nodes = 20
depth = 5

words = StringSplit[
   "dolor sit amet, consectetur adipisicing elit, sed do eiusmod \
tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim \
veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex \
ea commodo consequat. Duis aute irure dolor in reprehenderit in \
voluptate velit esse cillum dolore eu fugiat nulla pariatur. \
Excepteur sint occaecat cupidatat non proident, sunt in culpa qui \
officia deserunt mollit anim id est laborum."];

root = node[1, 1]
nodenum = 2
graph = VertexAdd[Graph[{}, GraphLayout -> {"MultipartiteEmbedding"}],
    root];

While[nodenum <= nodes, 
  While[(cand = RandomChoice@VertexList[graph]; 
    cand[[2]] > depth - 1)];
  graph = 
   EdgeAdd[graph, 
    cand \[UndirectedEdge] node[nodenum++, cand[[2]] + 1]];
  ];

TreeGraph[EdgeList[graph], 
 VertexLabels -> {node[1, 1] -> "Lorem", node[_, 2] -> "Ipsum", 
   node[_, depth_] /; depth > 2 :> RandomChoice[words]}, 
 ImageSize -> 500]

enter image description here

You can fiddle with layout/rendering options if you want a different look, or to enforce vertex positioning.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This looks great. I would just put "ipsum" on only one root child, but I can change it myself. Finally I have what I wanted - "neutral" meaning tree. Szabolc's answer was also good, but I'll mark yours as answer! $\endgroup$
    – VividD
    Jan 27, 2014 at 7:56
  • $\begingroup$ Glad it is useful. Re: Szabolc - yes, one of the group of true masters of MM here, always nice & informative answers. $\endgroup$
    – ciao
    Jan 27, 2014 at 20:42
2
$\begingroup$

Here's a naive iterative approach:

Have all nodes in the graph be labelled with their level (depth). 1. Select a random node. 2. If its depth is $<D$, then attach a new node to it. Repeat this until you have $N$ nodes. When you're done, name the nodes with the words from the text using DepthFirstScan.

Warning: this is not going to generate all trees satisfying the constraints with the same probability, and this it's not suitable for mathematical use!

This is some Mathematica code for the first part of the task. It generates a tree with depth d and n vertices.

n = 100;
d = 4;
g = Graph[{}];
i = 1;
g = VertexAdd[g, {v[i++, 1]}];

While[
 VertexCount[g] < n,

 With[{p = RandomChoice@VertexList[g]}, 
  If[p[[2]] < d, g = EdgeAdd[g, p -> v[i++, p[[2]] + 1]]]
  ]
 ]

g

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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