OKlibrary  0.2.1.6
Isomorphisms.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 9.8.2008 (Swansea) */
00002 /* Copyright 2008,  2011 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/CombinatorialMatrices/Lisp/Basics.mac")$
00024 
00025 
00026 kill(f)$
00027 
00028 /* ********************************
00029    * Incomplete isomorphism tests *
00030    ********************************
00031 */
00032 
00033 okltest_decisions_is_isomorphic_incl0_com(f) := block([fun1,fun2],
00034   assert(f([{},{},fun1],[{},{},fun2]) = true),
00035   assert(f([{},{1},fun1],[{},{2},fun2]) = true),
00036   assert(f([{3},{},fun1],[{4},{},fun2]) = true),
00037   assert(f([{},{},fun1],[{1},{},fun2]) = false),
00038   assert(f([{},{},fun1],[{},{1},fun2]) = false),
00039   assert(f([{},{1},fun1],[{1},{},fun2]) = false),
00040   assert(f([{1},{},fun1],[{},{1},fun2]) = false),
00041   assert(f([{1,2},{3},fun1],[{1},{2},fun2]) = false),
00042   assert(f([{1},{3},fun1],[{1},{2,3},fun2]) = false),
00043   assert(f(zerocom({1},{2}),zerocom({3},{4})) = true),
00044   assert(f(zerocom({1},{2}),constantcom({1},{2},1)) = false),
00045   true)$
00046 
00047 okltest_decisions_is_isomorphic_incl1_com(f) := (
00048   assert(okltest_decisions_is_isomorphic_incl0_com(f)),
00049   assert(f(zerocom({1,2},{2}),constantcom({1,2},{2},1)) = false),
00050   assert(f(m2com(matrix([1,1],[0,0])),m2com(matrix([1,0],[0,1]))) = false),
00051   true)$
00052 
00053 okltest_decisions_is_isomorphic_incl2a_com(f) := (
00054   assert(okltest_decisions_is_isomorphic_incl1_com(f)),
00055   assert(f(m2com(matrix([1,1],[1,1])),m2com(matrix([2,0],[0,2]))) = false),
00056   assert(f(m2com(matrix([0,1,1],[1,0,1],[1,1,0])),m2com(matrix([2,0,0],[0,2,0],[0,0,2]))) = false),
00057   assert(f(m2com(matrix([1,1,0],[0,1,1],[0,0,1])),m2com(matrix([2,0,1],[0,1,1],[0,0,1]))) = false),
00058   assert(f(m2com(matrix([1,1,0,0],[1,1,0,0],[0,0,1,0],[0,0,0,1])),m2com(matrix([1,0,1,0],[0,1,0,1],[1,0,0,0],[0,0,0,1]))) = false),
00059   true)$
00060 
00061 okltest_unknown_is_isomorphic_incl2a_com(f) := (
00062   assert(f(m2com(matrix([2,0],[0,0])),m2com(matrix([1,1],[1,1]))) = unknown), /* 2b succeeds */
00063   assert(f(m2com(matrix([0,1,1],[1,0,1],[1,1,0])),m2com(matrix([1,1,0],[1,0,1],[0,1,1]))) = unknown), /* iso */
00064   true)$
00065 
00066 okltest_decisions_is_isomorphic_incl2b_com(f) := (
00067   assert(okltest_decisions_is_isomorphic_incl1_com(f)),
00068   assert(f(m2com(matrix([1,1],[1,1])),m2com(matrix([2,0],[0,2]))) = false),
00069   assert(f(m2com(matrix([2,0],[0,0])),m2com(matrix([1,1],[1,1]))) = false),
00070   assert(f(m2com(matrix([0,1,1],[1,0,1],[1,1,0])),m2com(matrix([2,0,0],[0,2,0],[0,0,2]))) = false),
00071   assert(f(m2com(matrix([1,1,0],[0,1,1],[0,0,1])),m2com(matrix([2,0,1],[0,1,1],[0,0,1]))) = false),
00072   true)$
00073 
00074 okltest_unknown_is_isomorphic_incl2b_com(f) := (
00075   assert(f(m2com(matrix([1,1,0,0],[1,1,0,0],[0,0,1,0],[0,0,0,1])),m2com(matrix([1,0,1,0],[0,1,0,1],[1,0,0,0],[0,0,0,1]))) = unknown), /* 2a succeeds */
00076   assert(f(m2com(matrix([0,1,1],[1,0,1],[1,1,0])),m2com(matrix([1,1,0],[1,0,1],[0,1,1]))) = unknown), /* iso */
00077   true)$
00078 
00079 okltest_decisions_is_isomorphic_inclall_com(f) := (
00080   assert(okltest_decisions_is_isomorphic_incl2a_com(f)),
00081   assert(okltest_decisions_is_isomorphic_incl2b_com(f)),
00082   true)$
00083 
00084 
00085 /* ******************************
00086    * Complete isomorphism tests *
00087    ******************************
00088 */
00089 
00090 /* Generic testfunction for binary predicates f(A,B), which return true
00091    iff the combinatorial matrices A, B are isomorphic: */
00092 okltest_is_isomorphic_com_p(f) := block([fun1,fun2,M],
00093   assert(f([{},{},fun1], [{},{},fun2]) = true),
00094   assert(f([{},{},fun1], [{1},{},fun2]) = false),
00095   assert(f([{},{},fun1], [{},{1},fun2]) = false),
00096   assert(f([{},{},fun1], [{1},{1},fun2]) = false),
00097   assert(f([{1},{},fun1], [{1},{1},fun2]) = false),
00098   assert(f([{},{1},fun1], [{1},{1},fun2]) = false),
00099   assert(f(zerocom({1},{2}), zerocom({3},{4})) = true),
00100   assert(f(zerocom({1},{2}), constantcom({3},{4},1)) = false),
00101   assert(f(m2com(matrix([1,1],[0,0])), m2com(matrix([0,0],[1,1]))) = true),
00102   assert(f(m2com(matrix([1,0],[1,0])), m2com(matrix([0,1],[0,1]))) = true),
00103   assert(f(m2com(matrix([1,0],[0,1])), m2com(matrix([0,1],[0,1]))) = false),
00104   assert(f(m2com(matrix([1,0,0],[0,0,1],[0,0,0])), m2com(matrix([0,0,0],[0,0,1],[1,0,0]))) = true),
00105   assert(f(m2com(matrix([1,0,0],[0,0,2],[0,0,0])), m2com(matrix([0,0,0],[0,0,2],[1,0,0]))) = true),
00106   assert(f(m2com(matrix([1,0,0],[0,0,3],[0,0,0])), m2com(matrix([0,0,0],[0,0,2],[1,0,0]))) = false),
00107   if oklib_test_level = 0 then return(true),
00108   M : m2com(matrix([0,1,0,1,0,0],[0,0,1,1,1,0],[1,0,0,1,1,1],[0,1,1,0,1,0],[1,1,0,0,1,1],[0,1,1,1,1,1])),
00109   assert(f(M,trans_com(M)) = false),
00110   assert(f(m2com(matrix([1,1,2])),m2com(matrix([1,2,2]))) = false),
00111   true)$
00112 
00113 
00114 /* ************************
00115    * Duality and polarity *
00116    ************************
00117 */
00118 
00119 okltest_selfpolar_bydef_m_p(f) := (
00120   assert(f(matrix()) = true),
00121   assert(f(matrix([0])) = true),
00122   assert(f(matrix([1])) = true),
00123   assert(f(matrix([0,0],[0,0])) = true),
00124   assert(f(matrix([1,0],[0,0])) = true),
00125   assert(f(matrix([1,0],[1,0])) = false),
00126   assert(f(matrix([1,1],[0,0])) = false),
00127   assert(f(matrix([1,0],[0,1])) = true),
00128   assert(f(matrix([1,1],[1,0])) = true),
00129   assert(f(matrix([1,1],[1,1])) = true),
00130   true)$
00131 
00132 okltest_selfdual_bydef_m_p(f) := (
00133   assert(f(matrix()) = true),
00134   assert(f(matrix([0])) = true),
00135   assert(f(matrix([1])) = true),
00136   assert(f(matrix([0,0],[0,0])) = true),
00137   assert(f(matrix([1,0],[0,0])) = true),
00138   assert(f(matrix([1,0],[1,0])) = false),
00139   assert(f(matrix([1,1],[0,0])) = false),
00140   assert(f(matrix([1,0],[0,1])) = true),
00141   assert(f(matrix([1,1],[1,0])) = true),
00142   assert(f(matrix([1,1],[1,1])) = true),
00143   true)$
00144 
00145