Generating Various Types of Graphs by Proximity¶
This notebook illustrates how to generate and visualize different spatial graph types based on proximity metrics (KNN, Delaunay, Gilbert, Waxman) using City2Graph, OSMnx, and NetworkX.
Overview¶
This notebook covers:
- Setting up the environment and importing libraries
- Retrieving points of interest around a location
- Defining helper functions for node extraction and plotting
- Generating and visualizing KNN, Delaunay, Gilbert, and Waxman graphs interactively
1. Setup and Environment¶
In [1]:
Copied!
import warnings
import geopandas as gpd
import contextily as ctx
import matplotlib.pyplot as plt
import networkx as nx
import osmnx as ox
from IPython.display import HTML
from matplotlib import animation
import city2graph as c2g
warnings.filterwarnings("ignore")
import warnings import geopandas as gpd import contextily as ctx import matplotlib.pyplot as plt import networkx as nx import osmnx as ox from IPython.display import HTML from matplotlib import animation import city2graph as c2g warnings.filterwarnings("ignore")
2. Retrieve Points of Interest¶
Fetch restaurant POIs around Shibuya, Tokyo using OSMnx and filter to nodes only. Also, streets network is obtained for calculating network distances.
In [2]:
Copied!
poi_tags = {
"amenity": ["restaurant"]
}
#poi_gdf = ox.features_from_place("Shibuya, Tokyo, Japan", poi_tags)
poi_gdf = ox.features_from_point(
(35.658514, 139.70133), # Tokyo Tower coordinates
tags=poi_tags,
dist=1000, # Search radius in meters
)
# Filter to include only nodes, not ways and relations
poi_gdf = poi_gdf[poi_gdf.index.get_level_values("element") == "node"]
# Reproject to a projected CRS for accurate centroids
poi_gdf = poi_gdf.to_crs(epsg=6677)
poi_tags = { "amenity": ["restaurant"] } #poi_gdf = ox.features_from_place("Shibuya, Tokyo, Japan", poi_tags) poi_gdf = ox.features_from_point( (35.658514, 139.70133), # Tokyo Tower coordinates tags=poi_tags, dist=1000, # Search radius in meters ) # Filter to include only nodes, not ways and relations poi_gdf = poi_gdf[poi_gdf.index.get_level_values("element") == "node"] # Reproject to a projected CRS for accurate centroids poi_gdf = poi_gdf.to_crs(epsg=6677)
In [3]:
Copied!
segments_G = ox.graph_from_point(
(35.658514, 139.70133), # Tokyo Tower coordinates
dist=1000, # Search radius in meters
)
segments_gdf = c2g.nx_to_gdf(segments_G, nodes=False, edges=True)
segments_G = ox.graph_from_point( (35.658514, 139.70133), # Tokyo Tower coordinates dist=1000, # Search radius in meters ) segments_gdf = c2g.nx_to_gdf(segments_G, nodes=False, edges=True)
In [4]:
Copied!
import matplotlib.colors as mcolors
def get_degree_colors(graph, cmap_name='plasma'):
"""Generate colors based on node degree."""
if not graph:
return []
degree_dict = dict(graph.degree())
values = list(degree_dict.values())
if not values:
return []
norm = mcolors.Normalize(vmin=min(values), vmax=max(values))
cmap = plt.get_cmap(cmap_name)
# Match order of nodes in graph
return [mcolors.to_hex(cmap(norm(degree_dict[n]))) for n in graph.nodes()]
import matplotlib.colors as mcolors def get_degree_colors(graph, cmap_name='plasma'): """Generate colors based on node degree.""" if not graph: return [] degree_dict = dict(graph.degree()) values = list(degree_dict.values()) if not values: return [] norm = mcolors.Normalize(vmin=min(values), vmax=max(values)) cmap = plt.get_cmap(cmap_name) # Match order of nodes in graph return [mcolors.to_hex(cmap(norm(degree_dict[n]))) for n in graph.nodes()]
3. K-Nearest Neighbors (KNN) Graph¶
Create an interactive slider to plot KNN graphs for varying $k$ values. You can specify the distance metric from "manhattan", "euclidean", and "network". If you use network distance, you need to set the GeoDataFrame of network. You can save the output as GeoDataFrame or nx.Graph.
In [5]:
Copied!
knn_l1_nodes, knn_l1_edges = c2g.knn_graph(
poi_gdf,
distance_metric="manhattan",
network_gdf=segments_gdf.to_crs(epsg=6677)
)
knn_l2_nodes, knn_l2_edges = c2g.knn_graph(
poi_gdf,
distance_metric="euclidean",
network_gdf=segments_gdf.to_crs(epsg=6677)
)
knn_net_nodes, knn_net_edges = c2g.knn_graph(
poi_gdf,
k=10,
distance_metric="network",
network_gdf=segments_gdf.to_crs(epsg=6677)
)
knn_l1_nodes, knn_l1_edges = c2g.knn_graph( poi_gdf, distance_metric="manhattan", network_gdf=segments_gdf.to_crs(epsg=6677) ) knn_l2_nodes, knn_l2_edges = c2g.knn_graph( poi_gdf, distance_metric="euclidean", network_gdf=segments_gdf.to_crs(epsg=6677) ) knn_net_nodes, knn_net_edges = c2g.knn_graph( poi_gdf, k=10, distance_metric="network", network_gdf=segments_gdf.to_crs(epsg=6677) )
In [6]:
Copied!
fig, axes = plt.subplots(1, 3, figsize=(18, 6))
# Plot Manhattan distance KNN Graph
c2g.plot_graph(
nodes=poi_gdf,
edges=knn_l1_edges,
ax=axes[0],
node_color='darkred',
edge_color='red',
markersize=20,
node_alpha=0.8,
edge_linewidth=0.8,
edge_alpha=0.6
)
ctx.add_basemap(axes[0], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[0].set_title('KNN Graph - Manhattan Distance', fontsize=12, fontweight='bold')
axes[0].set_axis_off()
# Plot Euclidean distance KNN Graph
c2g.plot_graph(
nodes=poi_gdf,
edges=knn_l2_edges,
ax=axes[1],
node_color='darkblue',
edge_color='blue',
markersize=20,
node_alpha=0.8,
edge_linewidth=0.8,
edge_alpha=0.6
)
ctx.add_basemap(axes[1], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[1].set_title('KNN Graph - Euclidean Distance', fontsize=12, fontweight='bold')
axes[1].set_axis_off()
# Plot Network distance KNN Graph
c2g.plot_graph(
nodes=poi_gdf,
edges=knn_net_edges,
ax=axes[2],
node_color='darkgreen',
edge_color='green',
markersize=20,
node_alpha=0.8,
edge_linewidth=0.8,
edge_alpha=0.6
)
ctx.add_basemap(axes[2], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[2].set_title('KNN Graph - Network Distance', fontsize=12, fontweight='bold')
axes[2].set_axis_off()
plt.tight_layout()
plt.show()
fig, axes = plt.subplots(1, 3, figsize=(18, 6)) # Plot Manhattan distance KNN Graph c2g.plot_graph( nodes=poi_gdf, edges=knn_l1_edges, ax=axes[0], node_color='darkred', edge_color='red', markersize=20, node_alpha=0.8, edge_linewidth=0.8, edge_alpha=0.6 ) ctx.add_basemap(axes[0], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron) axes[0].set_title('KNN Graph - Manhattan Distance', fontsize=12, fontweight='bold') axes[0].set_axis_off() # Plot Euclidean distance KNN Graph c2g.plot_graph( nodes=poi_gdf, edges=knn_l2_edges, ax=axes[1], node_color='darkblue', edge_color='blue', markersize=20, node_alpha=0.8, edge_linewidth=0.8, edge_alpha=0.6 ) ctx.add_basemap(axes[1], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron) axes[1].set_title('KNN Graph - Euclidean Distance', fontsize=12, fontweight='bold') axes[1].set_axis_off() # Plot Network distance KNN Graph c2g.plot_graph( nodes=poi_gdf, edges=knn_net_edges, ax=axes[2], node_color='darkgreen', edge_color='green', markersize=20, node_alpha=0.8, edge_linewidth=0.8, edge_alpha=0.6 ) ctx.add_basemap(axes[2], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron) axes[2].set_title('KNN Graph - Network Distance', fontsize=12, fontweight='bold') axes[2].set_axis_off() plt.tight_layout() plt.show()
You can obtain the output as nx.Graph object.
In [7]:
Copied!
knn_l2_G = c2g.knn_graph(
poi_gdf,
distance_metric="euclidean",
as_nx=True
)
fig, ax = plt.subplots(figsize=(12, 10))
c2g.plot_graph(
graph=knn_l2_G,
ax=ax,
node_color=get_degree_colors(knn_l2_G),
edge_color="grey",
edge_alpha=0.5,
edge_linewidth=0.5,
node_alpha=0.9,
markersize=30,
bgcolor="white"
)
if poi_gdf.crs:
ctx.add_basemap(ax, crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
ax.set_title("KNN Graph - Euclidean Distance", fontsize=14, fontweight="bold", pad=20)
ax.set_axis_off()
plt.tight_layout()
plt.show()
knn_l2_G = c2g.knn_graph( poi_gdf, distance_metric="euclidean", as_nx=True ) fig, ax = plt.subplots(figsize=(12, 10)) c2g.plot_graph( graph=knn_l2_G, ax=ax, node_color=get_degree_colors(knn_l2_G), edge_color="grey", edge_alpha=0.5, edge_linewidth=0.5, node_alpha=0.9, markersize=30, bgcolor="white" ) if poi_gdf.crs: ctx.add_basemap(ax, crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron) ax.set_title("KNN Graph - Euclidean Distance", fontsize=14, fontweight="bold", pad=20) ax.set_axis_off() plt.tight_layout() plt.show()
In [8]:
Copied!
HTML("""
<video controls style="width: 100%; max-width: 800px; height: auto;">
<source src="../assets/videos/knn_graph.mp4" type="video/mp4">
</video>
""")
HTML(""" """)
Out[8]:
5. Delaunay Graph¶
Generate and plot a Delaunay triangulation graph of the POIs.
In [9]:
Copied!
del_l1_nodes, del_l1_edges = c2g.delaunay_graph(
poi_gdf,
distance_metric="manhattan"
)
del_l2_nodes, del_l2_edges = c2g.delaunay_graph(
poi_gdf,
distance_metric="euclidean"
)
del_net_nodes, del_net_edges = c2g.delaunay_graph(
poi_gdf,
distance_metric="network",
network_gdf=segments_gdf.to_crs(epsg=6677)
)
del_l1_nodes, del_l1_edges = c2g.delaunay_graph( poi_gdf, distance_metric="manhattan" ) del_l2_nodes, del_l2_edges = c2g.delaunay_graph( poi_gdf, distance_metric="euclidean" ) del_net_nodes, del_net_edges = c2g.delaunay_graph( poi_gdf, distance_metric="network", network_gdf=segments_gdf.to_crs(epsg=6677) )
In [10]:
Copied!
fig, axes = plt.subplots(1, 3, figsize=(18, 6))
# Plot Manhattan distance Delaunay Graph
c2g.plot_graph(
nodes=poi_gdf,
edges=del_l1_edges,
ax=axes[0],
node_color='darkred',
edge_color='red',
markersize=20,
node_alpha=0.8,
edge_linewidth=0.8,
edge_alpha=0.6
)
ctx.add_basemap(axes[0], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[0].set_title(
'Delaunay Graph - Manhattan Distance',
fontsize=12,
fontweight='bold'
)
axes[0].set_axis_off()
# Plot Euclidean distance Delaunay Graph
c2g.plot_graph(nodes=poi_gdf,
edges=del_l2_edges,
ax=axes[1],
node_color='darkblue',
edge_color='blue',
markersize=20,
node_alpha=0.8,
edge_linewidth=0.8,
edge_alpha=0.6
)
ctx.add_basemap(axes[1], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[1].set_title(
'Delaunay Graph - Euclidean Distance',
fontsize=12,
fontweight='bold'
)
axes[1].set_axis_off()
# Plot Network distance Delaunay Graph
c2g.plot_graph(
nodes=poi_gdf,
edges=del_net_edges,
ax=axes[2],
node_color='darkgreen',
edge_color='green',
markersize=20,
node_alpha=0.8,
edge_linewidth=0.8,
edge_alpha=0.6
)
ctx.add_basemap(axes[2], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron)
axes[2].set_title(
'Delaunay Graph - Network Distance',
fontsize=12,
fontweight='bold'
)
axes[2].set_axis_off()
plt.tight_layout()
plt.show()
fig, axes = plt.subplots(1, 3, figsize=(18, 6)) # Plot Manhattan distance Delaunay Graph c2g.plot_graph( nodes=poi_gdf, edges=del_l1_edges, ax=axes[0], node_color='darkred', edge_color='red', markersize=20, node_alpha=0.8, edge_linewidth=0.8, edge_alpha=0.6 ) ctx.add_basemap(axes[0], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron) axes[0].set_title( 'Delaunay Graph - Manhattan Distance', fontsize=12, fontweight='bold' ) axes[0].set_axis_off() # Plot Euclidean distance Delaunay Graph c2g.plot_graph(nodes=poi_gdf, edges=del_l2_edges, ax=axes[1], node_color='darkblue', edge_color='blue', markersize=20, node_alpha=0.8, edge_linewidth=0.8, edge_alpha=0.6 ) ctx.add_basemap(axes[1], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron) axes[1].set_title( 'Delaunay Graph - Euclidean Distance', fontsize=12, fontweight='bold' ) axes[1].set_axis_off() # Plot Network distance Delaunay Graph c2g.plot_graph( nodes=poi_gdf, edges=del_net_edges, ax=axes[2], node_color='darkgreen', edge_color='green', markersize=20, node_alpha=0.8, edge_linewidth=0.8, edge_alpha=0.6 ) ctx.add_basemap(axes[2], crs=poi_gdf.crs, source=ctx.providers.CartoDB.Positron) axes[2].set_title( 'Delaunay Graph - Network Distance', fontsize=12, fontweight='bold' ) axes[2].set_axis_off() plt.tight_layout() plt.show()