13
$\begingroup$

I'm now using scipy.spatial.Voronoi to generate a Voronoi graph, as shown here: voronoi graph. I'd like to apply the four color theorem on it, so that no adjcent regions share the same color. I converted it into a NetworkX graph, and used the method posted in this answer Do you know a faster algorithm to color planar graphs? to color the graph.

from sage.graphs.graph_coloring import vertex_coloring
coloring = vertex_coloring(G, 4, solver = "Gurobi", verbose = 10)

My operation system is Win10 with SageMath 9.3 installed. However, it only worked when the coloring number is equal or greater than 5, and the result is good: 5 color result. Changing the number to 4 caused the following error:

Traceback (most recent call last):
  File "five_color_sage.py", line 33, in <module>
    coloring = vertex_coloring(G, 4, solver = "Gurobi", verbose = 0)
  File "sage/graphs/graph_coloring.pyx", line 570, in sage.graphs.graph_coloring.vertex_coloring (build/cythonized/sage/graphs/graph_coloring.cpp:9000)
  File "sage/graphs/graph_coloring.pyx", line 587, in sage.graphs.graph_coloring.vertex_coloring (build/cythonized/sage/graphs/graph_coloring.cpp:9277)
  File "sage/numerical/mip.pyx", line 441, in sage.numerical.mip.MixedIntegerLinearProgram.__init__ (build/cythonized/sage/numerical/mip.c:3989)
  File "sage/numerical/backends/generic_backend.pyx", line 1640, in sage.numerical.backends.generic_backend.get_solver (build/cythonized/sage/numerical/backends/generic_backend.c:20569)
  File "sage/numerical/backends/generic_backend.pyx", line 1783, in sage.numerical.backends.generic_backend.get_solver (build/cythonized/sage/numerical/backends/generic_backend.c:20254)
ModuleNotFoundError: No module named 'sage_numerical_backends_gurobi'

I've tried to install sage_numerical_backends_gurobi, but result in the following error:

Building wheel for sage-numerical-backends-gurobi (setup.py) ... error
ERROR: Command errored out with exit status 1:
   command: /opt/sagemath-9.3/local/bin/python3 -u -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-install-b3w83q4_/sage-numerical-backends-gurobi_297d070e1a474477b24a1f3236b14fa2/setup.py'"'"'; __file__='"'"'/tmp/pip-install-b3w83q4_/sage-numerical-backends-gurobi_297d070e1a474477b24a1f3236b14fa2/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' bdist_wheel -d /tmp/pip-wheel-vggmxrhi
       cwd: /tmp/pip-install-b3w83q4_/sage-numerical-backends-gurobi_297d070e1a474477b24a1f3236b14fa2/
  Complete output (23 lines):
  /bin/sh: line 0: .: gurobi.sh: file not found
  GUROBI_HOME is not set, or it does not point to a directory with a Gurobi installation.  Trying to link against -lgurobi
  Checking whether HAVE_SAGE_CPYTHON_STRING...
  Checking whether HAVE_ADD_COL_UNTYPED_ARGS...
  Using compile_time_env: {'HAVE_SAGE_CPYTHON_STRING': True, 'HAVE_ADD_COL_UNTYPED_ARGS': True}
  running bdist_wheel
  running build
  running build_py
  creating build
  creating build/lib.cygwin-3.2.0-x86_64-3.7
  creating build/lib.cygwin-3.2.0-x86_64-3.7/sage_numerical_backends_gurobi
  copying sage_numerical_backends_gurobi/__init__.py -> build/lib.cygwin-3.2.0-x86_64-3.7/sage_numerical_backends_gurobi
  copying sage_numerical_backends_gurobi/gurobi_backend.pxd -> build/lib.cygwin-3.2.0-x86_64-3.7/sage_numerical_backends_gurobi
  running build_ext
  building 'sage_numerical_backends_gurobi.gurobi_backend' extension
  creating build/temp.cygwin-3.2.0-x86_64-3.7
  creating build/temp.cygwin-3.2.0-x86_64-3.7/sage_numerical_backends_gurobi
  gcc -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -ggdb -O2 -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -fstack-protector-strong --param=ssp-buffer-size=4 -fdebug-prefix-map=/pub/devel/python/python37/python37-3.7.10-2.x86_64/build=/usr/src/debug/python37-3.7.10-2 -fdebug-prefix-map=/pub/devel/python/python37/python37-3.7.10-2.x86_64/src/Python-3.7.10=/usr/src/debug/python37-3.7.10-2 -ggdb -O2 -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -fstack-protector-strong --param=ssp-buffer-size=4 -fdebug-prefix-map=/pub/devel/python/python37/python37-3.7.10-2.x86_64/build=/usr/src/debug/python37-3.7.10-2 -fdebug-prefix-map=/pub/devel/python/python37/python37-3.7.10-2.x86_64/src/Python-3.7.10=/usr/src/debug/python37-3.7.10-2 -I/opt/sagemath-9.3/local/lib/python3.7/site-packages/sage/cpython -I/opt/sagemath-9.3/local/lib/python3.7/site-packages/cysignals -I/opt/sagemath-9.3/local/lib/python3.7/site-packages -I/usr/include/python3.7m -I/opt/sagemath-9.3/local/lib/python3.7/site-packages/numpy/core/include -I/opt/sagemath-9.3/local/include -I/usr/include/python3.7m -c sage_numerical_backends_gurobi/gurobi_backend.c -o build/temp.cygwin-3.2.0-x86_64-3.7/sage_numerical_backends_gurobi/gurobi_backend.o
  sage_numerical_backends_gurobi/gurobi_backend.c:639:10: fatal error: gurobi_c.h: No such file or directory
    639 | #include "gurobi_c.h"
        |          ^~~~~~~~~~~~
  compilation terminated.
  error: command 'gcc' failed with exit status 1
  ----------------------------------------
  ERROR: Failed building wheel for sage-numerical-backends-gurobi
 Running setup.py clean for sage-numerical-backends-gurobi
