OKlibrary  0.2.1.6
Trees.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 7.5.2008 (Guangzhou) */
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/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/tests/HashMaps.mac")$
00025 
00026 kill(f)$
00027 
00028 
00029 /* *******************************************
00030    * Analysing unlabelled rooted trees       *
00031    *******************************************
00032 */
00033 
00034 okltest_canonical_tpd(f) := (
00035   assert(f([]) = [[[]],1]),
00036   assert(f([[]]) = [[[1], [[]]], 1]),
00037   assert(f([[[]]]) = [[[1], [[1], [[]]]], 1]),
00038   assert(f([[],[]]) = [[[1/2,1/2], [[]], [[]]], 2]),
00039   assert(f([[],[],[]]) = [[[1/3,1/3,1/3], [[]], [[]], [[]]], 3]),
00040   assert(f([[[]],[]]) = [[[1/2,1/2], [[1],[[]]], [[]]], 2]),
00041   assert(f([[[]],[[]]]) = [[[1/2,1/2], [[1],[[]]], [[1], [[]]]], 2]),
00042   assert(f([[[],[]], [[],[]], []]) = [[[2/5,2/5,1/5], [[1/2,1/2],[[]],[[]]], [[1/2,1/2],[[]],[[]]], [[]]], 5]),
00043   true)$
00044 
00045 okltest_uniform_tpd(f) := (
00046   assert(f([]) = [[]]),
00047   assert(f([[]]) = [[1],[[]]]),
00048   assert(f([[[]]]) = [[1],[[1],[[]]]]),
00049   assert(f([[],[]]) = [[1/2,1/2],[[]],[[]]]),
00050   assert(f([[],[],[]]) = [[1/3,1/3,1/3],[[]],[[]],[[]]]),
00051   assert(f([[[],[]],[]]) = [[1/2,1/2], [[1/2,1/2],[[]],[[]]], [[]]]),
00052   true)$
00053 
00054 
00055 /* **************************************************
00056    * Rooted trees labelled with branching tuples    *
00057    **************************************************
00058 */
00059 
00060 okltest_tbtp(f) := (
00061   assert(f(0) = false),
00062   assert(f([]) = false),
00063   assert(f([[]]) = true),
00064   assert(f([[[]]]) = false),
00065   assert(f([[0,0], [[]], [[]]]) = true),
00066   assert(f([[0,0,0], [[]], [[]], [[]]]) = true),
00067   assert(f([[0,0], [[0,0], [[]], [[]]], [[]]]) = true),
00068   assert(f([[0,0], [[0,0], [[]], [[]]], [[0],[]]]) = false),
00069   true)$
00070 
00071 okltest_min_sum_tbt(f) := block([x,y],
00072   assert(f([[]]) = [0]),
00073   assert(f([[1,2], [[]], [[]]]) = [1, [0], [0]]),
00074   assert(f([[x],[[y],[[]]]]) = [x+y,[y,[0]]]),
00075   assert(f([[1,2], [[3,4], [[]], [[]]], [[]]]) = [2, [3,[0],[0]], [0]]),
00076   true)$
00077 
00078 okltest_max_sum_tbt(f) := (
00079   assert(f([[]]) = [0]),
00080   assert(f([[1,2], [[]], [[]]]) = [2, [0], [0]]),
00081   assert(f([[x],[[y],[[]]]]) = [x+y,[y,[0]]]),
00082   assert(f([[1,2], [[3,4], [[]], [[]]], [[]]]) = [5, [4,[0],[0]], [0]]),
00083   true)$
00084 
00085 okltest_delta_tm(f) := block([x,y,z],
00086   assert(f([0]) = [[]]),
00087   assert(f([0,[0]]) = [[0],[[]]]),
00088   assert(f([x,[y]]) = [[x-y],[[]]]),
00089   assert(f([x,[y,[z]]]) = [[x-y],[[y-z],[[]]]]),
00090   assert(f([x,[y],[z]]) = [[x-y,x-z],[[]],[[]]]),
00091   assert(f([x,[y],[z,[1],[2]]]) = [[x-y,x-z],[[]],[[z-1,z-2],[[]],[[]]]]),
00092   assert(f([x,[y],[z],[5]]) = [[x-y,x-z,x-5],[[]],[[]],[[]]]),
00093   true)$
00094 
00095 okltest_tauprob_tbt(f) := block([x,res],
00096   assert(f([[]]) = [[]]),
00097   assert(f([[0],[[]]]) = [[1],[[]]]),
00098   assert(f([[x],[[]]]) = [[1],[[]]]),
00099   for l : 2 thru 4 do
00100    for v : 1 thru 3 do (
00101     res : f(cons(create_list(v,i,1,l), create_list([[]],i,1,l))),
00102     for r in res[1] do
00103      assert_float_equal(r,1/l)
00104   ),
00105   true)$
00106 
00107 okltest_tauprob_hp_tbt(f) := block([x,res,d:30],
00108   assert(f([[]],d) = [[]]),
00109   assert(f([[0],[[]]],d) = [[1],[[]]]),
00110   assert(f([[x],[[]]],d) = [[1],[[]]]),
00111   for l : 2 thru 4 do
00112    for v : 1 thru 3 do (
00113     res : f(cons(create_list(v,i,1,l), create_list([[]],i,1,l)), d),
00114     for r in res[1] do
00115      assert_bfloat_equal(r,1/l,d)
00116   ),
00117   true)$
00118 
00119 okltest_tauprob_symbolical_tbt(f) := block([x],
00120   assert(f([[]]) = [[]]),
00121   assert(f([[0],[[]]]) = [[1],[[]]]),
00122   assert(f([[x],[[]]]) = [[1],[[]]]),
00123   for l : 2 thru 4 do
00124    for v : 1 thru 3 do
00125     assert(f(cons(create_list(v,i,1,l), create_list([[]],i,1,l))) = cons(create_list(1/l,i,1,l), create_list([[]],i,1,l))),
00126   assert(f([[1,1], [[2,2],[[]],[[]]], [[]]]) = [[1/2,1/2], [[1/2,1/2],[[]],[[]]], [[]]]),
00127   true)$
00128 
00129 
00130 /* **********************************************************
00131    * Rooted trees labelled with probability distributions   *
00132    **********************************************************
00133 */
00134 
00135 okltest_ipd_rp(f) := (
00136   assert(eq_hmsm_p(f([[]]), {[1,1]}) = true),
00137   assert(eq_hmsm_p(f([[1/2,1/2],[[]],[[]]]), {[2,1]}) = true),
00138   assert(eq_hmsm_p(f([[1/3,2/3],[[]],[[]]]), {[3,1/3],[3/2,2/3]}) = true),
00139   assert(eq_hmsm_p(f([[1/3,2/3],[[1/2,1/2],[[]],[[]]],[[]]]), {[6,1/3],[3/2,2/3]}) = true),
00140   assert(eq_hmsm_p(f([[1/3,2/3],[[1/2,1/2],[[]],[[]]],[[1/4,3/4],[[]],[[]]]]), {[6,1/2],[2,1/2]}) = true),
00141   true)$
00142 
00143 okltest_maxtau_tbt(f) := block([x,y],
00144   assert(f([[]]) = 1),
00145   assert(f([[x],[[]]]) = 1),
00146   assert(f([[x],[[y],[[]]]]) = 1),
00147   assert_float_equal(f([[1,1],[[]],[[]]]), 2),
00148   assert_float_equal(f([[1,1],[[1,1,1],[[]],[[]],[[]]],[[]]]), 3),
00149   true)$
00150 
00151 okltest_mintau_tbt(f) := (
00152   assert(f([[]]) = inf),
00153   assert(f([[x],[[]]]) = 1),
00154   assert(f([[x],[[y],[[]]]]) = 1),
00155   assert_float_equal(f([[1,1],[[]],[[]]]), 2),
00156   assert_float_equal(f([[1,1],[[1,1,1],[[]],[[]],[[]]],[[]]]), 2),
00157   true)$
00158 
00159