OKlibrary  0.2.1.6
Hypergraphs.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 2.2.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/Satisfiability/Lisp/Generators/Generators.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Graphs/Lisp/Basic.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/CombinatorialMatrices/Lisp/Basics.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/Basics.mac")$
00028 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/ClauseSets/BasicOperations.mac")$
00029 
00030 kill(f)$
00031 
00032 /* *******************************************
00033    * Clause-variable matrices and variations *
00034    *******************************************
00035 */
00036 
00037 okltest_clvar_g(f) := (
00038   assert(f([{},{}]) = [{},{}]),
00039   assert(f([{},{{}}]) = [{[{},1]},{}]),
00040   assert(f([{1},{}]) = [{[1,2]},{}]),
00041   assert(f([{1},{{}}]) = [{[{},1],[1,2]},{}]),
00042   assert(f([{1,2},{{1,2},{1,-2}}]) = [{[{1,2},1],[{1,-2},1],[1,2],[2,2]}, 
00043     {{[{1,2},1],[1,2]},{[{1,2},1],[2,2]},{[{1,-2},1],[1,2]},{[{1,-2},1],[2,2]}}]),
00044   true)$
00045 
00046 okltest_var_fcs2hg(f) := (
00047   assert(f([{},{}]) = [{},{}]),
00048   assert(f([{},{{}}]) = [{},{{}}]),
00049   assert(f([{1},{{-1}}]) = [{1},{{1}}]),
00050   assert(f([{1},{{-1},{1}}]) = [{1},{{1}}]),
00051   assert(f([{1,2},{{1},{-2}}]) = [{1,2},{{1},{2}}]),
00052   true)$
00053 
00054 okltest_var_fcs2ghg(f) := (
00055   /* XXX */
00056   assert(okltest_var_fcs2hg(buildq([f], lambda([FF], ghg2hg(f(FF))))) = true),
00057   true)$
00058 
00059 okltest_cvg_cs(f) := block([F,G],
00060   assert(f({}) = [{},{}]),
00061   assert(f({{}}) = [{{}},{}]),
00062   for n : 0 thru 4 do (
00063     F : full_fcs(n)[2],
00064     G : f(F),
00065     assert(G[1] = F),
00066     assert(complete_g_p(G))
00067   ),
00068   true)$
00069 
00070 okltest_cl_var_com_fcs(f) := block(
00071   assert(comequalp(f([{},{}]), emptycom) = true),
00072   assert(comequalp(f([{1},{}]), zerocom({},{1})) = true),
00073   assert(comequalp(f([{},{{}}]), zerocom({{}},{})) = true),
00074   assert(comequalp(f([{1},{{}}]), zerocom({{}},{1})) = true),
00075   assert(comequalp(f([{1},{{1}}]), [{{1}},{1},lambda([i,j],1)]) = true),
00076   assert(comequalp(f([{1},{{-1}}]), [{{-1}},{1},lambda([i,j],-1)]) = true),
00077   if oklib_test_level = 1 then return(true),
00078   true)$
00079 
00080 okltest_clvar_com2fcs(f) := block([x,L],
00081   assert(f([{},{},x]) = [{},{}]),
00082   assert(f([{1},{},x]) = [{},{{}}]),
00083   assert(f([{},{1},x]) = [{1},{}]),
00084   assert(f([{1},{1},lambda([i,j],0)]) = [{1},{{}}]),
00085   assert(f([{1},{1},lambda([i,j],-1)]) = [{1},{{-1}}]),
00086   assert(f([{1},{1},lambda([i,j],1)]) = [{1},{{1}}]),
00087   for n : 0 thru 6 do block([FF : full_fcs(n)],
00088     assert(f(clvar_fcs2com(FF)) = FF)
00089   ),
00090   assert(okltest_clvar_m2fcs(buildq([f], lambda([M], f(m2com(M))))) = true),
00091   true)$
00092 
00093 okltest_clvar_ocom2fcl(f) := block([x,L],
00094   assert(f([[],[],x]) = [[],[]]),
00095   assert(f([[1],[],x]) = [[],[{}]]),
00096   assert(f([[],[1],x]) = [[1],[]]),
00097   assert(f([[1],[1],lambda([i,j],0)]) = [[1],[{}]]),
00098   assert(f([[1],[1],lambda([i,j],-1)]) = [[1],[{-1}]]),
00099   assert(f([[1],[1],lambda([i,j],1)]) = [[1],[{1}]]),
00100   for n : 0 thru 6 do block([FF : full_fcl(n)],
00101     assert(f(clvar_fcl2ocom(FF)) = FF)
00102   ),
00103   assert(okltest_clvar_m2fcs(buildq([f], lambda([M], fcl2fcs(f(m2ocom(M)))))) = true),
00104   true)$
00105 
00106 okltest_clvar_m2fcs(f) := (
00107   assert(f(matrix()) = [{},{}]),
00108   assert(f(matrix([])) = [{},{{}}]).
00109   assert(f(matrix([-1,0,1,-2,2])) = [{1,2,3,4,5},{{-1,3,-4,5}}]),
00110   assert(f(matrix([],[])) = [{},{{}}]),
00111   assert(f(matrix([1],[-1])) = [{1},{{1},{-1}}]),
00112   assert(f(matrix([0,1,2],[-1,2,-4],[0,0,0],[1,1,-1])) = [{1,2,3},{{2,3},{-1,2,-3},{},{1,2,-3}}]),
00113   true)$
00114 
00115 okltest_clvar_w_com2fcs(f) := block([x,L],
00116   assert(f([{},{},x],gv) = [{},{}]),
00117   assert(f([{1},{},x],gv) = [{},{{}}]),
00118   assert(f([{},{1},x],gv) = [{gv(1)},{}]),
00119   assert(f([{1},{1},lambda([i,j],0)],gv) = [{gv(1)},{{}}]),
00120   assert(f([{1},{1},lambda([i,j],-1)],gv) = [{gv(1)},{{-gv(1)}}]),
00121   assert(f([{1},{1},lambda([i,j],1)],gv) = [{gv(1)},{{gv(1)}}]),
00122   for n : 0 thru 6 do block([FF : full_fcs(n)],
00123     assert(f(clvar_fcs2com(FF),identity) = FF)
00124   ),
00125   assert(okltest_clvar_m2fcs(buildq([f], lambda([M], f(m2com(M),identity)))) = true),
00126   true)$
00127 
00128 okltest_clvar_w_ocom2fcl(f) := block([x,L],
00129   assert(f([[],[],x],gv) = [[],[]]),
00130   assert(f([[1],[],x],gv) = [[],[{}]]),
00131   assert(f([[],[1],x],gv) = [[gv(1)],[]]),
00132   assert(f([[1],[1],lambda([i,j],0)],gv) = [[gv(1)],[{}]]),
00133   assert(f([[1],[1],lambda([i,j],-1)],gv) = [[gv(1)],[{-gv(1)}]]),
00134   assert(f([[1],[1],lambda([i,j],1)],gv) = [[gv(1)],[{gv(1)}]]),
00135   for n : 0 thru 6 do block([FF : full_fcl(n)],
00136     assert(f(clvar_fcl2ocom(FF),identity) = FF)
00137   ),
00138   assert(okltest_clvar_m2fcs(buildq([f], lambda([M], fcl2fcs(f(m2ocom(M),identity))))) = true),
00139   true)$
00140 
00141 okltest_cl_int_scom_cs(f) := (
00142   assert(scomequalp(f({}), emptyscom) = true),
00143   assert(scomequalp(f({{}}), zeroscom({{}})) = true),
00144   assert(scomequalp(f({{1}}), [{{1}},lambda([i,j],1)]) = true),
00145   assert(scomequalp(f({{-1}}), [{{-1}},lambda([i,j],1)]) = true),
00146   assert(scomequalp(f({{1},{-1}}), [{{1},{-1}},lambda([i,j], if i=j then 1 else -1)]) = true),
00147   assert(scomequalp(f({{1,2},{3,4}}), [{{1,2},{3,4}},lambda([i,j], if i=j then 2 else 0)]) = true),
00148   true)$
00149 
00150 okltest_var_int_scom_fcs(f) := (
00151   assert(scomequalp(f([{},{}]), emptyscom) = true),
00152   assert(scomequalp(f([{},{{}}]), emptyscom) = true),
00153   assert(scomequalp(f([{1},{}]), zeroscom({1})) = true),
00154   assert(scomequalp(f([{1},{{}}]), zeroscom({1})) = true),
00155   assert(scomequalp(f([{1},{{1}}]), constantscom({1},1)) = true),
00156   assert(scomequalp(f([{1},{{-1}}]), constantscom({1},1)) = true),
00157   assert(scomequalp(f([{1},{{1},{}}]), constantscom({1},1)) = true),
00158   assert(scomequalp(f([{1},{{1},{-1}}]), constantscom({1},2)) = true),
00159   assert(scomequalp(f([{1,2},{{1},{2}}]), [{1,2},lambda([i,j],if i=j then 1 else 0)]) = true),
00160   assert(scomequalp(f([{1,2},{{1,2},{-1,-2}}]), [{1,2},lambda([i,j],if i=j then 2 else 2)]) = true),
00161   assert(scomequalp(f([{1,2},{{1,2},{1,-2}}]), [{1,2},lambda([i,j],if i=j then 2 else 0)]) = true),
00162   for n : 0 thru 3 do block([FF : full_fcs(n)],
00163     assert(scomequalp(f(FF), cdiagscom(setn(n),2^n)))),
00164   true)$
00165 
00166 okltest_var_lit_clause_digraph(f) := block(
00167   assert(f([{},{}]) = [{},{}]),
00168   assert(f([{},{{}}]) = [{{}},{}]),
00169   assert(f([{1},{}]) = [{1,[1,1],[1,-1]},{[1,[1,1]],[1,[1,-1]]}]),
00170   assert(f([{1},{{}}]) = [{1,[1,1],[1,-1],{}},{[1,[1,1]],[1,[1,-1]]}]),
00171   assert(f([{1},{{1}}]) = [{1,[1,1],[1,-1],{1}},{[1,[1,1]],[1,[1,-1]],[[1,1],{1}]}]),
00172   assert(f([{1},{{1},{-1}}]) = [{1,[1,1],[1,-1],{1},{-1}},{[1,[1,1]],[1,[1,-1]],[[1,1],{1}],[[1,-1],{-1}]}]),
00173   assert(f([{1,2},{{1,2},{-1,-2}}]) = [
00174    {1,2,[1,-1],[1,1],[2,-1],[2,1],{1,2},{-1,-2}}, 
00175    { [1,[1,-1]],[1,[1,1]],[2,[2,-1]],[2,[2,1]], 
00176      [[1,1],{1,2}], [[2,1],{1,2}], [[1,-1],{-1,-2}],[[2,-1],{-1,-2}] }
00177   ]),
00178   true)$
00179 
00180 okltest_implication_dg_fcs(f) := block(
00181   assert(f([{},{}]) = [{},{}]),
00182   assert(f([{},{{}}]) = [{},{}]),
00183   assert(f([{1},{{1}}]) = [{1,-1},{[-1,1]}]),
00184   assert(f([{1},{{-1}}]) = [{1,-1},{[1,-1]}]),
00185   assert(f([{1},{{1},{-1}}]) = [{1,-1},{[-1,1],[1,-1]}]),
00186   true)$
00187 
00188 
00189 /* ************
00190    * Measures *
00191    ************
00192 */
00193 
00194 okltest_min_degree_cvg_cs(f) := (
00195   assert(f({}) = inf),
00196   assert(f({{}}) = 0),
00197   assert(f({{1}}) = 0),
00198   assert(f({{1},{-1}}) = 1),
00199   assert(f({{1},{-1},{}}) = 0),
00200   true)$
00201 
00202 okltest_max_degree_cvg_cs(f) := (
00203   assert(f({}) = minf),
00204   assert(f({{}}) = 0),
00205   assert(f({{1}}) = 0),
00206   assert(f({{1},{-1}}) = 1),
00207   assert(f({{1},{-1},{}}) = 1),
00208   true)$
00209 
00210 okltest_deficiency_fcs(f) := (
00211   assert(f([{},{}]) = 0),
00212   assert(f([{},{{}}]) = 1),
00213   assert(f([{1},{{1}}]) = 0),
00214   assert(f([{1},{{1},{-1}}]) = 1),
00215   assert(f([{1},{{1},{-1},{}}]) = 2),
00216   assert(f([{1,2},{{1},{-1}}]) = 0),
00217   assert(okltest_deficiency_cs(buildq([f], lambda([F], f(cs2fcs(F))))) = true),
00218   true)$
00219 
00220 okltest_deficiency_cs(f) := (
00221   assert(f({}) = 0),
00222   assert(f({{}}) = 1),
00223   assert(f({{1}}) = 0),
00224   assert(f({{1},{-1}}) = 1),
00225   assert(f({{1},{-1},{}}) = 2),
00226   for n : 0 thru 4 do
00227     assert(f(full_cs(n)) = 2^n-n),
00228   true)$
00229 
00230 okltest_max_deficiency_fcs(f) := (
00231   assert(f([{},{}]) = 0),
00232   assert(f([{},{{}}]) = 1),
00233   assert(f([{1},{{1}}]) = 0),
00234   assert(f([{1},{{1},{-1}}]) = 1),
00235   assert(f([{1},{{1},{-1},{}}]) = 2),
00236   assert(f([{1,2},{{1},{-1}}]) = 1),
00237   true)$
00238 
00239 okltest_surplus_bydef_fcs(f) := (
00240   assert(f([{},{}]) = 0),
00241   assert(f([{},{{}}]) = 0),
00242   assert(f([{1},{}]) = -1),
00243   assert(f([{1},{{}}]) = -1),
00244   assert(f([{1,2},{}]) = -2),
00245   assert(f([{1,2},{{}}]) = -2),
00246   assert(f([{1},{{1}}]) = 0),
00247   assert(f([{1},{{1},{-1}}]) = 1),
00248   assert(f([{1},{{1},{-1},{}}]) = 1),
00249   assert(f([{1,2},{{1},{-1},{2},{-2}}]) = 1),
00250   true)$
00251 
00252 okltest_surplus_bydef_cs(f) := (
00253   assert(okltest_surplus_bydef_fcs(buildq([f], lambda([FF], 
00254     block([d : nvar_fcs(FF) - nvar_cs(FF[2])], 
00255       if d>0 then min(f(FF[2]), 0) - d else f(FF[2]))))) = true),
00256   true)$
00257 
00258 
00259 /* ************
00260    * Analysis *
00261    ************
00262 */
00263 
00264 okltest_var_disjointfcsp(f) := (
00265   assert(f([{},{}],[{},{}]) = true),
00266   assert(f([{},{}],[{},{{}}]) = true),
00267   assert(f([{},{{}}],[{},{{}}]) = true),
00268   assert(f([{1},{{}}],[{},{{}}]) = true),
00269   assert(f([{},{{}}],[{2},{{}}]) = true),
00270   assert(f([{1},{{}}],[{1},{{}}]) = false),
00271   true)$
00272 
00273 okltest_accumulation_variables_cs(f) := (
00274   assert(f({}) = {}),
00275   assert(f({{}}) = {}),
00276   assert(f({{1}}) = {1}),
00277   assert(f({{1},{-1}}) = {1}),
00278   assert(f({{-3,-1},{-3,1},{-2,-1,3},{-2,1,3},{-1,2,3},{1,2,3}}) = {}),
00279   assert(f({{1,2,3},{1,-2,3},{1,2,-3},{1,-2,-3},{-1,4,5},{-1,-4,5},{-1,4,-5},{-1,-4,-5}}) = {1}),
00280   for n : 0 thru 3 do block([F : full_fcs(n)[2]],
00281     assert(f(F) = if n <= 1 then setn(n) else {})),
00282   true)$
00283 
00284 okltest_full_variables_fcs(f) := (
00285   assert(f([{},{}]) = {}),
00286   assert(f([{1,2},{}]) = {1,2}),
00287   assert(f([{},{{}}]) = {}),
00288   assert(f([{1,2},{{}}]) = {}),
00289   assert(f([{1,2,3},{{-3,-1},{-3,1},{-2,-1,3},{-2,1,3},{-1,2,3},{1,2,3}}]) = {1,3}),
00290   for n : 0 thru 3 do
00291     assert(f(full_fcs(n)) = setn(n)),
00292   true)$
00293