Failed to build sage-numerical-backends-gurobi
Installing collected packages: sage-numerical-backends-gurobi
    Running setup.py install for sage-numerical-backends-gurobi ... error
    ERROR: Command errored out with exit status 1:
     command: /opt/sagemath-9.3/local/bin/python3 -u -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-install-b3w83q4_/sage-numerical-backends-gurobi_297d070e1a474477b24a1f3236b14fa2/setup.py'"'"'; __file__='"'"'/tmp/pip-install-b3w83q4_/sage-numerical-backends-gurobi_297d070e1a474477b24a1f3236b14fa2/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' install --record /tmp/pip-record-ibpz889r/install-record.txt --single-version-externally-managed --compile --install-headers /opt/sagemath-9.3/local/include/site/python3.7/sage-numerical-backends-gurobi
         cwd: /tmp/pip-install-b3w83q4_/sage-numerical-backends-gurobi_297d070e1a474477b24a1f3236b14fa2/
    Complete output (23 lines):
    /bin/sh: line 0: .: gurobi.sh: file not found
    GUROBI_HOME is not set, or it does not point to a directory with a Gurobi installation.  Trying to link against -lgurobi
    Checking whether HAVE_SAGE_CPYTHON_STRING...
    Checking whether HAVE_ADD_COL_UNTYPED_ARGS...
    Using compile_time_env: {'HAVE_SAGE_CPYTHON_STRING': True, 'HAVE_ADD_COL_UNTYPED_ARGS': True}
    running install
    running build
    running build_py
    creating build
    creating build/lib.cygwin-3.2.0-x86_64-3.7
    creating build/lib.cygwin-3.2.0-x86_64-3.7/sage_numerical_backends_gurobi
    copying sage_numerical_backends_gurobi/__init__.py -> build/lib.cygwin-3.2.0-x86_64-3.7/sage_numerical_backends_gurobi
    copying sage_numerical_backends_gurobi/gurobi_backend.pxd -> build/lib.cygwin-3.2.0-x86_64-3.7/sage_numerical_backends_gurobi
    running build_ext
    building 'sage_numerical_backends_gurobi.gurobi_backend' extension
    creating build/temp.cygwin-3.2.0-x86_64-3.7
    creating build/temp.cygwin-3.2.0-x86_64-3.7/sage_numerical_backends_gurobi
    gcc -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -ggdb -O2 -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -fstack-protector-strong --param=ssp-buffer-size=4 -fdebug-prefix-map=/pub/devel/python/python37/python37-3.7.10-2.x86_64/build=/usr/src/debug/python37-3.7.10-2 -fdebug-prefix-map=/pub/devel/python/python37/python37-3.7.10-2.x86_64/src/Python-3.7.10=/usr/src/debug/python37-3.7.10-2 -ggdb -O2 -pipe -Wall -Werror=format-security -Wp,-D_FORTIFY_SOURCE=2 -fstack-protector-strong --param=ssp-buffer-size=4 -fdebug-prefix-map=/pub/devel/python/python37/python37-3.7.10-2.x86_64/build=/usr/src/debug/python37-3.7.10-2 -fdebug-prefix-map=/pub/devel/python/python37/python37-3.7.10-2.x86_64/src/Python-3.7.10=/usr/src/debug/python37-3.7.10-2 -I/opt/sagemath-9.3/local/lib/python3.7/site-packages/sage/cpython -I/opt/sagemath-9.3/local/lib/python3.7/site-packages/cysignals -I/opt/sagemath-9.3/local/lib/python3.7/site-packages -I/usr/include/python3.7m -I/opt/sagemath-9.3/local/lib/python3.7/site-packages/numpy/core/include -I/opt/sagemath-9.3/local/include -I/usr/include/python3.7m -c sage_numerical_backends_gurobi/gurobi_backend.c -o build/temp.cygwin-3.2.0-x86_64-3.7/sage_numerical_backends_gurobi/gurobi_backend.o
    sage_numerical_backends_gurobi/gurobi_backend.c:639:10: fatal error: gurobi_c.h: No such file or directory
      639 | #include "gurobi_c.h"
          |          ^~~~~~~~~~~~
    compilation terminated.
    error: command 'gcc' failed with exit status 1
    ----------------------------------------
