NetworkX vs igraph vs cuGraph for Large Graphs

Picking a graph library for OSM-derived routing stops being obvious once a graph crosses roughly half a million nodes — the point where NetworkX’s pure-Python priority queue becomes the visible bottleneck in a request path. This page benchmarks the three realistic options side by side as a companion to comparing Python graph libraries for OSM, and assumes the graph-construction groundwork covered in Python Routing Engines & Isochrone Mapping. The short version: igraph’s C core wins on single-query latency at almost every practical scale, and cuGraph only pulls ahead once the graph is large enough and the query volume high enough to amortize GPU transfer overhead.

When to Use Each Library

The three libraries sit on different points of a build-time-vs-query-latency-vs-operational-complexity curve. None is strictly better — the right choice depends on graph size, query pattern, and what’s already running in the deployment environment.

Choose NetworkX when:

• The graph stays under roughly 100,000–200,000 nodes and query volume is low (batch or interactive, not a hot API path)
• Iteration speed on graph-construction logic matters more than raw query throughput
• The team needs the richest algorithm library and the most forgiving debugging experience

Choose igraph when:

• The graph is in the 200,000-node to several-million-node range
• Shortest-path queries sit on a latency-sensitive API path but a GPU isn’t part of the deployment story
• You want a drop-in speedup without adding infrastructure — igraph is a pip-installable C library with no external service

Choose cuGraph when:

• The graph exceeds roughly 5 million nodes (continent- or country-scale OSM extracts)
• Query volume is high enough to keep a GPU warm — batch matrix computations or sustained concurrent single-source queries, not occasional lookups
• The deployment environment already has CUDA and an NVIDIA GPU provisioned for other workloads (isochrone rasterization, ML inference)

For most single-metro delivery graphs built following NetworkX shortest path algorithms for logistics, igraph is the pragmatic upgrade path: same conceptual API, no new infrastructure, 10–50x lower per-query overhead. cuGraph only earns its complexity budget at genuinely large scale.

Implementation

The benchmark below builds the same synthetic OSM-style graph in all three libraries and times a batch of single-source-to-target shortest-path queries. It assumes graph construction (parsing .pbf files, assigning edge weights) already happened upstream, as covered in NetworkX Dijkstra vs A* for route calculation — this snippet only compares query mechanics on an existing edge list.

# requires: networkx, python-igraph, cugraph, cudf, numpy (pip install networkx python-igraph)
# cugraph/cudf require the RAPIDS conda/pip channel and a CUDA-capable GPU — see rapids.ai
# Python 3.9+

import random
import time

import networkx as nx
import igraph as ig
import numpy as np

try:
    import cudf
    import cugraph
    HAS_CUGRAPH = True
except ImportError:
    HAS_CUGRAPH = False


def build_edge_list(num_nodes: int, avg_degree: int = 4, seed: int = 42):
    """Synthetic directed edge list resembling an OSM road graph's shape."""
    rng = random.Random(seed)
    edges = []
    for u in range(num_nodes):
        for _ in range(avg_degree):
            v = rng.randrange(num_nodes)
            if v != u:
                weight = round(rng.uniform(0.05, 3.0), 3)  # km, free-flow segment
                edges.append((u, v, weight))
    return edges


def benchmark_networkx(edges, num_nodes, queries):
    G = nx.DiGraph()
    G.add_weighted_edges_from(edges)
    t0 = time.perf_counter()
    for s, t in queries:
        try:
            nx.dijkstra_path_length(G, s, t, weight="weight")
        except nx.NetworkXNoPath:
            pass
    return time.perf_counter() - t0


def benchmark_igraph(edges, num_nodes, queries):
    g = ig.Graph(n=num_nodes, edges=[(u, v) for u, v, _ in edges], directed=True)
    g.es["weight"] = [w for _, _, w in edges]
    t0 = time.perf_counter()
    for s, t in queries:
        g.distances(source=s, target=t, weights="weight")
    return time.perf_counter() - t0


def benchmark_cugraph(edges, num_nodes, queries):
    if not HAS_CUGRAPH:
        return None
    src = np.array([u for u, _, _ in edges], dtype=np.int32)
    dst = np.array([v for _, v, _ in edges], dtype=np.int32)
    wt = np.array([w for _, _, w in edges], dtype=np.float32)
    gdf = cudf.DataFrame({"src": src, "dst": dst, "weight": wt})
    G = cugraph.Graph(directed=True)
    G.from_cudf_edgelist(gdf, source="src", destination="dst", edge_attr="weight")

    t0 = time.perf_counter()
    # cuGraph's SSSP is single-source — batch by grouping queries on shared sources
    sources = sorted({s for s, _ in queries})
    for s in sources:
        cugraph.sssp(G, source=s)
    return time.perf_counter() - t0


NUM_NODES = 200_000
edges = build_edge_list(NUM_NODES)
queries = [(random.randrange(NUM_NODES), random.randrange(NUM_NODES)) for _ in range(500)]

nx_time = benchmark_networkx(edges, NUM_NODES, queries)
ig_time = benchmark_igraph(edges, NUM_NODES, queries)
cg_time = benchmark_cugraph(edges, NUM_NODES, queries)

