Comparing Python Graph Libraries for OSM

Choosing a Python graph library for OSM routing work is an operational decision, not a style preference — it determines whether a nightly graph rebuild finishes in minutes or hours, and whether a single-node service can hold your target region in memory at all. This guide is part of the Python Routing Engines & Isochrone Mapping section and benchmarks the three libraries that come up most often once a team moves past prototyping: NetworkX, igraph, and cuGraph. Each occupies a distinct point on the trade-off curve between developer ergonomics, single-node throughput, and GPU-accelerated scale, and the right choice usually depends on where in your pipeline the graph sits — validation, production single-node serving, or bulk batch analytics.

Prerequisites

The three libraries have non-overlapping installation paths. Set up all three in an isolated environment before benchmarking, since cuGraph’s RAPIDS conda channel can shadow pip-installed packages if mixed carelessly.

# NetworkX and igraph — CPU-only, no GPU required
pip install networkx python-igraph pandas pyarrow

# cuGraph — requires an NVIDIA GPU with compute capability 7.0+ and a matching CUDA driver
conda create -n rapids-osm -c rapidsai -c conda-forge -c nvidia \
  cugraph=24.04 cudf=24.04 python=3.10 cudatoolkit=12.2

cuGraph is only worth installing if you have physical or cloud access to an NVIDIA GPU (an A10G, L4, or A100 covers state-to-country scale comfortably). If you are evaluating purely on CPU infrastructure, benchmark NetworkX against igraph first and treat the cuGraph numbers below as a scale-planning reference.

All three libraries in this guide load from the same preprocessed edge list — a u, v, length_m, speed_kph, oneway table produced during building directed graphs from OSM PBF files. Producing that edge list once and reusing it across libraries keeps the comparison apples-to-apples and avoids re-parsing PBF data three times.

Conceptual Architecture

The three libraries diverge at the storage layer, and that divergence explains almost every performance number in this guide.

NetworkX stores a DiGraph as a dictionary of dictionaries: each node key maps to a dictionary of successor nodes, each of which maps to an attribute dictionary. This gives flexible, mutable, Pythonic access — you can add an edge attribute mid-loop without any schema — but every node and edge carries the overhead of a full Python object plus at least one nested dict, typically 300–500 bytes beyond the raw numeric data. Traversal algorithms run in pure Python (or with light Cython acceleration in some paths) and are bound by the GIL, so they do not parallelize across threads.

igraph stores the graph as compact C arrays in a compressed adjacency representation close to CSR (compressed sparse row). Vertices and edges are referenced by dense, contiguous integer indices rather than arbitrary hashable keys, and attributes are stored as parallel arrays rather than per-object dictionaries. Because the core is compiled C with a thin Python binding layer, bulk operations — building the graph, running Dijkstra, computing centrality — execute at native speed and release the GIL during the C call, which matters if you multithread request handling around it.

cuGraph takes the CSR idea further and moves it onto the GPU. Edges are loaded as a cudf DataFrame (itself a GPU-resident columnar table), then renumbered into a dense integer space and converted to a device-resident CSR structure. Algorithms run as bulk-synchronous parallel CUDA kernels — thousands of GPU threads cooperatively relax edges in each SSSP or BFS frontier — which is why cuGraph’s advantage grows with graph size and especially with the number of simultaneous queries, but is diluted on small graphs by fixed host-to-device transfer and kernel launch overhead.

The practical consequence: NetworkX optimizes for developer iteration speed, igraph optimizes for single-node production throughput without a GPU dependency, and cuGraph optimizes for graphs or batch query volumes that exceed what a CPU core can push through, at the cost of GPU infrastructure and a narrower algorithm surface.

Build Time and Memory Footprint

Build time and memory scale very differently across the three libraries as graph size grows. The numbers below are illustrative, gathered from repeated runs on OSM extracts of increasing scale on a 16-core CPU host with an attached L4 GPU — treat them as directional, not as a guarantee for your hardware.

Two patterns are worth internalizing. First, igraph’s memory advantage over NetworkX widens as scale increases — the fixed per-object overhead in NetworkX compounds linearly with node count, while igraph’s array-backed storage grows close to the theoretical minimum. Second, cuGraph’s build time is dominated by a near-constant transfer and renumbering cost at small scale (it is slower than igraph on a city-sized graph) but overtakes igraph’s build time advantage on country-scale graphs, where the GPU’s parallel renumbering and CSR construction outpaces a single CPU core.

Shortest-Path Query Throughput

Single-query latency and batch throughput tell different stories, and conflating them is the most common mistake teams make when choosing a library for a production routing service.

*At city and metro scale, cuGraph’s single-query latency is dominated by host-to-device transfer and kernel launch overhead rather than the actual traversal — the GPU finishes the search almost instantly but pays a fixed tax to get there and back.

