Modeling Turn Restrictions as an Edge-Based Graph

The symptom is a route that tells a driver to make a turn a sign forbids. The root cause is structural: in a node-based road graph a junction is a single vertex, and a shortest-path algorithm treats every relationship arriving at that vertex as freely chainable to every relationship leaving it. There is no place to say “an arrival on Prinsengracht may not continue onto Leidsestraat.” Consulting a turn table at query time fixes it but forces a custom, turn-aware search. This page resolves it a different way — by transforming the graph itself so that turns become ordinary edges. Each original road segment becomes a node, each legal movement between two segments becomes an edge, and a banned turn is simply a link that was never created. The payoff is that any standard weighted shortest-path algorithm, including the built-in gds.shortestPath.dijkstra, honours turn restrictions with zero special-case logic. This is the transformation behind the flexible turn-table approach described in Turn-Restriction and Time-Dependent Routing.

Prerequisites & Versions

The transformation is pure Cypher plus an async orchestration layer. No GDS is required to build the edge-based graph, though you will typically route over it with GDS afterwards.

pip install "neo4j>=5.18"

This assumes the source graph already follows sound Node and Edge Spatial Mapping conventions — directed segments that respect one-way rules, stable segment ids, and geometry on native point properties — because the edge-based expansion inherits every topology defect in the source and multiplies it.

Implementation

The line-graph construction is one idempotent Cypher statement, orchestrated from async Python so it can run in bounded batches over a large network. It reads every directed pair of segments that share a junction, and for each pair that is not forbidden by a Restriction, it creates a TURN edge between the two segment-nodes carrying the turn penalty as its weight.

// Source model:  (:Segment {id, from_junction, to_junction, cost_s})
// A Restriction bans a specific ordered pair meeting at a via junction.
//   (:Restriction {via, from_segment, to_segment})
// Optional via-way restrictions add an intermediate segment (see failures below).

// One-time: index the join keys so the pairwise match seeks, not scans.
CREATE INDEX segment_from IF NOT EXISTS FOR (s:Segment) ON (s.from_junction);
CREATE INDEX segment_to   IF NOT EXISTS FOR (s:Segment) ON (s.to_junction);

// Materialize the edge-based graph: legal movements become TURN edges.
MATCH (a:Segment)-[]->()  // batch anchor; in practice page by a.id ranges
WHERE a.id >= $lo AND a.id < $hi
MATCH (b:Segment)
WHERE a.to_junction = b.from_junction        // a ends where b begins → they meet
  AND NOT (a.to_junction = b.to_junction AND a.from_junction = b.from_junction)  // skip exact twins
WITH a, b, a.to_junction AS via
// Reject banned movements: leave the TURN edge uncreated entirely.
WHERE NOT EXISTS {
  MATCH (:Restriction {via: via, from_segment: a.id, to_segment: b.id})
}
// U-turn penalty: returning onto the reverse of the arriving segment.
WITH a, b, via,
     CASE WHEN b.to_junction = a.from_junction THEN 300.0 ELSE 0.0 END AS uturn_penalty
MERGE (a)-[t:TURN {via: via}]->(b)
SET t.weight_s = b.cost_s + uturn_penalty

The orchestration pages the build by segment-id range so no single transaction holds the whole network, and it runs the ranges concurrently under a bounded pool:

import asyncio
from neo4j import AsyncGraphDatabase

BUILD_TURNS = """
MATCH (a:Segment)
WHERE a.id >= $lo AND a.id < $hi
MATCH (b:Segment)
WHERE a.to_junction = b.from_junction
WITH a, b, a.to_junction AS via
WHERE NOT EXISTS {
  MATCH (:Restriction {via: via, from_segment: a.id, to_segment: b.id})
}
WITH a, b, via,
     CASE WHEN b.to_junction = a.from_junction THEN 300.0 ELSE 0.0 END AS uturn_penalty
MERGE (a)-[t:TURN {via: via}]->(b)
SET t.weight_s = b.cost_s + uturn_penalty
RETURN count(t) AS turns_built
"""


async def build_edge_based_graph(
    uri: str, auth: tuple[str, str], id_ranges: list[tuple[int, int]]
) -> int:
    """Materialize TURN edges in bounded batches; returns total turns built."""
    driver = AsyncGraphDatabase.driver(
        uri, auth=auth,
        max_connection_pool_size=8,
        connection_acquisition_timeout=30.0,
    )
    total = 0
    try:
        sem = asyncio.Semaphore(4)  # cap concurrent write transactions

        async def run_range(lo: int, hi: int) -> int:
            async with sem:
                async with driver.session(database="neo4j") as s:
                    rec = await (await s.run(BUILD_TURNS, lo=lo, hi=hi)).single()
                    return rec["turns_built"]

        results = await asyncio.gather(*(run_range(lo, hi) for lo, hi in id_ranges))
        total = sum(results)
    finally:
        await driver.close()
    return total


if __name__ == "__main__":
    # Amsterdam centre extract: segment ids 0..40000 in 5k batches.
    ranges = [(i, i + 5000) for i in range(0, 40000, 5000)]
    built = asyncio.run(
        build_edge_based_graph(
            "neo4j+s://your-cluster.databases.neo4j.io",
            ("neo4j", "secure-password"),
            ranges,
        )
    )
    print(f"Edge-based graph built: {built} TURN edges.")

