OKlibrary  0.2.1.6
RecursiveSplitting.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/Generators.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Generators/VanderWaerden.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/tests/IndependentSets.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Transversals/Minimal/RecursiveSplitting.mac")$
00028 
00029 kill(f)$
00030 
00031 
00032 /* ************************************
00033    * Finding all minimal transversals *
00034    ************************************
00035 */
00036 
00037 /* Helper function for testing whether f applied twice to hypergraph G
00038    yields G after removal of subsumed elements from G:
00039 */
00040 check_involutiv_min(f,G) := block([G2 : f(f(G))],
00041   is(G2[1] = G[1] and G2[2] = min_elements(G[2])))$
00042 
00043 /* Testing whether f computes the transversal hypergraph of a hypergraph G: */
00044 okltest_transversal_hyp(f) := block([G],
00045   assert(f([{},{}]) = [{},{{}}]),
00046   assert(f([{},{{}}]) = [{},{}]),
00047   assert(f([{1,2},{{1,2}}]) = [{1,2},{{1},{2}}]),
00048   assert(f([{1,2,3,4},{{1,2},{1,3},{1,4}}]) = [{1,2,3,4},{{1},{2,3,4}}]),
00049   assert(check_involutiv_min(f,[{1,2,3,4},{{1,2},{1,2,4},{2,3},{1,3}}])),
00050   for k : 0 thru 3 do
00051     for n : 0 thru 6 do
00052       assert(check_involutiv_min(f,arithprog_hg(k,n))),
00053   if oklib_test_level = 0 then return(true),
00054   block([oklib_test_level : min(oklib_test_level-1, 2)],
00055     okltest_independence_hyp(buildq([f],lambda([G],ecomp_hyp(f(G)))))
00056   ),
00057 true)$
00058 
00059 /* Testing whether f(N,mongen_) computes the list of all transversals
00060    for n = 0,...,N for monoton hypergraph generator mongen_ (adding
00061    exactly one new vertex at a time, and all new hyperedges contain this
00062    vertex).
00063 */
00064 okltest_transversals_mongen(f) := (
00065   block([N : 5],
00066    for r : 0 thru 3 do block([G : lambda([n], complete_stdhg(n,r)), L],
00067     L : f(N,G),
00068     for i : 1 thru N+1 do block([n : i-1],
00069       if n < r then
00070         assert(L[i] = [{}])
00071       else block([res : powerset(setn(n),n-r+1)],
00072         assert(length(L[i]) = length(res)),
00073         assert(setify(L[i]) = res)
00074   )))),
00075   block(
00076    [N : if oklib_test_level=0 then 8 else 12, 
00077     G : lambda([n],arithprog_hg(3,n)), L],
00078     L : f(N,G),
00079     for i : 1 thru N+1 do block([n : i-1, res],
00080       res : transversal_hg_rs(G(n))[2],
00081       assert(setify(L[i]) = res),
00082       assert(length(L[i]) = length(res))
00083   )),
00084   true)$
00085 
00086 /* Testing the more general function, which requires to specify a start
00087    value n0 and a (complete) list of transversals (w.r.t. n0):
00088 */
00089 okltest_transversals_mongen_init(f) := (
00090   block([N0 : 3, N : 5],
00091    for r : 0 thru 3 do block([G : lambda([n], complete_stdhg(n,r)), L],
00092     L : f(N,G,N0,listify(transversal_ses_rs(G(N0)[2]))),
00093     for i : 1 thru N+1-N0 do block([n : N0+i-1],
00094       if n < r then
00095         assert(L[i] = [{}])
00096       else block([res : powerset(setn(n),n-r+1)],
00097         assert(length(L[i]) = length(res)),
00098         assert(setify(L[i]) = res)
00099   )))),
00100   true)$
00101 
00102