VehicleMapping HD AV Spatial Data

Building Lane Successor Graphs from OpenDRIVE

A planner needs to ask "which lanes can I legally drive into next?", but OpenDRIVE answers that only indirectly — through road links, lane-section boundaries, and junction connection matrices scattered across the file. This task materializes those into a single directed lane-successor graph, the query-ready form of lane-level topology modeling. The hard parts are the sign convention at road contact points and the many-to-many expansion of junctions; get those wrong and the graph routes traffic into oncoming lanes. This builds directly on the parsing covered in how to parse OpenDRIVE XML with Python.

OpenDRIVE link and junction records expand into a directed lane-successor graph:

Lane-Successor Graph Construction from OpenDRIVE Left column of lane nodes labelled road A lanes, right column labelled road B lanes, connected by directed edges representing successor links. A separate box shows a junction connection record expanding into incoming-to-connecting lane edges. A gate at the bottom states every non-terminal lane needs a successor and no edge may reverse direction. Road A lanes Road B lanes −1 −2 −3 −1 −2 −3 successor · contactPoint=start Junction laneLink from −1 → to −1 from −1 → to −2 from −2 → to −1 many-to-many turns every non-terminal lane has a successor · no direction reversal

Prerequisites #

  • Python 3.10+, NetworkX 3.2+, lxml 5.x, NumPy 1.24+.
  • Input: a schema-valid OpenDRIVE 1.7/1.8 file (validate first with OpenDRIVE XSD validation).
  • Upstream stage: roads, lane sections, and junctions parsed into Python objects with their link and junction records intact.
  • Output: a networkx.DiGraph whose nodes are lanes and whose edges are legal successor movements, ready for routing and validation.

Step-by-Step #

1. Create a node per lane per lane section #

Each driving lane in each lane section is a node keyed by (road_id, section_idx, lane_id). Skip lane id 0 (the reference-line centre lane, which is non-driving).

python
import networkx as nx

def add_lane_nodes(g: nx.DiGraph, roads) -> None:
    for road in roads:
        for si, section in enumerate(road.lane_sections):
            for lane in section.lanes:
                if lane.id == 0 or lane.type != "driving":
                    continue
                g.add_node((road.id, si, lane.id),
                           s_start=section.s, road=road.id)

Key parameters: the node key carries road id, section index, and signed lane id; filtering to type == "driving" keeps sidewalks and medians out of the routing graph.

Within one road, a lane in section i links to a lane in section i+1 via the lane-level <successor id="…"/>. This is a straight, sign-preserving link.

python
def add_intra_road_edges(g, road) -> None:
    for si in range(len(road.lane_sections) - 1):
        for lane in road.lane_sections[si].lanes:
            succ = lane.successor_id          # lane <link><successor>
            if succ is not None:
                g.add_edge((road.id, si, lane.id),
                           (road.id, si + 1, succ), kind="successor")

Road-level links join the last section of one road to a section of another. The contactPoint decides which section and whether the connecting lane id keeps its sign.

python
def add_inter_road_edges(g, road, roads_by_id) -> None:
    link = road.successor_link
    if link is None or link.element_type != "road":
        return
    other = roads_by_id[link.element_id]
    # contactPoint=start -> other's section 0, sign preserved;
    # contactPoint=end   -> other's last section, sign flipped.
    if link.contact_point == "start":
        tgt_si, sign = 0, +1
    else:
        tgt_si, sign = len(other.lane_sections) - 1, -1
    last_si = len(road.lane_sections) - 1
    for lane in road.lane_sections[last_si].lanes:
        if lane.successor_id is None:
            continue
        g.add_edge((road.id, last_si, lane.id),
                   (other.id, tgt_si, sign * lane.successor_id),
                   kind="road_link")

Key parameter: sign flips the connecting lane id when roads meet end-to-end, preserving driving direction. Omitting it is the classic bug that feeds a lane into oncoming traffic.

4. Expand junction connection matrices #

Each <connection> inside a <junction> carries a <laneLink from="…" to="…"/> table. Expand every entry into an explicit edge from the incoming road lane to the connecting road lane.

python
def add_junction_edges(g, junction, roads_by_id) -> None:
    for conn in junction.connections:
        inc = roads_by_id[conn.incoming_road]
        con = roads_by_id[conn.connecting_road]
        inc_si = len(inc.lane_sections) - 1
        con_si = 0 if conn.contact_point == "start" else len(con.lane_sections) - 1
        for ll in conn.lane_links:
            g.add_edge((inc.id, inc_si, ll.from_id),
                       (con.id, con_si, ll.to_id),
                       kind="junction", junction=junction.id)

Verification & Acceptance Criteria #

Validate the graph before any planner consumes it.

python
def assert_graph_valid(g: nx.DiGraph):
    # 1. no self-loops
    assert nx.number_of_selfloops(g) == 0, "lane links to itself"
    # 2. every edge endpoint is a real node
    assert all(u in g and v in g for u, v in g.edges), "dangling edge endpoint"
    # 3. no direction reversal: a lane and its successor share sign convention
    for u, v, k in g.edges(data="kind"):
        if k == "successor":
            assert (u[2] > 0) == (v[2] > 0), f"sign flip on plain successor {u}->{v}"
    print(f"graph OK: {g.number_of_nodes()} lanes, {g.number_of_edges()} edges")

Acceptance gate: no self-loops, no dangling endpoints, every non-terminal driving lane has ≥1 outgoing edge, and plain (non-junction) successors preserve sign. Feed the result into the deeper checks in detecting dangling lanes and connectivity gaps.

Common Errors & Fixes #

A lane connects to an oncoming lane through a junction. The contact-point sign rule was skipped on the connecting road. Apply the sign flip in step 3 and set con_si from contactPoint in step 4.

KeyError on a target node when adding an edge. The successor lane id points to a lane section that was filtered out (non-driving) or a road not yet indexed. Add all nodes for all roads before adding any edges, and skip links whose target is non-driving.

Terminal lanes flagged everywhere at map edges. Lanes that legitimately leave the mapped area have no successor. Mark boundary roads and exempt their end lanes from the "must have a successor" check rather than fabricating edges.

Junction turns missing from the graph. Only road-level links were resolved; the <laneLink> tables were never expanded. Junctions are many-to-many and must be expanded explicitly in step 4 — geometry proximity will not recover them.

FAQ #

Why does lane linking depend on the contact point? #

OpenDRIVE roads connect at either their start or end, given by the contactPoint attribute on the link. When two roads meet end-to-start the lane ids keep their sign, but when they meet end-to-end or start-to-start the driving direction reverses and the sign of the connecting lane id flips. Ignoring the contact point links the wrong lanes and produces a graph where a right lane feeds into an oncoming lane.

A plain road link is one-to-one: road A's end connects to road B's start. A junction is many-to-many: several incoming roads connect to several connecting roads, and each connection carries a laneLink table mapping specific incoming lane ids to connecting lane ids. You cannot infer these from geometry alone because turn movements overlap in space, so the connection matrix must be expanded edge by edge from the schema.

Why build the graph in NetworkX rather than query OpenDRIVE directly? #

OpenDRIVE stores connectivity as scattered link and junction records, which is fine for serialization but poor for the graph queries a planner needs — reachability, shortest lane path, cycle detection. Materializing a directed graph once turns those into standard graph algorithms, and lets connectivity invariants be checked with a single pass instead of walking XML for every query.

Up one level: Lane-Level Topology Modeling — the parent workflow on connectivity, junctions, and regulatory bindings this graph feeds.