Traversing Nested OSM Relations Safely

Relations can contain relations, nothing forbids a cycle, and nothing bounds the depth. A naive recursive walk over a route hierarchy works on every relation you test with and hangs on the one that matters.

Prerequisites

Conceptual minimum

An OSM relation’s members can be nodes, ways or other relations. That last case makes the structure a general directed graph rather than a tree, and three properties follow that a tree-shaped assumption gets wrong.

Cycles are possible. Relation A can contain B, which contains A. Nothing in the data model prevents it and mappers occasionally create it by accident. A recursive walk without a visited set recurses until the stack ends.

Depth is unbounded in principle. Route hierarchies nest three or four deep in practice; nothing guarantees that, and a walk with no ceiling has no bound on its work.

The same relation can be reached by several paths. A member may legitimately appear under two parents, and a walk that does not deduplicate will process it twice, producing doubled geometry or doubled counts.

Three structures a naive recursive walk gets wrong Three panels. A cycle, where a relation eventually contains itself through a chain of members, makes an unguarded recursive walk recurse until the stack is exhausted. A diamond, where one relation is reached through two different parents, makes a walk without a visited set process it twice and double whatever it accumulates. Deep nesting, where route relations contain route relations several levels down, makes an unbounded walk do far more work than expected with no signal that anything is wrong. Three shapes, three different failures Cycle A contains B contains A Rare but real Unguarded walk never ends Visited set fixes it Diamond One child, two parents Entirely legitimate Processed twice Counts and geometry double Deep nesting Routes within routes Three or four levels No bound in the model Work grows silently All three are fixed by the same three lines: a visited set, a depth ceiling and a member-count cap.
None of these is malformed data; the data model simply permits structures a tree-shaped walk cannot handle.

Runnable solution

python 
from __future__ import annotations

import logging
from collections import deque
from collections.abc import Callable
from dataclasses import dataclass, field

logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")
logger = logging.getLogger("osm.relations.traverse")

MAX_DEPTH = 8
MAX_MEMBERS = 250_000


class TraversalLimit(RuntimeError):
    """The traversal hit a guard rather than finishing naturally."""


@dataclass
class Result:
    ways: list[int] = field(default_factory=list)
    nodes: list[int] = field(default_factory=list)
    relations_visited: set[int] = field(default_factory=set)
    max_depth_seen: int = 0
    cycles: list[tuple[int, int]] = field(default_factory=list)


def traverse(root_id: int,
             members_of: Callable[[int], list[tuple[str, int, str]]],
             max_depth: int = MAX_DEPTH,
             max_members: int = MAX_MEMBERS) -> Result:
    """Breadth-first walk over a relation hierarchy, with every guard explicit.

    Iterative rather than recursive: a cycle in the data must not become a
    stack overflow, and an iterative walk makes the depth ceiling obvious.
    """
    result = Result()
    # (relation id, depth, parent id) — the parent is kept for cycle reporting.
    queue: deque[tuple[int, int, int | None]] = deque([(root_id, 0, None)])
    result.relations_visited.add(root_id)
    seen_members = 0

    while queue:
        relation_id, depth, parent = queue.popleft()
        result.max_depth_seen = max(result.max_depth_seen, depth)

        if depth >= max_depth:
            raise TraversalLimit(
                f"relation {relation_id} sits at depth {depth}; the ceiling is "
                f"{max_depth}. Either raise it deliberately or the hierarchy "
                f"is malformed.")

        for member_type, member_id, _role in members_of(relation_id):
            seen_members += 1
            if seen_members > max_members:
                raise TraversalLimit(
                    f"traversal exceeded {max_members} members after visiting "
                    f"{len(result.relations_visited)} relation(s)")

            if member_type == "way":
                result.ways.append(member_id)
            elif member_type == "node":
                result.nodes.append(member_id)
            elif member_type == "relation":
                if member_id in result.relations_visited:
                    # Already reached: either a diamond or a cycle. Record it
                    # and do NOT descend again.
                    result.cycles.append((relation_id, member_id))
                    continue
                result.relations_visited.add(member_id)
                queue.append((member_id, depth + 1, relation_id))

    # De-duplicate: a way can legitimately belong to several relations.
    result.ways = sorted(set(result.ways))
    result.nodes = sorted(set(result.nodes))
    logger.info("visited %d relation(s) to depth %d: %d way(s), %d node(s), "
                "%d repeat edge(s)", len(result.relations_visited),
                result.max_depth_seen, len(result.ways), len(result.nodes),
                len(result.cycles))
    return result


def detect_true_cycles(result: Result,
                       members_of: Callable[[int], list[tuple[str, int, str]]]
                       ) -> list[tuple[int, int]]:
    """Separate genuine cycles from harmless diamonds among the repeat edges."""
    genuine: list[tuple[int, int]] = []
    for parent, child in result.cycles:
        # A true cycle means the child can reach the parent again.
        reachable: set[int] = set()
        stack = [child]
        while stack:
            current = stack.pop()
            for t, i, _ in members_of(current):
                if t != "relation" or i in reachable:
                    continue
                reachable.add(i)
                stack.append(i)
        if parent in reachable:
            genuine.append((parent, child))
    if genuine:
        logger.error("%d genuine cycle(s): %s", len(genuine), genuine[:5])
    return genuine


if __name__ == "__main__":
    graph = {1: [("relation", 2, ""), ("way", 10, "")],
             2: [("way", 11, ""), ("relation", 1, "")]}
    result = traverse(1, lambda rid: graph.get(rid, []))
    detect_true_cycles(result, lambda rid: graph.get(rid, []))

