OKlibrary  0.2.1.6
BasicNotions.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 16.1.2009 (Swansea) */
00002 /* Copyright 2009 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/Graphs/Lisp/Basic.mac")$
00024 
00025 kill(f)$
00026 
00027 
00028 /* ***********************
00029    * Fundamental notions *
00030    ***********************
00031 */
00032 
00033 okltest_vbc_gl_p(f) := block([G],
00034   assert(f(0,G) = false),
00035   assert(f([],G) = false),
00036   assert(f([0,0],G) = false),
00037   assert(f([{1},{1}], G) = false),
00038   assert(f([{},{}], [{},{}]) = true),
00039   assert(f([{1},{}], [{},{}]) = false),
00040   assert(f([{1},{}], [{1},{}]) = true),
00041   assert(f([{},{1,2}], [{1,2,3},{{1,2}}]) = true),
00042   assert(f([{1,2},{3,4}], [{1,2,3,4},{{1,3},{1,4},{2,3},{2,4}}]) = true),
00043   assert(f([{1,2},{3,4}], [{1,2,3,4},{{1,3},{1,4},{2,3},{2,4},{1}}]) = true),
00044   assert(f([{1,2},{3,4}], [{1,2,3,4},{{1,3},{1,4},{2,3},{3,4}}]) = false),
00045   assert(f([{1},{2,3,4}], [{1,2,3,4},{{1,2},{1,3},{1,4}}]) = true),
00046   true)$
00047 
00048 okltest_vbc_mugl_p(f) := block([G],
00049   assert(f(0,G) = false),
00050   assert(f([],G) = false),
00051   assert(f([0,0],G) = false),
00052   assert(f([{1},{1}], G) = false),
00053   assert(f([{},{}], [{},{},lambda([e],2)]) = true),
00054   assert(f([{1},{}], [{},{},lambda([e],2)]) = false),
00055   assert(f([{1},{}], [{1},{},lambda([e],2)]) = true),
00056   assert(f([{},{1,2}], [{1,2,3},{{1,2}},lambda([e],2)]) = true),
00057   assert(f([{1,2},{3,4}], [{1,2,3,4},{{1,3},{1,4},{2,3},{2,4}},lambda([e],2)]) = true),
00058   assert(f([{1,2},{3,4}], [{1,2,3,4},{{1,3},{1,4},{2,3},{2,4},{1}},lambda([e],2)]) = true),
00059   assert(f([{1,2},{3,4}], [{1,2,3,4},{{1,3},{1,4},{2,3},{3,4}},lambda([e],2)]) = false),
00060   assert(okltest_vbc_gl_p(buildq([f],lambda([B,G],gl_p(G) and f(B,gl2mugl(G)))))),
00061   true)$
00062 
00063 okltest_vbc_gg_p(f) := block([G,edgef],
00064   assert(f(0,G) = false),
00065   assert(f([],G) = false),
00066   assert(f([0,0],G) = false),
00067   assert(f([{1},{1}], G) = false),
00068   assert(f([{},{}], [{},{},edgef]) = true),
00069   assert(f([{1},{}], [{},{},edgef]) = false),
00070   assert(f([{1},{}], [{1},{},edgef]) = true),
00071   assert(f([{},{1,2}], [{1,2,3},{1},lambda([e],{1,2})]) = true),
00072   assert(f([{1,2},{3}], [{1,2,3,4},{1,2,3},lambda([e],if e=1 then {1,2} elseif e=2 then {1,3} else {2,3})]) = true),
00073   assert(f([{1},{3,4}], [{1,2,3,4},{[1,3],[1,4],[1,1],[3,3]},lambda([e],setify(e))]) = true),
00074   assert(f([{1,2},{3}], [{1,2,3},{{1,2},{1,3},{3}},identity]) = false),
00075   assert(okltest_vbc_gl_p(buildq([f],lambda([B,G],gl_p(G) and f(B,gl2gg(G)))))),
00076   true)$
00077 
00078 okltest_vbc_dgl_p(f) := block([G],
00079   assert(f(0,G) = false),
00080   assert(f([],G) = false),
00081   assert(f([0,0],G) = false),
00082   assert(f([{1},{1}], G) = false),
00083   assert(f([{},{}], [{},{}]) = true),
00084   assert(f([{1},{}], [{},{}]) = false),
00085   assert(f([{1},{}], [{1},{}]) = true),
00086   assert(f([{},{1,2}], [{1,2,3},{[2,1]}]) = true),
00087   assert(f([{1,2},{3,4}], [{1,2,3,4},{[1,3],[1,4],[2,3],[2,4]}]) = true),
00088   assert(f([{1,2},{3,4}], [{1,2,3,4},{[3,1],[4,1],[3,2],[4,2],[1,1]}]) = false),
00089   assert(f([{3,4},{1,2}], [{1,2,3,4},{[3,1],[4,1],[3,2],[4,2],[1,1]}]) = true),
00090   assert(f([{1,2},{3,4}], [{1,2,3,4},{[1,3],[1,4],[2,3],[3,4]}]) = false),
00091   assert(okltest_vbc_gl_p(buildq([f],lambda([B,G],gl_p(G) and f(B,gl2dgl(G)))))),
00092   true)$
00093 
00094 okltest_ebc_gg_p(f) := block([edgef],
00095   assert(f({},[{},{},edgef]) = true),
00096   assert(f({},[{1},{},edgef]) = true),
00097   assert(f({1},[{1,2},{1},lambda([e],{1,2})]) = true),
00098   assert(f({1},[{1,2},{1},lambda([e],{1})]) = false),
00099   assert(f({2},[{1,2},{1,2},lambda([e],if e=1 then {1} else {1,2})]) = true),
00100   assert(f({1,2},[{1,2},{1,2},lambda([e],if e=1 then {1} else {1,2})]) = false),
00101   assert(f({1,2,4},[{1,2,3},{1,2,3},lambda([e],if e=1 then {1,2} elseif e=2 then {2,3} else {1,3})]) = false),
00102   true)$
00103 
00104 
00105 /* *********************
00106    * Maximal bicliques *
00107    *********************
00108 */
00109 
00110 okltest_maximal_bc_gl(f) := block(
00111   assert(f([{},{}],[{},{}]) = [{},{}]),
00112   assert(f([{},{}],[{1},{}]) = [{1},{}]),
00113   assert(f([{},{}],[{1,2},{}]) = [{1,2},{}]),
00114   assert(f([{},{1}],[{1},{}]) = [{},{1}]),
00115   assert(f([{},{1}],[{1,2},{}]) = [{},{1,2}]),
00116   assert(f([{1,2},{}], [{1,2},{{1,2}}]) = [{1,2},{}]),
00117   assert(f([{1,2},{}], [{1,2,3},{{1,2}}]) = [{1,2,3},{}]),
00118   assert(f([{1},{3}], [{1,2,3,4},{{1,2},{1,3},{2,3}}]) = [{1,2},{3}]),
00119   assert(f([{1},{}], [{1,2,5,4},{{1,2},{1,5},{2,4}}]) = [{1,4},{2}]),
00120   assert(f([{1},{}], [{1,2,3,4},{{1,2},{1,3},{2,4}}]) = [{1},{2,3}]),
00121   /* XXX */
00122   assert(f([{},{}],[{1,2},{{1,2}}]) = [{1},{2}]),
00123   assert(f([{1},{2,3}],[{1,2,3,4},{{1,2},{1,3},{1,4}}]) = [{1},{2,3,4}]),
00124   true)$
00125 
00126 
00127 /* *******************
00128    * Biclique covers *
00129    *******************
00130 */
00131 
00132 okltest_max_bc_cover_gl(f) := block(
00133   assert(f([{},{}]) = []),
00134   assert(f([{1,2},{{1,2}}]) = [[{1},{2}]]),
00135   assert(f([{1,2},{{1,2},{1}}]) = [[{1},{2}]]),
00136   assert(f([{1,2,3,4},{{1,2},{1},{3,4}}]) = [[{3},{4}],[{1},{2}]]),
00137   assert(f([{1,2,3,4},{{1,2},{3,4},{1,4},{2,4}}]) = [[{1,2,3},{4}],[{1,4},{2}]]),
00138   true)$
00139