{ "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-26T12:21:19.831166Z", "iopub.status.busy": "2024-04-26T12:21:19.819894Z", "iopub.status.idle": "2024-04-26T12:21:21.179897Z", "shell.execute_reply": "2024-04-26T12:21:21.179897Z" } }, "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-26T12:21:21.179897Z", "iopub.status.busy": "2024-04-26T12:21:21.179897Z", "iopub.status.idle": "2024-04-26T12:21:21.195760Z", "shell.execute_reply": "2024-04-26T12:21:21.195760Z" } }, "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-26T12:21:21.211824Z", "iopub.status.busy": "2024-04-26T12:21:21.211824Z", "iopub.status.idle": "2024-04-26T12:21:21.243125Z", "shell.execute_reply": "2024-04-26T12:21:21.243125Z" } }, "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-26T12:21:21.243125Z", "iopub.status.busy": "2024-04-26T12:21:21.243125Z", "iopub.status.idle": "2024-04-26T12:21:21.259131Z", "shell.execute_reply": "2024-04-26T12:21:21.259131Z" } }, "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-26T12:21:21.259131Z", "iopub.status.busy": "2024-04-26T12:21:21.259131Z", "iopub.status.idle": "2024-04-26T12:21:22.303586Z", "shell.execute_reply": "2024-04-26T12:21:22.302644Z" } }, "outputs": [ { "data": { "text/html": [ "\n", " | name | \n", "iso_a3 | \n", "continent | \n", "pop_est | \n", "gdp_md | \n", "geometry | \n", "
---|---|---|---|---|---|---|
0 | \n", "Fiji | \n", "FJI | \n", "Oceania | \n", "889953.0 | \n", "5496 | \n", "MULTIPOLYGON (((180.00000 -16.06713, 180.00000... | \n", "
1 | \n", "Tanzania | \n", "TZA | \n", "Africa | \n", "58005463.0 | \n", "63177 | \n", "POLYGON ((33.90371 -0.95000, 34.07262 -1.05982... | \n", "
2 | \n", "W. Sahara | \n", "ESH | \n", "Africa | \n", "603253.0 | \n", "907 | \n", "POLYGON ((-8.66559 27.65643, -8.66512 27.58948... | \n", "
3 | \n", "Canada | \n", "CAN | \n", "North America | \n", "37589262.0 | \n", "1736425 | \n", "MULTIPOLYGON (((-122.84000 49.00000, -122.9742... | \n", "
4 | \n", "United States of America | \n", "USA | \n", "North America | \n", "328239523.0 | \n", "21433226 | \n", "MULTIPOLYGON (((-122.84000 49.00000, -120.0000... | \n", "