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.
Best Answer
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.