OKlibrary  0.2.1.6
MaintainingBound.mac
Go to the documentation of this file.
```00001 /* Oliver Kullmann, 20.6.2009 (Swansea) */
00002 /* Copyright 2009, 2010 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/TestSystem/Lisp/Asserts.mac")\$
00023 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Generators/VanderWaerden.mac")\$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")\$
00025
00026 kill(f)\$
00027
00028
00029 /* *************************************
00030    * Finding size-bounded transversals *
00031    *************************************
00032 */
00033
00034 okltest_transversals_be(f) := (
00035   assert(f([],0) = [{}]),
00036   assert(f([],1) = [{}]),
00037   assert(f([{}],0) = []),
00038   assert(f([{}],1) = []),
00039   assert(f([{1}],0) = []),
00040   assert(f([{1}],1) = [{1}]),
00041   assert(f([{1}],2) = [{1}]),
00042   assert(f([{1,2}],0) = []),
00043   assert(f([{1,2}],1) = [{1},{2}]),
00044   assert(f([{1,2}],2) = [{1},{2}]),
00045   assert(f([{1,2},{2,3}],0) = []),
00046   assert(f([{1,2},{2,3}],1) = [{2}]),
00047   assert(elementp(f([{1,2},{2,3}],2), {[{1,2},{1,3},{2}], [{2},{1,3}]}) = true),
00048   assert(f([{1,2,3},{1,3},{1,2}],1) = [{1}]),
00049   assert(f([{1,2},{1,3},{2,3}],1) = []),
00050   true)\$
00051
00052
00053 /* ********************************
00054    * Finding minimum transversals *
00055    ********************************
00056 */
00057
00058 okltest_minimum_transversals_lbbvs_hg(f) := (
00059   /* XXX */
00060   true)\$
00061
00062 /* Generic test for algorithms which compute the set of minimum transversals
00063    of a hypergraph (which does not contain the empty hyperedge):
00064 */
00065 okltest_minimum_transversals_hg(f) := (
00066   assert(f([{},{}]) = {{}}),
00067   assert(f([{1},{}]) = {{}}),
00068   assert(f([{1,2},{}]) = {{}}),
00069   assert(f([{1},{{1}}]) = {{1}}),
00070   assert(f([{1,2,3,4},{{1,2},{3,4}}]) = {{1,3},{1,4},{2,3},{2,4}}),
00071   assert(f([{1,2,3},{{1,2},{2,3}}]) = {{2}}),
00072   for n : 0 thru 5 do block([N : setn(n)],
00073     assert(f([N, singletons(N)]) = {N})),
00074   /* XXX */
00075   true)\$
00076
00077
00078 /* *********************************
00079    * Monotone hypergraph sequences *
00080    *********************************
00081 */
00082
00083 okltest_minimum_transversals_mongen(f) := block(
00084  [A3_ : lambda([n], arithprog_hg(3,n))],
00085   assert(map(length,f(10,A3_,[{}])) = [1,1,1,3,2,1,4,10,25,4,24]),
00086   true)\$
00087
00088
00089 /* *********************************
00090    * Stratification of hypergraphs *
00091    *********************************
00092 */
00093
00094
```