Throughput under concurrent load reverses part of that picture:

The takeaway: for a single interactive route request, igraph is usually the pragmatic default — it beats NetworkX by one to two orders of magnitude without any GPU dependency. cuGraph only pulls ahead when you can batch requests, which is exactly the shape of workloads like population-weighted accessibility scoring or many-to-many distance matrix computation, where thousands of origins are evaluated together rather than one at a time.

API Ergonomics, Ecosystem Fit, and Licensing

For interactive point-to-point routing at production scale, most teams reach for OSRM or Valhalla rather than any of these three libraries directly — see deploying OSRM with Docker for local routing for that path. NetworkX, igraph, and cuGraph earn their place in the stack for the surrounding work: algorithm prototyping against NetworkX shortest path algorithms for logistics, graph-level validation, centrality-based network analysis, and bulk offline computation that a contraction-hierarchy engine is not built for.

Step-by-Step Implementation

1. Install and Configure Each Library

Use separate environments if you are running CPU-only benchmarks alongside cuGraph, since the RAPIDS conda channel pins specific numpy and pandas versions that can conflict with a pip-managed NetworkX/igraph environment.

# CPU environment
python3 -m venv .venv && source .venv/bin/activate
pip install networkx==3.2.1 python-igraph==0.11.4 pandas pyarrow

# GPU environment (separate conda env)
conda create -n rapids-osm -c rapidsai -c conda-forge -c nvidia \
  cugraph=24.04 cudf=24.04 python=3.10 cudatoolkit=12.2 -y

2. Load the OSM Edge List into NetworkX

# requires: networkx, pandas, pyarrow (pip install networkx pandas pyarrow)
import networkx as nx
import pandas as pd

def load_networkx_graph(edges_path: str) -> nx.DiGraph:
    """Build a directed graph from a preprocessed OSM edge list (vectorized)."""
    edges = pd.read_parquet(edges_path)  # columns: u, v, length_m, speed_kph, oneway
    edges["weight"] = edges["length_m"] / (edges["speed_kph"] / 3.6)

    forward = edges[["u", "v", "length_m", "weight"]]
    reverse = edges.loc[~edges["oneway"], ["v", "u", "length_m", "weight"]].rename(
        columns={"v": "u", "u": "v"}
    )
    all_edges = pd.concat([forward, reverse], ignore_index=True)

    graph = nx.from_pandas_edgelist(
        all_edges, source="u", target="v",
        edge_attr=["length_m", "weight"],
        create_using=nx.DiGraph,
    )
    return graph

graph = load_networkx_graph("metro_edges.parquet")
print(f"NetworkX graph: {graph.number_of_nodes():,} nodes, {graph.number_of_edges():,} edges")

3. Load the OSM Edge List into igraph

igraph requires contiguous 0-based integer vertex IDs, so the original OSM node IDs must be remapped and preserved as a vertex attribute for later lookups.

# requires: python-igraph, pandas, numpy, pyarrow (pip install python-igraph pandas numpy pyarrow)
import igraph as ig
import pandas as pd
import numpy as np

def load_igraph_graph(edges_path: str) -> ig.Graph:
    """Build a directed igraph Graph from a preprocessed OSM edge list."""
    edges = pd.read_parquet(edges_path)
    edges["weight"] = edges["length_m"] / (edges["speed_kph"] / 3.6)

    forward = edges[["u", "v", "length_m", "weight"]]
    reverse = edges.loc[~edges["oneway"], ["v", "u", "length_m", "weight"]].rename(
        columns={"v": "u", "u": "v"}
    )
    all_edges = pd.concat([forward, reverse], ignore_index=True)

    node_ids = np.union1d(all_edges["u"].unique(), all_edges["v"].unique())
    id_map = pd.Series(np.arange(len(node_ids)), index=node_ids)
    all_edges["u_idx"] = id_map.loc[all_edges["u"]].to_numpy()
    all_edges["v_idx"] = id_map.loc[all_edges["v"]].to_numpy()

    graph = ig.Graph(
        n=len(node_ids),
        edges=list(zip(all_edges["u_idx"], all_edges["v_idx"])),
        directed=True,
    )
    graph.es["length_m"] = all_edges["length_m"].to_numpy()
    graph.es["weight"] = all_edges["weight"].to_numpy()
    graph.vs["osm_id"] = node_ids  # preserve original OSM node IDs for lookups
    return graph

graph = load_igraph_graph("metro_edges.parquet")
print(f"igraph graph: {graph.vcount():,} nodes, {graph.ecount():,} edges")

4. Load the OSM Edge List into cuGraph

# requires: cudf, cugraph (RAPIDS 24.x, CUDA 12+; conda install -c rapidsai -c conda-forge -c nvidia cudf cugraph)
import cudf
import cugraph

