{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Minimalistic World Coloring\n", "\n", "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](https://en.wikipedia.org/wiki/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](https://networkx.github.io) package that provides us with the five-colored world.\n", "\n", "Note: here we disregard sea borders and only take land borders into account.\n", "\n", "Data was provided by [GeoDataSource](https://www.geodatasource.com), see their [repository](https://github.com/geodatasource/country-borders)." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "execution": { "iopub.execute_input": "2024-04-17T07:39:10.020455Z", "iopub.status.busy": "2024-04-17T07:39:10.020380Z", "iopub.status.idle": "2024-04-17T07:39:10.452004Z", "shell.execute_reply": "2024-04-17T07:39:10.451678Z" } }, "outputs": [], "source": [ "import pandas as pd\n", "import geopandas as gpd\n", "import networkx as nx\n", "\n", "from lets_plot import *" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "execution": { "iopub.execute_input": "2024-04-17T07:39:10.453493Z", "iopub.status.busy": "2024-04-17T07:39:10.453366Z", "iopub.status.idle": "2024-04-17T07:39:10.455642Z", "shell.execute_reply": "2024-04-17T07:39:10.455472Z" } }, "outputs": [ { "data": { "text/html": [ "\n", "
\n", " \n", " " ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "LetsPlot.setup_html()" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "execution": { "iopub.execute_input": "2024-04-17T07:39:10.468484Z", "iopub.status.busy": "2024-04-17T07:39:10.468371Z", "iopub.status.idle": "2024-04-17T07:39:10.470541Z", "shell.execute_reply": "2024-04-17T07:39:10.470361Z" } }, "outputs": [], "source": [ "def get_naturalearth_data(data_type=\"admin_0_countries\", columns=[\"NAME\", \"geometry\"]):\n", " import shapefile\n", " from shapely.geometry import shape\n", "\n", " naturalearth_url = \"https://raw.githubusercontent.com/JetBrains/lets-plot-docs/master/\" + \\\n", " \"data/naturalearth/{0}/data.shp?raw=true\".format(data_type)\n", " sf = shapefile.Reader(naturalearth_url)\n", "\n", " gdf = gpd.GeoDataFrame(\n", " [\n", " dict(zip([field[0] for field in sf.fields[1:]], record))\n", " for record in sf.records()\n", " ],\n", " geometry=[shape(s) for s in sf.shapes()]\n", " )[columns]\n", " gdf.columns = [col.lower() for col in gdf.columns]\n", "\n", " return gdf" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "execution": { "iopub.execute_input": "2024-04-17T07:39:10.471535Z", "iopub.status.busy": "2024-04-17T07:39:10.471442Z", "iopub.status.idle": "2024-04-17T07:39:10.472898Z", "shell.execute_reply": "2024-04-17T07:39:10.472719Z" } }, "outputs": [], "source": [ "def get_color_id(coloring, colors):\n", " return lambda color_name: colors[coloring[color_name]] if color_name in coloring.keys() else colors[-1]" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "execution": { "iopub.execute_input": "2024-04-17T07:39:10.473938Z", "iopub.status.busy": "2024-04-17T07:39:10.473778Z", "iopub.status.idle": "2024-04-17T07:39:11.681088Z", "shell.execute_reply": "2024-04-17T07:39:11.680812Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
nameiso_a3continentpop_estgdp_mdgeometry
0FijiFJIOceania889953.05496MULTIPOLYGON (((180.00000 -16.06713, 180.00000...
1TanzaniaTZAAfrica58005463.063177POLYGON ((33.90371 -0.95000, 34.07262 -1.05982...
2W. SaharaESHAfrica603253.0907POLYGON ((-8.66559 27.65643, -8.66512 27.58948...
3CanadaCANNorth America37589262.01736425MULTIPOLYGON (((-122.84000 49.00000, -122.9742...
4United States of AmericaUSANorth America328239523.021433226MULTIPOLYGON (((-122.84000 49.00000, -120.0000...
\n", "
" ], "text/plain": [ " name iso_a3 continent pop_est gdp_md \\\n", "0 Fiji FJI Oceania 889953.0 5496 \n", "1 Tanzania TZA Africa 58005463.0 63177 \n", "2 W. Sahara ESH Africa 603253.0 907 \n", "3 Canada CAN North America 37589262.0 1736425 \n", "4 United States of America USA North America 328239523.0 21433226 \n", "\n", " geometry \n", "0 MULTIPOLYGON (((180.00000 -16.06713, 180.00000... \n", "1 POLYGON ((33.90371 -0.95000, 34.07262 -1.05982... \n", "2 POLYGON ((-8.66559 27.65643, -8.66512 27.58948... \n", "3 MULTIPOLYGON (((-122.84000 49.00000, -122.9742... \n", "4 MULTIPOLYGON (((-122.84000 49.00000, -120.0000... " ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "world_gdf = get_naturalearth_data(columns=[\"NAME\", \"ISO_A3\", \"CONTINENT\", \"POP_EST\", \"GDP_MD\", \"geometry\"])\n", "world_gdf.head()" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "execution": { "iopub.execute_input": "2024-04-17T07:39:11.682290Z", "iopub.status.busy": "2024-04-17T07:39:11.682216Z", "iopub.status.idle": "2024-04-17T07:39:11.992508Z", "shell.execute_reply": "2024-04-17T07:39:11.992201Z" } }, "outputs": [], "source": [ "borders_df = pd.read_csv(\"https://raw.githubusercontent.com/JetBrains/lets-plot-docs/master/data/country_borders.csv\")\n", "borders_df = borders_df[['country_name', 'country_border_name']]\n", "borders_df = borders_df[~borders_df['country_border_name'].isna()]\n", "extra_countries = set(borders_df['country_name']) - set(world_gdf['name'])\n", "borders_df = borders_df[(~borders_df['country_name'].isin(extra_countries))&(~borders_df['country_border_name'].isin(extra_countries))]\n", "borders_df = borders_df.reset_index(drop=True)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "execution": { "iopub.execute_input": "2024-04-17T07:39:11.993683Z", "iopub.status.busy": "2024-04-17T07:39:11.993612Z", "iopub.status.idle": "2024-04-17T07:39:12.007987Z", "shell.execute_reply": "2024-04-17T07:39:12.007722Z" } }, "outputs": [], "source": [ "edges = [(country_name, neighbour_name) for index, (country_name, neighbour_name) in borders_df.iterrows()]\n", "G = nx.Graph(edges)\n", "coloring = nx.coloring.greedy_color(G)\n", "colors = ['#e41a1c', '#377eb8', '#4daf4a', '#984ea3', '#ffff33']\n", "\n", "world_gdf = world_gdf.assign(color=world_gdf['name'].apply(get_color_id(coloring, colors)))" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "execution": { "iopub.execute_input": "2024-04-17T07:39:12.009086Z", "iopub.status.busy": "2024-04-17T07:39:12.009017Z", "iopub.status.idle": "2024-04-17T07:39:12.062641Z", "shell.execute_reply": "2024-04-17T07:39:12.062434Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ggplot() + \\\n", " geom_map(aes(fill='color'), data=world_gdf, size=.3, color='black', \\\n", " tooltips=layer_tooltips().line('@name')) + \\\n", " scale_fill_identity() + \\\n", " ggtitle('World Coloring') + \\\n", " ggsize(800, 600) + \\\n", " theme_void()" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "execution": { "iopub.execute_input": "2024-04-17T07:39:12.065142Z", "iopub.status.busy": "2024-04-17T07:39:12.064982Z", "iopub.status.idle": "2024-04-17T07:39:12.114416Z", "shell.execute_reply": "2024-04-17T07:39:12.114211Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", " " ], "text/plain": [ "" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ggplot() + \\\n", " geom_map(aes(fill='color'), data=world_gdf, size=.3, color='black', \\\n", " tooltips=layer_tooltips().line('@name')) + \\\n", " scale_fill_identity() + \\\n", " coord_cartesian(xlim=[-10, 40], ylim=[30, 70]) + \\\n", " ggtitle('Europe Coloring') + \\\n", " ggsize(600, 450) + \\\n", " theme_void()" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.13" } }, "nbformat": 4, "nbformat_minor": 4 }