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.
00057  - Add edge {u,v}.
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