Module 13: Network Analysis

13.1 Network Data Models

How to represent roads, rivers, and pipes as graphs — the foundation of all routing.

Lesson 64 of 100·15 min read

Key takeaways

A network is a graph: nodes (vertices) connected by edges (links), each with attributes.

Directed vs undirected, weighted vs unweighted — four combinations covering most real networks.

Topology matters — small errors in the graph cause dramatic routing bugs.

Introduction

Roads, rivers, power lines, bus routes, pipe networks — all of them are graphs. Before you can route, you need a properly structured network data model. This lesson covers how networks are represented and what can go wrong.

Nodes and edges

Node (vertex) — a junction, an intersection, a terminus. Usually a point feature.
Edge (link) — a connection between two nodes. Usually a line feature.
Attributes — on both nodes and edges: speed limits, capacities, turn restrictions.

A road network has tens of thousands of intersections (nodes) and tens of thousands of segments (edges).

Directed vs undirected

Undirected — you can traverse edges in either direction (most footpaths, rivers analysed for connectivity).
Directed — edges have a direction (one-way streets, river flow, power distribution).
Mixed — some edges are directed, others not (most real road networks).

Nearly all real street datasets need directed edges.

Weighted vs unweighted

Unweighted — every edge counts as 1 step.
Weighted — each edge has a cost (distance, travel time, fuel burn). Most real routing uses weights.

Weights can be:

Static — always the same.
Time-varying — rush-hour slowdowns.
Stochastic — traffic uncertainty.

Building a network graph

From raw line features, construct a graph by:

Splitting lines at every intersection (so each edge connects exactly two nodes).
Creating a node at every line endpoint and intersection.
Assigning each edge a "from node", "to node", direction, and weight.

Tools: osmnx, networkx, pgRouting, GraphHopper, OSRM.

Python

1import osmnx as ox
2[object Object]
3[object Object]
4

OSM as a network

OSM stores roads as ways with highway=* tags. Converting to a routable graph involves:

Ignoring non-motorable ways (footpaths for driving, motorways for walking).
Respecting oneway=yes.
Honouring access=no, vehicle=no.
Applying default speed limits by highway class.

OSRM, Valhalla, and GraphHopper all ship recipes for this.

Topology validation

Common errors:

Dangling edges — a road that ends mid-block (usually unfinished data).
Over-connected intersections — two segments that should meet but have slightly different endpoints.
Missing one-way directionality — a street that's one-way but not tagged as such.
Invalid turn restrictions — "no left turn" not encoded.
Disconnected components — parts of the network unreachable from others (often near ferry terminals, private roads).

Validate before routing. Every routing engine has import-time diagnostics.

Turn restrictions

Beyond edge-level directionality, real networks have turn restrictions:

Banned left turns.
Mandatory turns (from X you must go right).
Time-dependent restrictions (no left turn 8 AM–9 AM).

Modern engines encode these via turn edges (mini-edges at intersections) or separate restriction tables.

Multimodal networks

Combining road + public transit + walking requires:

Per-mode edges (buses can only travel bus-allowed segments).
Transfer nodes (bus stop = road + transit node).
Schedule data (GTFS) attached to transit edges.

Tools like OpenTripPlanner, Valhalla, and Google Maps combine all of these.

Scale

A country-scale routing graph has ~10 million nodes and edges. Optimisations:

Contraction hierarchies — pre-compute shortcuts, making queries sub-millisecond.
A* — heuristic pruning of Dijkstra.
Multi-level graphs — for continental routing.

Storing networks

pgRouting (PostGIS extension) — full SQL control; moderate performance.
OSRM — pre-processes OSM into in-memory graphs; very fast.
Valhalla — tile-based routing engine.
GraphHopper — JVM-based; production-grade.
NetworkX — Python in-memory; educational and small-scale.

Self-check exercises

1. Why is your route going the wrong way down a one-way street?

Your graph probably treats the edge as undirected. One-way streets in OSM are tagged oneway=yes, and the graph must reflect that — for a DiGraph, add the edge only in the direction from → to. For an undirected graph, add both directions only for two-way streets. Verify by plotting the graph and checking a known one-way.

2. A network has two disconnected components. What does that imply for routing?

Routes between components are impossible — the engine will fail or return an error. Common causes: ferry crossings not modelled, private roads excluded, data gaps. Either accept the limitation or add the missing connections (ferries as special edges with long travel times).

3. Why are contraction hierarchies dramatically faster than plain Dijkstra for long-distance routing?

CH pre-computes shortcuts across the graph: travelling "from Copenhagen to Paris" often goes through a small number of major highways, and those are pre-stitched into longer edges. A query then only needs to traverse a few high-level edges near the source and destination, not the entire network. Trade-off: preprocessing is expensive, updates require re-running.

Summary

Networks are graphs — nodes and edges with attributes.
Directed + weighted is the default for real routing.
Topology errors cause routing bugs; validate before use.
OSRM / Valhalla / GraphHopper are the production engines; pgRouting and NetworkX are educational.