OKlibrary  0.2.1.6
Homomorphisms.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 2.11.2011 (Swansea) */
00002 /* Copyright 2011, 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/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Generators/Generators.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/tests/Colouring.mac")$
00026 
00027 
00028 kill(f)$
00029 
00030 
00031 /* *****************
00032    * Basic notions *
00033    *****************
00034 */
00035 
00036 okltest_homomorphism_bydef_hg(f) := (
00037   assert(f(identity,[{},{}],[{},{}]) = true),
00038   assert(f(identity,[{},{}],[{},{{}}]) = true),
00039   assert(f(identity,[{},{{}}],[{},{}]) = false),
00040   assert(f(identity,[{1},{}],[{},{}]) = false),
00041   assert(f(identity,[{1},{}],[{1},{}]) = true),
00042   assert(f(identity,[{1},{}],[{1,2},{{}}]) = true),
00043   assert(f(lambda([x],x-1), [{1,2,3},{{1},{2,3},{1,3}}],[{0,1,2},{{0},{1,2},{0,2}}]) = true),
00044   assert(f(lambda([x],x-1), [{1,2,3},{{1},{2,3},{1,3}}],[{0,1,2},{{0},{1,2},{0,1}}]) = false),
00045   true)$
00046 
00047 okltest_automorphism_bydef_hg(f) := (
00048   assert(f(identity,[{},{}]) = true),
00049   assert(f(identity,[{},{{}}]) = true),
00050   assert(f(identity,[{1},{}]) = true),
00051   assert(f(identity,[{1},{{}}]) = true),
00052   /* XXX */
00053   true)$
00054 
00055 okltest_suphomomorphism_bydef_hg(f) := (
00056   assert(f(identity,[{},{}],[{},{}]) = true),
00057   assert(f(identity,[{},{}],[{},{{}}]) = true),
00058   assert(f(identity,[{},{{}}],[{},{}]) = false),
00059   assert(f(identity,[{1},{}],[{},{}]) = false),
00060   assert(f(identity,[{1},{}],[{1},{}]) = true),
00061   assert(f(identity,[{1},{}],[{1,2},{{}}]) = true),
00062   assert(f(lambda([x],x-1), [{1,2,3},{{1},{2,3},{1,3}}],[{0,1,2},{{0},{1,2},{0,2}}]) = true),
00063   assert(f(lambda([x],x-1), [{1,2,3},{{1},{2,3},{1,3}}],[{0,1,2},{{0},{1,2},{0,1}}]) = true),
00064   assert(f(identity,[{1,2,3},{{1,3},{2,4},{1,4}}],[{1,2,3,4},{{2},{1,3}}]) = false),
00065  assert(f(identity,[{1,2,3},{{1,3},{2,4},{1,4}}],[{1,2,3,4},{{2},{1}}]) = true),
00066   true)$
00067 
00068 okltest_transport_hg(f) := (
00069   assert(f(identity,[{},{}]) = [{},{}]),
00070   assert(f(identity,[{1,2},{{},{1},{2}}]) = [{1,2},{{},{1},{2}}]),
00071   assert(f(lambda([x],1), [{1,2,3},{{1,2},{2,3}}]) = [{1},{{1}}]),
00072   true)$
00073 
00074 
00075 /* **************************
00076    * Special transport-maps *
00077    **************************
00078 */
00079 
00080 okltest_colouring_blocks(f) := block([A,c],
00081   A : il2ary([]),
00082   c : f(A,1),
00083   assert(c(0) = 0),
00084   A : il2ary([1]),
00085   c : f(A,1),
00086   assert(create_list(c(i),i,0,1) = [1,1]),
00087   c : f(A,2),
00088   assert(create_list(c(i),i,0,1) = [1,1]),
00089   A : il2ary([1,2]),
00090   c : f(A,1),
00091   assert(create_list(c(i),i,0,2) = [2,1,2]),
00092   c : f(A,2),
00093   assert(create_list(c(i),i,0,2) = [2,1,1]),
00094   c : f(A,3),
00095   assert(create_list(c(i),i,0,2) = [2,1,1]),
00096   A : il2ary([3,2,1]),
00097   c : f(A,1),
00098   assert(create_list(c(i),i,0,3) = [3,3,2,1]),
00099   c : f(A,2),
00100   assert(create_list(c(i),i,0,3) = [3,2,1,1]),
00101   c : f(A,3),
00102   assert(create_list(c(i),i,0,3) = [3,1,1,1]),
00103   A : il2ary([1,2,3]),
00104   c : f(A,1),
00105   assert(create_list(c(i),i,0,3) = [3,1,2,3]),
00106   c : f(A,2),
00107   assert(create_list(c(i),i,0,3) = [3,1,1,2]),
00108   c : f(A,3),
00109   assert(create_list(c(i),i,0,3) = [3,1,1,1]),
00110   A : il2ary([3,2,1,4]),
00111   c : f(A,1),
00112   assert(create_list(c(i),i,0,4) = [4,3,2,1,4]),
00113   c : f(A,2),
00114   assert(create_list(c(i),i,0,4) = [4,2,1,1,2]),
00115   c : f(A,3),
00116   assert(create_list(c(i),i,0,4) = [4,1,1,1,2]),
00117   c : f(A,4),
00118   assert(create_list(c(i),i,0,4) = [4,1,1,1,1]),
00119   true)$
00120 
00121 okltest_random_colouring(f) := block([c],
00122   for n : 1 thru 5 do (
00123     c : f(n,n),
00124     for i : 1 thru n do
00125       assert(c(i) = 1)
00126   ),
00127   set_random(1),
00128   c : f(5,1),
00129   assert(create_list(c(i),i,1,5) = [1,5,3,4,2]),
00130   c : f(5,2),
00131   assert(create_list(c(i),i,1,5) = [3,2,1,1,2]),
00132   true)$
00133 
00134 okltest_random_projection_hg(f) := (
00135   assert(f([{},{}],1) = [{},{}]),
00136   assert(f([{},{{}}],1) = [{},{{}}]),
00137   assert(f([{1},{}],1) = [{1},{}]),
00138   assert(f([{1},{{}}],1) = [{1},{{}}]),
00139   set_random(1),
00140   assert(f([{1,2,3,4,5},{{1,2},{2,3},{3,4},{4,5}}],1) = [{1,2,3,4,5},{{1,5},{5,3},{3,4},{4,2}}]),
00141   assert(f([{1,2,3,4,5},{{1,2},{2,3},{3,4},{4,5}}],2) = [{1,2,3},{{3,2},{2,1},{1},{1,2}}]),
00142   true)$
00143 
00144 okltest_random_projection_min_hg(f) := (
00145   assert(f([{},{}],1) = [{},{}]),
00146   assert(f([{},{{}}],1) = [{},{{}}]),
00147   assert(f([{1},{}],1) = [{1},{}]),
00148   assert(f([{1},{{}}],1) = [{1},{{}}]),
00149   set_random(1),
00150   assert(f([{1,2,3,4,5},{{1,2},{2,3},{3,4},{4,5}}],1) = [{1,2,3,4,5},{{1,5},{5,3},{3,4},{4,2}}]),
00151   assert(f([{1,2,3,4,5},{{1,2},{2,3},{3,4},{4,5}}],2) = [{1,2,3},{{3,2},{1}}]),
00152   true)$
00153 
00154 okltest_modulo_colouring(f) := block([mc],
00155   mc : f(1),
00156   assert(create_list(mc(i),i,1,5) = create_list(1,i,1,5)),
00157   mc : f(2),
00158   assert(create_list(mc(i),i,1,5) = [1,2,1,2,1]),
00159   mc : f(3),
00160   assert(create_list(mc(i),i,1,10) = [1,2,3,1,2,3,1,2,3,1]),
00161   true)$
00162 
00163 okltest_modulo_projection_hg(f) := (
00164   assert(f([{},{}],1) = [{},{}]),
00165   assert(f([{1,3,5,6},{{1,3},{3,6},{1,6}}],2) = [{1,2},{{1},{1,2}}]),
00166   assert(f([{1,2,3,4},{{1,2},{1,3},{2,4},{1,3,4}}],3) = [{1,2,3},{{1,2},{1,3}}]),
00167   /* XXX */
00168   true)$
00169 
00170 okltest_mirrorfold(f) := block([mf,L,l],
00171   for n : 0 thru 5 do block([L : create_list(i,i,1,n)],
00172     mf : f(0,n),
00173     assert(create_list(mf(i),i,1,3*n) = append(L,L,L))
00174   ),
00175   assert(okltest_modulo_colouring(buildq([f],lambda([m],f(0,m)))) = true),
00176   for k : 0 thru 5 do (
00177     mf : f(k,1),
00178     assert(create_list(mf(i),i,1,5) = create_list(1,i,1,5))
00179   ),
00180   for k : 1 thru 5 do (
00181     mf : f(k,2),
00182     assert(create_list(mf(i),i,1,5) = create_list(1,i,1,5))
00183   ),
00184   l : 9,
00185   mf : f(2,l),
00186   L : [1,2,3,2,1,2,3,2,1],
00187   assert(create_list(mf(i),i,1,3*l) = append(L,L,L)),
00188   l : 10,
00189   mf : f(2,l),
00190   L : [1,2,3,2,1,1,2,3,2,1],
00191   assert(create_list(mf(i),i,1,3*l) = append(L,L,L)),
00192   l : 11,
00193   mf : f(2,l),
00194   L : [1,2,3,3,2,1,2,3,3,2,1],
00195   assert(create_list(mf(i),i,1,3*l) = append(L,L,L)),
00196   l : 12,
00197   mf : f(2,l),
00198   L : [1,2,3,3,2,1,1,2,3,3,2,1],
00199   assert(create_list(mf(i),i,1,3*l) = append(L,L,L)),
00200   for n : 1 thru 8 do (
00201     mf : f(3,n),
00202     assert(create_list(mf(i),i,1,24) = create_list(1,i,1,24))
00203   ),
00204   /* XXX */
00205   true)$
00206 
00207 okltest_mirrorexpand(f) := (
00208   for k : 0 thru if oklib_test_level=0 then 4 else 6 do
00209     for n : 0 thru if oklib_test_level=0 then 32 else 128 do
00210       assert(f(k,n)(create_list(i,i,1,ceiling(n/2^k))) = create_list(mirrorfold(k,n)(i),i,1,n)),
00211   true)$
00212 
00213 
00214 /* ***********************************
00215    * Translations to non-boolean SAT *
00216    ***********************************
00217 */
00218 
00219 okltest_hyphom_dirneg_ohg2nbfcsud(f) := (
00220   assert(f([{},{}],[{},{}]) = [{},{},{}]),
00221   assert(f([{},{}],[{},{{}}]) = [{},{},{}]),
00222   assert(f([{},{}],[{},{}]) = [{},{},{}]),
00223   assert(f([{},{{}}],[{},{}]) = [{},{{}},{}]),
00224   assert(f([{},{{}}],[{},{{}}]) = [{},{},{}]),
00225   assert(okltest_col2sat_stdhg2stdnbfcsud(buildq([f], lambda([G,S], f(G,colouring_hg(S))))) = true),
00226   /* XXX */
00227   true)$
00228 
00229