Building a Routing Graph from OSM: Transition Constraints and Path Constraints

Over the last years, I have built road networks based on OpenStreetMap in different contexts and for different clients. That work taught me a lot. It also made one thing very clear to me: there is a big difference between consuming map data and actually defining the road network a machine should work with. What I am building now is my own Road Network API. Not a map viewer, not a routing frontend, and not another wrapper around an existing routing engine, but the road network itself as a product and as an API.

That sounds simpler than it is. OpenStreetMap gives us nodes, ways, relations, tags, and geometry. It gives us a rich and detailed description of the world. But it does not hand us a finished road network in the form needed when the real question is not what is visible on a map, but what movement is actually possible.

That difference becomes very concrete around restrictions. A road can exist visually and still not be reachable from a certain direction. A turn can be illegal at one junction. A whole maneuver can be forbidden even though each individual road segment looks valid on its own. This is exactly where the model has to become explicit. In this article, I want to focus on that point and explain why a serious road network needs two different kinds of movement rules: transition constraints and path constraints.

From OSM Data to a Routing Graph

Over the years I learned to treat OpenStreetMap with a bit more precision than I did at the beginning. It is tempting to look at a road, a junction, a restriction relation, and assume the routing graph is already there. It is not. OSM gives us great source data: nodes with coordinates, ways with ordered node references, relations with members and tags. That is a strong and flexible model for describing the world. But it is still a source model. It is not yet the structure a routing system can execute directly when the real question is no longer what is visible on the map, but what movement is actually allowed.

You can see that immediately in the raw data itself. A street arrives as a way with node references and tags. A restriction arrives as a relation with members and roles. Even the common restriction shape already tells the story: from, via, to. And OSM does not stop at a via node. The via member can also be a way. That one detail is enough to show why the source representation cannot be the final routing representation. A simple turn at one node and a maneuver that runs through an intermediate connector are different things. OSM can describe both, but a routing graph has to resolve them into something explicit and operational.

<!-- A road as it appears in OSM XML -->
<way id="26659127" user="Masch" uid="55988" visible="true" version="5" changeset="4142606" timestamp="2010-03-16T11:47:08Z">
  <nd ref="292403538"/>
  <nd ref="298884289"/>
  <nd ref="261728686"/>
  <tag k="highway" v="unclassified"/>
  <tag k="name" v="Pastower Straße"/>
</way>

<!-- A turn restriction as it appears in OSM XML -->
<relation id="1630776" version="3">
  <member type="way" ref="24644266" role="from"/>
  <member type="node" ref="270186" role="via"/>
  <member type="way" ref="24644267" role="to"/>
  <tag k="restriction" v="no_left_turn"/>
  <tag k="type" v="restriction"/>
</relation>

That is why I do not treat OSM relations as the golden form for routing. They are the right source form for editing, exchange, and community-maintained map data. But a routing graph still has to do the harder part. It has to turn ways into directed edges. It has to make access and direction explicit. And it has to translate restriction relations into rules that are local to the graph and efficient to evaluate. Geisberger and Vetter make the same point from the routing side when they move to an edge-based model to handle turn costs properly. Once turns and movement rules matter, the plain road graph is no longer enough. You need a representation that makes those transitions explicit.

I think the important thing is the transformation from descriptive map data into a movement model that can actually be queried and used. That is the value of a road network. It makes the hidden structure of movement explicit. Roads become directed edges and restrictions become real rules in the graph. That changes everything for the systems built on top of it, because they no longer have to reinterpret raw OSM relations again and again. They can work against a road network that already answers the harder question: not what is mapped here, but what movement is possible here. This is also the point where the distinction in this article begins to matter. Some restrictions affect one immediate turn at one node. Others describe a maneuver that runs through an intermediate path. Treating both as if they were the same would flatten an important difference that the road network has to preserve.

Restrictions Force a Different Graph

Before considering restrictions, it's natural to think in terms of roads, intersections, and geometry. A street connects to another street, a vehicle moves from one segment to the next, and the whole thing still feels close to the visual map. Restrictions break that illusion. They force the model to care about movement itself, not just about connected lines. OSM makes that visible in a very direct way. A restriction relation is not attached to a road as a passive property. It defines a permitted or forbidden movement from one way, through a via element, into another way. In the common case, that via element is a node. But OSM also supports a via way, which already tells you that not every forbidden maneuver is just a turn at one junction. Some restrictions span an intermediate connector or slip road and only make sense as a sequence.

