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