OKlibrary  0.2.1.6
Generators.hpp File Reference

Plans for the generation of various forms of trees. More...

Go to the source code of this file.

## Detailed Description

Plans for the generation of various forms of trees.

Todo:
Counting, enumeration and sampling
• We need counting, enumeration and sampling of all types of trees:
1. trees;
2. rooted trees;
3. rooted ordered trees (here "ordered" refers to the order of children), especially if all inner nodes have at most resp. exactly 2 children; see all2_rt in ComputerAlgebra/Trees/Lisp/Basics.mac for the enumeration of the Maxima list-representations for the binary case.
4. oriented trees.
• This for "labelled structures" (i.e., all such structures with standardised vertex sets) or "unlabelled structures" (i.e., all isomorphism types).
• See ComputerAlgebra/Combinatorics/Lisp/Enumeration/plans/general.hpp for the proper handling of the enumerative aspects; likely in this module perhaps only the basic generators are to be found.
Todo:
Evaluating the Maxima function random_tree
• The following function
```test_generator(f,h) := do enter_new_occurrence(h,f())\$
```
is called with a generator f() for some object type and with a hash-map h, passed by reference, i.e., quoted.
• Initialisation:
```oklib_load_all();
set_random_state(make_random_state(0));
h_rt5 : sm2hm({});
f_rt5 : lambda([],mg2g(random_tree(5))[2]);
test_generator(f_rt5,h_rt5);
```
• This computation can be interrupted, h evaluated by
```freq_rt5 : map(second,get_distribution(h_rt5));
N_rt5 : apply("+",freq_rt5);
min_rt5 : lmin(freq_rt5);
max_rt5 : lmax(freq_rt5);
q_rt5 : float(max_rt5 / min_rt5);
```
and then the computation continued (by "test_generator(f_rt5,h_rt5);").
• We obtain the data
1. N_rt5 = 7014267
2. q_rt5 = 24.65672898770423
• Considering the stars, we get
```create_list(ev_hm(h_rt5,star_g(5,i)), i,1,5);
[292774,72603,73530,73473,72716]
```
• For n=4:
```set_random_state(make_random_state(0));
h_rt4 : sm2hm({});
f_rt4 : lambda([],mg2g(random_tree(4))[2]);
test_generator(f_rt4,h_rt4);
dist_rt4 : get_distribution(h_rt4);
freq_rt4 : map(second,dist_rt4);
N_rt4 : apply("+",freq_rt4);
```
• We have four classes of trees (n=4; each with same likelihood):
1. C1 : The 6 trees (all pathgraphs)
```{{1,4},{2,3},{3,4}}
{{1,4},{2,3},{2,4}}
{{1,3},{2,4},{3,4}}
{{1,3},{2,3},{2,4}}
{{1,2},{2,4},{3,4}}
{{1,2},{2,3},{3,4}}
```
have probability p. They all have vertex 1 as endpoint.
2. C2 : The 3 trees (all stars)
```{{1,4},{2,4},{3,4}}
{{1,3},{2,3},{3,4}}
{{1,2},{2,3},{2,4}}
```
have probability 2p (they don't have vertex 1 as centre).
3. C3 : The 6 trees (all pathgraphs)
```{{1,3},{1,4},{2,4}}
{{1,3},{1,4},{2,3}}
{{1,2},{1,4},{3,4}}
{{1,2},{1,4},{2,3}}
{{1,2},{1,3},{3,4}}
{{1,2},{1,3},{2,4}}
```
have probability 3p (they don't have vertex 1 as endpoint).
4. C4 : The tree (a star)
```{{1,2},{1,3},{1,4}}
```
has probability 6p (it has vertex 1 as centre).
• The explanation is that "random_tree" implements a simple random process, which is captured by "randomtree_pr1".
• There are 4 isomorphism types of rooted trees with root 1 for n=4:
1. T1 = {{1,2},{2,3},{3,4}} (C1)
2. T2 = {{1,2},{2,3},{2,4}} (C2)
3. T3 = {{1,2},{1,3},{2,4}} (C3)
4. T4 = {{1,2},{1,3},{1,4}} (C4).
• We have the following probabilities for these four trees (showing the probabilities for the right new vertex and the right tree vertex):
1. T1 : (1/3*1) * (1/2*1/2) * (1*1/3) = 1/36
2. T2 : (1/3*1) * (1*1/2) * (1*1/2) = 2/36
3. T3 : (1/3*1) * (1/2*1/2) * (1*1/3) + (1/3*1) * (1*1/2) * (1*1/3) = 1/36 + 2/26 = 3/36
4. T4 : (1*1) * (1*1/2) * (1*1/3) = 6/36
• It remains to analyse randomtree_pr1:
1. Given a concrete tree, what's its probability?
2. Regarding isomorphisms of graphs: Do isomorphic trees have the same probability? No (see above).
3. Regarding isomorphisms of rooted trees (root always vertex 1): Do isomorphic rooted trees have the same probability?
4. If this is true, given an isomorphism class, what's its probability? For n=4 we have C1 -> 6/36, C2 -> 6/36, C3 -> 18/36, C4 -> 6/36.
Todo:
Evaluating uniform_randomtree_og
• As above, using
```test_generator(f,h) := do enter_new_occurrence(h,f())\$
```
with the following setting:
```oklib_load_all();
set_random_state(make_random_state(0));
h_rt5 : sm2hm({});
f_rt5 : lambda([],og2g(uniform_randomtree_og(5))[2]);
test_generator(f_rt5,h_rt5);
```
• Evaluation again by
```freq_rt5 : map(second,get_distribution(h_rt5));
N_rt5 : apply("+",freq_rt5);
min_rt5 : lmin(freq_rt5);
max_rt5 : lmax(freq_rt5);
q_rt5 : float(max_rt5 / min_rt5);
```

Definition in file Generators.hpp.