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],