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, 2011, 2012 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/Graphs/Lisp/Basic.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00024 
00025 
00026 /* ***************************
00027    * Using Maxima facilities *
00028    ***************************
00029 */
00030 
00031 /* Computing the chromatic number of a graph via the Maxima function: */
00032 /* RENAME: chromaticnumber_m_g */
00033 chromatic_number_gr_m(G) := if emptyp(G[2]) then if emptyp(G[1]) then 0 else 1
00034  else chromatic_number(g2mg(G))$
00035 chromaticnumber_m_g(G) := chromatic_number_gr_m(G)$
00036 
00037 
00038 /* ********************
00039    * Greedy colouring *
00040    ********************
00041 */
00042 
00043 /* Apply the greedy colouring algorithm to the ordered graph G,
00044    and obtain [n,C], where n is the number of colours used, and C
00045    is the list of colours for the vertices (in the given order):
00046 */
00047 greedy_colouring_og(G) := block([h : sm2hm({}), C : []],
00048   for v in G[1] do block([N : neighbours_og(v,G), CN, c:1],
00049     CN : disjoin(false, map(lambda([w], ev_hm(h,w)), N)),
00050     while elementp(c,CN) do c:c+1,
00051     C : cons(c,C),
00052     set_hm(h,v,c)
00053   ),
00054   return([if emptyp(C) then 0 else lmax(C),reverse(C)])
00055 )$
00056 
00057 
00058 /* *******************************************
00059    * Searching for interesting planar graphs *
00060    *******************************************
00061 */
00062 
00063 /* Searching for small 3-colourable planar graphs where the colouring is hard
00064    to find.
00065 */
00066 /* Searching for d-regular 3-colourable planar graphs with n vertices;
00067    if unsuccessful, then a 4-tupel [N,count,numpl,num3] is returned, where
00068    N is the total number of graphs envisaged, count the actual number
00069    considered (=N here), numpl the number of planar graphs among them,
00070    and num3 the number of 3-colourable graphs among them; and if successful,
00071    then a 5-tupel is returned, containing additionally also the graph found: */
00072 search_planar3col(n,d,N) := block(
00073  [found : false, g, count : 0, numpl : 0, num3 : 0, ispl, is3],
00074   while not found and count < N do (
00075     g : random_regular_graph(n,d),
00076     count : count+1,
00077     ispl : is_planar(g),
00078     if ispl then numpl : numpl + 1,
00079     is3 : is(chromatic_number(g) = 3),
00080     if is3 then num3 : num3 + 1,
00081     if ispl and is3 then found : true
00082   ),
00083   if found then return([N,count,numpl, num3, mg2og(g)])
00084   else return([N,count,numpl,num3]))$
00085