ERROR: Command errored out with exit status 1: /opt/sagemath-9.3/local/bin/python3 -u -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-install-b3w83q4_/sage-numerical-backends-gurobi_297d070e1a474477b24a1f3236b14fa2/setup.py'"'"'; __file__='"'"'/tmp/pip-install-b3w83q4_/sage-numerical-backends-gurobi_297d070e1a474477b24a1f3236b14fa2/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' install --record /tmp/pip-record-ibpz889r/install-record.txt --single-version-externally-managed --compile --install-headers /opt/sagemath-9.3/local/include/site/python3.7/sage-numerical-backends-gurobi Check the logs for full command output.

Is there any solution to the problem? Or any other method of four color theorem implemented in Python? Grateful for your help and suggestions.

Improve this question
$\endgroup$
9
  • 5
    $\begingroup$ Nice question. I'll guess that there is no (known) "simple and fast" algorithm to find a four-colouring of a given planar graph. This is motivated by the observation that any such algorithm would give a new, and computer-free, proof of the four-colour theorem! (Ok, ok, this depends on the nature of the correctness proof of the algorithm. But that is what the phrase "simple and fast" was supposed to ensure.) $\endgroup$
    – Sam Nead
    Commented Apr 7, 2022 at 9:56
  • 3
    $\begingroup$ The sage-numerical-backends-gurobi package says in its documentation that you first have to obtain and install the proprietary Gurobi software, and set the GUROBI_HOME environment variable. The error message seems to say that this has not been done. $\endgroup$
    – Nate Eldredge
    Commented Apr 7, 2022 at 14:27
  • 1
    $\begingroup$ Have you tried using sage.graphs.graph_coloring.all_graph_colorings and taking just the first colouring from the iterator returned? $\endgroup$
    – Peter Taylor
    Commented Apr 7, 2022 at 15:56
  • 2
    $\begingroup$ @SamNead There may be an algorithm that is simple and fast most of the time but takes very long on some rare graphs. Make a reasonable guess, if it works it is fast and simple, if it doesn't try again. $\endgroup$
    – quarague
    Commented Apr 8, 2022 at 9:35
  • 1
    $\begingroup$ @SamNead: it's possible to have a simple and efficient algorithm whose proof of correctness is long and technical. $\endgroup$
    – Ryan Budney
    Commented Oct 12 at 18:26

