OKlibrary  0.2.1.6
Basics.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 16.3.2008 (Swansea) */
00002 /* Copyright 2008, 2009, 2010, 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 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Generators/Generators.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Graphs/Lisp/tests/Generators.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Basics.mac")$
00027 
00028 
00029 kill(f)$
00030 
00031 /* ************************************
00032    * Checking the defining properties *
00033    ************************************
00034 */
00035 
00036 okltest_hg_p(f) := (
00037   assert(f(0) = false),
00038   assert(f([]) = false),
00039   assert(f([{}]) = false),
00040   assert(f([{},[]]) = false),
00041   assert(f([[],{}]) = false),
00042   assert(f([{},{}]) = true),
00043   /* XXX */
00044   true)$
00045 
00046 okltest_ohg_p(f) := (
00047   assert(f(0) = false),
00048   assert(f([]) = false),
00049   assert(f([[]]) = false),
00050   assert(f([{},[]]) = false),
00051   assert(f([[],{}]) = false),
00052   assert(f([[],[]]) = true),
00053   /* XXX */
00054   true)$
00055 
00056 okltest_ghg_p(f) := (
00057   /* XXX */
00058   true)$
00059 
00060 okltest_oghg_p(f) := (
00061   /* XXX */
00062   true)$
00063 
00064 
00065 /* *********************
00066    * Checking equality *
00067    *********************
00068 */
00069 
00070 
00071 /* **************
00072    * Promotions *
00073    **************
00074 */
00075 
00076 okltest_hg2ohg(f) := (
00077   assert(f([{},{}]) = [[],[]]),
00078   assert(f([{},{{}}]) = [[],[{}]]),
00079   assert(f([{1},{}]) = [[1],[]]),
00080   assert(f([{1},{{}}]) = [[1],[{}]]),
00081   assert(f([{1},{{},{1}}]) = [[1],[{},{1}]]),
00082   true)$
00083 
00084 
00085 /* *************
00086    * Downcasts *
00087    *************
00088 */
00089 
00090 okltest_ghg2hg(f) := (
00091   assert(f([{},{},identity]) = [{},{}]),
00092   assert(f([{1},{},identity]) = [{1},{}]),
00093   assert(f([{},{1},lambda([H],{})]) = [{},{{}}]),
00094   assert(f([{1,2},{1,2,3},lambda([e],if e<=2 then {1,2} else {2,3})]) = [{1,2},{{1,2},{2,3}}]),
00095   true)$
00096 
00097 
00098 /* ************* **
00099    * Conversions *
00100    ***************
00101 */
00102 
00103 okltest_setsystem2hg(f) := (
00104   assert(f({}) = [{},{}]),
00105   assert(f({{}}) = [{},{{}}]),
00106   assert(f({{1}}) = [{1},{{1}}]),
00107   assert(f({{},{1},{1,2}}) = [{1,2},{{},{1},{1,2}}]),
00108   true)$
00109 
00110 okltest_listsets2hg(f) := (
00111   assert(f([]) = [{},{}]),
00112   assert(f([{}]) = [{},{{}}]),
00113   assert(f([{1}]) = [{1},{{1}}]),
00114   assert(f([{},{1},{1,2}]) = [{1,2},{{},{1},{1,2}}]),
00115   true)$
00116 
00117 okltest_listsets2oghg(f) := (
00118   assert(f([]) = [[],[],identity]),
00119   assert(f([{}]) = [[],[{}],identity]),
00120   assert(f([{1}]) = [[1],[{1}],identity]),
00121   assert(f([{1,2},{-3,1},{3,2}]) = [[-3,1,2,3],[{1,2},{-3,1},{2,3}],identity]),
00122   true)$
00123 
00124 
00125 /* ************
00126    * Matrices *
00127    ************
00128 */
00129 
00130 okltest_hypver_hg2com(f) := (
00131   assert(comequalp(f([{},{}]), emptycom) = true),
00132   assert(comequalp(f([{},{{}}]), zerocom({{}},{})) = true),
00133   assert(comequalp(f([{1},{}]), zerocom({},{1})) = true),
00134   assert(comequalp(f([{1},{{}}]), zerocom({{}},{1})) = true),
00135   assert(comequalp(f([{1},{{1}}]), constantcom({{1}},{1},1)) = true),
00136   assert(comequalp(f([{1,2},{{1}}]), [{{1}},{1,2},lambda([H,v],if v=1 then 1 else 0)]) = true),
00137 true)$
00138 
00139 okltest_hypver_ghg2com(f) := block([x,y],
00140   assert(com_equalp(f([{},{},x]), [{},{},y]) = true),
00141   /* XXX */
00142   assert(okltest_hypver_hg2com(buildq([f], lambda([G], f(hg2ghg(G))))) = true),
00143   true)$
00144 
00145 okltest_edge_int_com_hg(f) := (
00146   assert(scomequalp(f([{},{}]), emptyscom) = true),
00147   assert(scomequalp(f([{},{{}}]), zeroscom({{}})) = true),
00148   assert(scomequalp(f([{1,2},{{}}]), zeroscom({{}})) = true),
00149   assert(scomequalp(f([{1},{{1}}]), constantscom({{1}},1)) = true),
00150   assert(scomequalp(f([{1},{{1},{}}]), [{{1},{}},lambda([H1,H2], if emptyp(H1) or emptyp(H2) then 0 else 1)]) = true),
00151   assert(scomequalp(f([{1,2},{{1},{2}}]), [{{1},{2}},lambda([H1,H2], if H1 = H2 then 1 else 0)]) = true),
00152   assert(scomequalp(f([{1,2},{{1},{1,2}}]), [{{1},{1,2}},lambda([H1,H2], if H1 = {1} or H2 = {1} then 1 else 2)]) = true),
00153   true)$
00154 
00155 okltest_vertex_int_com_hg(f) := (
00156   assert(scomequalp(f([{},{}]), emptyscom) = true),
00157   assert(scomequalp(f([{},{{}}]), emptyscom) = true),
00158   assert(scomequalp(f([{1,2},{{}}]), zeroscom({1,2})) = true),
00159   assert(scomequalp(f([{1},{{1}}]), constantscom({1},1)) = true),
00160   assert(scomequalp(f([{1},{{1},{}}]), constantscom({1},1)) = true),
00161   assert(scomequalp(f([{1,2},{{1},{2}}]), [{1,2},lambda([v1,v2], if v1 = v2 then 1 else 0)]) = true),
00162   assert(scomequalp(f([{1,2},{{1},{1,2}}]), [{1,2},lambda([v1,v2], if v1 = 1 and v2 = 1 then 2 else 1)]) = true),
00163   true)$
00164 
00165 
00166 /* *******************
00167    * Transformations *
00168    *******************
00169 */
00170 
00171 okltest_edge_k_hg(f) := (
00172   for n : 0 thru 2 do
00173     assert(f([{},{}],n) = [{},{}]),
00174   for n : 0 thru 2 do
00175     assert(f([{},{{}}],n) = [{{}},{}]),
00176   for n : 0 thru 2 do
00177     assert(f([{1},{}],n) = [{}, if n=0 then {{}} else {}]),
00178   for n : 0 thru 2 do
00179     assert(f([{1},{{}}],n) = [{{}}, if n=0 then {{}} else {}]),
00180   /* XXX */
00181   true)$
00182 
00183 okltest_edge_g_hg(f) := (
00184   /* XXX */
00185   assert(f([{1,2,3,4},{{1},{2},{1,2},{2,3}}]) = [{{1},{2},{1,2},{2,3}}, {{{1},{1,2}},{{2},{1,2}},{{2},{2,3}},{{1,2},{2,3}}}]),
00186   true)$
00187 
00188 okltest_anti_edge_k_hg(f) := (
00189   assert(okltest_edge_k_hg(buildq([f], lambda([G,k], block([E:f(G,k)], [E[1], setdifference(powerset(G[2],k),E[2])])))) = true),
00190   true)$
00191 
00192 okltest_kneser_g_hg(f) := (
00193   /* XXX */
00194   assert(okltest_kneser_g(buildq([f], lambda([n,m], kneser_g_hg(complete_stdhg(n,m))))) = true),
00195   true)$
00196 
00197 
00198 /* *****************
00199    * Constructions *
00200    *****************
00201 */
00202 
00203 okltest_union_hg(f) := (
00204   assert(f() = [{},{}]),
00205   for n : 0 thru 3 do
00206     assert(apply(f,create_list([{},{}],i,1,n)) = [{},{}]),
00207   assert(f([{1,2,3},{{1,2},{2,3}}],[{2,3,4},{{2,4},{3}}]) = [{1,2,3,4},{{1,2},{2,3},{2,4},{3}}]),
00208   true)$
00209 
00210 
00211 /* ************************************************
00212    * Constructions related to the subset-relation *
00213    ************************************************
00214 */
00215 
00216 okltest_min_hg(f) := (
00217   assert(f([{},{}]) = [{},{}]),
00218   assert(f([{},{{}}]) = [{},{{}}]),
00219   assert(f([{1,2,3},{{2,3},{1,2,3},{1},{1,2}}]) = [{1,2,3},{{2,3},{1}}]),
00220   true)$
00221 
00222 okltest_max_hg(f) := (
00223   assert(f([{},{}]) = [{},{}]),
00224   assert(f([{},{{}}]) = [{},{{}}]),
00225   assert(f([{1,2,3},{{2,3},{1,2,3},{1},{1,2}}]) = [{1,2,3},{{1,2,3}}]),
00226   true)$
00227 
00228 okltest_subsumption_ghg(f) := block([E],
00229   assert(ghg_equalp(f({},{}), [{},{},E]) = true),
00230   assert(ghg_equalp(f({},{{}}), [{},{{}}, lambda([H],{})]) = true),
00231   assert(ghg_equalp(f({{}},{}), [{{}},{}, E]) = true),
00232   assert(ghg_equalp(f({{}},{{}}), [{{}},{{}}, lambda([H],{{}})]) = true),
00233   assert(ghg_equalp(f({{1},{1,2}},{{3},{1,3},{1,2,3}}), [{{1},{1,2}}, {{3},{1,3},{1,2,3}}, lambda([H], if H={3} then {} elseif H={1,3} then {{1}} else {{1},{1,2}})]) = true),
00234   /* XXX */
00235   true)$
00236 
00237 okltest_subsumption_oghg(f) := block([E],
00238   assert(ghg_equalp(f([],[]), [[],[],E]) = true),
00239   assert(ghg_equalp(f([],[{}]), [[],[{}], lambda([H],{})]) = true),
00240   assert(ghg_equalp(f([{}],[]), [[{}],[], E]) = true),
00241   assert(ghg_equalp(f([{}],[{}]), [[{}],[{}], lambda([H],{{}})]) = true),
00242   assert(ghg_equalp(f([{1},{1,2}],[{3},{1,3},{1,2,3}]), [[{1},{1,2}], [{3},{1,3},{1,2,3}], lambda([H], if H={3} then {} elseif H={1,3} then {{1}} else {{1},{1,2}})]) = true),
00243   /* XXX */
00244   true)$
00245 
00246 okltest_rsubsumption_hg(f) := (
00247   assert(f({},{}) = [[{},{}], {}]),
00248   assert(f({},{{}}) = [[{},{{}}], {}]),
00249   assert(f({{1}},{{}}) = [[{}, {{}}], {}]),
00250   assert(f({{1}},{{1}}) = [[{}, {}], {{1}}]),
00251   assert(f({{1}},{{1},{}}) = [[{}, {{}}], {}]),
00252   assert(f({{1},{2}}, {{1,2}}) = [[{{1},{2}}, {{{1},{2}}}], {}]),
00253   assert(f({{1,2},{-2,3}}, {{1,2,3},{-1,2,3},{1,-2,3},{1,-2,-3}}) = [[{},{{}}], {}]),
00254 assert(f({{1,2},{-2,3}}, {{1,2,3},{1,-2,3},{1,2,-3}}) = [[{},{}], {{1,2},{-2,3}}]),
00255   /* XXX */
00256   true)$
00257 
00258 
00259 /* *****************
00260    * Connectedness *
00261    *****************
00262 */
00263 
00264 okltest_components_hg(f) := (
00265   assert(f([{},{}]) = {}),
00266   assert(f([{},{{}}]) = {{}}),
00267   assert(f([{1},{}]) = {{1}}),
00268   assert(f([{1},{{}}]) = {{1},{}}),
00269   assert(f([{1},{{},{1}}]) = {{1},{}}),
00270   assert(f([{1,2},{}]) = {{1},{2}}),
00271   assert(f([{1,2},{{}}]) = {{},{1},{2}}),
00272   assert(f([{1,2},{{1}}]) = {{1},{2}}),
00273   assert(f([{1,2},{{2}}]) = {{1},{2}}),
00274   assert(f([{1,2},{{},{1}}]) = {{},{1},{2}}),
00275   assert(f([{1,2},{{},{1},{2}}]) = {{},{1},{2}}),
00276   assert(f([{1,2},{{1,2}}]) = {{1,2}}),
00277   assert(f([{1,2},{{1,2},{}}]) = {{},{1,2}}),
00278   assert(f([{1,2},{{1,2},{},{1},{2}}]) = {{},{1,2}}),
00279   assert(f([{1,2,3},{{1,2},{1,3}}]) = {{1,2,3}}),
00280   assert(f([{1,2,3},{{1,2},{1,3},{}}]) = {{},{1,2,3}}),
00281   assert(f([{1,2,3},{{1},{2},{3}}]) = {{1},{2},{3}}),
00282   true)$
00283 
00284 okltest_components_ghg(f) := (
00285   /* XXX */
00286   assert(okltest_components_hg(buildq([f], lambda([G], f(hg2ghg(G))))) = true),
00287   true)$
00288 
00289 okltest_disjoint_union_rep_hg(f) := (
00290   assert(f([{},{}]) = []),
00291   assert(f([{},{{}}]) = [[{},{{}}]]),
00292   for n : 1 thru 4 do block(
00293    [G : [setn(n),{}], L : create_list([{i},{}],i,1,n)],
00294     assert(f(G) = L),
00295     assert(f([G[1],adjoin({},G[2])]) = cons([{},{{}}], L))
00296   ),
00297   assert(f([{1,2},{{1,2}}]) = [[{1,2},{{1,2}}]]),
00298   assert(f([{1,2,3,4,5},{{1,2},{2,3},{4},{4,5},{}}]) = [[{},{{}}], [{1,2,3},{{1,2},{2,3}}],[{4,5},{{4},{4,5}}]]),
00299   true)$
00300 
00301 okltest_is_connected_hg_p(f) := (
00302   assert(f([{},{}]) = true),
00303   assert(f([{},{{}}]) = true),
00304   assert(f([{1},{}]) = true),
00305   assert(f([{1},{{}}]) = false),
00306   assert(f([{1},{{},{1}}]) = false),
00307   assert(f([{1,2},{}]) = false),
00308   assert(f([{1,2},{{}}]) = false),
00309   assert(f([{1,2},{{1}}]) = false),
00310   assert(f([{1,2},{{2}}]) = false),
00311   assert(f([{1,2},{{},{1}}]) = false),
00312   assert(f([{1,2},{{},{1},{2}}]) = false),
00313   assert(f([{1,2},{{1,2}}]) = true),
00314   assert(f([{1,2},{{1,2},{}}]) = false),
00315   assert(f([{1,2},{{1,2},{},{1},{2}}]) = false),
00316   assert(f([{1,2,3},{{1,2},{1,3}}]) = true),
00317   assert(f([{1,2,3},{{1,2},{1,3},{}}]) = false),
00318   assert(f([{1,2,3},{{1},{2},{3}}]) = false),
00319   true)$
00320 
00321