That is exactly where a plain road graph becomes too flat. If the graph only knows that roads are connected, it still does not know whether a specific movement through that connection is legal. And once the via member can be a way, the problem gets even sharper. Now the legality of the movement depends on a short path through the network, not only on one local turn. This is why routing literature moves beyond the simple node-edge picture as soon as turn costs and turn restrictions matter. Geisberger and Vetter do not treat this as an edge case. They treat it as a structural requirement of realistic routing. The graph has to represent turns explicitly because the cost or legality of movement depends on more than the current road segment alone.

That is also the point where I stopped looking at restriction relations as something the routing layer could just evaluate later. They are still the right source representation in OSM, but they are not yet the operational rule set of the road network. A routing system needs something sharper. It needs rules that are already resolved against the graph it works on. That means one kind of rule for immediate edge-to-edge movement at a node, and another kind of rule for a maneuver that runs through an ordered sequence of intermediate edges. Treating both as if they were the same would erase a distinction that exists in the source data itself and matters even more once the graph is built.

For me, the consequence is clear: the road network cannot end at roads and intersections. It has to model admissible movement. And the moment it does that seriously, two different kinds of constraints appear naturally. One describes an immediate transition at a node. The other describes a maneuver across a path. That is the point where transition constraints and path constraints stop sounding like internal terminology and start looking like the only honest way to represent what the road network actually contains.

Transition Constraints

The simpler of the two cases is the one OSM users know best. A vehicle comes in on one road, reaches a junction, and is not allowed to continue into one specific outgoing road. That is the familiar shape behind restrictions like no left turn, no right turn, no U-turn, or only straight on. In OSM, this is usually represented as a relation with a from way, a via node, and a to way. The important part is not the XML shape itself. The important part is what it means once the road network has already been built: this is no longer just a tagged relation. It becomes a rule about one immediate movement from one directed edge to another through one node.

That's why it is called a transition constraint. The word transition is doing real work here. The restriction does not live on the incoming edge alone. It does not live on the outgoing edge alone either. And it does not live on the node in isolation. It lives in the transition between two edges at that node. That is the real object the routing graph has to reason about. A road can be perfectly valid on its own, the next road can also be perfectly valid on its own, and still the movement from one into the other can be forbidden. Once you see that clearly, it becomes hard to accept looser models that treat restrictions as decorative metadata hanging somewhere near the junction.

A transition constraint is represented in our road network as a rule over three concrete graph elements: an incoming directed edge, a via node, and an outgoing directed edge. In other words, the restriction is no longer attached vaguely to a junction or carried around as a relation that still needs interpretation later. It is resolved into the actual movement the graph must allow or deny. If edge E1 enters node N from the south and edge E2 leaves N to the west, then a no left turn becomes a rule that says: the transition from E1 through N into E2 is denied. If the source restriction is an only straight on, the shape is the same, but the meaning changes slightly. Then the graph stores that only one specific outgoing transition is allowed from that incoming edge at that node, and every other outgoing transition from the same incoming edge is excluded.

A tiny example makes that more tangible:

          E2
          ←
          |
          |
E3  ←-----N-----→ E4
          |
          |
          ↑
          E1

If a vehicle arrives on E1 and the source data contains a no left turn restriction, then the graph stores a transition constraint like this:

from_edge = E1
via_node  = N
to_edge   = E2
kind      = deny
restriction = no_left_turn

That is the design choice that matters here. We do not keep the restriction as a loose source object and hope the routing layer will reconstruct the meaning later. We resolve it once into the graph itself. The result is a road network that can answer the real question directly: may a vehicle move from this edge through this node into that edge, yes or no?

There is also a nice conceptual fit here with the graph literature around forbidden transitions. That work describes exactly this kind of situation: whether a walk through a graph is valid depends on whether a consecutive pair of edges is permitted at a shared vertex. That is almost a direct formal description of a node-based turn restriction in a routing graph. It is a useful reminder because it shows that this is not some special OSM quirk. It is a more general graph problem that just becomes very concrete in road networks.

Path Constraints