Step-by-step walkthrough

  1. Iterate, do not recurse. A cycle in the data should produce a clear error, not a stack overflow whose traceback says nothing about relations.
  2. Mark visited on enqueue, not on dequeue. Marking on dequeue lets the same relation be queued several times before any of them is processed, which reintroduces the duplication the set exists to prevent.
  3. Cap the depth explicitly. Eight levels is far beyond anything legitimate; hitting it means the hierarchy is malformed and the message says so rather than leaving somebody to guess.
  4. Cap the member count. Depth alone does not bound the work, because a shallow hierarchy can still fan out enormously. A member ceiling is the guard that actually bounds memory.
  5. Record repeat edges rather than ignoring them. A relation reached twice is either a diamond or a cycle, and recording the edge lets the two be distinguished afterwards without slowing the main walk.
  6. Deduplicate the results. A way belonging to three route relations appears three times; a consumer counting kilometres will triple them.
  7. Separate cycles from diamonds after the fact. Only a genuine cycle is a data error worth reporting to mappers, and the reachability check that distinguishes them is too expensive to run inline.
The four guards and what each one bounds Four guards applied in order. The visited set bounds the number of relations processed, ensuring each is handled exactly once regardless of how many paths reach it. The depth ceiling bounds how far the hierarchy can nest before the traversal refuses, catching malformed structures. The member cap bounds total work, which depth alone cannot because a shallow hierarchy can fan out widely. The result deduplication bounds the output, because a way belonging to several relations would otherwise be counted once per membership. Four guards, four different things bounded visited set bounds relations each one once depth ceiling bounds nesting catches malformed member cap bounds total work depth cannot dedupe output bounds the result a way counted once Omitting any one of the four leaves a structure that the other three permit and that still produces a wrong or unbounded result.
The third guard is the one usually missing, because a depth limit feels like it should be enough and is not.
What each guard costs and what it prevents A grid of four guards against their runtime cost and the failure each prevents. A visited set costs one hash set of relation identifiers and prevents infinite recursion on a cycle. A depth ceiling costs one integer comparison per relation and prevents unbounded descent through a malformed hierarchy. A member cap costs one counter increment per member and prevents memory exhaustion from a wide fan-out. Output deduplication costs one pass over the collected identifiers and prevents counts and geometry being multiplied by membership. Four guards, all of them cheap Costs Prevents Visited set a hash set infinite recursion Depth ceiling one comparison unbounded descent Member cap one counter memory exhaustion Output dedupe one final pass multiplied counts Together they add a few lines and a set, which is negligible against the cost of the traversal they are protecting.
None of these is an optimisation trade-off; they are all cheap enough to be unconditional.

Verification

  • A cycle terminates. Build a two-relation cycle and confirm the walk finishes and reports a repeat edge.
  • A diamond is not reported as a cycle. Build one and confirm the repeat edge is recorded but the genuine-cycle check returns nothing.
  • The depth ceiling fires. Construct a hierarchy deeper than the limit and confirm the error names the depth.
  • The member cap fires. Lower the cap and confirm the traversal stops with a count rather than exhausting memory.
  • Results are deduplicated. A way in two child relations must appear once in the output.

Common errors and fixes

Symptom Root cause One-line fix
Traversal never finishes Cycle with no visited set Mark relations visited as they are enqueued
Stack overflow on deep data Recursive implementation Use an iterative queue with an explicit depth
Same relation processed twice Visited marked on dequeue Mark on enqueue instead
Geometry or counts doubled Results not deduplicated Collapse way and node identifiers to a set
Memory exhausted at shallow depth Only depth bounded Add a member-count ceiling
Every repeat edge reported as a cycle Diamonds and cycles conflated Run a reachability check to separate them
Limits hit on legitimate data Ceilings set too tight Raise them deliberately, with the reason recorded

Specification reference

A relation’s members may be nodes, ways or other relations, and the data model places no restriction on nesting depth or on a relation being a member of one it transitively contains. Consumers are therefore responsible for cycle detection and for bounding traversal. See the relation documentation for the member model and the super-relation discussion for how route hierarchies nest in practice.

Frequently Asked Questions

Are cycles in OSM relations actually possible?

Yes. Nothing in the data model or the editing API prevents relation A from containing relation B while B contains A, and mappers create such structures occasionally by accident when reorganising route hierarchies. They are rare, which is why an unguarded traversal survives testing, and they are catastrophic when encountered, which is why the visited set is not optional.

Is a depth limit enough on its own?

No, because depth does not bound breadth. A hierarchy three levels deep whose top relation has five thousand children, each with five thousand members, stays well inside any reasonable depth ceiling while producing tens of millions of members. A member-count cap is the guard that actually bounds memory, and it is the one most often omitted because the depth limit feels sufficient.

How do I tell a cycle from a legitimate shared member?

By checking reachability after the walk. Reaching the same relation twice is ordinary — a way or a sub-relation can belong to several parents, and that diamond shape is entirely valid. It is only a cycle if the child can reach the parent again by following member links. That check is too expensive to run during the traversal and cheap enough to run afterwards on the handful of repeat edges recorded.

Should the traversal be breadth-first or depth-first?

Breadth-first, for two practical reasons. It makes the depth of each relation directly available, which is what the ceiling is checked against, and it naturally uses a queue rather than a call stack, so a pathological structure produces a clear error instead of a stack overflow. The traversal order itself rarely matters for the result, since the output is deduplicated anyway.

Up one level: Node, Way & Relation Data Model.