def load_cugraph_graph(edges_path: str) -> cugraph.Graph:
    """Build a directed cuGraph Graph from a preprocessed OSM edge list on GPU."""
    edges = cudf.read_parquet(edges_path)
    edges["weight"] = edges["length_m"] / (edges["speed_kph"] / 3.6)

    forward = edges[["u", "v", "length_m", "weight"]]
    reverse = edges[~edges["oneway"]][["v", "u", "length_m", "weight"]].rename(
        columns={"v": "u", "u": "v"}
    )
    all_edges = cudf.concat([forward, reverse], ignore_index=True)

    graph = cugraph.Graph(directed=True)
    graph.from_cudf_edgelist(
        all_edges, source="u", destination="v", edge_attr="weight", renumber=True
    )
    return graph

graph = load_cugraph_graph("metro_edges.parquet")
print(f"cuGraph graph: {graph.number_of_vertices():,} nodes, {graph.number_of_edges():,} edges")

renumber=True is the default and should stay on for any graph built from raw OSM IDs — cuGraph’s internal renumbering table is what lets you translate GPU-side vertex indices back to OSM node IDs after a query, mirroring the vs["osm_id"] pattern used for igraph above.

5. Benchmark Shortest-Path Queries Across Libraries

# requires: networkx, python-igraph, cugraph (see prerequisites for install commands)
import time

def benchmark_single_source(nx_graph, ig_graph, cu_graph, source_osm_id: int) -> dict:
    """Time a single-source shortest-path computation across all three libraries."""
    results = {}

    start = time.perf_counter()
    nx.single_source_dijkstra_path_length(nx_graph, source_osm_id, weight="weight")
    results["networkx_ms"] = (time.perf_counter() - start) * 1000

    source_idx = ig_graph.vs.find(osm_id=source_osm_id).index
    start = time.perf_counter()
    ig_graph.distances(source=source_idx, weights="weight")
    results["igraph_ms"] = (time.perf_counter() - start) * 1000

    start = time.perf_counter()
    cugraph.sssp(cu_graph, source=source_osm_id)
    results["cugraph_ms"] = (time.perf_counter() - start) * 1000

    return results

timings = benchmark_single_source(nx_graph, ig_graph, cu_graph, source_osm_id=42871093)
print(timings)

6. Validate Path-Length Parity Between Libraries

# requires: networkx, python-igraph, cugraph, numpy
import numpy as np

def validate_parity(nx_graph, ig_graph, cu_graph, source_osm_id: int, target_osm_id: int) -> None:
    """Assert that all three libraries agree on shortest-path distance within tolerance."""
    nx_dist = nx.dijkstra_path_length(nx_graph, source_osm_id, target_osm_id, weight="weight")

    src_idx = ig_graph.vs.find(osm_id=source_osm_id).index
    tgt_idx = ig_graph.vs.find(osm_id=target_osm_id).index
    ig_dist = ig_graph.distances(source=src_idx, target=tgt_idx, weights="weight")[0][0]

    cu_result = cugraph.sssp(cu_graph, source=source_osm_id)
    cu_dist = cu_result[cu_result["vertex"] == target_osm_id]["distance"].iloc[0]

    assert np.isclose(nx_dist, ig_dist, rtol=1e-6), f"NetworkX/igraph mismatch: {nx_dist} vs {ig_dist}"
    assert np.isclose(nx_dist, float(cu_dist), rtol=1e-4), f"NetworkX/cuGraph mismatch: {nx_dist} vs {cu_dist}"
    print(f"[PASS] Parity within tolerance: NetworkX={nx_dist:.2f}, igraph={ig_dist:.2f}, cuGraph={float(cu_dist):.2f}")

validate_parity(nx_graph, ig_graph, cu_graph, source_osm_id=42871093, target_osm_id=42871512)

Note the looser tolerance for the cuGraph comparison — rtol=1e-4 rather than 1e-6 — to account for float32 accumulation differences described in the troubleshooting section below.

Production Optimization and Scaling

Match the library to the pipeline stage, not the whole system

Few production stacks run one graph library end to end. A common pattern is NetworkX for CI-time algorithm validation on small representative subgraphs (fast to write assertions against, no compiled dependency to manage in test containers), igraph as the default in-process engine for any service that needs graph traversal beyond what a routing engine’s HTTP API exposes, and cuGraph reserved for genuinely large batch jobs — continental centrality computation, many-to-many distance matrices, or accessibility scoring across large origin sets like the workflow in generating isochrones with PySAL and GeoPandas.

Avoid rebuilding the renumbering map on every request

