At CARTO we challenge ourselves to use our platform as our users do. For us, this serves several purposes:
Since use cases at CARTO go from very simple visualizations to complex geospatial solutions, one of the challenges I set for myself was to solve the graph coloring problem with CARTO.
Graph coloring is a technique to assign colors to the vertices of a graph such that no two adjacent vertices share the same color.
But what does graph coloring have to do with maps?
Map coloring is an application of graph coloring so each two adjacent polygons (countries, provinces, etc.) are assigned different colors.
Map coloring helps to better understand maps and solve other kind of problems like mobile radio frequency assignment or other scheduling problems.
Having said that, graph coloring is a very interesting topic covered by several theorems and algorithms, like the 4-color theorem which basically states that any map can be colored using 4 colors.
Let’s put ourselves in the boots of a CARTO user that wants to draw the world map in 4 colors. We don’t have much programming skills, but we know a bit of SQL and spatial concepts.
For this case we’ll work with the world_borders
layer that can be imported into any CARTO account from our Data Library.
The graph coloring problem needs two mathematical artifacts to be solved: a model and an algorithm.
So we have to model a PostGIS table into a graph. This may sound like complex stuff but it can be actually solved in less than 10 lines of SQL by creating an adjacency list:
With this query we obtain the world map adjacency list having for each country, the list of adjacent countries and its valence (the number of adjacent countries).
Learning point: Note the use of PostgreSQL Window functions to aggregate and count the adjacent countries in a single column. Window functions are a really handy resource to have in your SQL tool box.
We can generalize this query by wrapping it as a PostgreSQL function so that it can be executed for any of our datasets and store the results in a table:
Learning point: By wrapping a query into a function we are able to re-use it and even provide of a geospatial framework to the users in our CARTO organization.
Note as well the use of the EXECUTE
and format
functions to avoid missusing of the function or SQL injection issues.
Let’s start by implementing the most simpler algorithm for graph coloring, the Welsh-Powell one. This algorithm is as follows:
Let’s see how we can implement the Welsh-Powell algorithm as a PostGIS function.
In this case we have two different sections in our function. First we DECLARE
temporary variables needed to store results and second we have the actual algorithm implementation between a BEGIN
and END
clause.
Since we need to model our dataset as an adjacency list we start by calling our adjacency_list
function:
Then we need to know the number of rows in the dataset and start an iterative algorithm:
Let’s color the first vertex in the list with color 1
Go down the list and color every vertex not connected to the colored vertices above the same color
Finally, repeat on the uncolored vertices with a new color, always working in descending order of valence until all the vertices have been colored.
Now we have two functions that can be stored in our CARTO account by running them into the SQL console in our BUILDER dashboard, but how do we run this map coloring algorithm?
Best option here is using our batch SQL API, this allows us to run any SQL that could take several seconds or minutes safely. In this case we just have to do a SELECT to our greedy
function passing the table_name
and our user_name
. We can do this directly from a terminal:
curl -X POST -H "Content-Type: application/json" -d "{
\"query\": \"SELECT greedy('world_borders', 'aromeu')\"
}" https://aromeu.carto.com/api/v2/sql/job?api_key={api_key}
The resulting table world_borders_adjacency_list
contains a color assigned for each cartodb_id
, now we just can join this table with the original world_borders
table and apply a category thematic to visualize the result (plus a bit of CartoCSS magic):
In this case we have colored every adjacent country with a different color, in a total of 5 colors, but can we do it better?
Note: for the sake of simplicity in the examples above and below, we are not working with multipolygons; so that, countries composed of several polygons are assigned different colors to each polygon.
In 1879, Alfred B. Kempe tried to prove the 4-color theorem and while years later it was demonstrated that it didn’t solved the problem for all cases, the algorithm he designed still can be used to color the world map using just 4 colors.
The Kempe’s graph color algorithm is as follows:
This is a little bit more complex algorithm that still can be solved using a pure PostgreSQL function:
Again we can create the function from the SQL console, execute it for the world_borders
dataset using the batch SQL API and then map it with BUILDER. Let’s see the result:
In this case we have colored the world map in 4 colors, challenge accomplished!
Learning point: We have not only learned how to solve the graph coloring problem with CARTO but we have ended up creating the basis for a geospatial framework by creating PostgreSQL functions into our CARTO account.
So, let’s finish by applying these map coloring functions that now are part of our own geospatial framework inside CARTO to some other of our datasets.
The 4 color theorem applied to the US states dataset
A greedy approach to map color the US counties dataset
Another greedy example with the Spain municipalities
Note that the map coloring algorithm implementations presented in this blog post are totally naive and don’t pretend to be exact or to be used under a production environment, they just pretend to showcase a user workflow to solve a geospatial problem with CARTO.
For reference, all these functions are available here. Feel free to add any comment or improve them.
If you like the kind of stuff we are involved in you may want to join us :)
The recent release of PostGIS 3.0 brings an updated spatial reference system table that includes over 8000 projections out-of-the-box. We’re happy to report that the Equal ...
Cartography & VisualizationLike much of the rest of the world, the team here at CARTO includes dozens of passionate fans of HBO’s megahit, Game of Thrones, which comes to its much anticipated conclus...
Cartography & VisualizationYou have probably heard about Microsoft’s work this past year, in training a neural network to polygonize satellite imagery into building footprints. This work resulted in ...
Cartography & VisualizationPlease fill out the below form and we'll be in touch real soon.