Graph representation

Graph representation

This page explains the OSRM graph represation, including nodes, ways, edges and segments.

OSM input data

Data comes from OSM, which has nodes, ways and relations

Node

Everything in OSRM is based on nodes. An OSM node is a 2D point with latitude and longitude.

Way

An OSM way connects a number of nodes. A ways is thus a 2D poly-line, consisting of a number of segments. Several ways can share the same node where they cross.

Relation

An OSM relation relates several nodes or ways, or both. It can be used for turn restrictions, routes, and other things. A relation is often not a physical structure.

OSRM edge based graph

OSRM loads the OSM data, and transforms it into an edge-based graph that's better suited for fast routing. Suppose this OSM data is loaded:

|   |   | d |
| a | b | c |
|   |   | e |

The data consists of two ways: abc, and dce, meeting at node c.

First, all ways are split into individual segments: ab,bc,cd,ce. For each segment, two graph nodes are created, one for each direction of the segment:

ab, ba
bc, cb
cd, dc
ce, ec

Finally, a graph edge is create for every possible turn taking you from one graph node (direction of a OSM segment) to another. If we allow all turns (including u-turns), in the map above, we get these edges:

(ab > bc)
(ba > ab)
(bc > cd), (bc > ce)
(cb > ba)
(cd > dc)
(dc > cb), (dc > ce)
(ce > ec)
(ec > eb), (ec > cd)

Here, each edge have been written in the form (graph_node1 > graph_node2). Nodes with more than one outgoing edge (choice of direction) have been placed on the same line. For example, when you're at graph node bc (which represents moving from b to c in the OSM map), you can go either to graph node cd or ce, and there are therefore two edges starting from the bc graph node: (bc > cd) and (bc > ce).

Graph node

Graph nodes represents moving in a specific direction (forward or backward) on a segment.

Graph Node

A graph edges connect graph nodes, and thus represent moving from one segment to another, either via a turn, or just be moving from segment to segment along a way.