The Routing Graph

Path matching is one of the most important algorithms provided by the Location Library. This algorithm frequently queries for information about the road network. So the response to such a request must be returned quickly.

The HERE Map Content Topology Graph

The Road Topology and Geometry Layer of HERE Map Content stores a graph. This graph is called the topology graph and models the road network. This model consists of two types of elements:

  • A node represents a junction.
  • A segment represents a road that connects two junctions.


Each node or segment of the topology graph has a unique identifier. A node or segment identifier is a string that does not change between map versions, except if the corresponding element itself changes. HERE Map Content uses these identifiers to associate properties of the road network to nodes or segments. The storage of properties was not optimized to retrieve properties for a particular node or segment: retrieving properties for a particular node or segment requires scanning all the properties in the relevant partition.

For more information on how to attach properties to the road network, see the HERE Map Content Topology Attribution Referencing Model.

The Location Library Routing Graph

The Location Library uses a different graph to model the road network. This graph is called the routing graph and is derived from the topology graph of HERE Map Content.

The routing graph models the road network with the following two types of elements:

  • A vertex represents travel in a particular direction along a road segment.
  • An edge represents a possible transition from one vertex to another.

The following picture illustrates the difference between the topology graph and the routing graph:

Topology graph (in blue-green) vs. routing graph (in black)
Figure 1. Topology graph (in blue-green) vs. routing graph (in black)

Each vertex is identified by a tile ID and a vertex index. Vertex indices are positive integers that the Location Library can use to store vertex properties into arrays. An access to a property in an array is faster than in a HERE Map Content partition because the latter requires a scan of all properties in this partition.

On the other hand, vertex indices may change between two successive versions of a map. Therefore, do not use vertex indices as persistent identifiers, use segment identifiers instead.

The same comments and considerations apply to nodes (topology graph) and edges (routing graph). For more information about vertex and edge properties, see Graph Properties.

results matching ""

    No results matching ""