The second case is the one that makes the distinction unavoidable. A restriction is no longer about one immediate turn at one node. It is about a maneuver that runs through an intermediate connector, slip road, or short link before reaching its final continuation. OSM allows exactly that by letting the via member of a restriction relation be a way, not only a node. That means the source data itself already distinguishes between a local turn at a junction and a movement that spans a whole intermediate path. If the road network flattened both into the same kind of rule, it would throw away information that is explicitly present in the source.

This is the reason why the road network needs a second kind of constraint. A path constraint is not attached to one node and it is not defined by one adjacent edge pair. It is defined by a sequence: an incoming edge, an ordered set of intermediate edges, and the outgoing edge that completes the maneuver. The crucial point is the order. A connector road is not just “somewhere in between.” It is part of the movement that is being restricted. The graph therefore has to preserve that sequence and evaluate it as a sequence, not as a loose collection of roads that happen to touch. This is also exactly the kind of problem that pushes routing beyond the simple node-edge picture. Once turn costs and turn restrictions matter, the legality of a route depends on more than the current edge alone. That is why turn-aware and edge-based representations appear so naturally in routing literature.

In the road network we built, a path constraint is resolved into three parts: a from edge, an ordered via-edge sequence, and a to edge. That is the design decision that keeps the source semantics intact. We do not reduce a via-way restriction to a vague note saying that something is forbidden around here. We resolve it into the exact maneuver the graph must deny or allow. If a vehicle comes from E1, then follows E2 and E3 through a connector path, and finally reaches E4, the graph can state precisely that this whole maneuver is forbidden. We resolve it into the exact maneuver the graph must deny or allow, including the entry into the connector, the ordered path through it, and the final continuation.

A small example makes that easier to see:

A ----E1---- B ----E2---- C ----E3---- D ----E4---- E

If the restriction is about the maneuver from E1 through the connector path E2 and E3 into E4, then the graph stores a path constraint like this:

from_edge   = E1
via_edges   = [E2, E3]
to_edge     = E4
kind        = deny
restriction = no_right_turn

The important thing here is that none of the intermediate edges is invalid on its own. E2 may be perfectly traversable. E3 may also be perfectly traversable. E4 may be perfectly fine when approached from somewhere else. What is restricted is the maneuver formed by that ordered sequence. That is exactly why a transition constraint is not enough in this case. A transition constraint can describe one immediate move from one edge through one node into another edge. It cannot carry the fact that the rule only becomes meaningful once the vehicle has already committed to a particular intermediate path.

This is the point where the road network becomes much more honest than the visual map. On the map, all those segments just look connected. In the graph, the model can say something much sharper: yes, these roads exist; yes, they are traversable in general; but no, this specific maneuver through them is not allowed. That is the value of turning source relations into explicit path constraints. The graph stops guessing later and starts carrying the actual movement rule now.

Why Both Are Needed

At that point the obvious question comes up. If both cases exist, why not collapse them into one single kind of rule? Why not treat every restriction as a path, or force every maneuver back into local edge-to-edge transitions? The idea sounds tidy at first, but it stops fitting the moment you look closely at what the restriction is actually describing.

A transition constraint works because it stays exactly where the rule lives. One incoming edge, one node, one outgoing edge. Nothing more. That is the natural shape of a local turn restriction. It keeps the graph precise and it keeps the rule understandable. The graph can say exactly what is forbidden or allowed at that point, without wrapping a simple turn in a heavier structure than it needs.

A path constraint solves a different problem. It keeps the shape of a maneuver that only makes sense across an ordered intermediate path. That is not the same thing as one turn at one node. If I tried to break that kind of restriction into a series of local transitions, I would spread one movement rule across several smaller rules and lose the fact that they belong together as one maneuver. The graph would still contain fragments of the logic, but not the rule in the form it actually exists.

The other direction is not better. A no-left-turn at a junction is not a path just because it can be written as a very short sequence. Modeling it that way would make the graph more uniform on the surface, but less exact in meaning. It would blur the difference between a local transition and a maneuver across a connector, even though OSM itself already distinguishes between those two cases.

That is why both are needed. The road network has to preserve the actual shape of the movement rule it represents. Some restrictions describe one immediate transition at one node. Others describe a maneuver through an intermediate path. If the graph keeps that difference intact, it becomes much easier to understand, much easier to inspect, and much closer to the real movement rules hidden inside the source data.

Cheers!