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.