Once the TURN edges exist, routing is a plain weighted shortest path over segment-nodes — no turn-aware search, no special state. A GDS projection of (:Segment)-[:TURN]->(:Segment) weighted by weight_s routes correctly because every illegal movement is already missing from the projection.

How It Works

The construction is a graph-theoretic line graph with turn semantics layered on top. Three mechanics carry it:

• Segments become nodes, movements become edges. The join condition a.to_junction = b.from_junction finds every ordered pair of segments that physically meet — segment a ends at the junction where segment b begins. Each such pair is a candidate movement. Creating a TURN edge for it promotes the movement to a first-class, weighted object that a shortest-path algorithm can reason about directly.
• The ban is subtraction, not annotation. Instead of marking a movement as forbidden, the WHERE NOT EXISTS { MATCH (:Restriction ...) } guard simply declines to create its TURN edge. A missing edge is unreachable by construction, so no search — Cypher, GDS, or hand-written — can ever emit the banned turn. There is no flag to check and no rule to forget.
• Penalty rides on the edge weight. A turn that is legal but costly — a hard left across traffic, a U-turn — carries its penalty in weight_s, added to the cost of the segment being entered. Because the penalty is now part of an ordinary edge weight, plain weighted Dijkstra minimizes total time including turn cost with no modification.

The weight convention matters: weight_s is set to the entered segment’s own cost plus any turn penalty, so the total path cost is the sum of TURN edge weights and equals travel time through the segments plus the cost of every turn taken. The origin and destination need bootstrap edges (a virtual source that links to the first segment-node and a virtual sink reachable from the last), which the routing layer adds per query rather than baking into the graph.

Common Failure Patterns

1. Doubling — or worse — the graph size. The edge-based graph has one node per directed segment and one edge per legal movement. Node count therefore roughly doubles a two-way network (each street becomes two directed segments), and edge count grows with the sum of squared junction degrees, because a degree-d junction generates up to d² movements. On a dense grid this is a several-fold blow-up. Cap it by only expanding junctions that actually carry restrictions or penalties and leaving unrestricted junctions in the cheaper node-based form — a hybrid that keeps the expansion local to where it earns its cost.

// Only expand junctions that have at least one restriction or non-trivial penalty.
MATCH (r:Restriction) RETURN collect(DISTINCT r.via) AS via_to_expand

2. Forgetting U-turn edges. A movement from a segment back onto its own reverse is a legal turn in the graph-theory sense and must be represented, or the router silently loses the ability to route a dead-end reversal — and sometimes finds no path where one physically exists. The CASE WHEN b.to_junction = a.from_junction clause in the build detects the reversal and applies a heavy penalty rather than dropping it. Omitting U-turn edges entirely is a common and hard-to-spot correctness bug: most routes are unaffected, so tests pass, until a cul-de-sac delivery has no legal route out.

3. Restriction relations with via-ways. The simple (via, from_segment, to_segment) key handles “at this junction, you may not go from A to B.” It cannot express a restriction that spans an intermediate segment — “no right turn from A onto C when the approach used way B.” These via-way restrictions, common in OpenStreetMap data, need a key that includes the intermediate segment, and the expansion must forbid the two-hop movement A→B→C while leaving A→B and B→C individually legal. Encode them against the pair of TURN edges, not a single one:

// Via-way ban: forbid the A→B then B→C sequence without banning either alone.
MATCH (:Restriction {kind:'via_way', from_segment:'A', via_segment:'B', to_segment:'C'})
MATCH (eab:Segment {id:'A'})-[t1:TURN]->(eb:Segment {id:'B'})-[t2:TURN]->(ec:Segment {id:'C'})
SET t2.forbidden_after = coalesce(t2.forbidden_after, []) + eab.id
// The router then rejects t2 whenever the label arrived via t1 from A.

Performance Notes

Build cost is dominated by the pairwise segment match, which is why the join keys must be indexed. With segment_from/segment_to indexes in place, matching partners for one segment is an index seek over the junctions it touches, so total build work is proportional to the number of movements, not to the square of the segment count. Let $d$ be the average junction degree; the edge-based graph has on the order of

$$|E_{\text{turn}}| \approx |V_{\text{junction}}| \cdot \bar{d}^{,2}$$

turn edges, so a network of 20,000 junctions at average degree 3.2 produces roughly 200,000 turn edges — comfortably in memory, but a naive full-degree expansion of every junction is what turns a manageable build into an out-of-memory one. Batch the build by id range as shown, keep the write pool small (write contention, not read throughput, is the limit), and prefer the selective-expansion hybrid on dense networks. Query-time routing over the finished graph is ordinary weighted shortest path; its cost model and the GDS-versus-Cypher trade-off are covered under the parent Network Routing Algorithms in Python.

Related

• Turn-Restriction and Time-Dependent Routing — the turn-table alternative and where each approach fits.
• Time-Dependent Shortest Paths with Schedule Edges — the other hard routing constraint, layered on the same base graph.
• Contraction Hierarchies for Road Networks — preprocessing that can run over the finished edge-based graph.
• Node and Edge Spatial Mapping — the source-graph conventions the expansion depends on.

This guide is part of Turn-Restriction and Time-Dependent Routing, within the Network Routing Algorithms in Python knowledge base.

For authoritative reference on turn-restriction data and the line-graph construction, consult the OpenStreetMap turn-restriction relation documentation.