Building a Transfer Graph for Routing
Build the graph from three sources in strict precedence order — the rules in transfers.txt first, same-station edges from parent_station second, proximity-derived edges last — and then delete every edge that a transfer_type = 3 rule forbids. Keep the graph directed, because exit gates and one-way permissions are real, and record where each edge came from so an itinerary can say whether an interchange is agency-stated or inferred. The rules themselves are loaded in parsing GTFS transfers.txt in Python.
Root Cause Analysis
A routing engine needs to answer one question about every pair of stops: can a rider get from here to there without boarding a vehicle, and how long does it take? GTFS answers that question only partially, and from three different places.
transfers.txt is the authoritative source, and most feeds do not carry it. Where it exists it is usually sparse — a few hundred rules covering the interchanges the agency cared to constrain, out of tens of thousands of stop pairs where a change is physically possible.
The parent_station hierarchy fills part of the gap. Two platforms sharing a parent are, by definition, in the same station, and a change between them is possible unless something says otherwise. This is reliable where the feed models stations properly and useless where every platform is a standalone stop.
Proximity fills the rest. Two stops fifty metres apart on opposite sides of a road are a real interchange that neither of the first two sources mentions. Deriving those edges is necessary and is also the source of every bad interchange a router has ever produced, because distance is not walkability — a stop across a motorway is thirty metres away and unreachable.
The failure that matters most is not a missing edge but a wrongly present one. A router with an extra edge produces itineraries riders cannot follow; a router missing an edge produces a slightly worse itinerary. That asymmetry is why prohibitions must be applied last and why they must remove edges rather than make them expensive. A weighted-out edge is still a path, and a query with no alternative will take it.
Production-Ready Python Implementation
"""Build a directed, provenance-carrying transfer graph from a GTFS feed."""
from __future__ import annotations
import logging
from dataclasses import dataclass
import networkx as nx
import pandas as pd
log = logging.getLogger("gtfs.transfers.graph")
# Defaults, in seconds, for edges the feed does not time itself.
SAME_STATION_SECONDS = 180.0
WALK_SPEED_MPS = 1.2 # a deliberately unhurried walking pace
MAX_PROXIMITY_M = 400.0 # beyond this, model it as a walking leg
DEFAULT_MIN_TRANSFER_SECONDS = 120.0
# Edge provenance, in precedence order — earlier sources win.
AGENCY, HIERARCHY, PROXIMITY = "agency", "hierarchy", "proximity"
@dataclass
class GraphReport:
edges_by_source: dict[str, int]
forbidden_removed: int
nodes: int
def build_transfer_graph(index, stops: pd.DataFrame,
projected: pd.DataFrame | None = None
) -> tuple[nx.DiGraph, GraphReport]:
"""index: the TransferIndex loaded from transfers.txt.
stops: stops.txt. projected: optional stop_id/x/y in a METRIC CRS."""
graph = nx.DiGraph()
counts = {AGENCY: 0, HIERARCHY: 0, PROXIMITY: 0}
def add(u: str, v: str, seconds: float, source: str, kind: str) -> None:
if u == v:
return
existing = graph.get_edge_data(u, v)
if existing is not None:
return # an earlier, higher-precedence source already claimed it
graph.add_edge(u, v, seconds=float(seconds), source=source, kind=kind)
counts[source] += 1
# 1. Agency-stated rules. These are the only edges anyone actually vouched for.
for rules in index._by_pair.values():
for rule in rules:
if not rule.permitted:
continue
seconds = rule.effective_seconds
if rule.kind == 2 and rule.min_seconds is None:
seconds = DEFAULT_MIN_TRANSFER_SECONDS
add(rule.from_stop, rule.to_stop, seconds, AGENCY, f"type {rule.kind}")
# 2. Same-station edges from the parent hierarchy.
parented = stops[stops["parent_station"].notna() & (stops["parent_station"] != "")]
for _, siblings in parented.groupby("parent_station"):
members = list(siblings["stop_id"])
for u in members:
for v in members:
add(u, v, SAME_STATION_SECONDS, HIERARCHY, "same station")
# 3. Proximity, in metres — never in degrees.
if projected is not None and not projected.empty:
for u, v, metres in _nearby_pairs(projected, MAX_PROXIMITY_M):
seconds = metres / WALK_SPEED_MPS
add(u, v, seconds, PROXIMITY, f"{metres:.0f} m walk")
add(v, u, seconds, PROXIMITY, f"{metres:.0f} m walk")
# 4. Prohibitions LAST, and they delete rather than penalise.
removed = 0
for rules in index._by_pair.values():
for rule in rules:
if rule.permitted or rule.specificity:
continue # trip- or route-scoped bans are applied at query time
if graph.has_edge(rule.from_stop, rule.to_stop):
graph.remove_edge(rule.from_stop, rule.to_stop)
removed += 1
report = GraphReport(edges_by_source=counts, forbidden_removed=removed,
nodes=graph.number_of_nodes())
log.info("transfer graph: %d node(s), %d agency + %d hierarchy + %d proximity "
"edge(s), %d forbidden edge(s) removed",
report.nodes, counts[AGENCY], counts[HIERARCHY], counts[PROXIMITY], removed)
return graph, report
def _nearby_pairs(projected: pd.DataFrame, radius_m: float):
"""Stop pairs within radius_m, using a grid so the comparison is not quadratic."""
from collections import defaultdict
cell = radius_m
buckets: dict[tuple[int, int], list] = defaultdict(list)
for row in projected.itertuples(index=False):
buckets[(int(row.x // cell), int(row.y // cell))].append(row)
for (cx, cy), members in buckets.items():
neighbours = []
for dx in (-1, 0, 1):
for dy in (-1, 0, 1):
neighbours.extend(buckets.get((cx + dx, cy + dy), ()))
for a in members:
for b in neighbours:
if a.stop_id >= b.stop_id:
continue # each unordered pair once
metres = ((a.x - b.x) ** 2 + (a.y - b.y) ** 2) ** 0.5
if metres <= radius_m:
yield a.stop_id, b.stop_id, metres
Step-by-Step Walkthrough
add refuses to overwrite an existing edge. That single rule implements the whole precedence policy. Because the sources are applied in order, an agency-stated 240-second interchange is never replaced by a hierarchy default of 180, and a hierarchy edge is never replaced by a proximity guess. Precedence lives in the call order, not in a comparison.
Every edge carries source and kind. A routing engine that knows an interchange came from proximity rather than agency can present it differently — “about a two-minute walk” rather than “change here” — and an analyst debugging a bad itinerary can see immediately whether the offending edge was stated or inferred.
Hierarchy edges are added in both directions explicitly, by the nested loop. They are symmetric in fact, but adding them as two directed edges keeps the graph type uniform and leaves each direction available for individual removal by a prohibition.
Proximity uses a projected CRS, and the parameter is named projected to make that unavoidable. Euclidean distance on latitude and longitude is not a distance; it varies by a factor of two between the equator and northern Europe. The choice of projected CRS is a real decision and the function declines to make it.
_nearby_pairs grids the stops rather than comparing all pairs. A feed with 9,000 stops has 40 million unordered pairs; bucketing by the search radius and checking only the nine surrounding cells reduces that to the handful of genuinely nearby candidates. The a.stop_id >= b.stop_id guard yields each pair once despite each appearing in both stops’ neighbourhoods.
Prohibitions run last and only unqualified ones are applied to the graph. A transfer_type = 3 rule that names specific trips forbids a change between those trips, not between the stops in general, so removing the stop-level edge would be too strong. Those rules stay in the index and are enforced when the router evaluates a concrete connection.
Verification and Output
def verify(graph: nx.DiGraph, index, report: GraphReport) -> list[str]:
problems: list[str] = []
for rules in index._by_pair.values():
for rule in rules:
if rule.permitted or rule.specificity:
continue
if graph.has_edge(rule.from_stop, rule.to_stop):
problems.append(
f"forbidden transfer {rule.from_stop}->{rule.to_stop} is still "
"traversable")
for u, v, data in graph.edges(data=True):
if data["seconds"] < 0:
problems.append(f"negative transfer time on {u}->{v}")
if data["source"] not in (AGENCY, HIERARCHY, PROXIMITY):
problems.append(f"edge {u}->{v} has no provenance")
if report.edges_by_source[PROXIMITY] > 20 * max(1, report.edges_by_source[AGENCY]):
problems.append(
"the graph is overwhelmingly proximity-derived — check that the feed's "
"parent_station hierarchy is actually populated")
return problems
A feed with a well-modelled hierarchy:
INFO gtfs.transfers.graph: transfer graph: 4218 node(s), 1257 agency + 6140 hierarchy + 812 proximity edge(s), 27 forbidden edge(s) removed
A feed without one:
INFO gtfs.transfers.graph: transfer graph: 8904 node(s), 0 agency + 0 hierarchy + 19446 proximity edge(s), 0 forbidden edge(s) removed
WARN the graph is overwhelmingly proximity-derived — check that the feed's parent_station hierarchy is actually populated
The second graph will route, and every interchange in it is a guess. That is worth knowing before the itineraries reach riders rather than after.
Gotchas and Edge Cases
- Stations with dozens of platforms. The hierarchy loop is quadratic in the platform count, which is fine at ten and noticeable at eighty. Where a feed also carries pathways, use those traversal times instead of a flat default — they are measured rather than assumed.
- Proximity edges across barriers. A motorway, a river or a rail cutting makes two nearby stops unreachable, and nothing in the feed says so. Only an agency
transfer_type = 3rule or an external street network can catch it, which is the strongest argument for keeping the radius conservative. - Nested boarding areas. A
location_type = 4boarding area’s parent is a platform, not a station, so grouping onparent_stationalone puts it in a group of one. Resolve up to the station first if the feed uses them. - Self-loops.
adddrops them. A transfer from a stop to itself is meaningful as a minimum connection time — it constrains changing vehicles at one platform — but it is not a graph edge; it belongs in the router’s per-stop dwell rule, taken from the index directly. - Directed asymmetry from proximity. The code adds both directions with equal cost, which is right for a flat walk and wrong where a prohibition removes one side. That is intended: the prohibition pass is what introduces the asymmetry, and it runs after.
Frequently Asked Questions
Why must the transfer graph be directed?
Because real constraints are directional. An exit-only gate, a one-way escalator, and a transfer the agency permits one way but not the other all exist, and an undirected graph silently makes them symmetric.
Should forbidden transfers be removed or weighted heavily?
Removed. A large weight is still traversable, and a routing query with no alternative will take it and present the rider with an impossible itinerary. An absent edge cannot be traversed at any price.
How close do two stops have to be before a proximity edge is justified?
Measured in metres in a projected CRS, not in degrees. A 150-metre radius is a reasonable default for street-level interchange; beyond about 400 metres a walk should be modelled as a walking leg rather than as a transfer.
What order should the three edge sources be applied in?
Agency rules first, hierarchy second, proximity last, with earlier sources winning. The agency knows its own stations; proximity is a guess that should only fill genuine gaps.
Related
- Parsing GTFS transfers.txt in Python — the index this graph is built from
- Detecting Impossible Transfers in GTFS — auditing the edges before a router trusts them
- Up: Transfers and Trip Linking — where transfers sit among the feed’s linking mechanisms
- Section: Python Parsing & Data Normalization · Home