{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Knuth Miles\n\n`miles_graph()` returns an undirected graph over 128 US cities. The\ncities each have location and population data. The edges are labeled with the\ndistance between the two cities.\n\nThis example is described in Section 1.1 of\n\n Donald E. Knuth, \"The Stanford GraphBase: A Platform for Combinatorial\n Computing\", ACM Press, New York, 1993.\n http://www-cs-faculty.stanford.edu/~knuth/sgb.html\n\nThe data file can be found at:\n\n- https://github.com/networkx/networkx/blob/main/examples/drawing/knuth_miles.txt.gz\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import gzip\nimport re\n\n# Ignore any warnings related to downloading shpfiles with cartopy\nimport warnings\n\nwarnings.simplefilter(\"ignore\")\n\nimport numpy as np\nimport matplotlib.pyplot as plt\nimport networkx as nx\n\n\ndef miles_graph():\n \"\"\"Return the cites example graph in miles_dat.txt\n from the Stanford GraphBase.\n \"\"\"\n # open file miles_dat.txt.gz (or miles_dat.txt)\n\n fh = gzip.open(\"knuth_miles.txt.gz\", \"r\")\n\n G = nx.Graph()\n G.position = {}\n G.population = {}\n\n cities = []\n for line in fh.readlines():\n line = line.decode()\n if line.startswith(\"*\"): # skip comments\n continue\n\n numfind = re.compile(r\"^\\d+\")\n\n if numfind.match(line): # this line is distances\n dist = line.split()\n for d in dist:\n G.add_edge(city, cities[i], weight=int(d))\n i = i + 1\n else: # this line is a city, position, population\n i = 1\n (city, coordpop) = line.split(\"[\")\n cities.insert(0, city)\n (coord, pop) = coordpop.split(\"]\")\n (y, x) = coord.split(\",\")\n\n G.add_node(city)\n # assign position - Convert string to lat/long\n G.position[city] = (-float(x) / 100, float(y) / 100)\n G.population[city] = float(pop) / 1000\n return G\n\n\nG = miles_graph()\n\nprint(\"Loaded miles_dat.txt containing 128 cities.\")\nprint(G)\n\n# make new graph of cites, edge if less than 300 miles between them\nH = nx.Graph()\nfor v in G:\n H.add_node(v)\nfor u, v, d in G.edges(data=True):\n if d[\"weight\"] < 300:\n H.add_edge(u, v)\n\n# draw with matplotlib/pylab\nfig = plt.figure(figsize=(8, 6))\n\n# nodes colored by degree sized by population\nnode_color = [float(H.degree(v)) for v in H]\n\n# Use cartopy to provide a backdrop for the visualization\ntry:\n import cartopy.crs as ccrs\n import cartopy.io.shapereader as shpreader\n\n ax = fig.add_axes([0, 0, 1, 1], projection=ccrs.LambertConformal(), frameon=False)\n ax.set_extent([-125, -66.5, 20, 50], ccrs.Geodetic())\n # Add map of countries & US states as a backdrop\n for shapename in (\"admin_1_states_provinces_lakes_shp\", \"admin_0_countries\"):\n shp = shpreader.natural_earth(\n resolution=\"110m\", category=\"cultural\", name=shapename\n )\n ax.add_geometries(\n shpreader.Reader(shp).geometries(),\n ccrs.PlateCarree(),\n facecolor=\"none\",\n edgecolor=\"k\",\n )\n # NOTE: When using cartopy, use matplotlib directly rather than nx.draw\n # to take advantage of the cartopy transforms\n ax.scatter(\n *np.array(list(G.position.values())).T,\n s=[G.population[v] for v in H],\n c=node_color,\n transform=ccrs.PlateCarree(),\n zorder=100, # Ensure nodes lie on top of edges/state lines\n )\n # Plot edges between the cities\n for edge in H.edges():\n edge_coords = np.array([G.position[v] for v in edge])\n ax.plot(\n edge_coords[:, 0],\n edge_coords[:, 1],\n transform=ccrs.PlateCarree(),\n linewidth=0.75,\n color=\"k\",\n )\n\nexcept ImportError:\n # If cartopy is unavailable, the backdrop for the plot will be blank;\n # though you should still be able to discern the general shape of the US\n # from graph nodes and edges!\n nx.draw(\n H,\n G.position,\n node_size=[G.population[v] for v in H],\n node_color=node_color,\n with_labels=False,\n )\n\nplt.show()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.12.7"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Generated by dwww version 1.16 on Wed Apr 8 10:58:33 CEST 2026.