print(f"NetworkX : {nx_time:.3f}s  ({len(queries) / nx_time:.1f} q/s)")
print(f"igraph   : {ig_time:.3f}s  ({len(queries) / ig_time:.1f} q/s)")
if cg_time is not None:
    print(f"cuGraph  : {cg_time:.3f}s  ({len(sorted({s for s, _ in queries})) / cg_time:.1f} src/s)")
else:
    print("cuGraph  : skipped (no GPU / RAPIDS install detected)")

Two mechanical differences drive the results. First, igraph.Graph.distances() runs entirely in compiled C, so per-query Python overhead disappears — the timing loop above still pays a Python function-call cost per query, but the graph traversal itself doesn’t touch the interpreter. Second, cugraph.sssp() computes single-source shortest paths to every reachable node in one GPU kernel launch, not point-to-point — batch queries by source node to amortize the launch and transfer cost, never call it once per origin-destination pair.

Key Parameters and Tuning

Node indexing. igraph and cuGraph both require dense integer node IDs starting at zero — OSM node IDs are large sparse integers and must be remapped through a lookup table before loading. Keep the remap dictionary (osm_id -> igraph_index) alive alongside the graph so you can translate query results back to OSM IDs.

Weight arrays vs attributes. igraph accepts weights as a plain list matching edge insertion order (g.es["weight"] = [...]), which is far faster to construct than iterating and calling add_edge() per edge as NetworkX requires. Build the edge and weight arrays with vectorized list comprehensions or numpy, not row-by-row loops, when working from a pandas-derived edge table.

cuGraph batching granularity. cugraph.sssp() cost scales with the number of distinct source nodes launched, not the number of origin-destination pairs. If a workload has many-to-many queries (an OD matrix), route it through cugraph.sssp() once per unique origin rather than reformulating as pairwise calls — this is the same batching principle used in chunking large origin-destination matrices.

Integration Points

Feeding OSRM or Valhalla for production routing. All three libraries are best used as an analysis or pre-computation layer, not a live turn-by-turn engine. Once a candidate route or reachable-node set is identified with igraph or cuGraph, snap the result to the full road network and request final geometry through the deploying OSRM with Docker for local routing workflow rather than reconstructing polylines from the simplified analysis graph.

Algorithm parity with NetworkX prototypes. Development and correctness testing typically stay in NetworkX because of its debuggability and the breadth of examples in NetworkX shortest path algorithms for logistics; the production query path swaps to igraph or cuGraph behind the same interface once correctness is established. Keep the edge-list export function as the single seam between graph construction and the query backend so switching libraries doesn’t touch upstream OSM-parsing code.

Isochrone and accessibility workloads. cuGraph’s sssp() — cost-to-every-node from one source — maps directly onto isochrone generation at scale. For metro-level isochrones, NetworkX’s single_source_dijkstra_path_length remains adequate; cuGraph becomes worthwhile when generating isochrones for thousands of origin points against a national or continental graph in a single batch job.

Data exchange format. Standardize on a plain (source_id, target_id, weight) edge list (or a pandas/cudf DataFrame with those three columns) as the export format from graph construction. Every library in this comparison ingests that shape directly, which keeps the OSM-parsing and weight-assignment code — including work from configuring edge weights for freight logistics — entirely decoupled from the query backend choice.

Validation Checklist

1. Path cost parity. For a sample of 100+ random source-target pairs, confirm abs(networkx_cost - igraph_cost) < 1e-6 and, where GPU is available, abs(networkx_cost - cugraph_cost) < 1e-3 (allow slightly looser tolerance for float32 GPU precision vs float64 CPU).

2. Node ID remap round-trip. Verify every igraph/cuGraph integer index maps back to the correct original OSM node ID after a query — a broken remap table produces plausible-looking but wrong routes that won’t surface as errors.

3. Directed edge fidelity. Confirm one-way street edges inserted only in the forward direction in NetworkX are also single-directional in the igraph and cuGraph exports; a bug in the export step commonly duplicates edges as bidirectional.

4. Disconnected component handling. Run a query between two nodes known to be in separate components and confirm all three libraries raise or return the expected “no path” signal (nx.NetworkXNoPath, igraph returning inf, cugraph.sssp() returning unreached nodes with distance inf) rather than silently returning zero or a stale cached result.

5. Memory ceiling check. Load the full target graph size in a staging environment and record peak RSS (CPU libraries) or peak VRAM (cugraph) before deploying — GPU out-of-memory failures on cuGraph typically surface as an unhandled MemoryError deep in the RAPIDS stack rather than a clean exception.

6. Cold-start build time budget. If the graph is rebuilt on deploy rather than persisted, measure build time under production data volume for all candidate libraries — a fast query engine with a five-minute cold build can still violate a deployment’s startup SLA.

Related

• Comparing Python graph libraries for OSM — the broader guide to memory, build-time, and scaling trade-offs across these libraries
• NetworkX Dijkstra vs A* for route calculation — algorithm-level comparison within NetworkX before considering a library switch
• NetworkX shortest path algorithms for logistics — graph construction and weighting patterns shared across all three libraries
• Deploying OSRM with Docker for local routing — where to send a candidate path once analysis-layer routing is done