OKlibrary  0.2.1.6
Generators.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 15.7.2008 (Swansea) */
00002 /* Copyright 2008 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/Hypergraphs/Lisp/SetSystems.mac")\$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")\$
00024 oklib_include("OKlib/ComputerAlgebra/Graphs/Lisp/Trees/Representations.mac")\$
00025
00026
00027 /* **********************
00028    * Some special trees *
00029    **********************
00030 */
00031
00032 /* pathgraph_og(n) creates a path of length n
00033    (in ComputerAlgebra/Graphs/Lisp/Generators.mac).
00034 */
00035 /* For a list-permutation of length n the corresponding path graph
00036    (with standardised vertex-set {1,...,n}: */
00037 path_p_og(P) := block([n : length(P)],
00038  [create_list(i,i,1,n),
00039   create_list({P[i],P[i+1]},i,1,n-1)])\$
00040 /* pathgraph_og(n) = path_p_og(create_list(i,i,1,n)) */
00041
00042 /* The star with vertex set V and centre r: */
00043 star_V_g(V,r) := map(lambda([v],{r,v}), disjoin(r,V))\$
00044 /* The special case with standardised vertex set {1,...,n}: */
00045 star_g(n,r) := star_V_g(setn(n),r)\$
00046
00047
00048 /* ****************
00049    * Random trees *
00050    ****************
00051 */
00052
00053 /* Creating a random (rooted) tree according to "process 1":
00054  - Choose a random vertex u from the vertices not yet in the
00055    tree.
00056  - Choose a random vertex v in the current tree.
00058
00059    The vertex set is standardised, and the root is vertex 1.
00060 */
00061 /* Replaces the Maxima/graphs function random_tree (which does
00062    not use random(), and thus is not reproducible for us). */
00063 /* Prerequisite: n >= 1. */
00064 randomtree_pr1_og(n) := block(
00065  [V : create_list(i,i,2,n), R],
00066   R : random_permutation(V),
00067   V : cons(1,V), R : cons(1,R),
00068   [V, map(lambda([u,i],block([v:random_element_ab(1,i,R)],{u,v})),
00069           rest(R), rest(V,-1))])\$
00070
00071 /* Creating a standardised random tree, drawn from the uniform distribution.
00072    Remark: As with randomtree_pr1_og, the output is ordered, but w.r.t.
00073    randomness (unordered) trees have to be considered.
00074 */
00075 /* Prerequisite: n >= 1. */
00076 uniform_randomtree_og(n) :=
00077   pruefercode2tree_og(create_list(i,i,1,n), create_list(random(n)+1,i,1,n-2))\$
00078
```