Both igraph and cuGraph pay a real cost to remap arbitrary OSM node IDs to dense integer indices. Build that mapping once at graph-load time, persist it alongside the graph artifact (a Parquet file mapping osm_id -> internal_idx works for both libraries), and reload it rather than recomputing np.union1d and index maps per process restart. For cuGraph specifically, cache the renumbered edge list itself — skipping from_cudf_edgelist’s renumbering pass on a warm restart cuts multi-second startup time to under a second on state-scale graphs.

Use RMM pooled memory allocation for repeated cuGraph calls

By default, cugraph allocates and frees GPU memory per call through CUDA’s native allocator, which adds latency under high query rates. Initialize a RAPIDS Memory Manager (RMM) pool allocator once at process startup:

# requires: rmm (bundled with the RAPIDS cugraph/cudf conda install)
import rmm

rmm.reinitialize(pool_allocator=True, initial_pool_size=2 * 1024**3)  # 2 GiB pool

This preallocates a memory pool that subsequent cudf and cugraph calls draw from, avoiding repeated cudaMalloc/cudaFree round-trips that otherwise dominate latency for small, frequent GPU operations.

Scale igraph horizontally with a thread pool, not multiprocessing

Because igraph’s C core releases the GIL during traversal calls, a concurrent.futures.ThreadPoolExecutor wrapping shared read-only graph queries scales close to linearly with core count — unlike NetworkX, which needs separate processes (and separate graph copies in memory) to achieve any real concurrency. Keep the graph object read-only across threads; igraph’s C core is not designed for concurrent mutation.

Scale cuGraph across GPUs with Dask-cuGraph

For graphs that exceed a single GPU’s memory (country-to-continent scale on commodity GPU instances), dask-cugraph partitions the edge list across multiple GPUs and coordinates distributed BFS/SSSP execution. This is a meaningfully larger operational surface — a Dask scheduler, worker health checks, and partition-aware edge loading — and is worth the complexity only once single-GPU memory is the binding constraint, not before.

Validation and Benchmarking

Before trusting a library migration (for example moving a service from NetworkX to igraph, or introducing cuGraph for a new batch job), run a repeatable benchmark and parity harness rather than eyeballing a handful of manual queries.

# requires: networkx, python-igraph, pandas, numpy, time (pip install networkx python-igraph pandas numpy)
import time
import numpy as np
import pandas as pd

def run_benchmark_suite(nx_graph, ig_graph, source_ids: list[int], trials: int = 5) -> pd.DataFrame:
    """Run repeated shortest-path timings and return a summary DataFrame."""
    rows = []
    for source_osm_id in source_ids:
        nx_times, ig_times = [], []
        for _ in range(trials):
            start = time.perf_counter()
            nx.single_source_dijkstra_path_length(nx_graph, source_osm_id, weight="weight")
            nx_times.append((time.perf_counter() - start) * 1000)

            src_idx = ig_graph.vs.find(osm_id=source_osm_id).index
            start = time.perf_counter()
            ig_graph.distances(source=src_idx, weights="weight")
            ig_times.append((time.perf_counter() - start) * 1000)

        rows.append({
            "source_osm_id": source_osm_id,
            "networkx_p50_ms": np.median(nx_times),
            "igraph_p50_ms": np.median(ig_times),
            "speedup": np.median(nx_times) / np.median(ig_times),
        })
    return pd.DataFrame(rows)

summary = run_benchmark_suite(nx_graph, ig_graph, source_ids=[42871093, 42871512, 42872001])
print(summary.to_string(index=False))
assert (summary["speedup"] > 5).all(), "Expected igraph to outperform NetworkX by at least 5x on this graph"

Checks to run before promoting a new library into production:

• Path-length parity across libraries within the tolerances shown in step 6 above, run against at least 50–200 representative origin/destination pairs, not a single spot check.
• Node count and edge count equality after loading — a silent off-by-one in the reverse-edge filter for oneway segments will produce a graph with the right node count but the wrong edge count.
• Memory ceiling validation under your actual container mem_limit, not just local development RAM, since CI runners and production containers frequently have less headroom than a developer workstation.
• Cold-start timing for the target library, since igraph and cuGraph both front-load work (index construction, renumbering) that NetworkX defers until first query.

Troubleshooting

Related

• NetworkX vs igraph vs cuGraph for Large Graphs — continent-scale benchmarks and the crossover point where GPU acceleration pays off
• NetworkX shortest path algorithms for logistics — Dijkstra vs A*, directed graph construction, and subgraph validation workflows
• NetworkX Dijkstra vs A* for route calculation — heuristic design and when A* outperforms plain Dijkstra on road networks
• Building directed graphs from OSM PBF files — producing the edge list that feeds all three libraries in this comparison
• Python Routing Engines & Isochrone Mapping — the broader guide to engine selection, cost functions, and isochrone generation