3 Answers 3

Reset to default
13
$\begingroup$

If you have have some specific, moderately large graphs that you want to color with four colors, you could try using a SAT solver. For each vertex $v$ and each integer $i\in \{1,2,3,4\}$, let $x_{v,i}$ denote a binary variable that is 1 if $v$ is assigned the color $i$ and 0 otherwise. Then for every vertex $v$, introduce the clauses $$x_{v,1} \vee x_{v,2} \vee x_{v,3} \vee x_{v,4}$$ to ensure that every vertex gets some color, and $$(\neg x_{v,i}) \vee (\neg x_{v,j}) \qquad \forall i \ne j$$ to ensure that no vertex gets assigned more than one color. The proper coloring constraint means that for every edge $(u,v)$ and every color $i$ you need a constraint $$(\neg x_{u,i}) \vee (\neg x_{v,i})$$ This might seem like a lot of variables and clauses, but I would expect that modern SAT solvers would have no trouble with graphs with 3000 vertices and 10000 edges. I usually use SAT solvers written in C, but I'm sure there are Python SAT solvers out there.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ There's a bunch of Python SAT solver packages, they all call SAT solvers written in other languages though. I would personally recommend z3. $\endgroup$
    – orlp
    Commented Apr 7, 2022 at 15:18
  • 4
    $\begingroup$ The clauses "to ensure that no vertex gets assigned more than one color" aren't really needed. If the other clauses are satisfied but some vertices have several colors, just give each such vertex any one of its assigned colors. (I have no idea whether this can actually simplify a SAT-solver's work, but it simplifies my view of the situation.) $\endgroup$
    – Andreas Blass
    Commented Apr 7, 2022 at 16:03
  • 3
    $\begingroup$ @AndreasBlass Adding unnecessary but true clauses to a problem can both speed up or slow down a SAT solver's solution speed and I'd say it's hard to know which without trying it out for your particular problem. $\endgroup$
    – orlp
    Commented Apr 7, 2022 at 19:25
  • 3
    $\begingroup$ Before running the SAT solver, make sure you have iteratively removed all vertices of degree at most 4 (these can be colored greedily and efficiently at a later stage, using Kempe chains) until reaching a graph with minimum degree 5. On certain instances, this can dramatically reduce the size of the input. $\endgroup$
    – Louis Esperet
    Commented Apr 8, 2022 at 7:01
  • 4
    $\begingroup$ I have a different suggestion. Try running the SAT solver directly. This requires less work on your part and may solve the problem in a few seconds of running time. Only if this naive approach does not work would I try some preprocessing. $\endgroup$
    – Timothy Chow
    Commented Apr 8, 2022 at 13:28
11
$\begingroup$

Robertson, Sanders, Seymour and Thomas, who produced a more streamlined proof of the 4-colour theorem, also addressed the algorithmic question in the paper

https://dl.acm.org/doi/pdf/10.1145/237814.238005

EDIT 9 April - Additional Remarks

It is interesting to see the number of different ways in which this question has been answered, which seem to result from different interpretations of what the phrase "implementation of four-colour theorem" (4CT) actually means.

If the OP just wants his/her graphs coloured, then any graph colouring algorithm can be used. I use a small suite of programs, some deterministic and some heuristic, from the gCol package written by Rhyd Lewis, available at http://rhydlewis.eu/gcol/. This makes no particular use of the 4CT

If the OP wants to make what I would call incidental use of the 4CT, namely just using the fact that the graphs in question must have a 4-colouring, then most graph colouring algorithms can still be used, or a bespoke instance of another heavily studied NP-complete problem (e.g SAT) can be created. Again though, this is not really using the 4CT in any significant way.

