OKlibrary  0.2.1.6
Trees.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 5.1.2008 (Swansea) */
00002 /* Copyright 2008, 2009 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007
00022 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/BranchingTuples/Basic.mac")\$
00023 oklib_include("OKlib/ComputerAlgebra/Graphs/Lisp/Basic.mac")\$
00024 oklib_include("OKlib/ComputerAlgebra/Trees/Lisp/Basics.mac")\$
00025 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")\$
00026 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")\$
00027
00028
00029 /* **********************************************************
00030    * Rooted trees labelled with probability distributions   *
00031    **********************************************************
00032 */
00033
00034 /*
00035    A "rooted tree with tree probability distribution (tpd)" is recursively
00036    defined as [[p_1, ..., p_n], T_1, ..., T_n] (n >= 0) where p_i are the
00037    probabilities attached to subtree T_i (n = 0 is the case of a leaf).
00038 */
00039
00040 /* For the following functions the input T is a tree with tpd. */
00041
00042 /* the probability distribution induced on the leaves by a tree with tpd */
00043 tpd_flatten(T) := if T = [[]] then [1] else
00044  xreduce(append, T[1] * map(tpd_flatten, rest(T)))\$
00045
00046 /* the r-th moment of the random variable prob^-1 */
00047 tpd_moment(T,r) := xreduce("+",tpd_flatten(T)^(1-r))\$
00048 /* We have tpd_moment(T,r) = length(tpd_flatten(T)). */
00049
00050 /* the variance of the random variable prob^-1 */
00051 tpd_variance(T) := tpd_moment(T,2) - nlvs_l(T)^2\$
00052
00053 /* the lower bound on the number of leaves associated with the random variable prob^-1 */
00054 lower_bound_nlvs(T) := 1 / lmax(tpd_flatten(T))\$
00055
00056 /* the upper bound on the number of leaves associated with the random variable prob^-1 */
00057 upper_bound_nlvs(T) := 1 / lmin(tpd_flatten(T))\$
00058
00059
00060 /* The induced probability distribution of the random variable prob^-1
00061    as a hash-table. */
00062 /* ATTENTION: The hash-map will only work correctly if the expressions
00063    stored in it (as strings!) are equal iff they are identical. */
00064 ipd_rp(T) := block([P : tpd_flatten(T), h : sm2hm({})],
00065  for p in P do block([rp : 1/p],
00066    set_hm(h,rp,ev_hm_d(h,rp,0)+p)),
00067  return(h))\$
00068
00069
00070 /* *******************************************
00071    * Analysing unlabelled rooted trees       *
00072    *******************************************
00073 */
00074
00075 /* For an unlabelled tree T, returns (as a pair) the tree equipped with the
00076    canonical tpd together with the number of leaves: */
00077 canonical_tpd(T) := if emptyp(T) then [[[]],1] else
00078  block([S : map(canonical_tpd,T), s],
00079   s : sum_l(map(second,S)),
00080   return([cons(map(second,S)/s, map(first,S)), s]))\$
00081
00082 /* Simpler, equip unlabelled tree T with the uniform tpd at each node: */
00083 uniform_tpd(T) := block([l : length(T)],
00084   cons(create_list(1/l,i,1,l), map(uniform_tpd,T)))\$
00085
00086
00087 /* **************************************************
00088    * Rooted trees labelled with branching tuples    *
00089    **************************************************
00090 */
00091
00092 /* A "distance" on a rooted tree is given by a labelling of the nodes
00093    with branching tuples (of the same width as the branching), while
00094    a "measure" is given by a node-labelling with numbers.
00095    Trees with distances are treated here as "trees with branching tuples".
00096 */
00097
00098 /* Check whether T is "formally" a tree with distances
00099    (or "with branching tuples"): */
00100 tbtp(T) := if not listp(T) then false else block([l : length(T)],
00101   is(l > 0) and listp(T[1]) and length(T[1]) = l-1 and
00102    every_s(tbtp, rest(T)))\$
00103
00104
00105 /* Transformations of a tree with distances to a tree with measure */
00106
00107 /* The min-sum of a tree with branching tuples: */
00108 min_sum_tbt(T) := if length(T) = 1 then [0] else
00109  block([L : map(min_sum_tbt,rest(T))],
00110   return(cons(lmin(T[1] + map(first,L)), L)))\$
00111
00112 /* The max-sum of a tree with branching tuples: */
00113 max_sum_tbt(T) := if length(T) = 1 then [0] else
00114  block([L : map(max_sum_tbt,rest(T))],
00115   return(cons(lmax(T[1] + map(first,L)), L)))\$
00116
00117
00118 /* Transformation of a tree with measure to a tree with distance: */
00119
00120 /* The differences for a tree with a measure: */
00121 delta_tm(T) := if length(T) = 1 then [[]] else
00122  cons(T[1]-map(first,rest(T)), map(delta_tm,rest(T)))\$
00123
00124
00125 /* Transformation of a tree with distances to a tree with tpd: */
00126 tauprob_tbt(T) := if length(T) = 1 then [[]] else
00127  cons(tauprob(T[1]), map(tauprob_tbt, rest(T)))\$
00128 /* The same, but with higher precision: */
00129 tauprob_hp_tbt(T,d) := if length(T) = 1 then [[]] else
00130  cons(tauprob_hp(T[1],d), map(lambda([t], tauprob_hp_tbt(t,d)), rest(T)))\$
00131 /* The same, but using symbolical calculations (if possible!): */
00132 tauprob_symbolical_tbt(T) := if length(T) = 1 then [[]] else
00133  cons(tauprob_symbolical(T[1]), map(tauprob_symbolical_tbt, rest(T)))\$
00134
00135
00136 /* The maximal tau-value for a tree with distances: */
00137 maxtau_tbt(T) := if length(T) = 1 then 1 else
00138  max(tau(T[1]), lmax(map(maxtau_tbt,rest(T))))\$
00139 /* The minimal tau-value for a tree with distances: */
00140 mintau_tbt(T) := if length(T) = 1 then inf else
00141  min(tau(T[1]), lmin(map(mintau_tbt, rest(T))))\$
00142
00143
00144 /* The lower bound on nlvs for a tree with distances given by
00145    the tau-function */
00146 lower_bound_nlvs_tau(T) := mintau_tbt(T)^(min_sum_tbt(T)[1])\$
00147 /* The upper bound on nlvs for a tree with distances given by
00148    the tau-function */
00149 upper_bound_nlvs_tau(T) := maxtau_tbt(T)^(max_sum_tbt(T)[1])\$
00150
00151
```