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()