Minimalistic World Coloring

We try to use the minimal number of colors for world coloring so that any two neighboring countries are colored differently. Due to the four color theorem, four colors should be enough, but since there are enclaves and exclaves, the theorem cannot be applied. So here we use the greedy coloring algorithm from the networkx package that provides us with the five-colored world.

Note: here we disregard sea borders and only take land borders into account.

Data was provided by GeoDataSource, see their repository.

import pandas as pd
import geopandas as gpd
import networkx as nx

from lets_plot import *

LetsPlot.setup_html()

def get_naturalearth_data(data_type="admin_0_countries", columns=["NAME", "geometry"]):
    import shapefile
    from shapely.geometry import shape

    naturalearth_url = "https://raw.githubusercontent.com/JetBrains/lets-plot-docs/master/" + \
                       "data/naturalearth/{0}/data.shp?raw=true".format(data_type)
    sf = shapefile.Reader(naturalearth_url)

    gdf = gpd.GeoDataFrame(
        [
            dict(zip([field[0] for field in sf.fields[1:]], record))
            for record in sf.records()
        ],
        geometry=[shape(s) for s in sf.shapes()]
    )[columns]
    gdf.columns = [col.lower() for col in gdf.columns]

    return gdf

def get_color_id(coloring, colors):
    return lambda color_name: colors[coloring[color_name]] if color_name in coloring.keys() else colors[-1]

world_gdf = get_naturalearth_data(columns=["NAME", "ISO_A3", "CONTINENT", "POP_EST", "GDP_MD", "geometry"])
world_gdf.head()

	name	iso_a3	continent	pop_est	gdp_md	geometry
0	Fiji	FJI	Oceania	889953.0	5496	MULTIPOLYGON (((180.00000 -16.06713, 180.00000...
1	Tanzania	TZA	Africa	58005463.0	63177	POLYGON ((33.90371 -0.95000, 34.07262 -1.05982...
2	W. Sahara	ESH	Africa	603253.0	907	POLYGON ((-8.66559 27.65643, -8.66512 27.58948...
3	Canada	CAN	North America	37589262.0	1736425	MULTIPOLYGON (((-122.84000 49.00000, -122.9742...
4	United States of America	USA	North America	328239523.0	21433226	MULTIPOLYGON (((-122.84000 49.00000, -120.0000...

borders_df = pd.read_csv("https://raw.githubusercontent.com/JetBrains/lets-plot-docs/master/data/country_borders.csv")
borders_df = borders_df[['country_name', 'country_border_name']]
borders_df = borders_df[~borders_df['country_border_name'].isna()]
extra_countries = set(borders_df['country_name']) - set(world_gdf['name'])
borders_df = borders_df[(~borders_df['country_name'].isin(extra_countries))&(~borders_df['country_border_name'].isin(extra_countries))]
borders_df = borders_df.reset_index(drop=True)

edges = [(country_name, neighbour_name) for index, (country_name, neighbour_name) in borders_df.iterrows()]
G = nx.Graph(edges)
coloring = nx.coloring.greedy_color(G)
colors = ['#e41a1c', '#377eb8', '#4daf4a', '#984ea3', '#ffff33']

world_gdf = world_gdf.assign(color=world_gdf['name'].apply(get_color_id(coloring, colors)))

ggplot() + \
    geom_map(aes(fill='color'), data=world_gdf, size=.3, color='black', \
             tooltips=layer_tooltips().line('@name')) + \
    scale_fill_identity() + \
    ggtitle('World Coloring') + \
    ggsize(800, 600) + \
    theme_void()

ggplot() + \
    geom_map(aes(fill='color'), data=world_gdf, size=.3, color='black', \
             tooltips=layer_tooltips().line('@name')) + \
    scale_fill_identity() + \
    coord_cartesian(xlim=[-10, 40], ylim=[30, 70]) + \
    ggtitle('Europe Coloring') + \
    ggsize(600, 450) + \
    theme_void()