OKlibrary  0.2.1.6
Consensus.mac
Go to the documentation of this file.
00001 /* Matthew Lewsey, 11.2.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/Bicliques/Consensus.mac")$
00024 
00025 kill(f)$
00026 
00027 okltest_bc_absorbs_bc_gl_p(f) := block(
00028   assert(f([{},{}],[{},{}]) = true),
00029   assert(f([{},{}],[{1},{}]) = false),
00030   assert(f([{1},{}],[{},{}]) = true),
00031   assert(f([{},{1}],[{1},{}]) = true),
00032   assert(f([{1,3},{4,6}],[{2,3},{4,5}]) = false),
00033   assert(f([{1,2,3,4},{5,6}],[{1,3},{4,6}]) = false),
00034   true)$
00035 
00036 okltest_con_adj_gl_b1_1_b2_1_p(f) := block(
00037   assert(f([{},{}],[{},{}],[]) = false),
00038   assert(f([{1},{}],[{1},{}],[]) = true),
00039   assert(f([{1,2},{}],[{1},{}],[]) = true),
00040   assert(f([{1,2},{}],[{},{1}],[]) = false),
00041   assert(f([{1},{}],[{2},{}],[]) = false),
00042   assert(f([{1,2},{}],[{1},{}],[[{1},{3}]]) = false),
00043   true)$
00044   
00045 okltest_con_adj_gl_b1_1_b2_2_p(f) := block(
00046   assert(f([{},{}],[{},{}],[]) = false),
00047   assert(f([{1},{}],[{},{1}],[]) = true),
00048   assert(f([{1,2},{}],[{},{1}],[]) = true),
00049   assert(f([{1,2},{}],[{1},{}],[]) = false),
00050   assert(f([{1},{}],[{},{2}],[]) = false),
00051   assert(f([{1,2},{}],[{},{1}],[[{3},{1}]]) = false),
00052   true)$
00053 
00054 okltest_con_adj_gl_b1_2_b2_1_p(f) := block(
00055   assert(f([{},{}],[{},{}],[]) = false),
00056   assert(f([{},{1}],[{1},{}],[]) = true),
00057   assert(f([{},{1,2}],[{1},{}],[]) = true),
00058   assert(f([{},{1,2}],[{},{1}],[]) = false),
00059   assert(f([{},{1}],[{2},{}],[]) = false),
00060   assert(f([{},{1,2}],[{1},{}],[[{1},{3}]]) = false),
00061   true)$
00062 
00063 okltest_con_adj_gl_b1_2_b2_2_p(f) := block(
00064   assert(f([{},{}],[{},{}],[]) = false),
00065   assert(f([{},{1}],[{},{1}],[]) = true),
00066   assert(f([{},{1,2}],[{},{1}],[]) = true),
00067   assert(f([{},{1,2}],[{1},{}],[]) = false),
00068   assert(f([{},{1}],[{},{2}],[]) = false),
00069   assert(f([{},{1,2}],[{},{1}],[[{3},{1}]]) = false),
00070   true)$
00071 
00072 okltest_con_adj_gl_b1_1_b2_1(f) := block(
00073   assert(f([{1},{}],[{1},{}]) = [{1},{}]),
00074   assert(f([{1,2},{}],[{1},{}]) = [{1},{}]),
00075   assert(f([{1,2},{}],[{2,3},{}]) = [{2},{}]),
00076   assert(f([{1,2,3},{7}],[{3,4,5},{6}]) = [{3},{6,7}]),
00077   true)$
00078 
00079 okltest_con_adj_gl_b1_1_b2_2(f) := block(
00080   assert(f([{1},{}],[{},{1}]) = [{1},{}]),
00081   assert(f([{1,2},{}],[{},{1}]) = [{1},{}]),
00082   assert(f([{1,2},{}],[{},{2,3}]) = [{2},{}]),
00083   assert(f([{1,2,3},{7}],[{6},{3,4,5}]) = [{3},{6,7}]),
00084   true)$
00085 
00086 okltest_con_adj_gl_b1_2_b2_1(f) := block(
00087   assert(f([{},{1}],[{1},{}]) = [{1},{}]),
00088   assert(f([{},{1,2}],[{1},{}]) = [{1},{}]),
00089   assert(f([{},{1,2}],[{2,3},{}]) = [{2},{}]),
00090   assert(f([{7},{1,2,3}],[{3,4,5},{6}]) = [{3},{6,7}]),
00091   true)$
00092 
00093 okltest_con_adj_gl_b1_2_b2_2(f) := block(
00094   assert(f([{},{1}],[{},{1}]) = [{1},{}]),
00095   assert(f([{},{1,2}],[{},{1}]) = [{1},{}]),
00096   assert(f([{},{1,2}],[{},{2,3}]) = [{2},{}]),
00097   assert(f([{7},{1,2,3}],[{6},{3,4,5}]) = [{3},{6,7}]),
00098   true)$
00099 
00100 okltest_con_adj_gl_bc(f) := block(
00101   assert(f([{},{}],[{},{}],[]) = []),
00102   assert(f([{1},{2}],[{1},{3}],[]) = [[{1},{2,3}]]),
00103   assert(f([{1},{2}],[{1},{3}],[[{2,3},{1}]]) = [[{2,3},{1}]]),
00104   true)$
00105 
00106 okltest_con_ext_gl_bc(f) := block(
00107   assert(f([{},{}],[{},{}],[],[{},{}]) = []),
00108   assert(f([{1},{2}],[{1},{3}],[],[{1,2,3},{{1,2},{1,3}}]) = [[{1},{2,3}]]),
00109   assert(f([{1},{2}],[{1},{3}],[[{2,3},{1}]],[{1,2,3},{{1,2},{1,3}}]) = [[{2,3},{1}]]),
00110   assert(f([{1},{2}],[{1},{3}],[],[{1,2,3,4},{{1,2},{1,3},{1,4}}]) = [[{1},{2,3,4}]]),
00111   assert(f([{1},{2}],[{1},{3}],[],[{1,2,3,4,5},{{1,2},{1,3},{1,4},{5,2},{5,3},{5,4}}]) = [[{1,5},{2,3,4}]]),
00112   assert(f([{1},{2}],[{1},{3}],[[{1},{4}]],[{1,2,3,4,5},{{1,2},{1,3},{1,4},{5,2},{5,3}}]) = [[{1},{2,3,4}],[{1},{4}]]),
00113   true)$
00114 
00115 okltest_aux_con_alg1_abs(f) := block(
00116   assert(f([[{1},{2}],[{3},{4}],[{1},{}]]) = [[{1},{2}],[{3},{4}]]),
00117   assert(f([[{2},{1}],[{2},{1}],[{1,3},{2,4}]]) = [[{2},{1}],[{1,3},{2,4}]]),
00118   true)$
00119 
00120 okltest_aux_con_alg1_con(f) := block(
00121   assert(f([[{1},{2}],[{1},{4}]]) = [[{1},{2,4}],[{1},{2}],[{1},{4}]]),
00122   assert(f([[{1},{2,3}],[{1},{3,4}]]) = [[{1},{2,3,4}],[{1},{2,3}],[{1},{3,4}]]),
00123   true)$
00124 
00125 okltest_aux_con_alg2_ext(f) := block(
00126   assert(f([[{1,2},{3,4}],[{1,5},{6}]],[{1,2,3,4,5,6},{{1,3},{1,4},{2,3},{2,4},{1,6},{5,6}}]) = [[{1},{3,4,6}],[{1,2},{3,4}],[{1,5},{6}]]),
00127   assert(f([[{1,2},{3,4}],[{5,6},{7,8}],[{1,5},{4,7}]],[{1,2,3,4,5,6,7,8},{{1,3},{1,4},{2,3},{2,4},{5,7},{5,8},{6,7},{6,8},{1,4},{1,7},{5,4},{5,7}}]) = [[{1},{3,4,7}],[{1,2},{3,4}],[{5,6},{7,8}],[{1,5},{4,7}]]),
00128   true)$
00129 
00130 okltest_con_alg1(f) := block(
00131   assert(setify(f([{},{}])) = setify([])),
00132   assert(setify(f([{1,2},{}])) = setify([])),
00133   assert(setify(f([{1},{{1}}])) = setify([])),
00134   assert(setify(f([{1,2},{{1,2}}])) = setify([[{1},{2}]])),
00135   assert(setify(f([{1,2,3,4},{{1,2},{3,4}}])) = setify([[{1},{2}],[{3},{4}]])),
00136   assert(setify(f([{1,2,3,4,5,6,7,8},{{1,3},{1,4},{2,3},{2,4},{5,7},{5,8},{6,7},{6,8},{1,4},{1,7},{5,4},{5,7}}])) = setify([[{1},{3,4,7}],[{1,2},{3,4}],[{1,5},{4,7}],[{1,5,6},{7}],[{4},{1,2,5}],[{5},{4,7,8}],[{5,6},{7,8}]])),
00137   assert(setify(f([{1,2,3,4,5,6,7,8},{{1,3},{1,4},{2,3},{2,4},{5,3},{5,6},{2,6},{7,4},{7,8},{2,8}}])) = setify([[{4},{1,2,7}],[{2},{3,4,6,8}],[{3},{1,2,5}],[{1,2},{3,4}],[{2,5},{3,6}],[{2,7},{4,8}]])),
00138   true)$
00139 
00140 okl_test_con_alg2(f) := block(
00141   assert(setify(f([{},{}])) = setify([])),
00142   assert(setify(f([{1,2},{}])) = setify([])),
00143   assert(setify(f([{1},{{1}}])) = setify([])),
00144   assert(setify(f([{1,2},{{1,2}}])) = setify([[{1},{2}]])),
00145   assert(setify(f([{1,2,3,4},{{1,2},{3,4}}])) = setify([[{1},{2}],[{3},{4}]])),
00146   assert(setify(f([{1,2,3,4,5,6,7,8},{{1,3},{1,4},{2,3},{2,4},{5,7},{5,8},{6,7},{6,8},{1,4},{1,7},{5,4},{5,7}}])) = setify([[{1},{3,4,7}],[{1,2},{3,4}],[{1,5},{4,7}],[{1,5,6},{7}],[{4},{1,2,5}],[{5},{4,7,8}],[{5,6},{7,8}]])),
00147   assert(setify(f([{1,2,3,4,5,6,7,8},{{1,3},{1,4},{2,3},{2,4},{5,3},{5,6},{2,6},{7,4},{7,8},{2,8}}])) = setify([[{4},{1,2,7}],[{2},{3,4,6,8}],[{3},{1,2,5}],[{1,2},{3,4}],[{2,5},{3,6}],[{2,7},{4,8}]])),
00148   assert(setify(f([{1,2,3,4,5,6,7,8,9},{{1,3},{1,4},{2,3},{2,4},{5,3},{5,4},{5,7},{6,3},{6,7},{8,4},{5,9},{8,9}}])) = setify([[{4},{1,2,5,8}],[{3},{1,2,5,6}],[{5},{3,4,7,9}],[{1,2,5},{3,4}],[{5,6},{3,7}],[{5,8},{4,9}]])),
00149   true) $
00150