OKlibrary  0.2.1.6
Basic.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 30.4.2008 (Guangzhou) */
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/Graphs/Lisp/Basic.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/ClauseSets/Hypergraphs.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Graphs/Lisp/Generators.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00028 
00029 
00030 kill(f)$
00031 
00032 
00033 /* ******************************
00034    * Providing basic test cases *
00035    ******************************
00036 */
00037 
00038 okltest_list_g : [
00039  [{},{}],
00040  [{1},{}],
00041  [{1,2},{{1,2}}],
00042  [{1,2,3},{{1,2},{1,3}}],
00043  [{1,2,3},{{1,2},{1,3},{2,3}}],
00044  [{1,2,3,4},{{1,2},{2,3},{3,4},{4,1}}]
00045 ]$
00046 
00047 okltest_list_gl : [
00048  [{1},{{1}}],
00049  [{1,2},{{1},{2},{1,2}}]
00050 ]$
00051 
00052 okltest_list_dg : [
00053  [{},{}],
00054  [{1},{}],
00055  [{1,2},{[1,2]}],
00056  [{1,2},{[1,2],[2,1]}]
00057 ]$
00058 
00059 okltest_list_dgl : [
00060  [{1},{[1,1]}],
00061  [{1,2},{[1,1],[2,2],[1,2]}]
00062 ]$
00063 
00064 okltest_list_mug : [
00065  [{},{},identity],
00066  [{1},{},identity],
00067  [{1,2},{{1,2}},lambda([e],2)]
00068 ]$
00069 
00070 okltest_list_mugl : [
00071  [{1},{{1}},lambda([e],2)]
00072 ]$
00073 
00074 okltest_list_mudg : [
00075  [{},{},identity],
00076  [{1},{},identity],
00077  [{1,2},{[1,2]},lambda([e],2)],
00078  [{1,2},{[1,2],[2,1]},lambda([e],if e=[1,2] then 1 else 2)]
00079 ]$
00080 
00081 okltest_list_mudgl : [
00082  [{1},{[1,1]},lambda([e],2)]
00083 ]$
00084 
00085 okltest_list_gg : [
00086  [{},{},identity],
00087  [{1},{},identity],
00088  [{1},{1,2},lambda([e],{1})],
00089  [{1,2},{1,2,3,4},lambda([e],if e=1 then {1} elseif e=2 then {2} else {1,2})]
00090 ]$
00091 
00092 okltest_list_gdg : [
00093  [{},{},identity],
00094  [{1},{},identity],
00095  [{1},{1,2},lambda([e],[1,1])],
00096  [{1,2},{1,2,3,4},lambda([e],if e=1 then [1,1] elseif e=2 then [2,2] else [1,2])]
00097 ]$
00098 
00099 okltest_list_og : [
00100  [[],[]],
00101  [[1],[]],
00102  [[1,2],[{1,2}]],
00103  [[2,1],[{1,2}]]
00104 ]$
00105 
00106 okltest_list_ogl : [
00107  [[1],[{1}]],
00108  [[1,2],[{1},{2},{1,2}]],
00109  [[2,1],[{1,2},{2},{1}]]
00110 ]$
00111 
00112 okltest_list_odg : [
00113  [[],[]],
00114  [[1],[]],
00115  [[1,2],[[1,2]]],
00116  [[2,1],[[2,1],[1,2]]]
00117 ]$
00118 
00119 okltest_list_odgl : [
00120  [[1],[[1,1]]],
00121  [[1,2],[[1,1],[2,2],[1,2]]],
00122  [[2,1],[[2,2],[1,2],[1,1],[2,1]]]
00123 ]$
00124 
00125 okltest_list_omug : [
00126  [[],[],identity],
00127  [[1],[],identity],
00128  [[1,2],[{1,2}],lambda([e],2)],
00129  [[2,1],[{1,2}],lambda([e],2)]
00130 ]$
00131 
00132 okltest_list_omugl : [
00133  [[1],[{1}],lambda([e],2)],
00134  [[2,1],[{2},{1},{1,2}],lambda([e],2)]
00135 ]$
00136 
00137 okltest_list_omudg : [
00138  [[],[],identity],
00139  [[1],[],identity],
00140  [[1,2],[[1,2]],lambda([e],2)],
00141  [[2,1],[[2,1],[1,2]],lambda([e],if e=[1,2] then 1 else 2)]
00142 ]$
00143 
00144 okltest_list_omudgl : [
00145  [[1],[[1,1]],lambda([e],2)]
00146 ]$
00147 
00148 okltest_list_ogg : [
00149  [[],[],identity],
00150  [[1],[],identity],
00151  [[1],[1,2],lambda([e],{1})],
00152  [[1,2],[1,2,3,4],lambda([e],if e=1 then {1} elseif e=2 then {2} else {1,2})]
00153 ]$
00154 
00155 okltest_list_ogdg : [
00156  [[],[],identity],
00157  [[1],[],identity],
00158  [[1],[1,2],lambda([e],[1,1])],
00159  [[1,2],[1,2,3,4],lambda([e],if e=1 then [1,1] elseif e=2 then [2,2] else [1,2])]
00160 ]$
00161 
00162 okltest_list_allgraphs : [
00163  okltest_list_g,okltest_list_gl,okltest_list_dgl,okltest_list_mug,
00164  okltest_list_mugl,okltest_list_mudg,okltest_list_mudgl,okltest_list_gg,
00165  okltest_list_gdg,okltest_list_og,okltest_list_ogl,okltest_list_odg,
00166  okltest_list_odgl,okltest_list_omug,okltest_list_omugl,okltest_list_omudg,
00167  okltest_list_omudgl,okltest_list_ogg,okltest_list_ogdg
00168 ]$
00169 
00170 /* ************************************
00171    * Checking the defining properties *
00172    ************************************
00173 */
00174 
00175 okltest_g_p(f) := block(
00176   for G in okltest_list_g do
00177     assert(f(G) = true),
00178   assert(f([]) = false),
00179   assert(f([[],{}]) = false),
00180   assert(f([{},[]]) = false),
00181   assert(f([[],[]]) = false),
00182   assert(f([{},{{}}]) = false),
00183   assert(f([{},{{1,2}}]) = false),
00184   assert(f([{1},{{1}}]) = false),
00185   assert(f([{1,2},{[1,2]}]) = false),
00186   assert(f([{1,2,3},{{1,2,3}}]) = false),
00187   true)$
00188 
00189 okltest_gl_p(f) := block(
00190   for G in okltest_list_gl do
00191     assert(f(G) = true),
00192   assert(f([]) = false),
00193   assert(f([[],{}]) = false),
00194   assert(f([{},[]]) = false),
00195   assert(f([[],[]]) = false),
00196   assert(f([{},{{}}]) = false),
00197   assert(f([{},{{1,2}}]) = false),
00198   assert(f([{1},{{1}}]) = true),
00199   assert(f([{1,2},{[1,2]}]) = false),
00200   assert(f([{1,2,3},{{1,2,3}}]) = false),
00201   true)$
00202 
00203 okltest_dg_p(f) := block(
00204   for G in okltest_list_dg do
00205     assert(f(G) = true),
00206   assert(f([]) = false),
00207   assert(f([[],{}]) = false),
00208   assert(f([{},[]]) = false),
00209   assert(f([[],[]]) = false),
00210   assert(f([{},{[]}]) = false),
00211   assert(f([{},{[1,2]}]) = false),
00212   assert(f([{1},{[1]}]) = false),
00213   assert(f([{1,2},{{1,2}}]) = false),
00214   assert(f([{1,2,3},{[1,2,3]}]) = false),
00215   true)$
00216 
00217 okltest_dgl_p(f) := block(
00218   for G in okltest_list_dgl do
00219     assert(f(G) = true),
00220   assert(f([]) = false),
00221   assert(f([[],{}]) = false),
00222   assert(f([{},[]]) = false),
00223   assert(f([[],[]]) = false),
00224   assert(f([{},{[]}]) = false),
00225   assert(f([{},{[1,2]}]) = false),
00226   assert(f([{1},{[1,1]}]) = true),
00227   assert(f([{1,2},{{1,2}}]) = false),
00228   assert(f([{1,2,3},{[1,2,3]}]) = false),
00229   true)$
00230 
00231 okltest_mug_p(f) := block(
00232   for G in okltest_list_mug do
00233     assert(f(G) = true),
00234   okltest_g_p(buildq([f],lambda([G],
00235     listp(G) and is(length(G) = 2) and f([G[1],G[2],lambda([e],1)])))),
00236   assert(f([{1,2},{{1,2}},lambda([e],1.0)]) = false),
00237   true)$
00238 
00239 okltest_mugl_p(f) := block(
00240   for G in okltest_list_mugl do
00241     assert(f(G) = true),
00242   okltest_gl_p(buildq([f],lambda([G],
00243     listp(G) and is(length(G)=2) and f([G[1],G[2],lambda([e],1)])))),
00244   assert(f([{1,2},{{1,2}},lambda([e],1.0)]) = false),
00245   true)$
00246 
00247 okltest_mudg_p(f) := block(
00248   for G in okltest_list_mudg do
00249     assert(f(G) = true),
00250   okltest_dg_p(buildq([f],lambda([G],
00251     listp(G) and is(length(G)=2) and f([G[1],G[2],lambda([e],1)])))),
00252   assert(f([{1,2},{[1,2]},lambda([e],1.0)]) = false),
00253   true)$
00254 
00255 okltest_mudgl_p(f) := block(
00256   for G in okltest_list_mudgl do
00257     assert(f(G) = true),
00258   okltest_dgl_p(buildq([f],lambda([G],
00259     listp(G) and is(length(G)=2) and f([G[1],G[2],lambda([e],1)])))),
00260   assert(f([{1,2},{[1,2]},lambda([e],1.0)]) = false),
00261   true)$
00262 
00263 okltest_gg_p(f) := block(
00264   for G in okltest_list_gg do
00265     assert(f(G) = true),
00266   okltest_gl_p(buildq([f],lambda([G],
00267     listp(G) and is(length(G)=2) and f([G[1],G[2],identity])))),
00268   true)$
00269 
00270 okltest_gdg_p(f) := block(
00271   for G in okltest_list_gdg do
00272     assert(f(G) = true),
00273   okltest_dgl_p(buildq([f],lambda([G],
00274     listp(G) and is(length(G)=2) and f([G[1],G[2],identity])))),
00275   true)$
00276 
00277 okltest_og_p(f) := block(
00278   for G in okltest_list_og do
00279     assert(f(G) = true),
00280   assert(f([]) = false),
00281   assert(f([[],{}]) = false),
00282   assert(f([{},[]]) = false),
00283   assert(f([{},{}]) = false),
00284   assert(f([[],[{}]]) = false),
00285   assert(f([[],[{1,2}]]) = false),
00286   assert(f([[1],[{1}]]) = false),
00287   assert(f([[1,2],[[1,2]]]) = false),
00288   assert(f([[1,2,3],[{1,2,3}]]) = false),
00289   assert(f([[1,2],[{1,2},{1,2}]]) = false),
00290   true)$
00291 
00292 okltest_ogl_p(f) := block(
00293   for G in okltest_list_ogl do
00294     assert(f(G) = true),
00295   assert(f([]) = false),
00296   assert(f([[],{}]) = false),
00297   assert(f([{},[]]) = false),
00298   assert(f([{},{}]) = false),
00299   assert(f([[],[{}]]) = false),
00300   assert(f([[],[{1,2}]]) = false),
00301   assert(f([[1],[{1}]]) = true),
00302   assert(f([[1,2],[[1,2]]]) = false),
00303   assert(f([[1,2,3],[{1,2,3}]]) = false),
00304   assert(f([[1,2],[{1,2},{1,2}]]) = false),
00305   true)$
00306 
00307 okltest_odg_p(f) := block(
00308   for G in okltest_list_odg do
00309     assert(f(G) = true),
00310   assert(f([]) = false),
00311   assert(f([[],{}]) = false),
00312   assert(f([{},[]]) = false),
00313   assert(f([{},{}]) = false),
00314   assert(f([[],[[]]]) = false),
00315   assert(f([[],[[1,2]]]) = false),
00316   assert(f([[1],[[1]]]) = false),
00317   assert(f([[1,2],[{1,2}]]) = false),
00318   assert(f([[1,2,3],[[1,2,3]]]) = false),
00319   assert(f([[1,2],[[1,2],[1,2]]]) = false),
00320   true)$
00321 
00322 okltest_odgl_p(f) := block(
00323   for G in okltest_list_odgl do
00324     assert(f(G) = true),
00325   assert(f([]) = false),
00326   assert(f([[],{}]) = false),
00327   assert(f([{},[]]) = false),
00328   assert(f([{},{}]) = false),
00329   assert(f([[],[[]]]) = false),
00330   assert(f([[],[[1,2]]]) = false),
00331   assert(f([[1],[[1,1]]]) = true),
00332   assert(f([[1,2],[{1,2}]]) = false),
00333   assert(f([[1,2,3],[[1,2,3]]]) = false),
00334   assert(f([[1,2],[[1,2],[1,2]]]) = false),
00335   true)$
00336 
00337 okltest_omug_p(f) := block(
00338   for G in okltest_list_omug do
00339     assert(f(G) = true),
00340   okltest_og_p(buildq([f],lambda([G],
00341     listp(G) and is(length(G)=2) and f([G[1],G[2],lambda([e],1)])))),
00342   assert(f([[1,2],[{1,2}],lambda([e],1.0)]) = false),
00343   true)$
00344 
00345 okltest_omugl_p(f) := block(
00346   for G in okltest_list_omugl do
00347     assert(f(G) = true),
00348   okltest_ogl_p(buildq([f],lambda([G],
00349     listp(G) and is(length(G)=2) and f([G[1],G[2],lambda([e],1)])))),
00350   assert(f([[1,2],[{1,2}],lambda([e],1.0)]) = false),
00351   true)$
00352 
00353 okltest_omudg_p(f) := block(
00354   for G in okltest_list_omudg do
00355     assert(f(G) = true),
00356   okltest_odg_p(buildq([f],lambda([G],
00357     listp(G) and is(length(G)=2) and f([G[1],G[2],lambda([e],1)])))),
00358   assert(f([[1,2],[[1,2]],lambda([e],1.0)]) = false),
00359   true)$
00360 
00361 okltest_omudgl_p(f) := block(
00362   for G in okltest_list_omudgl do
00363     assert(f(G) = true),
00364   okltest_odgl_p(buildq([f],lambda([G],
00365     listp(G) and is(length(G)=2) and f([G[1],G[2],lambda([e],1)])))),
00366   assert(f([[1,2],[[1,2]],lambda([e],1.0)]) = false),
00367   true)$
00368 
00369 okltest_ogg_p(f) := block(
00370   for G in okltest_list_ogg do
00371     assert(f(G) = true),
00372   okltest_ogl_p(buildq([f],lambda([G],
00373     listp(G) and is(length(G)=2) and f([G[1],G[2],identity])))),
00374   true)$
00375 
00376 okltest_ogdg_p(f) := block(
00377   for G in okltest_list_ogdg do
00378     assert(f(G) = true),
00379   okltest_odgl_p(buildq([f],lambda([G],
00380     listp(G) and is(length(G)=2) and f([G[1],G[2],identity])))),
00381   true)$
00382 
00383 
00384 /* *********************
00385    * Checking equality *
00386    *********************
00387 */
00388 
00389 okltest_gr_equalp(f) := block(
00390   for L in okltest_list_allgraphs do
00391     for i : 1 thru length(L) do
00392       for j : 1 thru length(L) do
00393         if i=j then
00394           assert(f(L[i],L[j]) = true)
00395         else
00396           assert(f(L[i],L[j]) = false),
00397   true)$
00398 
00399 
00400 /* **************
00401    * Promotions *
00402    **************
00403 */
00404 
00405 
00406 okltest_g2mug(f) := block(
00407   assert(gr_equalp(f([{},{}]), [{},{},identity]) = true),
00408   assert(gr_equalp(f([{1},{}]), [{1},{},identity]) = true),
00409   assert(gr_equalp(f([{1,2},{{1,2}}]), [{1,2},{{1,2}},lambda([e],1)]) = true),
00410   for L in [okltest_list_g] do
00411     for G in L do
00412       assert(mug2g(f(G)) = G),
00413   true)$
00414 
00415 okltest_gl2mugl(f) := block(
00416   assert(gr_equalp(f([{},{}]), [{},{},identity]) = true),
00417   assert(gr_equalp(f([{1},{}]), [{1},{},identity]) = true),
00418   assert(gr_equalp(f([{1,2},{{1,2}}]), [{1,2},{{1,2}},lambda([e],1)]) = true),
00419   for L in [okltest_list_g,okltest_list_gl] do
00420     for G in L do
00421       assert(mugl2gl(f(G)) = G),
00422   true)$
00423 
00424 okltest_g2gg(f) := block(
00425   assert(gr_equalp(f([{},{}]), [{},{},identity]) = true),
00426   assert(gr_equalp(f([{1},{}]), [{1},{},identity]) = true),
00427   assert(gr_equalp(f([{1,2},{{1,2}}]), [{1,2},{{1,2}},identity]) = true),
00428   for G in okltest_list_g do
00429     assert(gg2gl(f(G)) = G),
00430   true)$
00431 
00432 okltest_gl2gg(f) := block(
00433   assert(gr_equalp(f([{},{}]), [{},{},identity]) = true),
00434   assert(gr_equalp(f([{1},{}]), [{1},{},identity]) = true),
00435   assert(gr_equalp(f([{1,2},{{1,2}}]), [{1,2},{{1,2}},identity]) = true),
00436   for L in [okltest_list_g,okltest_list_gl] do
00437     for G in L do
00438       assert(gg2gl(f(G)) = G),
00439   true)$
00440 
00441 okltest_mug2gg(f) := block([k1,k2],
00442   assert(gr_equalp(f([{},{},k1]), [{},{},k2]) = true),
00443   assert(gr_equalp(f([{1},{},k1]), [{1},{},k2]) = true),
00444   assert(gr_equalp(f([{1,2},{{1,2}},lambda([e],2)]), [{1,2},{[{1,2},1],[{1,2},2]},first]) = true),
00445   for L in [okltest_list_mug] do
00446     for G in L do
00447       assert(gr_equalp(gg2mugl(f(G)),G) = true),
00448   true)$
00449 
00450 okltest_mugl2gg(f) := block([k1,k2],
00451   assert(gr_equalp(f([{},{},k1]), [{},{},k2]) = true),
00452   assert(gr_equalp(f([{1},{},k1]), [{1},{},k2]) = true),
00453   assert(gr_equalp(f([{1,2},{{1,2}},lambda([e],2)]), [{1,2},{[{1,2},1],[{1,2},2]},first]) = true),
00454   for L in [okltest_list_mug,okltest_list_mugl] do
00455     for G in L do
00456       assert(gr_equalp(gg2mugl(f(G)),G) = true),
00457   true)$
00458 
00459 okltest_ogl2omugl(f) := block(
00460   assert(gr_equalp(f([[],[]]), [[],[],identity]) = true),
00461   assert(gr_equalp(f([[1],[]]), [[1],[],identity]) = true),
00462   assert(gr_equalp(f([[1,2],[{1,2}]]), [[1,2],[{1,2}],lambda([e],1)]) = true),
00463   for L in [okltest_list_og,okltest_list_ogl] do
00464     for G in L do
00465       assert(omugl2ogl(f(G)) = G),
00466   true)$
00467 
00468 okltest_og2ogg(f) := block(
00469   assert(gr_equalp(f([[],[]]), [[],[],identity]) = true),
00470   assert(gr_equalp(f([[1],[{1}]]), [[1],[{1}],identity]) = true),
00471   assert(gr_equalp(f([[1,2],[{1,2}]]), [[1,2],[{1,2}],identity]) = true),
00472   for G in okltest_list_og do
00473     assert(ogg2ogl(f(G)) = G),
00474   true)$
00475 
00476 okltest_ogl2ogg(f) := block(
00477   assert(gr_equalp(f([[],[]]), [[],[],identity]) = true),
00478   assert(gr_equalp(f([[1],[{1}]]), [[1],[{1}],identity]) = true),
00479   assert(gr_equalp(f([[1,2],[{1,2}]]), [[1,2],[{1,2}],identity]) = true),
00480   for L in [okltest_list_og,okltest_list_ogl] do
00481     for G in L do
00482       assert(ogg2ogl(f(G)) = G),
00483   true)$
00484 
00485 okltest_omugl2ogg(f) := block([k1,k2],
00486   assert(gr_equalp(f([[],[],k1]), [[],[],k2]) = true),
00487   assert(gr_equalp(f([[1],[],k1]), [[1],[],k2]) = true),
00488   assert(gr_equalp(f([[2,1],[{1,2},{1}],lambda([e],2)]), [[2,1],[[{1,2},1],[{1,2},2],[{1},1],[{1},2]],first]) = true),
00489   for L in [okltest_list_omug,okltest_list_omugl] do
00490     for G in L do
00491       assert(gr_equalp(ogg2omugl(f(G)),G) = true),
00492   true)$
00493 
00494 okltest_g2og(f) := block(
00495   assert(f([{},{}]) = [[],[]]),
00496   assert(f([{1},{}]) = [[1],[]]),
00497   assert(f([{1,2},{{1,2}}]) = [[1,2],[{1,2}]]),
00498   for G in okltest_list_g do
00499     assert(og2g(f(G)) = G),
00500   true)$
00501 
00502 okltest_gl2ogl(f) := block(
00503   assert(f([{},{}]) = [[],[]]),
00504   assert(f([{1},{}]) = [[1],[]]),
00505   assert(f([{1,2},{{1,2}}]) = [[1,2],[{1,2}]]),
00506   for L in [okltest_list_g,okltest_list_gl] do
00507     for G in L do
00508       assert(ogl2gl(f(G)) = G),
00509   true)$
00510 
00511 okltest_mug2omug(f) := block([k],
00512   assert(f([{},{},k]) = [[],[],k]),
00513   assert(gr_equalp(f([{1},{},k]), [[1],[],identity]) = true),
00514   assert(f([{1,2},{{1,2}},lambda([e],2)]) = [[1,2],[{1,2}],lambda([e],2)]),
00515   for G in okltest_list_mug do
00516     assert(omug2mug(f(G)) = G),
00517   true)$
00518 
00519 okltest_mugl2omugl(f) := block([k],
00520   assert(f([{},{},k]) = [[],[],k]),
00521   assert(gr_equalp(f([{1},{},k]), [[1],[],identity]) = true),
00522   assert(f([{1,2},{{1,2}},lambda([e],2)]) = [[1,2],[{1,2}],lambda([e],2)]),
00523   for L in [okltest_list_mug,okltest_list_mugl] do
00524     for G in L do
00525       assert(omugl2mugl(f(G)) = G),
00526   true)$
00527 
00528 okltest_gg2ogg(f) := block([k],
00529   assert(f([{},{},k]) = [[],[],k]),
00530   assert(f([{1},{},k]) = [[1],[],k]),
00531   assert(f([{1,2},{1,2},lambda([e],{1,2})]) = [[1,2],[1,2],lambda([e],{1,2})]),
00532   for G in okltest_list_gg do
00533     assert(ogg2gg(f(G)) = G),
00534   true)$
00535 
00536 okltest_dg2mudg(f) := block ([k],
00537   assert(gr_equalp(f([{},{}]), [{},{},k]) = true),
00538   assert(gr_equalp(f([{1},{}]), [{1},{},k]) = true),
00539   assert(f([{1,2},{[1,2],[2,1]}]) = [{1,2},{[1,2],[2,1]},lambda([e],1)]),
00540   for L in [okltest_list_dg] do
00541     for G in L do
00542       assert(mudgl2dgl(f(G)) = G),
00543   true)$
00544 
00545 okltest_dgl2mudgl(f) := block ([k],
00546   assert(gr_equalp(f([{},{}]), [{},{},k]) = true),
00547   assert(gr_equalp(f([{1},{}]), [{1},{},k]) = true),
00548   assert(f([{1,2},{[1,2],[2,1]}]) = [{1,2},{[1,2],[2,1]},lambda([e],1)]),
00549   assert(f([{1,2},{[1,2],[2,1],[1,1]}]) = [{1,2},{[1,2],[2,1],[1,1]},lambda([e],1)]),
00550   for L in [okltest_list_dg,okltest_list_dgl] do
00551     for G in L do
00552       assert(mudgl2dgl(f(G)) = G),
00553   true)$
00554 
00555 okltest_dg2gdg(f) := block([k],
00556   assert(gr_equalp(f([{},{}]), [{},{},k]) = true),
00557   assert(gr_equalp(f([{1},{}]), [{1},{},k]) = true),
00558   assert(gr_equalp(f([{1,2},{[1,2],[2,1]}]), [{1,2},{[1,2],[2,1]},identity]) = true),
00559   for L in [okltest_list_dg] do
00560     for G in L do
00561       assert(gdg2dgl(f(G)) = G),
00562   true)$
00563 
00564 okltest_dgl2gdg(f) := block([k],
00565   assert(gr_equalp(f([{},{}]), [{},{},k]) = true),
00566   assert(gr_equalp(f([{1},{}]), [{1},{},k]) = true),
00567   assert(gr_equalp(f([{1,2},{[1,2],[2,1]}]), [{1,2},{[1,2],[2,1]},identity]) = true),
00568   assert(gr_equalp(f([{1,2},{[1,2],[2,1],[1,1]}]), [{1,2},{[1,2],[2,1],[1,1]},identity]) = true),
00569   for L in [okltest_list_dg,okltest_list_dgl] do
00570     for G in L do
00571       assert(gdg2dgl(f(G)) = G),
00572   true)$
00573 
00574 okltest_mudg2gdg(f) := block([k1,k2],
00575   assert(gr_equalp(f([{},{},k1]), [{},{},k2]) = true),
00576   assert(gr_equalp(f([{1},{},k1]), [{1},{},k2]) = true),
00577   assert(gr_equalp(f([{1,2},{[1,2]},lambda([e],2)]), [{1,2},{[[1,2],1],[[1,2],2]},first]) = true),
00578   for L in [okltest_list_mudg] do
00579     for G in L do
00580       assert(gr_equalp(gdg2mudgl(f(G)),G) = true),
00581   true)$
00582 
00583 okltest_mudgl2gdg(f) := block([k1,k2],
00584   assert(gr_equalp(f([{},{},k1]), [{},{},k2]) = true),
00585   assert(gr_equalp(f([{1},{},k1]), [{1},{},k2]) = true),
00586   assert(gr_equalp(f([{1},{[1,1]},lambda([e],3)]), [{1},{[[1,1],1],[[1,1],2],[[1,1],3]},first]) = true),
00587   assert(gr_equalp(f([{1,2},{[1,2]},lambda([e],2)]), [{1,2},{[[1,2],1],[[1,2],2]},first]) = true),
00588   for L in [okltest_list_mudg,okltest_list_mudgl] do
00589     for G in L do
00590       assert(gr_equalp(gdg2mudgl(f(G)),G) = true),
00591   true)$
00592 
00593 okltest_odgl2omudgl(f) := block ([k],
00594   assert(gr_equalp(f([[],[]]), [[],[],k]) = true),
00595   assert(gr_equalp(f([[1],[]]), [[1],[],k]) = true),
00596   assert(f([[1,2],[[2,1],[1,2]]]) = [[1,2],[[2,1],[1,2]],lambda([e],1)]),
00597   for L in [okltest_list_odg,okltest_list_odgl] do
00598     for G in L do
00599       assert(omudgl2odgl(f(G)) = G),
00600   true)$
00601 
00602 okltest_odg2ogdg(f) := block([k],
00603   assert(gr_equalp(f([[],[]]), [[],[],k]) = true),
00604   assert(gr_equalp(f([[1],[]]), [[1],[],k]) = true),
00605   assert(gr_equalp(f([[2,1],[[1,2],[2,1]]]), [[2,1],[[1,2],[2,1]],identity]) = true),
00606   for L in [okltest_list_odg] do
00607     for G in L do
00608       assert(ogdg2odgl(f(G)) = G),
00609   true)$
00610 
00611 okltest_odgl2ogdg(f) := block([k],
00612   assert(gr_equalp(f([[],[]]), [[],[],k]) = true),
00613   assert(gr_equalp(f([[1],[]]), [[1],[],k]) = true),
00614   assert(gr_equalp(f([[2,1],[[1,2],[2,1]]]), [[2,1],[[1,2],[2,1]],identity]) = true),
00615   for L in [okltest_list_odg,okltest_list_odgl] do
00616     for G in L do
00617       assert(ogdg2odgl(f(G)) = G),
00618   true)$
00619 
00620 okltest_omudgl2ogdg(f) := block([k1,k2],
00621   assert(gr_equalp(f([[],[],k1]), [[],[],k2]) = true),
00622   assert(gr_equalp(f([[1],[],k1]), [[1],[],k2]) = true),
00623   assert(gr_equalp(f([[1,2],[[1,2]],lambda([e],2)]), [[1,2],[[[1,2],1],[[1,2],2]],first]) = true),
00624   for L in [okltest_list_omudg,okltest_list_omudgl] do
00625     for G in L do
00626       assert(gr_equalp(ogdg2omudgl(f(G)),G) = true),
00627   true)$
00628 
00629 okltest_dg2odg(f) := block(
00630   assert(f([{},{}]) = [[],[]]),
00631   assert(f([{1},{}]) = [[1],[]]),
00632   assert(f([{1,2},{[1,2]}]) = [[1,2],[[1,2]]]),
00633   for G in okltest_list_dg do
00634     assert(odgl2dgl(f(G)) = G),
00635   true)$
00636 
00637 okltest_dgl2odgl(f) := block(
00638   assert(f([{},{}]) = [[],[]]),
00639   assert(f([{1},{}]) = [[1],[]]),
00640   assert(f([{1,2},{[1,2]}]) = [[1,2],[[1,2]]]),
00641   for L in [okltest_list_dg,okltest_list_dgl] do
00642     for G in L do
00643       assert(odgl2dgl(f(G)) = G),
00644   true)$
00645 
00646 okltest_mudg2omudg(f) := block([k],
00647   assert(f([{},{},k]) = [[],[],k]),
00648   assert(gr_equalp(f([{1},{},k]), [[1],[],identity]) = true),
00649   assert(f([{1,2},{[1,2],[2,1]},lambda([e],2)]) = [[1,2],[[1,2],[2,1]],lambda([e],2)]),
00650   for L in [okltest_list_mudg] do
00651     for G in L do
00652       assert(omudg2mudg(f(G)) = G),
00653   true)$
00654 
00655 okltest_mudgl2omudgl(f) := block([k],
00656   assert(f([{},{},k]) = [[],[],k]),
00657   assert(gr_equalp(f([{1},{},k]), [[1],[],identity]) = true),
00658   assert(f([{1,2},{[1,2],[2,1]},lambda([e],2)]) = [[1,2],[[1,2],[2,1]],lambda([e],2)]),
00659   for L in [okltest_list_mudg,okltest_list_mudgl] do
00660     for G in L do
00661       assert(omudgl2mudgl(f(G)) = G),
00662   true)$
00663 
00664 okltest_gdg2ogdg(f) := block([k],
00665   assert(f([{},{},k]) = [[],[],k]),
00666   assert(f([{1},{},k]) = [[1],[],k]),
00667   assert(f([{1,2,3},{1,2,3},lambda([e],if e=1 then [1,2] elseif e=2 then [2,3] else [3,1])]) = [[1,2,3],[1,2,3],lambda([e],if e=1 then [1,2] elseif e=2 then [2,3] else [3,1])]),
00668   for G in okltest_list_gg do
00669     assert(ogdg2gdg(f(G)) = G),
00670   true)$
00671 
00672 
00673 /* *************
00674    * Downcasts *
00675    *************
00676 */
00677 
00678 okltest_mug2g(f) := block([k,V,E],
00679   assert(f([{},{},k]) = [{},{}]),
00680   assert(f([V,E,k]) = [V,E]),
00681   true)$
00682 
00683 okltest_mugl2gl(f) := block([k,V,E],
00684   assert(f([{},{},k]) = [{},{}]),
00685   assert(f([{1},{{1}},k]) = [{1},{{1}}]),
00686   assert(f([V,E,k]) = [V,E]),
00687   assert(okltest_mug2g(f) = true),
00688   true)$
00689 
00690 okltest_gg2gl(f) := block([e],
00691   assert(f([{},{},e]) = [{},{}]),
00692   assert(f(cyclegraph_gg(1)) = [{1},{{1}}]),
00693   assert(f(cyclegraph_gg(2)) = [{1,2},{{1,2}}]),
00694   for n : 1 thru 3 do
00695     assert(f(dipole_gg(n)) = [{1,2},{{1,2}}]),
00696   true)$
00697 
00698 okltest_gg2mugl(f) := block([x],
00699   assert(gr_equalp(f([{},{},e]), [{},{},lambda([e],x)]) = true),
00700   assert(gr_equalp(f(cyclegraph_gg(1)), [{1},{{1}}, lambda([e],1)]) = true),
00701   assert(gr_equalp(f(cyclegraph_gg(2)), [{1,2},{{1,2}}, lambda([e],2)]) = true),
00702   for n : 1 thru 3 do
00703     assert(gr_equalp(f(dipole_gg(n)), [{1,2},{{1,2}}, \lambda([e],n)]) = true),
00704   true)$
00705 
00706 okltest_omug2og(f) := block([k,V,E],
00707   assert(f([[],[],k]) = [[],[]]),
00708   assert(f([V,E,k]) = [V,E]),
00709   true)$
00710 
00711 okltest_omugl2ogl(f) := block([k,V,E],
00712   assert(f([[],[],k]) = [[],[]]),
00713   assert(f([[1],[{1}],k]) = [[1],[{1}]]),
00714   assert(f([V,E,k]) = [V,E]),
00715   assert(okltest_mug2g(f) = true),
00716   true)$
00717 
00718 okltest_ogg2ogl(f) := block([e],
00719   assert(f([[],[],e]) = [[],[]]),
00720   assert(f(cyclegraph_ogg(1)) = [[1],[{1}]]),
00721   assert(f(cyclegraph_ogg(2)) = [[1,2],[{1,2}]]),
00722   for n : 1 thru 3 do
00723     assert(f(dipole_ogg(n)) = [[1,2],[{1,2}]]),
00724   true)$
00725 
00726 okltest_ogg2omugl(f) := block([e,e2,x],
00727   assert(gr_equalp(f([[],[],e]), [[],[],e2]) = true),
00728   assert(gr_equalp(f(cyclegraph_ogg(1)), [[1],[{1}], lambda([e],1)]) = true),
00729   assert(gr_equalp(f(cyclegraph_ogg(2)), [[1,2],[{1,2}], lambda([e],2)]) = true),
00730   for n : 1 thru 3 do
00731     assert(gr_equalp(f(dipole_ogg(n)), [[1,2],[{1,2}], lambda([e],n)]) = true),
00732   true)$
00733 
00734 okltest_og2g(f) := (
00735   assert(f([[],[]]) = [{},{}]),
00736   assert(f([[1],[]]) = [{1},{}]),
00737   assert(f([[1,2],[{1,2}]]) = [{1,2},{{1,2}}]),
00738   true)$
00739 
00740 okltest_ogl2gl(f) := (
00741   assert(okltest_og2g(f) = true),
00742   assert(f([[1],[{1}]]) = [{1},{{1}}]),
00743   true)$
00744 
00745 okltest_omug2mug(f) := block([e],
00746   assert(f([[],[],e]) = [{},{},e]),
00747   assert(f([[1],[],e]) =  [{1},{},e]),
00748   assert(f([[1,2],[{1,2}],e]) = [{1,2},{{1,2}},e]),
00749   true)$
00750 
00751 okltest_omugl2mugl(f) := block([e],
00752   assert(okltest_omug2mug(f) = true),
00753   assert(f([[1],[{1}],e]) = [{1},{{1}},e]),
00754   true)$
00755 
00756 okltest_ogg2gg(f) := block([ef,e,e2],
00757   assert(f([[],[],ef]) = [{},{},ef]),
00758   assert(f([[1],[],ef]) =  [{1},{},ef]),
00759   assert(f([[1],[e],ef]) =  [{1},{e},ef]),
00760   assert(f([[1,2],[e,e2],ef]) = [{1,2},{e,e2},ef]),
00761   true)$
00762 
00763 okltest_mudg2dg(f) := block([e],
00764   assert(f([{},{},e]) = [{},{}]),
00765   assert(f([{1},{},e]) = [{1},{}]),
00766   assert(f([{1,2},{[1,2]},e]) = [{1,2},{[1,2]}]),
00767   assert(f([{1,2},{[1,2],[2,1]},e]) = [{1,2},{[1,2],[2,1]}]),
00768   true)$
00769 
00770 okltest_mudgl2dgl(f) := block([e],
00771   assert(f([{},{},e]) = [{},{}]),
00772   assert(f([{1},{},e]) = [{1},{}]),
00773   assert(f([{1,2},{[1,2]},e]) = [{1,2},{[1,2]}]),
00774   assert(f([{1,2},{[1,2],[2,1]},e]) = [{1,2},{[1,2],[2,1]}]),
00775   assert(f([{1},{[1,1]},e]) = [{1},{[1,1]}]),
00776   true)$
00777 
00778 okltest_gdg2dgl(f) := block([e],
00779   assert(f([{},{},e]) = [{},{}]),
00780   assert(f([{1,2},{},e]) = [{1,2},{}]),
00781   assert(f([{1,2,3},{[1,1],[1,2],[2,3]},identity]) = [{1,2,3},{[1,1],[1,2],[2,3]}]),
00782   assert(f([{1},{1},lambda([x],[1,1])]) = [{1},{[1,1]}]),
00783   true)$
00784 
00785 okltest_gdg2mudgl(f) := block([e],
00786   assert(gr_equalp(f([{},{},e]), [{},{},e]) = true),
00787   assert(gr_equalp(f([{1},{},e]), [{1},{},e]) = true),
00788   assert(gr_equalp(f([{1},{1,2},lambda([x],[1,1])]), [{1},{[1,1]}, lambda([x],2)]) = true),
00789   assert(gr_equalp(f([{1,2},{1,2,3,4},lambda([x],[1,2])]), [{1,2},{[1,2]}, lambda([x],4)]) = true),
00790   true)$
00791 
00792 okltest_omudg2odg(f) := block([e],
00793   assert(f([[],[],e]) = [[],[]]),
00794   assert(okltest_mudg2dg(buildq([f], lambda([G], odg2dg(f(mudg2omudg(G)))))) = true),
00795   true)$
00796 
00797 okltest_omudgl2odgl(f) := block([e],
00798   assert(f([[],[],e]) = [[],[]]),
00799   assert(okltest_mudgl2dgl(buildq([f], lambda([G], odgl2dgl(f(mudgl2omudgl(G)))))) = true),
00800   true)$
00801 
00802 okltest_ogdg2odgl(f) := block([e],
00803   assert(f([[],[],e]) = [[],[]]),
00804   assert(okltest_gdg2dgl(buildq([f], lambda([G], odgl2dgl(f(gdg2ogdg(G)))))) = true),
00805   true)$
00806 
00807 okltest_ogdg2omudgl(f) := block([e],
00808   assert(gr_equalp(f([[],[],e]), [[],[],e]) = true),
00809   assert(okltest_gdg2mudgl(buildq([f], lambda([G], omudgl2mudgl(f(gdg2ogdg(G)))))) = true),
00810   true)$
00811 
00812 okltest_odg2dg(f) := (
00813   assert(f([[],[]]) = [{},{}]),
00814   assert(f([[1],[]]) = [{1},{}]),
00815   assert(f([[1,2],[[1,2]]]) = [{1,2},{[1,2]}]),
00816   assert(f([[1,3,2,4],[[3,1],[4,2]]]) = [{1,2,3,4},{[3,1],[4,2]}]),
00817   true)$
00818 
00819 okltest_odgl2dgl(f) := (
00820   assert(f([[],[]]) = [{},{}]),
00821   assert(f([[1],[[1,1]]]) = [{1},{[1,1]}]),
00822   assert(f([[1,2],[[1,2],[2,2]]]) = [{1,2},{[1,2],[2,2]}]),
00823   assert(okltest_odg2dg(f) = true),
00824   true)$
00825 
00826 okltest_omudg2mudg(f) := block([e],
00827   assert(f([[],[],e]) = [{},{},e]),
00828   assert(f([[1,2],[[1,2],[2,1]],e]) = [{1,2},{[1,2],[2,1]},e]),
00829   true)$
00830 
00831 okltest_omudgl2mudgl(f) := block([e],
00832   assert(f([[],[],e]) = [{},{},e]),
00833   assert(okltest_omudg2mudg(f) = true),
00834   assert(f([[1,2],[[1,2],[2,1],[1,1]],e]) = [{1,2},{[1,2],[2,1],[1,1]},e]),
00835   true)$
00836 
00837 okltest_ogdg2gdg(f) := block([e],
00838   assert(f([[],[],e]) = [{},{},e]),
00839   assert(f([[1,2],[1,3,-1],e]) = [{1,2},{1,3,-1},e]),
00840   true)$
00841 
00842 
00843 /* ***************
00844    * Conversions *
00845    ***************
00846 */
00847 
00848 okltest_gl2g(f) := (
00849   assert(f([{},{}]) = [{},{}]),
00850   assert(f([{1},{}]) = [{1},{}]),
00851   assert(f([{1},{{1}}]) = [{1},{}]),
00852   /* XXX */
00853   true)$
00854 
00855 okltest_gg2g(f) := (
00856   for n : 0 thru 3 do block([G : dipole_gg(n)],
00857     if n = 0 then assert(f(G) = [{1,2},{}])
00858     else assert(f(G) = [{1,2},{{1,2}}])),
00859   for n : 0 thru 3 do block([G : bouquet_gg(n)],
00860     assert(f(G) = [{1},{}])),
00861   assert(okltest_gl2g(buildq([f],lambda([G],f(gl2gg(G)))))),
00862   true)$
00863 
00864 okltest_ogl2og(f) := (
00865   assert(f([[1,3,2],[{2,3},{1},{1,3},{2}]]) = [[1,3,2],[{2,3},{1,3}]]),
00866   /* XXX */
00867   assert(okltest_gl2g(buildq([f],lambda([G],og2g(f(gl2ogl(G))))))),
00868   true)$
00869 
00870 okltest_ogg2og(f) := (
00871   /* XXX */
00872   assert(okltest_gg2g(buildq([f],lambda([G],og2g(f(gg2ogg(G))))))),
00873   true)$
00874 
00875 okltest_mugl2mug(f) := (
00876   /* XXX */
00877   assert(okltest_gl2g(buildq([f],lambda([G],mug2g(f(gl2mugl(G))))))),
00878   true)$
00879 
00880 okltest_omugl2omug(f) := (
00881   /* XXX */
00882   assert(okltest_ogl2og(buildq([f],lambda([G],omug2og(f(ogl2omugl(G))))))),
00883   true)$
00884 
00885 okltest_dgl2dg(f) := (
00886   assert(f([{},{}]) = [{},{}]),
00887   assert(f([{1},{[1,1]}]) = [{1},{}]),
00888   assert(f([{1,2,3},{[1,2],[2,1],[3,3],[1,3]}]) = [{1,2,3},{[1,2],[2,1],[1,3]}]),
00889   true)$
00890 
00891 okltest_odgl2odg(f) := (
00892     assert(f([[2,1,3],[[1,2],[2,1],[3,3],[1,3]]]) = [[2,1,3],[[1,2],[2,1],[1,3]]]),
00893   assert(okltest_dgl2dg(buildq([f], lambda([G], odgl2dgl(f(dgl2odgl(G)))))) = true),
00894   true)$
00895 
00896 okltest_dg2g(f) := (
00897   assert(f([{},{}]) = [{},{}]),
00898   assert(f([{1},{}]) = [{1},{}]),
00899   assert(f([{1,2},{[1,2]}]) = [{1,2},{{1,2}}]),
00900   assert(f([{1,2},{[1,2],[2,1]}]) = [{1,2},{{1,2}}]),
00901   /* XXX */
00902   true)$
00903 
00904 okltest_odg2og(f) := (
00905   assert(f([[3,2,1],[[3,1],[2,1],[2,3],[1,3],[1,2]]]) = [[3,2,1],[{1,3},{1,2},{2,3}]]),
00906   assert(okltest_dg2g(buildq([f],lambda([G],og2g(f(dg2odg(G))))))),
00907   true)$
00908 
00909 okltest_dgl2gl(f) := (
00910   assert(f([{1},{[1,1]}]) = [{1},{{1}}]),
00911   assert(okltest_dg2g(f)),
00912   true)$
00913 
00914 okltest_odgl2ogl(f) := (
00915   /* XXX */
00916   assert(okltest_odg2og(f)),
00917   assert(okltest_dgl2gl(buildq([f],lambda([G],ogl2gl(f(dgl2odgl(G))))))),
00918   true)$
00919 
00920 okltest_gdg2gg(f) := (
00921   for n : 0 thru 3 do block([G : dipole_gdg(n)],
00922     assert(gr_equalp(f(G), dipole_gg(n)) = true)),
00923   assert(okltest_dgl2gl(buildq([f],lambda([G],gg2gl(f(dgl2gdg(G))))))),
00924   true)$
00925 
00926 okltest_ogdg2ogg(f) := (
00927   for n : 0 thru 3 do block([G : dipole_ogdg(n)],
00928     assert(gr_equalp(f(G), dipole_ogg(n)) = true)),
00929   assert(okltest_odgl2ogl(buildq([f],lambda([G],ogg2ogl(f(odgl2ogdg(G))))))),
00930   assert(okltest_gdg2gg(buildq([f],lambda([G],ogg2gg(f(gdg2ogdg(G))))))),
00931   true)$
00932 
00933 okltest_mudg2mug(f) := block([ef],
00934   assert(gr_equalp(f([{},{},ef]), [{},{},ef]) = true),
00935   assert(gr_equalp(f([{11},{},ef]), [{11},{},ef]) = true),
00936   assert(gr_equalp(f([{1,2},{[1,2]},lambda([e],3)]), [{1,2},{{1,2}},lambda([e],3)]) = true),
00937   assert(gr_equalp(f([{1,2},{[2,1]},lambda([e],3)]), [{1,2},{{1,2}},lambda([e],3)]) = true),
00938   assert(gr_equalp(f([{1,2},{[1,2],[2,1]},lambda([e],3)]), [{1,2},{{1,2}},lambda([e],6)]) = true),
00939   assert(okltest_dg2g(buildq([f], lambda([G], mug2g(f(dg2mudg(G)))))) = true),
00940   true)$
00941 
00942 okltest_g2dg(f) := block(
00943   assert(f([{},{}]) = [{},{}]),
00944   assert(f([{1},{}]) = [{1},{}]),
00945   assert(f([{1,2},{{1,2}}]) = [{1,2},{[1,2],[2,1]}]),
00946   for G in okltest_list_g do
00947     assert(dgl2gl(f(G)) = G),
00948   true)$
00949 
00950 okltest_gl2dgl(f) := block(
00951   assert(f([{},{}]) = [{},{}]),
00952   assert(f([{1},{}]) = [{1},{}]),
00953   assert(f([{1},{{1}}]) = [{1},{[1,1]}]),
00954   assert(f([{1,2},{{1,2}}]) = [{1,2},{[1,2],[2,1]}]),
00955   for G in append(okltest_list_g,okltest_list_gl) do
00956     assert(dgl2gl(f(G)) = G),
00957   true)$
00958 
00959 okltest_mug2mudg(f) := block([e],
00960   assert(gr_equalp(f([{},{},e]), [{},{},e]) = true),
00961   assert(gr_equalp(f([{1},{},e]), [{1},{},e]) = true),
00962   assert(gr_equalp(f([{1,2},{{1,2}},lambda([e],2)]), [{1,2},{[1,2],[2,1]},lambda([e],2)]) = true),
00963   for G in okltest_list_mug do block([G2 : mudg2mug(f(G))],
00964     assert(gr_equalp([G2[1],G2[2],buildq([G2],lambda([e],G2[3](e)/2))], G) = true)
00965   ),
00966   true)$
00967 
00968 
00969 /* **************************
00970    * Basic graph operations *
00971    **************************
00972 */
00973 
00974 okltest_expand_edge(f) := (
00975   assert(f({1,2}) = [1,2]),
00976   assert(f({1}) = [1,1]),
00977   true)$
00978 
00979 okltest_neighbours_g(f) := block([G],
00980   assert(f(1,[{1},{}]) = {}),
00981   assert(f(1,[{1,2},{{1,2}}]) = {2}),
00982   for n : 1 thru 4 do
00983     assert(f(1,complete_g(setn(n))) = setmn(2,n)),
00984   true)$
00985 
00986 okltest_neighbours_og(f) := block([G],
00987   assert(f(1,[[1],[]]) = {}),
00988   assert(f(1,[[1,2],[{1,2}]]) = {2}),
00989   assert(okltest_neighbours_g(buildq([f], lambda([v,G], f(v,g2og(G))))) = true),
00990   true)$
00991 
00992 okltest_neighbours_gl(f) := block([G],
00993   assert(f(1,[{1},{{1}}]) = {1}),
00994   assert(okltest_neighbours_g(buildq([f],lambda([v,G],f(v,G))))),
00995   G : [{1,2,3,4,5,6,7},{{1,2},{1,3},{1,6},{2,3},{2,5},{3,4},{4},{4,7},{5},{5,7},{6},{6,7}}],
00996   assert(f(1,G) = {2,3,6}),
00997   assert(f(6,G) = {1,6,7}),
00998   assert(okltest_neighbours_g(f)),
00999   true)$
01000 
01001 okltest_neighbours_gg(f) := block(
01002   okltest_neighbours_gl(buildq([f],lambda([v,G],f(v,gl2gg(G))))),
01003   for n : 0 thru 2 do block([G : ogg2gg(dipole_ogg(n))],
01004     for v : 1 thru 2 do
01005       if n=0 then assert(f(v,G) = {})
01006       else assert(f(v,G) = disjoin(v,{1,2})
01007   ),
01008   for n : 0 thru 2 do block([G : ogg2gg(bouquet_ogg(n))],
01009     if n=0 then assert(f(1,G) = {})
01010       else assert(f(1,G) = {1})
01011   ),
01012   true))$
01013 
01014 okltest_outneighbours_dg(f) := (
01015   assert(f(1,[{1},{}]) = {}),
01016   assert(f(1,[{1,2,3},{[1,2],[2,3]}]) = {2}),
01017   true)$
01018 
01019 okltest_outneighbours_dgl(f) := (
01020   assert(f(1,[{1},{}]) = {}),
01021   assert(f(1,[{1},{[1,1]}]) = {1}),
01022   assert(okltest_outneighbours_dg(f) = true),
01023   true)$
01024 
01025 okltest_inneighbours_dg(f) := (
01026   assert(f(1,[{1},{}]) = {}),
01027   assert(f(1,[{1,2,3},{[1,2],[2,3]}]) = {}),
01028   assert(f(1,[{1,2,3},{[2,1],[2,3]}]) = {2}),
01029   assert(okltest_outneighbours_dg(buildq([f], lambda([v,G],f(v,transposed_dg(G))))) = true),
01030   true)$
01031 
01032 okltest_inneighbours_dgl(f) := (
01033   assert(f(1,[{1},{}]) = {}),
01034   assert(f(1,[{1},{[1,1]}]) = {1}),
01035   assert(okltest_inneighbours_dg(f) = true),
01036   assert(okltest_outneighbours_dgl(buildq([f], lambda([v,G],f(v,transposed_dgl(G))))) = true),
01037   true)$
01038 
01039 okltest_remove_vertices_gl(f) := (
01040   assert(f({1,2,3},[{},{}]) = [{},{}]),
01041   assert(f({},[{},{}]) = [{},{}]),
01042   assert(f({},[{2,3,4},{{3,4}}]) = [{2,3,4},{{3,4}}]),
01043   assert(f({1},[{1,2,3},{{1},{1,2},{2,3}}]) = [{2,3},{{2,3}}]),
01044   assert(f({1,3},[{1,2,3,4},{{1},{2},{1,3},{1,4},{3,2},{2,4}}]) = [{2,4},{{2},{2,4}}]),
01045   true)$
01046 
01047 
01048 /* *****************************
01049    * Basic graph constructions *
01050    *****************************
01051 */
01052 
01053 
01054 okltest_edge_induced_subgraph_g(f) := (
01055   assert(f({},[{},{}]) = [{},{}]),
01056   assert(f({},[{1},{}]) = [{},{}]),
01057   assert(f({{1,2}},[{1,2,3},{{1,2}}]) = [{1,2},{{1,2}}]),
01058   assert(f({{1,2},{2,3}},[{1,2,3},{{1,2},{2,3}}]) = [{1,2,3},{{1,2},{2,3}}]),
01059   assert(f({{1,2},{2,3}},[{1,2,3},{{1,2},{2,3},{1,3}}]) = [{1,2,3},{{1,2},{2,3}}]),
01060   true)$
01061 
01062 okltest_edge_induced_subgraph_gl(f) := (
01063   assert(f({{1}},[{1},{{1}}]) = [{1},{{1}}]),
01064   assert(f({{1,2}},[{1,2},{{1,2},{2}}]) = [{1,2},{{1,2}}]),
01065   assert(f({{1,2}},[{1,2,3},{{1,2},{3}}]) = [{1,2},{{1,2}}]),
01066   true)$
01067 
01068 okltest_edge_induced_subgraph_mug(f) := block([edgef],
01069   assert(gr_equalp(f({},[{},{},edgef]), [{},{},edgef]) = true),
01070   assert(gr_equalp(f({},[{1},{},edgef]), [{},{},edgef]) = true),
01071   assert(gr_equalp(f({{1,2}},[{1,2},{{1,2}},lambda([e],1)]), [{1,2},{{1,2}},lambda([e],if e={1,2} then 1)]) = true),
01072   assert(gr_equalp(f({{1,2}},[{1,2},{{1,2}},lambda([e],2)]), [{1,2},{{1,2}},lambda([e],if e={1,2} then 2)]) = true),
01073   assert(gr_equalp(f({{1,2}},[{1,2,3},{{1,2},{2,3}},lambda([e],if e={1,2} then 2 elseif e={2,3} then 3)]), [{1,2},{{1,2}},lambda([e],if e={1,2} then 2)]) = true),
01074   true)$
01075 
01076 okltest_edge_induced_subgraph_mugl(f) := block([edgef],
01077   assert(gr_equalp(f({},[{},{},edgef]), [{},{},edgef]) = true),
01078   assert(gr_equalp(f({},[{1},{},edgef]), [{},{},edgef]) = true),
01079   assert(gr_equalp(f({{1}},[{1},{{1}},lambda([e],2)]), [{1},{{1}},lambda([e],if e={1} then 2)]) = true),
01080   assert(gr_equalp(f({{1}},[{1,2},{{1},{1,2}},lambda([e],if e={1} then 2 else 3)]), [{1},{{1}},lambda([e],if e={1} then 2)]) = true),
01081   assert(gr_equalp(f({{1,2},{1,3}}, [{1,2,3,4},{{1,2},{1},{1,3},{2,4}},lambda([e],3)]), [{1,2,3},{{1,2},{1,3}},lambda([e],3)]) = true),
01082   true)$
01083 
01084 okltest_edge_induced_subgraph_gg(f) := block([edgef],
01085   assert(f({},[{},{},edgef]) = [{},{},edgef]),
01086   assert(f({},[{1},{},edgef]) = [{},{},edgef]),
01087   assert(f({1},[{1,2},{1},lambda([e],{1,2})]) = [{1,2},{1},lambda([e],{1,2})]),
01088   assert(f({1},[{1,2,3},{1,2},lambda([e],if e=1 then {1,2} else {2,3})]) = [{1,2},{1},lambda([e],if e=1 then {1,2} else {2,3})]),
01089   assert(f({1,2},[{1,2,3},{1,2,3},lambda([e],if e=1 then {1,2} elseif e=2 then {2,3} else {1,3})]) = [{1,2,3},{1,2},lambda([e],if e=1 then {1,2} elseif e=2 then {2,3} else {1,3})]),
01090   assert(gr_equalp(f({1,2},[{1,2,3},{1,2,3},lambda([e],if e=1 then {1,2} elseif e=2 then {2,3} else {1,3})]), [{1,2,3},{1,2},lambda([e],if e=1 then {1,2} elseif e=2 then {2,3})]) = true),
01091   true)$
01092 
01093 okltest_edge_induced_subgraph_dg(f) := (
01094   assert(f({},[{},{}]) = [{},{}]),
01095   assert(f({},[{1},{}]) = [{},{}]),
01096   assert(f({[1,2]},[{1,2,3},{[1,2]}]) = [{1,2},{[1,2]}]),
01097   assert(f({[1,2],[3,2]},[{1,2,3},{[1,2],[3,2],[1,3]}]) = [{1,2,3},{[1,2],[3,2]}]),
01098   true)$
01099 
01100 okltest_edge_induced_subgraph_dgl(f) := (
01101   assert(f({},[{1},{[1,1]}]) = [{},{}]),
01102   assert(f({[1,1]},[{1},{[1,1]}]) = [{1},{[1,1]}]),
01103   assert(f({[1,2],[1,1]},[{1,2},{[1,2],[1,1]}]) = [{1,2},{[1,2],[1,1]}]),
01104   assert(f({[1,2]},[{1,2},{[2,2],[1,2]}]) = [{1,2},{[1,2]}]),
01105   true)$
01106 
01107 okltest_edge_induced_subgraph_mudg(f) := block([edgef],
01108   assert(gr_equalp(f({},[{},{},edgef]), [{},{},edgef]) = true),
01109   assert(gr_equalp(f({},[{1},{},edgef]), [{},{},edgef]) = true),
01110   assert(gr_equalp(f({[1,2]},[{1,2},{[1,2]},lambda([e],1)]), [{1,2},{[1,2]},lambda([e],if e=[1,2] then 1)]) = true),
01111   assert(gr_equalp(f({[1,2]},[{1,2},{[1,2]},lambda([e],2)]), [{1,2},{[1,2]},lambda([e],if e=[1,2] then 2)]) = true),
01112   assert(gr_equalp(f({[1,2]},[{1,2,3},{[1,2],[2,3]},lambda([e],if e=[1,2] then 2 elseif e=[2,3] then 3)]), [{1,2},{[1,2]},lambda([e],if e=[1,2] then 2)]) = true),
01113   true)$
01114 
01115 okltest_edge_induced_subgraph_mudgl(f) := block([edgef],
01116   assert(gr_equalp(f({},[{},{},edgef]), [{},{},edgef]) = true),
01117   assert(gr_equalp(f({},[{1},{},edgef]), [{},{},edgef])),
01118   assert(gr_equalp(f({[1,1]},[{1},{[1,1]},lambda([e],2)]), [{1},{[1,1]},lambda([e],if e=[1,1] then 2)]) = true),
01119   assert(gr_equalp(f({[1,1]},[{1,2},{[1,1],[1,2]},lambda([e],if e=[1,1] then 2 else 3)]), [{1},{[1,1]},lambda([e],if e=[1,1] then 2)]) = true),
01120   true)$
01121 
01122 okltest_edge_induced_subgraph_gdg(f) := block([edgef],
01123   assert(gr_equalp(f({},[{},{},edgef]), [{},{},edgef]) = true),
01124   assert(gr_equalp(f({},[{1},{},edgef]), [{},{},edgef]) = true),
01125   assert(gr_equalp(f({1},[{1,2},{1},lambda([e],[1,2])]), [{1,2},{1},lambda([e],if e=1 then [1,2])]) = true),
01126   assert(gr_equalp(f({1},[{1,2,3},{1,2},lambda([e],if e=1 then [1,2] else [2,3])]), [{1,2},{1},lambda([e],if e=1 then [1,2])]) = true),
01127   assert(gr_equalp(f({1,2},[{1,2,3},{1,2,3},lambda([e],if e=1 then [1,2] elseif e=2 then [2,3] else [1,3])]), [{1,2,3},{1,2},lambda([e],if e=1 then [1,2] elseif e=2 then [2,3])]) = true),
01128   true)$
01129 
01130 okltest_complement_g(f) := (
01131   assert(f([{},{}]) = [{},{}]),
01132   assert(f([{1},{}]) = [{1},{}]),
01133   assert(f([{1,2},{}]) = [{1,2},{{1,2}}]),
01134   assert(f([{1,2},{{1,2}}]) = [{1,2},{}]),
01135   assert(f([{1,2,3},{{1,2}}]) = [{1,2,3},{{1,3},{2,3}}]),
01136   true)$
01137 
01138 okltest_transposed_dg(f) := (
01139   assert(f([{},{}]) = [{},{}]),
01140   assert(f([{1},{}]) = [{1},{}]),
01141   assert(f([{1,2,3},{[1,2],[2,3],[3,1]}]) = [{1,2,3},{[1,3],[3,2],[2,1]}]),
01142   true)$
01143 
01144 okltest_transposed_dgl(f) := (
01145   assert(f([{1},{[1,1]}]) = [{1},{[1,1]}]),
01146   assert(okltest_transposed_dg(f) = true),
01147   true)$
01148 
01149 okltest_transposed_odg(f) := (
01150   assert(f([[],[]]) = [[],[]]),
01151   assert(f([[1],[]]) = [[1],[]]),
01152   assert(f([[1,2,3],[[1,2],[2,3],[3,1]]]) = [[1,2,3],[[2,1],[3,2],[1,3]]]),
01153   true)$
01154 
01155 okltest_transposed_odgl(f) := (
01156   assert(f([[1],[[1,1]]]) = [[1],[[1,1]]]),
01157   assert(okltest_transposed_odg(f) = true),
01158   true)$
01159 
01160 
01161 /* **********
01162    * Tests  *
01163    **********
01164 */
01165 
01166 okltest_parallel_edges_gg_p(f) := block([EF],
01167   assert(f([{},{},EF]) = false),
01168   assert(f([{1},{},EF]) = false),
01169   assert(f([{1},{1},lambda([e],{1})]) = false),
01170   assert(f([{1},{1,2},lambda([e],{1})]) = true),
01171   true)$
01172 
01173 okltest_parallel_edges_mug_p(f) := block([EF],
01174   assert(f([{},{},EF]) = false),
01175   assert(f([{1},{},EF]) = false),
01176   assert(f([{1,2},{{1,2}},lambda([e],choose_element(e))]) = false),
01177   assert(f([{1,2,3},{{2,3}},lambda([e],choose_element(e))]) = true),
01178   true)$
01179 
01180 okltest_parallel_edges_mugl_p(f) := (
01181   assert(okltest_parallel_edges_mug_p(f) = true),
01182   assert(f([{1},{{1}},lambda([e],choose_element(e))]) = false),
01183   assert(f([{2},{{2}},lambda([e],choose_element(e))]) = true),
01184   true)$
01185 
01186 okltest_parallel_edges_ogg_p(f) := (
01187   assert(okltest_parallel_edges_gg_p(buildq([f],lambda([G],f(gg2ogg(G))))) = true),
01188   true)$
01189 
01190 okltest_parallel_edges_omug_p(f) := (
01191   assert(okltest_parallel_edges_mug_p(buildq([f],lambda([G],f(mug2omug(G))))) = true),
01192   true)$
01193 
01194 okltest_parallel_edges_omugl_p(f) := (
01195   assert(okltest_parallel_edges_mugl_p(buildq([f],lambda([G],f(mugl2omugl(G))))) = true),
01196   true)$
01197 
01198 okltest_irreflexive_gl_p(f) := (
01199   assert(f([{},{}]) = true),
01200   assert(f([{1},{{1}}]) = false),
01201   /* XXX */
01202   true)$
01203 
01204 okltest_irreflexive_mugl_p(f) := block([EF],
01205   assert(f([{},{},EF]) = true),
01206   assert(f([{1},{{1}},lambda([e],1)]) = false),
01207   assert(f([{1},{{1}},lambda([e],2)]) = false),
01208   assert(okltest_irreflexive_gl_p(buildq([f],lambda([G],f(gl2mugl(G))))) = true),
01209   /* XXX */
01210   true)$
01211 
01212 okltest_irreflexive_gg_p(f) := (
01213   assert(okltest_irreflexive_mugl_p(buildq([f],lambda([G],f(mugl2gg(G))))) = true),
01214   true)$
01215 
01216 okltest_irreflexive_ogl_p(f) := (
01217   assert(okltest_irreflexive_gl_p(buildq([f],lambda([G],f(gl2ogl(G))))) = true),
01218   true)$
01219 
01220 okltest_irreflexive_omugl_p(f) := (
01221   assert(okltest_irreflexive_mugl_p(buildq([f],lambda([G],f(mugl2omugl(G))))) = true),
01222   true)$
01223 
01224 okltest_irreflexive_ogg_p(f) := (
01225   assert(okltest_irreflexive_gg_p(buildq([f],lambda([G],f(gg2ogg(G))))) = true),
01226   true)$
01227 
01228 okltest_orientedgraph_dg_p(f) := (
01229   assert(f([{},{}]) = true),
01230   assert(f([{1},{}]) = true),
01231   assert(f([{1,2},{}]) = true),
01232   assert(f([{1,2},{[1,2]}]) = true),
01233   assert(f([{1,2},{[2,1]}]) = true),
01234   assert(f([{1,2},{[1,2],[2,1]}]) = false),
01235   true)$
01236 
01237 okltest_orientedgraph_dgl_p(f) := (
01238   assert(okltest_orientedgraph_dg_p(f) = true),
01239   assert(f([{1},{[1,1]}]) = true),
01240   true)$
01241 
01242 okltest_orientedgraph_odg_p(f) := (
01243   assert(okltest_orientedgraph_dg_p(buildq([f], lambda([G],f(dg2odg(G))))) = true),
01244   true)$
01245 
01246 okltest_orientedgraph_odgl_p(f) := (
01247   assert(okltest_orientedgraph_dgl_p(buildq([f], lambda([G],f(dgl2odgl(G))))) = true),
01248   true)$
01249 
01250 okltest_complete_g_p(f) := (
01251   assert(f([{},{}]) = true),
01252   assert(f([{3},{}]) = true),
01253   assert(f([{3,5},{{3,5}}]) = true),
01254   assert(f([{1,2},{}]) = false),
01255   assert(f([{3,5,6},{{3,5},{3,6},{5,6}}]) = true),
01256   true)$
01257 
01258 okltest_complete_gl_p(f) := (
01259   assert(f([{},{}]) = true),
01260   assert(f([{3},{}]) = true),
01261   assert(f([{3},{{3}}]) = true),
01262   assert(f([{3,5},{{3,5}}]) = true),
01263   assert(f([{3,5},{{3,5},{5}}]) = true),
01264   assert(f([{1,2},{}]) = false),
01265   assert(f([{1,2},{{1}}]) = false),
01266   assert(f([{3,5,6},{{3,5},{3,6},{5,6}}]) = true),
01267   true)$
01268 
01269 okltest_complete_og_p(f) := (
01270   assert(f([[],[]]) = true),
01271   assert(f([[3],[]]) = true),
01272   assert(f([[3,5],[{3,5}]]) = true),
01273   assert(f([[1,2],[]]) = false),
01274   assert(f([[3,5,6],[{3,5},{3,6},{5,6}]]) = true),
01275   true)$
01276 
01277 okltest_complete_ogl_p(f) := (
01278   assert(f([[],[]]) = true),
01279   assert(f([[3],[]]) = true),
01280   assert(f([[3],[{3}]]) = true),
01281   assert(f([[3,5],[{3,5}]]) = true),
01282   assert(f([[3,5],[{3,5},{5}]]) = true),
01283   assert(f([[1,2],[]]) = false),
01284   assert(f([[1,2],[{1}]]) = false),
01285   assert(f([[3,5,6],[{3,5},{3,6},{5,6}]]) = true),
01286   true)$
01287 
01288 okltest_complete_mug_p(f) := block([e],
01289   assert(f([{},{},e]) = true),
01290   assert(f([{3},{},e]) = true),
01291   assert(f([{3,5},{{3,5}},e]) = true),
01292   assert(f([{1,2},{},e]) = false),
01293   assert(f([{3,5,6},{{3,5},{3,6},{5,6}},e]) = true),  
01294   true)$
01295 
01296 okltest_complete_mugl_p(f) := block([e],
01297   assert(f([{},{},e]) = true),
01298   assert(f([{3},{},e]) = true),
01299   assert(f([{3},{{3}},e]) = true),
01300   assert(f([{3,5},{{3,5}},e]) = true),
01301   assert(f([{3,5},{{3,5},{5}},e]) = true),
01302   assert(f([{1,2},{},e]) = false),
01303   assert(f([{1,2},{{1}},e]) = false),
01304   assert(f([{3,5,6},{{3,5},{3,6},{5,6}},e]) = true),
01305   true)$
01306 
01307 okltest_complete_omug_p(f) := block([e],
01308   assert(f([[],[],e]) = true),
01309   assert(f([[3],[],e]) = true),
01310   assert(f([[3,5],[{3,5}],e]) = true),
01311   assert(f([[1,2],[],e]) = false),
01312   assert(f([[3,5,6],[{3,5},{3,6},{5,6}],e]) = true),
01313   true)$
01314 
01315 okltest_complete_omugl_p(f) := block([e],
01316   assert(f([[],[],e]) = true),
01317   assert(f([[3],[],e]) = true),
01318   assert(f([[3],[{3}],e]) = true),
01319   assert(f([[3,5],[{3,5}],e]) = true),
01320   assert(f([[3,5],[{3,5},{5}],e]) = true),
01321   assert(f([[1,2],[],e]) = false),
01322   assert(f([[1,2],[{1}],e]) = false),
01323   assert(f([[3,5,6],[{3,5},{3,6},{5,6}],e]) = true),
01324   true)$
01325 
01326 okltest_complete_gg_p(f) := block([ef],
01327   assert(f([{},{},ef]) = true),
01328   assert(f([{1},{},ef]) = true),
01329   assert(f([{1},{1},lambda([e],{1})]) = true),
01330   assert(f([{1,2},{{1,2}},identity]) = true),
01331   assert(f([{1,2},{},ef]) = false),
01332   assert(f([{1,2},{{1}},identity]) = false),
01333   assert(okltest_complete_gl_p(buildq([f], lambda([G], f(gl2gg(G))))) = true),
01334   true)$
01335 
01336 okltest_complete_ogg_p(f) := (
01337   assert(okltest_complete_gg_p(buildq([f], lambda([G], f(gg2ogg(G))))) = true),
01338   true)$
01339 
01340 okltest_dominating_vertex_g_p(f) := (
01341   assert(f(1,[{1},{}]) = true),
01342   assert(f(1,[{1,2},{}]) = false),
01343   assert(f(1,[{1,2},{{1,2}}]) = true),
01344   true)$
01345 
01346 okltest_dominating_vertex_gl_p(f) := (
01347   assert(f(1,[{1},{}]) = false),
01348   assert(f(1,[{1,2},{}]) = false),
01349   assert(f(1,[{1,2},{{1,2}}]) = false),
01350   assert(f(1,[{1},{{1}}]) = true),
01351   assert(f(1,[{1,2},{{1,2},{1}}]) = true),
01352   true)$
01353 
01354 okltest_has_dominating_vertex_g(f) := (
01355   assert(f([{},{}]) = false),
01356   assert(f([{1},{}]) = true),
01357   assert(f([{1,2},{}]) = false),
01358   assert(f([{1,2},{{1,2}}]) = true),
01359   assert(f([{1,2,3,4},{{1,2},{1,3},{2,4}}]) = false),
01360   assert(f([{1,2,3,4},{{1,2},{1,3},{1,4}}]) = true),
01361   true)$
01362 
01363 okltest_has_dominating_vertex_gl(f) := (
01364   assert(f([{},{}]) = false),
01365   assert(f([{1},{}]) = false),
01366   assert(f([{1,2},{}]) = false),
01367   assert(f([{1,2},{{1,2}}]) = false),
01368   assert(f([{1,2,3,4},{{1,2},{1,3},{2,4}}]) = false),
01369   assert(f([{1,2,3,4},{{1,2},{1,3},{1,4}}]) = false),
01370   assert(f([{1},{{1}}]) = true),
01371   assert(f([{1,2},{{1,2},{2}}]) = true),
01372   assert(f([{1,2,3,4},{{2,1},{2,3},{2,4},{2}}]) = true),
01373   true)$
01374 
01375 okltest_connected_g_p(f) := (
01376   assert(f([{},{}]) = true),
01377   assert(f([{1},{}]) = true),
01378   assert(f([{1,2},{}]) = false),
01379   assert(f([{1,2},{{1,2}}]) = true),
01380   for n : 0 thru 4 do block([G : complete_stdg(n)],
01381     assert(f(G) = true)),
01382   for n : 1 thru 4 do block([G : pathgraph_g(n)],
01383     assert(f(G) = true)),
01384   true)$
01385 
01386 okltest_connected_og_p(f) := (
01387   assert(okltest_connected_g_p(buildq([f], lambda([G], f(g2og(G))))) = true),
01388   true)$
01389 
01390 okltest_connected_mug_p(f) := (
01391   assert(f([{1,2},{{1,2}},lambda([e],2)]) = true),
01392   assert(okltest_connected_g_p(buildq([f], lambda([G], f(g2mug(G))))) = true),
01393   true)$
01394 
01395 okltest_connected_omug_p(f) := (
01396   assert(okltest_connected_mug_p(buildq([f], lambda([G], f(mug2omug(G))))) = true),
01397   true)$
01398 
01399 okltest_connected_gg_p(f) := (
01400   assert(f([{1,2},{1,2},lambda([e],{e})]) = false),
01401   assert(okltest_connected_mug_p(buildq([f], lambda([G], f(mug2gg(G))))) = true),
01402   true)$
01403 
01404 okltest_connected_ogg_p(f) := (
01405   assert(okltest_connected_gg_p(buildq([f], lambda([G], f(gg2ogg(G))))) = true),
01406   true)$
01407 
01408 okltest_connected_gl_p(f) := (
01409   assert(okltest_connected_gg_p(buildq([f], lambda([G], f(gg2gl(G))))) = true),
01410   true)$
01411 
01412 okltest_connected_ogl_p(f) := (
01413   assert(okltest_connected_gl_p(buildq([f], lambda([G], f(gl2ogl(G))))) = true),
01414   true)$
01415 
01416 okltest_connected_mugl_p(f) := (
01417   assert(okltest_connected_gg_p(buildq([f], lambda([G], f(gg2mugl(G))))) = true),
01418   true)$
01419 
01420 okltest_connected_omugl_p(f) := (
01421   assert(okltest_connected_mugl_p(buildq([f], lambda([G], f(mugl2omugl(G))))) = true),
01422   true)$
01423 
01424 okltest_sconnected_dg_p(f) := (
01425   assert(f([{},{}]) = true),
01426   assert(f([{1,2},{[1,2]}]) = false),
01427   assert(f([{1,2},{[1,2],[2,1]}]) = true),
01428   assert(f([{1,2,3},{[1,2],[2,3],[3,1]}]) = true),
01429   assert(f([{1,2,3},{[1,2],[2,3],[1,3]}]) = false),
01430   assert(okltest_connected_g_p(buildq([f], lambda([G], f(g2dg(G))))) = true),
01431   true)$
01432 
01433 okltest_sconnected_odg_p(f) := (
01434   assert(okltest_sconnected_dg_p(buildq([f], lambda([G], f(dg2odg(G))))) = true),
01435   true)$
01436 
01437 okltest_sconnected_mudg_p(f) := (
01438   assert(okltest_sconnected_dg_p(buildq([f], lambda([G], f(dg2mudg(G))))) = true),
01439   assert(okltest_connected_mug_p(buildq([f], lambda([G], f(mug2mudg(G))))) = true),
01440   true)$
01441 
01442 okltest_sconnected_omudg_p(f) := (
01443   assert(okltest_sconnected_mudg_p(buildq([f], lambda([G], f(mudg2omudg(G))))) = true),
01444   true)$
01445 
01446 okltest_sconnected_gdg_p(f) := (
01447   assert(okltest_sconnected_mudg_p(buildq([f], lambda([G], f(mudg2gdg(G))))) = true),
01448   assert(okltest_sconnected_dg_p(buildq([f], lambda([G], f(dg2gdg(G))))) = true),
01449   true)$
01450 
01451 okltest_sconnected_ogdg_p(f) := (
01452   assert(okltest_sconnected_gdg_p(buildq([f], lambda([G], f(gdg2ogdg(G))))) = true),
01453   true)$
01454 
01455 okltest_sconnected_dgl_p(f) := (
01456   assert(okltest_sconnected_gdg_p(buildq([f], lambda([G], f(gdg2dgl(G))))) = true),
01457   true)$
01458 
01459 okltest_sconnected_odgl_p(f) := (
01460   assert(okltest_sconnected_ogdg_p(buildq([f], lambda([G], f(ogdg2odgl(G))))) = true),
01461   true)$
01462 
01463 okltest_sconnected_mudgl_p(f) := (
01464   assert(okltest_sconnected_gdg_p(buildq([f], lambda([G], f(gdg2mudgl(G))))) = true),
01465   true)$
01466 
01467 okltest_sconnected_omudgl_p(f) := (
01468   assert(okltest_sconnected_mudgl_p(buildq([f], lambda([G], f(mudgl2omudgl(G))))) = true),
01469   true)$
01470 
01471 okltest_tree_g_p(f) := (
01472   assert(f([{},{}]) = false),
01473   assert(f([{1},{}]) = true),
01474   assert(f([{2},{}]) = true),
01475   assert(f([{1,2},{}]) = false),
01476   assert(f([{1,2},{{1,2}}]) = true),
01477   assert(f([{1,2,3},{}]) = false),
01478   assert(f([{1,2,3},{{1,2}}]) = false),
01479   assert(f([{1,2,3},{{1,2},{1,3}}]) = true),
01480   assert(f([{1,2,3},{{1,2},{2,3}}]) = true),
01481   assert(f([{1,2,3},{{1,2},{1,3},{2,3}}]) = false),
01482   for n : 0 thru 4 do
01483     assert(f(complete_stdg(n)) = if n=1 or n=2 then true else false),
01484   for n : 1 thru 4 do
01485     assert(f(pathgraph_g(n)) = true),
01486   true)$
01487 
01488 okltest_tree_og_p(f) := (
01489   assert(okltest_tree_g_p(buildq([f],lambda([G], f(g2og(G))))) = true),
01490   true)$
01491 
01492 okltest_tree_mug_p(f) := (
01493   assert(okltest_tree_g_p(buildq([f], lambda([G], f(g2mug(G))))) = true),
01494   assert(f([{1,2},{{1,2}},lambda([e],2)]) = false),
01495   true)$
01496 
01497 okltest_tree_omug_p(f) := (
01498   assert(okltest_tree_mug_p(buildq([f], lambda([G], f(mug2omug(G))))) = true),
01499   true)$
01500 
01501 okltest_tree_gg_p(f) := (
01502   assert(okltest_tree_mug_p(buildq([f], lambda([G], f(mug2gg(G))))) = true),
01503   assert(f([{1},{{1}},identity]) = false),
01504   true)$
01505 
01506 okltest_tree_ogg_p(f) := (
01507   assert(okltest_tree_gg_p(buildq([f], lambda([G],f(gg2ogg(G))))) = true),
01508   true)$
01509 
01510 okltest_tree_gl_p(f) := (
01511   assert(f([{1},{{1}}]) = false),
01512   assert(okltest_tree_g_p(f) = true),
01513   true)$
01514 
01515 okltest_tree_ogl_p(f) := (
01516   assert(okltest_tree_gl_p(buildq([f], lambda([G],f(gl2ogl(G))))) = true),
01517   true)$
01518 
01519 okltest_tree_mugl_p(f) := (
01520   assert(f([{1},{{1}},lambda([e],2)]) = false),
01521   assert(okltest_tree_gl_p(buildq([f], lambda([G], f(gl2mugl(G))))) = true),
01522   assert(okltest_tree_mug_p(f) = true),
01523   true)$
01524 
01525 okltest_tree_omugl_p(f) := (
01526   assert(okltest_tree_mugl_p(buildq([f], lambda([G],f(mugl2omugl(G))))) = true),
01527   true)$
01528 
01529 okltest_regular_g_p(f) := (
01530   assert(f(0,[{},{}]) = true),
01531   assert(f(1,[{},{}]) = true),
01532   assert(f(2,[{},{}]) = true),
01533   assert(f(0,[{1},{}]) = true),
01534   assert(f(1,[{1},{}]) = false),
01535   /* XXX */
01536   true)$
01537 
01538 okltest_regular1_gg_p(f) := (
01539   /* *** */
01540   assert(okltest_regular_g_p(buildq([f],lambda([k,G],f(k,g2gg(G)))))),
01541   true)$
01542 
01543 okltest_regular2_gg_p(f) := (
01544   /* *** */
01545   assert(okltest_regular_g_p(buildq([f],lambda([k,G],f(k,g2gg(G)))))),
01546   true)$
01547 
01548 okltest_cycle_gg_p(f) := block([ef],
01549   for n : 1 thru 4 do
01550     assert(f(ogg2gg(cyclegraph_ogg(n))) = true),
01551   assert(f([{},{},ef]) = false),
01552   /* *** */
01553   true)$
01554 
01555 okltest_bipartite_g_p(f) := (
01556   assert(f([{},{}]) = true),
01557   assert(f([{1,2,3},{}]) = true),
01558   assert(f([{1,2,3},{{1,2}}]) = true),
01559   assert(f([{1,2,3},{{1,2},{2,3}}]) = true),
01560   assert(f([{1,2,3},{{1,2},{2,3},{3,1}}]) = false)
01561 )$
01562 
01563 okltest_completebipartite_g_p(f) := block(
01564   assert(f([{},{}])=true),
01565   assert(f([{1},{}]) = true),
01566   assert(f([{1,2},{{1,2}}]) = true),
01567   assert(f([{1,2},{}]) = false),
01568   assert(f([{1,2,3},{{1,2}}]) = false),
01569   assert(f([{1,2,3},{{1,2},{2,3}}]) = true),
01570   assert(f([{1,2,3},{{1,2},{2,3},{1,3}}]) = false),
01571   assert(f([{1,2,3},{}]) = false),
01572   assert(f([{1,2,3,4},{{1,2},{1,3},{1,4},{2,3}}]) = false),
01573   assert(f([{1,2,3,4},{{1,2},{1,3}}]) = false),
01574   assert(f([{1,2,3,4},{{1,2},{3,4},{1,4},{2,3}}]) = true),
01575   true)$
01576 
01577 okltest_completebipartite_gl_p(f) := block(
01578   assert(f([{1},{{1}}]) = false),
01579   assert(f([{1,2},{{1,2},{2}}]) = false),
01580   assert(okltest_completebipartite_g_p(f)),
01581   true)$
01582 
01583 okltest_completebipartite_gg_p(f) := block([G,edgef],
01584   assert(f([{},{},edgef])=true),
01585   assert(f([{1},{},edgef]) = true),
01586   for n : 1 thru 6 do block([G : cyclegraph_gg(n)],
01587     assert(f(G) = elementp(n,{2,4}))),
01588   assert(okltest_completebipartite_gl_p(buildq([f],lambda([G],f(gl2gg(G)))))),
01589   true)$
01590 
01591 /* ********************************
01592    * Connections to Maxima-graphs *
01593    ********************************
01594 */
01595 
01596 okltest_g2mg(f) := block(
01597   block([G : f([{},{}])],
01598     assert(is_graph(G) = true),
01599     assert(setify(vertices(G)) = {}),
01600     assert(setify(edges(G)) = {})
01601   ),
01602   block([G : f([{1},{}])],
01603     assert(is_graph(G) = true),
01604     assert(setify(vertices(G)) = {1}),
01605     assert(setify(edges(G)) = {}),
01606     assert(get_vertex_label(1,G) = 1)
01607   ),
01608   block([G : f([{2},{}])],
01609     assert(is_graph(G) = true),
01610     assert(setify(vertices(G)) = {1}),
01611     assert(setify(edges(G)) = {}),
01612     assert(get_vertex_label(1,G) = 2)
01613   ),
01614   block([G : f([{1,2},{{1,2}}])],
01615     assert(is_graph(G) = true),
01616     assert(setify(vertices(G)) = {1,2}),
01617     assert(setify(edges(G)) = {[1,2]}),
01618     assert(get_vertex_label(1,G) = 1),
01619     assert(get_vertex_label(2,G) = 2)
01620   ),
01621   block([G : f([{2,4},{{2,4}}])],
01622     assert(is_graph(G) = true),
01623     assert(setify(vertices(G)) = {1,2}),
01624     assert(setify(edges(G)) = {[1,2]}),
01625     assert(get_vertex_label(1,G) = 2),
01626     assert(get_vertex_label(2,G) = 4)
01627   ),
01628   block([G : f([{1,2,3},{{1,2},{2,3},{3,1}}])],
01629     assert(is_graph(G) = true),
01630     assert(setify(vertices(G)) = {1,2,3}),
01631     assert(setify(edges(G)) = {[1,2],[2,3],[1,3]}),
01632     assert(get_vertex_label(1,G) = 1),
01633     assert(get_vertex_label(2,G) = 2),
01634     assert(get_vertex_label(3,G) = 3)
01635   ),
01636   block([G : f([{1,[1,-1],[1,1]},{{1,[1,-1]},{1,[1,1]}}])],
01637     assert(is_graph(G) = true),
01638     assert(setify(vertices(G)) = {1,2,3}),
01639     assert(setify(edges(G)) = {[1,2],[1,3]}),
01640     assert(get_vertex_label(1,G) = 1),
01641     assert(get_vertex_label(2,G) = [1,-1]),
01642     assert(get_vertex_label(3,G) = [1,1])
01643   ),
01644   true)$
01645 
01646 okltest_mg2og(f) := block(
01647   assert(f(complete_graph(1)) = [[1], []]),
01648   assert(f(complete_graph(2)) = [[2,1], [{1,2}]]),
01649   assert(f(complete_graph(3)) = [[3,2,1], [{2,3},{1,3},{1,2}]]),
01650   assert(f(empty_graph(0)) = [[],[]]),
01651   assert(f(empty_graph(1)) = [[1],[]]),
01652   assert(f(empty_graph(2)) = [[2,1],[]]),
01653   assert(f(og2mg([[1,2,3],[{1,2},{2,3},{1,3}]])) = [[1,2,3],[{1,3},{2,3},{1,2}]]),
01654   assert(f(og2mg([[d,b,c,a],[{b,c},{c,d}]])) = [[1,2,3,4],[{1,3},{2,3}]]),
01655   /* set_random(1),
01656   assert(f(random_regular_graph(5)) = [[1,2,3,4,5], XXX defect with
01657   random_regular_graph */
01658   true)$
01659 
01660 okltest_mg2g(f) := block(
01661   for G in okltest_list_g do
01662     assert(mg2g(g2mg(G)) = G),
01663   true)$
01664 
01665 okltest_dg2mdg(f) := block(
01666   block([G : f([{},{}])],
01667     assert(is_digraph(G) = true),
01668     assert(setify(vertices(G)) = {}),
01669     assert(setify(edges(G)) = {})
01670   ),
01671   block([G : f([{1},{}])],
01672     assert(is_digraph(G) = true),
01673     assert(setify(vertices(G)) = {1}),
01674     assert(setify(edges(G)) = {}),
01675     assert(get_vertex_label(1,G) = 1)
01676   ),
01677   block([G : f([{2},{}])],
01678     assert(is_digraph(G) = true),
01679     assert(setify(vertices(G)) = {1}),
01680     assert(setify(edges(G)) = {}),
01681     assert(get_vertex_label(1,G) = 2)
01682   ),
01683   block([G : f([{1,2},{[1,2]}])],
01684     assert(is_digraph(G) = true),
01685     assert(setify(vertices(G)) = {1,2}),
01686     assert(setify(edges(G)) = {[1,2]}),
01687     assert(get_vertex_label(1,G) = 1),
01688     assert(get_vertex_label(2,G) = 2)
01689   ),
01690   block([G : f([{2,4},{[2,4]}])],
01691     assert(is_digraph(G) = true),
01692     assert(setify(vertices(G)) = {1,2}),
01693     assert(setify(edges(G)) = {[1,2]}),
01694     assert(get_vertex_label(1,G) = 2),
01695     assert(get_vertex_label(2,G) = 4)
01696   ),
01697   block([G : f([{1,2},{[1,2],[2,1]}])],
01698     assert(is_digraph(G) = true),
01699     assert(setify(vertices(G)) = {1,2}),
01700     assert(setify(edges(G)) = {[1,2],[2,1]}),
01701     assert(get_vertex_label(1,G) = 1),
01702     assert(get_vertex_label(2,G) = 2)
01703   ),
01704   block([G : f([{1,2,3},{[1,2],[2,3],[3,1]}])],
01705     assert(is_digraph(G) = true),
01706     assert(setify(vertices(G)) = {1,2,3}),
01707     assert(setify(edges(G)) = {[1,2],[2,3],[3,1]}),
01708     assert(get_vertex_label(1,G) = 1),
01709     assert(get_vertex_label(2,G) = 2),
01710     assert(get_vertex_label(3,G) = 3)
01711   ),
01712   block([G : f([{1,[1,-1],[1,1]},{[1,[1,-1]],[1,[1,1]]}])],
01713     assert(is_digraph(G) = true),
01714     assert(setify(vertices(G)) = {1,2,3}),
01715     assert(setify(edges(G)) = {[1,2],[1,3]}),
01716     assert(get_vertex_label(1,G) = 1),
01717     assert(get_vertex_label(2,G) = [1,-1]),
01718     assert(get_vertex_label(3,G) = [1,1])
01719   ),
01720   block([G : f(var_lit_clause_digraph([{1},{}]))],
01721     assert(is_digraph(G) = true)
01722   ),
01723   true);
01724 
01725 
01726