OKlibrary  0.2.1.6
Symmetries.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 30.4.2008 (Guangzhou) */
00002 /* Copyright 2008, 2013 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/Satisfiability/Lisp/Generators/Generators.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/Generators/Pigeonhole.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/ClauseSets/BasicOperations.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/Reductions/GeneralisedUCP.mac")$
00028 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00029 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/Symmetries/Symmetries.mac")$
00030 
00031 
00032 kill(f)$
00033 
00034 /* ***********************
00035    * Isomorphism testing *
00036    ***********************
00037 */
00038 
00039 /* Generic test function, checking for fcs-isomorphism-predicates: */
00040 
00041 okltest_is_isomorphic_fcs(f) := block(
00042   assert(f([{},{}],[{},{}]) = true),
00043   assert(f([{},{{}}],[{},{{}}]) = true),
00044   assert(f([{},{}],[{},{{}}]) = false),
00045   assert(f([{},{}],[{1},{}]) = false),
00046   assert(f([{2},{}],[{1},{}]) = true),
00047   assert(f([{1},{{-1},{1}}],[{2},{{-2},{2}}]) = true),
00048   assert(f([{1},{{1}}],[{1},{{-1}}]) = true),
00049   assert(f([{1},{{1},{}}],[{1},{{-1}}]) = false),
00050   assert(f([{1,2,3},{{-3,-2},{-3,-1,2},{-3,1,2},{-2,-1,3},{-1,2,3},{1,3}}],
00051     [{1,2,3},{{-3,-2},{-3,-1,2},{-3,1,2},{-2,-1,3},{-2,1,3},{2,3}}])
00052     = false),
00053   assert(f([{1,2,3},{{-3,-2},{-3,-1,2},{-3,1,2},{-2,-1,3},{-1,2,3},{1,3}}],
00054     [{1,2,3},{{-3,-2},{-3,1,2},{-2,-1,3},{-2,1,3},{-1,2},{1,2,3}}]) = true),
00055   assert(f([{1,2,3},{{-3,-2},{-3,1,2},{-2,-1,3},{-2,1,3},{-1,2},{1,2,3}}],
00056     [{1,2,3},{{-3,-2},{-3,-1,2},{-3,1,2},{-2,-1,3},{-1,2,3},{1,3}}]) = true),
00057   assert(f([{1,2,3,4},{{-4,-3},{-4,-1,2,3},{-4,1,3},{-3,-2,-1,4},{-2,-1,3},{-2,1,4},{2,4}}],
00058     [{1,2,3,4},{{-4,-3},{-4,1,2,3},{-3,-2,1,4},{-3,-1,4},{-2,3},{-1,2,3},{1,2,4}}])
00059     = true),
00060   if oklib_test_level = 0 then return(true),
00061   for n : 3 thru 4 do block([FF : weak_php_fcs(n+1,n), v, G],
00062     v : choose_element(FF[1]),
00063     G : apply_pa_f({v},FF),
00064     G : cs_to_fcs(weakaut_red(generalised_ucp1(G[2]),1)),
00065     assert(f(G, weak_php_fcs(n,n-1)) = true)
00066   ),
00067   block([FF1 : full_fcs(3), FF2 : full_fcs(3)],
00068     assert(f(FF1,FF2) = true),
00069     assert(FF1 = full_fcs(3)), assert(FF2 = full_fcs(3))
00070   ),
00071   true)$
00072 
00073 okltest_is_varisomorphic_fcs_p(f) := block(
00074   assert(f([{},{}],[{},{}]) = true),
00075   assert(f([{},{{}}],[{},{{}}]) = true),
00076   assert(f([{},{}],[{},{{}}]) = false),
00077   assert(f([{},{}],[{1},{}]) = false),
00078   assert(f([{2},{}],[{1},{}]) = true),
00079   assert(f([{1},{{-1},{1}}],[{2},{{-2},{2}}]) = true),
00080   assert(f([{1},{{1}}],[{1},{{-1}}]) = false),
00081   assert(f([{1},{{1},{}}],[{1},{{-1}}]) = false),
00082   assert(f([{1,2},{{},{1},{2},{1,2},{-1}}], [{1,3},{{},{1},{3},{1,3},{-3}}]) = true),
00083   true)$
00084 
00085 
00086 /* **********************************
00087    * Isomorphism classes management *
00088    **********************************
00089 */
00090 
00091 okltest_representatives_fcs(f) := block([FF,SFF],
00092   assert(f({}) = {}),
00093   assert(f({FF}) = {FF}),
00094   assert(f({[{},{{}}],[{},{}]}) = {[{},{{}}],[{},{}]}),
00095   block([R : f({[{1},{}], [{2},{}], [{},{}]})],
00096     assert(length(R) = 2),
00097     assert(elementp([{},{}], R) = true),
00098     assert(length(intersection(R, {[{1},{}], [{2},{}]})) = 1)
00099   ),
00100   SFF : 
00101    {[setn(4),{{-4,-3,-2},{-4,-3,-1,2},{-4,-3,1,2},{-4,-2,-1,3},{-4,-2,1,3},
00102    {-4,-1,2,3},{-3,-2,-1,4},{-3,-2,1,4},{-3,-1,2,4},{-3,1,2,4},
00103    {-2,-1,3,4},{-2,1,3,4},{-1,2,3,4},{1,2,3}}],
00104    [setn(4),{{-4,-3,-2,-1},{-4,-3,-2,1},{-4,-3,-1,2},{-4,-2,-1,3},
00105    {-4,-2,1,3},{-4,-1,2,3},{-3,-2,-1,4},{-3,-2,1,4},{-3,-1,2,4},
00106    {-3,1,2},{-2,-1,3,4},{-2,1,3,4},{-1,2,3,4},{1,2,3}}]},
00107   assert(f(SFF) = SFF),
00108   true)$
00109 
00110 okltest_manage_repository_isomorphism_types(f) := block([repo,M,FF1,FF2,deg],
00111   repo : sm2hm({}),
00112   assert(f([{},{}],repo) = true),
00113   M : {[[0,0,[],[]], {[{},{}]}]},
00114   assert(hm2sm(repo) = M),
00115   assert(f([{},{}],repo) = false),
00116   assert(hm2sm(repo) = M),
00117   assert(f([{},{{}}],repo) = true),
00118   M : adjoin([[0,1,[],[[0,1]]], {[{},{{}}]}], M),
00119   assert(hm2sm(repo) = M),
00120   assert(f([{},{{}}],repo) = false),
00121   assert(hm2sm(repo) = M),
00122   assert(f([{1},{}],repo) = true),
00123   M : adjoin([[1,0,[[0,2]],[]],{[{1},{}]}], M),
00124   assert(hm2sm(repo) = M),
00125   assert(f([{1},{}],repo) = false),
00126   assert(hm2sm(repo) = M),
00127   assert(f([{2},{}],repo) = false),
00128   assert(hm2sm(repo) = M),
00129   assert(f([{1},{{1}}],repo) = true),
00130   M : adjoin([[1,1,[[0,1],[1,1]],[[1,1]]], {[{1},{{1}}]}], M),
00131   assert(hm2sm(repo) = M),
00132   assert(f([{1},{{1}}],repo) = false),
00133   assert(hm2sm(repo) = M),
00134   FF1 : [setn(4),{{-4,-3},{-4,-1,2,3},{-4,1,2,3},{-3,-2,4},{-2,-1,3},{-2,1,3},{2,4}}],
00135   assert(f(FF1,repo) = true),
00136   deg : [4,7,[[2,4],[3,3],[4,1]],[[2,2],[3,3],[4,2]]],
00137   M : adjoin([deg, {FF1}], M),
00138   assert(hm2sm(repo) = M),
00139   FF2 : [setn(4),{{-4,-3},{-4,2,3},{-3,-2,1,4},{-3,-1,4},{-2,3},{-1,2,3,4},{1,2,4}}],
00140   assert(f(FF2,repo) = true),
00141   M : disjoin([deg,{FF1}],M), M : adjoin([deg,{FF1,FF2}],M),
00142   assert(hm2sm(repo) = M),
00143   true)$
00144 
00145 
00146 /* *******************************
00147    * Analysing hash-repositories *
00148    *******************************
00149 */
00150 
00151 okltest_analyse_isorepo_def(f) := block([R],
00152   assert(f(sm2hm({})) = []),
00153   true)$
00154 
00155 okltest_analyse_isorepo_set(f) := block(
00156   assert(f(sm2hm({})) = {}),
00157   true)$
00158 
00159 okltest_analyse_isorepo_defset_reference_implementation(repository) := block(
00160  [E : equiv_classes(analyse_isorepo_set(repository), 
00161         lambda([F,G], is(deficiency_cs(F) = deficiency_cs(G))))],
00162   return(map(lambda([S],[deficiency_cs(choose_element(S)),S]),
00163            sort(listify(E), lambda([S1,S2], 
00164              is(deficiency_cs(choose_element(S1)) < 
00165                 deficiency_cs(choose_element(S2))))))))$
00166 
00167 okltest_analyse_isorepo_defset(f) := block(
00168  [FF : make_array(any,4), h : sm2hm({})],
00169   assert(f(h) = []),
00170   FF[0] : [{},{}],
00171   compose_hm_sm(h,{[fcs_identifier(FF[0]), {FF[0]}]}),
00172   assert(f(h) = [[0,{FF[0][2]}]]),
00173   FF[1] : [{1},{{1}}],
00174   set_hm(h,fcs_identifier(FF[0]), {FF[0],FF[1]}),
00175   assert(f(h) = [[0,{FF[0][2],FF[1][2]}]]),
00176   FF[2] : [{},{{}}],
00177   set_hm(h,fcs_identifier(FF[2]), {FF[2]}),
00178   assert(f(h) = [[0,{FF[0][2],FF[1][2]}], [1,{FF[2][2]}]]),
00179   FF[3] : full_fcs(2),
00180   set_hm(h,fcs_identifier(FF[3]), {FF[3]}),
00181   assert(f(h) = [[0,{FF[0][2],FF[1][2]}], [1,{FF[2][2]}], [2,{FF[3][2]}]]),
00182   if oklib_test_level = 0 then return(true),
00183   for n : 0 thru 3 do
00184     manage_repository_isomorphism_types(weak_php_fcs(n+2,n),h),
00185   assert(okltest_analyse_isorepo_defset_reference_implementation(h) = f(h)),
00186   true)$
00187