OKlibrary  0.2.1.6
Basics.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 26.5.2012 (Swansea) */
00002 /* Copyright 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/Hypergraphs/Lisp/Basics.mac")\$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")\$
00024 oklib_include("OKlib/ComputerAlgebra/Matroids/Lisp/Basics.mac")\$
00025
00026
00027 /* ***********************
00028    * Fundamental notions *
00029    ***********************
00030 */
00031
00032 /* Checking whether M is a greedoid given by the feasible sets: */
00033 grdfs_p(M) := hg_p(M) and not emptyp(second(M)) and
00034  accessible_ss_p(second(M)) and augmentation_ss_p(second(M))\$
00035
00036
00037 /* Computing the rank of a greedoid G: */
00038 rank_grdfs(G) := lmax(map(length,G[2]))\$
00039
00040 /* Computing the set of bases of a greedoid G: */
00041 bases_grdfs(G) := block([r : rank_grdfs(G)],
00042  subset(G[2], lambda([H], is(length(H)=r))))\$
00043
00044 /* For a greedoid G and a set A, the greedoid given by all the feasible sets
00045    contained in A:
00046 */
00047 restriction_grdfs(G,A) := [A, subset(G[2], lambda([B], subsetp(B,A)))]\$
00048
00049
00050 /* ******************************
00051    * Special forms of greedoids *
00052    ******************************
00053 */
00054
00055 /* Whether G is an antimatroid given by the feasible sets: */
00056 antimtrfs_p(G) := hg_p(G) and elementp({},second(G)) and
00057  accessible_ss_p(second(G)) and bunion_closed_p(second(G))\$
00058
00059
00060 /* Whether the greedoid G is an interval greedoid: */
00061 intervalgrdfs_p(G) := block([B : bases_grdfs(G)],
00062  every_s(lambda([A], antimtrfs_p(restriction_grdfs(G,A))), B))\$
00063 /* Remark: Here the characterisation is used, that a greedoid G is an interval
00064    greedoid iff every restriction to a feasible set is an antimatroid.
00065    Are there more efficient tests?
00066 */
00067
00068 /* A greedoid G is Gaussian iff G[2] fulfils the following Gaussian
00069    property:
00070 */
00071 gaussian_ss_p(S) := block(
00072 [A : sort_length_part_ary(listify(disjoin({},S))), l, j, found : true],
00073  l : A[0],
00074  for i : 1 thru l-1 while found do (
00075   j : i+1,
00076   if length(first(A[i]))+1 = length(first(A[j])) then
00077    for a in A[i] while found do
00078     for b in A[j] while
00079      (found : some_s(lambda([x],