OKlibrary  0.2.1.6
Basics.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 12.1.2008 (Swansea) */
00002 /* Copyright 2008, 2009, 2010, 2012 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/Graphs/Lisp/Basic.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/NumberTheory/Lisp/Auxiliary.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00027 
00028 
00029 /* ****************************
00030    * Unlabelled rooted trees  *
00031    ****************************
00032 */
00033 
00034 /* An "unlabelled rooted tree" is recursively defined as a list
00035    [T_1, ..., T_n], where the T_i are the subtrees (the case
00036    n=0, i.e., the empty list, represents the trivial tree).
00037 
00038    Note that these trees are ordered (the order of children matters).
00039 
00040    In other words, an "rt" is represented by a term which uses only
00041    "[", "]" and commas.
00042 */
00043 
00044 /* Checking whether T is an unlabelled rooted tree: */
00045 rt_p(T) := listp(T) and every_s(rt_p,T)$
00046 
00047 /* Checking whether for unlabelled rooted tree T every inner node
00048    has precisely 2 children:
00049 */
00050 rt2_p(T) := emptyp(T) or (length(T)=2 and every_s(rt2_p,T))$
00051 
00052 /* A "node representation" for an unlabelled rooted tree is a list
00053    of natural numbers (>= 1) representing the path from the root
00054    to the node. */
00055 
00056 /* The set of "leaves" of an unlabelled tree: */
00057 lvs(T) := if emptyp(T) then {[]} else
00058   lunion(
00059     map(lambda([S,i],map(lambda([p],cons(i,p)),S)), 
00060       map(lvs,T), 
00061       create_list(i,i,1,length(T))))$
00062 
00063 /* The set of "nodes" of an unlabelled tree: */
00064 nds(T) := adjoin([], lunion(
00065   map(lambda([S,i],map(lambda([p],cons(i,p)),S)), 
00066     map(nds,T), 
00067     create_list(i,i,1,length(T)))))$
00068 
00069 
00070 /* The subtree of unlabelled tree T at node (representation) p;
00071    prerequisite: p is a valid node representation for T, that is
00072    elementp(p,nds(T)) is true. */
00073 subtree(T,p) := if p = [] then T else
00074   subtree(T[p[1]], rest(p))$
00075 /* Remark: The subtree is a shallow copy, and so replacing an element of it
00076    will have the same effect for the original tree.
00077 */
00078 
00079 /* The successor nodes (i.e., representations) of node (representation) p
00080    in unlabelled tree T: */
00081 dst(T,p) := block([S : subtree(T,p)],
00082   setify(create_list(endcons(i,p),i,1,length(S))))$
00083 
00084 
00085 /* ****************************
00086    * Labelled rooted trees    *
00087    ****************************
00088 */
00089 
00090 /* A "labelled rooted tree" ("lrt") is recursively defined as a list
00091    [L, T_1, ..., T_n], n >= 0, where L is the label, and the T_i
00092    are the subtrees.
00093 */
00094 
00095 /* Checking whether T is a labelled rooted tree: */
00096 lrt_p(T) := listp(T) and is(length(T) >= 1) and every_s(lrt_p,rest(T))$
00097 
00098 
00099 /* For a node-representation p in the labelled tree T, compute the label: */
00100 ndrep2l_lrt(p,T) := if emptyp(p) then first(T) else
00101  ndrep2l_lrt(rest(p), T[first(p) + 1])$
00102 
00103 
00104 /* Transforms a labelled into an unlabelled tree by removing the labels: */
00105 /* UPDATE: rename to lrt2rt. */
00106 l2ult(T) := map(l2ult,rest(T))$
00107 lrt2rt(T) := l2ult(T)$
00108 
00109 /* Apply map lmap_ to all labels of lrt T (obtaining another lrt): */
00110 lmap_lrt(T, lmap_) := cons(lmap_(first(T)),
00111  map(lambda([t], lmap_lrt(t, lmap_)), rest(T)))$
00112 
00113 
00114 /* Adding labels from list L to unlabelled tree T at inner nodes in in-order,
00115    while leaves are labelled by l.
00116    Prerequisite: the length of L is at least the number of inner nodes of T.
00117 */
00118 rt2lrt_il(T,L,l) := if emptyp(T) then [l] else
00119   block([res : [first(L)]],
00120     L : rest(L),
00121     for S in T do block([n : ninds_rt(S)],
00122       res : cons(rt2lrt_il(S, take_l(n,L), l), res),
00123       L : rest(L,n)
00124     ),
00125     reverse(res))$
00126 
00127 /* The set of leaf-labels: */
00128 ll_lrt(T) := if length(T) = 1 then {first(T)}
00129 else lunion(map(ll_lrt,rest(T)))$
00130 /* The list-form (listing the leaf-labels from left to right): */
00131 lll_lrt(T) := if length(T) = 1 then [first(T)]
00132 else lappend(map(lll_lrt,rest(T)))$
00133 
00134 /* The set of non-leaf-node-labels: */
00135 il_lrt(T) := if length(T) = 1 then {}
00136 else adjoin(first(T), lunion(map(il_lrt,rest(T))))$
00137 
00138 /* The set of all labels: */
00139 l_lrt(T) := adjoin(first(T), lunion(map(l_lrt,rest(T))))$
00140 /* The list of labels, in pre-order: */
00141 preorderl_lrt(T) := cons(first(T), lappend(map(preorderl_lrt, rest(T))))$
00142 /* The list of labels, first sorted by level-order, then from left to right: */
00143 levelorderl_lrt(T) := map(first,
00144  sort(preorderl_lrt(depth_annotation_lrt(T)),
00145       lambda([p1,p2], is(second(p1) < second(p2)))))$
00146 
00147 
00148 /* Replacing every label l with the pair [l,d], where d is the depth of
00149    the node (the distance to the root):
00150 */
00151 depth_annotation_g_lrt(T,k) :=
00152  cons([first(T), k], map(lambda([t], depth_annotation_g_lrt(t,k+1)), rest(T)))$
00153 depth_annotation_lrt(T) := depth_annotation_g_lrt(T,0)$
00154 
00155 
00156 /* ************
00157    * Measures *
00158    ************
00159 */
00160 
00161 /* The number of nodes in an unlabelled tree: */
00162 /* RENAME: nnds_rt */
00163 nnds(T) := 1+sum_l(map(nnds,T))$
00164 nnds_rt(T) := nnds(T)$
00165 /* Number of nodes in a labelled rooted tree: */
00166 /* RENAME: nnds_lrt */
00167 nnds_l(T) := 1+sum_l(map(nnds_l,rest(T)))$
00168 nnds_lrt(T) := nnds_l(T)$
00169 
00170 /* The number of leaves in an unlabelled rooted tree: */
00171 /* RENAME: nlvs_rt */
00172 nlvs(T) := if emptyp(T) then 1 else sum_l(map(nlvs,T))$
00173 nlvs_rt(T) := nlvs(T)$
00174 /* The number of leaves in a labelled rooted tree: */
00175 /* RENAME: nlvs_lrt */
00176 nlvs_l(T) := if length(T) = 1 then 1 else sum_l(map(nlvs_l,rest(T)))$
00177 nlvs_lrt(T) := nlvs_l(T)$
00178 
00179 /* The number of inner nodes in an unlabelled rooted tree: */
00180 ninds_rt(T) := if emptyp(T) then 0 else 1+sum_l(map(ninds_rt,T))$
00181 /* The number of inner nodes in a labelled rooted tree: */
00182 ninds_lrt(T) := if length(T) = 1 then 0 else 1+sum_l(map(ninds_lrt,rest(T)))$
00183 
00184 /* We have nnds(T) = nlvs(T) + ninds(T). */
00185 
00186 /* The height of an unlabelled tree: */
00187 /* RENAME: height_rt */
00188 height(T) := if T = [] then 0 else
00189   1 + lmax(map(height,T))$
00190 height_rt(T) := height(T)$
00191 
00192 /* The "levelled height" of an unlabelled tree 
00193    (also the "Horton-Strahler number"): */
00194 /* RENAME: levelled_height_rt */
00195 levelled_height(T) := if T = [] then 0 else block(
00196   [H : map(levelled_height,T), max, count : 0],
00197    max : lmax(H),
00198    for h in H unless count=2 do
00199      if h=max then count : count + 1,
00200    if count <= 1 then return(max) else return(1+max))$
00201 levelled_height_rt(T) := levelled_height(T)$
00202 
00203 
00204 /* ****************
00205    * Transformers *
00206    ****************
00207 */
00208 
00209 /* Transforms a graph G, which is a tree, into a labelled rooted tree 
00210    (using root r, and the natural order on the vertices of G): */
00211 g2lrt(G,r) := block([N : listify(neighbours(r,G))],
00212  return(cons(r, create_list(g2lrt(remove_vertices_graph({r},G),v),v,N))))$
00213 
00214 
00215 /* **************
00216    * Generators *
00217    **************
00218 */
00219 
00220 /* The complete (unlabelled, rooted) tree of depth d and with q children at
00221    each inner node: */
00222 complete_rt(d,q) := if d=0 then [] else
00223   create_list(complete_rt(d-1,q),i,1,q)$
00224 
00225 oklib_plain_include(graphs)$
00226 /* A random labelled tree with n vertices (labels 1,...,n; root is 1) */
00227 random_lrt(n) := g2lrt(mg2g(random_tree(n)),1);
00228 
00229 
00230 /* The list of all binary unlabelled trees with m nodes (recursively
00231    created, with increasing node number in the left subtree).
00232    Prerequisite: m is an odd natural number.
00233 
00234    Note that "binary" here just means that every inner node has exactly
00235    two children (while we are considering unlabelled rooted trees as
00236    defined above).
00237 */
00238 oklib_plain_include("integer_sequence")$
00239 all2_rt(m) := if m=1 then [[]] else
00240   lappend(create_list(
00241     cartesian_product_l([all2_rt(a),all2_rt(m-a-1)]), 
00242     a, 1 .. 2 .. m-2))$
00243 /* The number of all these trees: */
00244 num_all2_rt(m) := num_all2i_rt((m-1)/2)$
00245 /* Now given the number i of inner nodes (a natural number >= 0): */
00246 all2i_rt(i) := all2_rt(2*i+1)$
00247 /* The number of all these trees: */
00248 num_all2i_rt(i) := catalan_number(i)$
00249 /* And given the number of leaves (a natural number >= 1): */
00250 all2l_rt(l) := all2_rt(2*l-1)$
00251 /* The number of all these trees: */
00252 num_all2l_rt(l) := num_all2i_rt(l-1)$
00253 
00254 /* Creating "random" binary unlabelled trees with m nodes, by a simple
00255    random process where all possibilities for distributions of node
00256    counts on the two children are equally likely (this does not create the
00257    uniform distribution over all binary unlabelled trees).
00258    Prerequisite: m is an odd natural number.
00259 */
00260 random2_rt(m) := if m=1 then [] else
00261  block([num_possibilities : (m-1)/2, rand, left, right],
00262   rand : random(num_possibilities),
00263   left : 1 + rand * 2,
00264   right : (m-1) - left,
00265   [random2_rt(left), random2_rt(right)])$
00266 
00267 /* The variation which allows single nodes: Now all node distributions
00268    over left and right subtree are possible (and equally likely), and
00269    the cases with empty left or empty right subtree create a single node.
00270    (Thus single nodes are the likelier the smaller the (sub-)tree.
00271    Prerequisite: m >= 1 is an natural number.
00272 */
00273 random12_rt(m) := if m=1 then [] else if m=2 then [[]] else
00274  block([left, right],
00275   left : random(m),
00276   right : (m-1) - left,
00277   if left=0 then [random12_rt(right)] else
00278   if right=0 then [random12_rt(left)]
00279   else [random12_rt(left), random12_rt(right)])$
00280 
00281 /* The list of all unlabelled (rooted) trees with m nodes (where m is
00282    an integer).
00283    The order is is given by the lexicographical order of unordered integer
00284    partitions (recursively).
00285 */
00286 all_rt(m) := if m <= 0 then [] elseif m=1 then [[]] else
00287   lappend(create_list(cartesian_product_l(map(all_rt,p)), p, listify(uinteger_partitions(m-1))))$
00288 /* The number of all these trees: */
00289 num_all_rt(m) := if m <= 0 then 0 else catalan_number(m-1)$
00290 
00291 catalan_number(n) :=  binomial(2*n,n)/(n+1)$
00292 
00293 
00294 /* **************
00295    * Operations *
00296    **************
00297 */
00298 
00299 /* The mirror image of trees: */
00300 mirror_rt(T) := reverse(map(mirror_rt,T))$
00301 
00302 /* A "labelled tree with 2-dimensional coordinates", short "tdlrt",
00303    is a labelled tree, where each label is a list containing a
00304    list of 2 elements (the coordinates) as first element.
00305 */
00306 
00307 /* Testing whether T is a labelled tree with 2-dimensional coordinates: */
00308 tdlrt_p(T) := listp(T) and is(length(T) >= 1) and listp(first(T))
00309 and is(length(first(T)) >= 1) and listp(first(first(T))) and
00310 is(length(first(first(T))) = 2) and every_s(tdlrt_p,rest(T))$
00311 
00312 
00313 /* Given a labelled tree T with 2-dimensional coordinates and
00314    a coordinate vector p, translate the coordinates by p:
00315 */
00316 trans_lrt(T,p) := 
00317  cons(cons(first(first(T))+p, rest(first(T))), 
00318       map(lambda([S],trans_lrt(S,p)),rest(T)))$
00319 
00320 
00321 /* The top-most (i.e., minimal) y-coordinate of a labelled rooted tree with
00322    2-dimensional coordinates: */
00323 y_extreme_tdlrt(T) := if length(T)=1 then y_tdlrt(T) else
00324          lmin(map(y_extreme_tdlrt,rest(T)))$
00325 
00326 
00327 /* Access-functions for labelled rooted trees with 2-dimensional coordinates:
00328 */
00329 x_tdlrt(T) := T[1][1][1]$
00330 y_tdlrt(T) := T[1][1][2]$
00331 
00332