OKlibrary  0.2.1.6
Colouring.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 26.2.2008 (Swansea) */
00002 /* Copyright 2008, 2010 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/Graphs/Lisp/Generators.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00026 
00027 
00028 kill(f)$
00029 
00030 /* ***************************
00031    * Using Maxima facilities *
00032    ***************************
00033 */
00034 
00035 okltest_chromatic_number_gr(f) := block(
00036   assert(f([{},{}]) = 0),
00037   assert(f([{1},{}]) = 1),
00038   assert(f([{1,2},{}]) = 1),
00039   assert(f([{1,2},{{1,2}}]) = 2),
00040   for n : 0 thru 3 do
00041     assert(f(complete_g(setn(n))) = n),
00042   for n : 3 thru 6 do
00043    for m : 2 thru (n+1)/2 do
00044     assert(f(kneser_g(n,m)) = n - 2 * m + 2),
00045   true);
00046 
00047 
00048 /* ********************
00049    * Greedy colouring *
00050    ********************
00051 */
00052 
00053 okltest_greedy_colouring_og(f) := (
00054   assert(f([[],[]]) = [0,[]]),
00055   assert(f([[1],[]]) = [1,[1]]),
00056   assert(f([[1,2],[]]) = [1,[1,1]]),
00057   assert(f([[1,2],[{1,2}]]) = [2,[1,2]]),
00058   assert(f([[1,2,3],[]]) = [1,[1,1,1]]),
00059   assert(f([[1,2,3],[{1,2}]]) = [2,[1,2,1]]),
00060   assert(f([[1,2,3],[{1,2},{2,3}]]) = [2,[1,2,1]]),
00061   assert(f([[1,2,3],[{1,2},{2,3},{1,3}]]) = [3,[1,2,3]]),
00062   assert(f([[1,2,3,4,5,6],[{1,3},{2,4},{2,5},{3,6},{2,6},{4,5}]]) = [3, [1,1,2,2,3,3]]),
00063   for n : 0 thru 6 do block([G : g2og(complete_g(setn(n)))],
00064     assert(f(G) = [n, create_list(i,i,1,n)])),
00065   true);
00066