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