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],
00080                        elementp(adjoin(x,a),S) and elementp(disjoin(x,b),S)),
00081                      setdifference(b,a)))
00082       do 0),
00083  found)$
00084