But perhaps the OP wants to make fundamental use of the 4CT, in that the algorithm should actually mirror in code the steps taken in the proof of the 4CT and so the code finds the 4-colouring in the exact same way as the proof finds the 4-colouring.

In the comments, Noah Snyder suggests using Steinberg's variation on the proof of the 4CT which (to paraphrase his 37-page paper in one sentence) only uses "simple" unavoidable configurations to recursively reduce the size of the graph to be coloured. It would be very interesting to see if an algorithm based on this could ever be competitive with a plain graph colouring algorithm.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Do you know if anyone else has implemented their quadratic algorithm? The paper mentions a C implementation hosted on a defunct ftp server. The webpage of the late Robin Thomas includes a link to a copy of the content on that server, but that link is also currently inaccessible. Thomas also wrote a guide to the material on the ftp server, but as far as I can tell (maybe I am overlooking something) it does not include the 4-coloring program itself. $\endgroup$
    – Noam Zeilberger
    Commented Apr 7, 2022 at 12:50
  • 1
    $\begingroup$ It appears that a copy of the contents of that FTP server has been preserved here. $\endgroup$
    – Timothy Chow
    Commented Apr 7, 2022 at 14:31
  • $\begingroup$ @NoamZeilberger, when you say "the paper mentions a C implementation" are you referring to "The C program that the authors used, as well as the configurations in appropriate form for input and a paper explaining the details of the program, is available by anonymous ftp"? I read that as referring to reduce.c from the page you link as Thomas' guide, not to an implementation of the quadratic four-colouring algorithm itself. $\endgroup$
    – Peter Taylor
    Commented Apr 7, 2022 at 15:03
  • $\begingroup$ Hi @PeterTaylor, yes you are probably right, thanks! So a question is whether anybody has implemented their quadratic 4-coloring algorithm in any programming language. $\endgroup$
    – Noam Zeilberger
    Commented Apr 7, 2022 at 15:27
  • 1
    $\begingroup$ If one were to reimplement this, I’ll give my usual plug for the simpler version of the proof given by Steinberger. $\endgroup$
    – Noah Snyder
    Commented Apr 8, 2022 at 12:56
6
$\begingroup$

Here is a greedy algorithm by Febi Mudiyantoto solve the four-color problem in Python.
And here is another Python algorithm that also uses Sage.

If you wish to rely on a program with a more formal (refereed) publication, try Implementation of the greedy algorithm on graph coloring.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your answer. I've already tried the first two methods before asking the question, and neither of them worked. Maybe they are suitable for small size graphs, but mine consists of over 3k vertices and 10k edges, with the maximum node degree 11. Anyway, I'll have a try on the method discussed in the paper. Any other idea of solving the four color theorem? Best if implemented in Python. $\endgroup$
    – ReZhacai
    Commented Apr 7, 2022 at 7:29
  • $\begingroup$ Hi @ReZhacai. If you need help with this github.com/stefanutti/maps-coloring-python I can help. Fastest way to have the four coloring of the graph is to prepare a file with a planar representation of the graph (I can give info about it). This is because if you start from any other representation (.edgelist or .dot) when you load the file it has to verify the graph is planar using the sage function, which is slow. Or if you can send me the graph in a standard format I can return it to you colored. $\endgroup$
    – Mario Stefanutti
    Commented Sep 4, 2022 at 9:07
  • $\begingroup$ I forgot about one thing. The graph has to be 3-regular for my algorithm to work. Voronoi are not :-(. For the study of the four-color theorem, this is a standard limitation $\endgroup$
    – Mario Stefanutti
    Commented Sep 4, 2022 at 9:23
  • $\begingroup$ Here is an example of the steps to take to use the 4ct algorithm on Voronoi diagrams. four-color-theorem.org/2022/09/04/color-voronoi-graphs $\endgroup$
    – Mario Stefanutti
    Commented Sep 4, 2022 at 15:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .