Skip to content

Nutigraph format

Jump to bottom
Jaak Laineste edited this page Nov 30, 2017 · 1 revision

About

Nutigraph files are used for offline routing. The files are converted from OpenStreetMap Routing Machine (OSRM) graphs and are roughly 10x more compact while preserving the original contracted edge-expanded graph.

High level structure

Nutigraph files use Extended IFF (Interchange File Format) generic container format. Extended IFF uses 64-bit offset and size fields vs 32-bit fields in original IFF files. The following sections list chunks that are present in all Nutigraph files. Each chunk itself uses bitstream for its data. Thus the fields are not byte-aligned usually.

HEAD chunk

Field Bits Comment
Version 32 Expected to be 0
PackageNameLen 16 The length in bytes of the following field
PackageName PackageNameLen UTF8 encoding
Lat0 32 Multiplied by 10e6
Lon0 32 Multiplied by 10e6
Lat1 32 Multiplied by 10e6
Lon1 32 Multiplied by 10e6

The Lat and Lon fields define the spatial bounding box of the graph.

NODE chunk

Nodes are organized as blocks and the node blocks are represented using the following structure:

Field Bits Comment
BlockCount 32
BlockOffsets (BlockCount+1)*64 Chunk-relative offsets
Block1 (variable) described below
Block2 (variable)
... ...

Note that the number of block offsets is block count + 1. The last offset denotes the offset just past the last block. Individual node blocks are defined as follows:

Field Bits Comment
MaxInternalNodeIndexBits 6
MaxExternalNodeBlockBits 6
MaxExternalNodeIndexBits 6
MaxGlobalNodeBlockBits 6
MaxGlobalNodeIndexBits 6
MaxContractedNodeBlockBits 6
MaxContractedNodeIndexBits 6
MaxGeometryBlockBits 6
MaxGeometryBlockDiffBits 6
MaxGeometryIndexBits 6
MaxNameBlockBits 6
MaxNameBlockDiffBits 6
MaxNameIndexBits 6
MaxNodeOutDegreeBits 6
MaxTravelModeBits 6
MaxInstructionBits 6
SmallWeightBits 6
LargeWeightBits 6
MinGeometryBlockId MaxGeometryBlockBits
MinNameBlockId MaxNameBlockBits
NodeCount 32
Node1 (variable) described below
Node2 (variable)
... ...

The meaning of the fields should be clearer from the definition of nodes:

Field Bits Comment
EdgeCount MaxNodeOutDegreeBits
GeometryBlockId MaxGeometryBlockDiffBits relative to MinGeometryBlockId
GeometryIndexId MaxGeometryIndexBits
GeometryReversed 1 If 1, the referenced geometry should be flipped
NameBlockId MaxNameBlockDiffBits relative to MinNameBlockId
NameIndexId MaxNameIndexBits
TravelMode MaxTravelModeBits
WeightType 1 If 0, then small weight. If 1, then large weight
Weight SmallWeightBits or LargeWeightBits bits depends on the preceding field
Edge1 (variable) described below
Edge2 (variable)
... ...

Each edge is encoded as follows:

Field Bits Comment
TargetNodeType 1 0 for intra-block/global node, 1 for inter-block node
TargetNode (variable) described below
Forward 1 1 if forward directed
Backward 1 1 if backward directed
WeightType 1 If 0, then small weight. If 1, then large weight
Weight SmallWeightBits or LargeWeightBits bits depends on the preceding field
Contracted 1 If 1, this is a contracted node (not present in original graph)
ContractedNode or TurnInstruction (variable) depends on the preceding field

TargetNode can be either intra-node, inter-node or global-node. Intra-nodes refer to the nodes in the same block, inter-nodes refer to the nodes in different blocks but in the same package. Global nodes refer to nodes in other packages.

Inter-nodes are encoded as follows:

Field Bits Comment
TargetBlockIndex MaxExternalNodeBlockBits relative to current block, moving backwards
TargetNodeIndex MaxExternalNodeIndexBits

Intra-nodes are encoded as follows:

Field Bits Comment
TargetNodeIndex MaxInternalNodeIndexBits relative to current node, moving backwards

If the fields is 0, then the node is global node and additional fields are used:

Field Bits Comment
GlobalTargetBlockIndex MaxGlobalNodeBlockBits
GlobalTargetNodeIndex MaxGlobalNodeIndexBits

Global nodes are used as references to other packages and the references are stored in LINK chunk.

ContractedNode is stored similarly to TargetNode with one exception: TargetBlockIndex for inter-nodes is stored a signed zig-zag value and this can refer to blocks coming after the current block.

GEOM chunk

Geometries are organized as blocks and the geometry blocks are represented using the following structure:

Field Bits Comment
BlockCount 32
BlockOffsets (BlockCount+1)*64 Chunk-relative offsets
Block1 (variable) described below
Block2 (variable)
... ...

Note that the number of block offsets is block count + 1. The last offset denotes the offset just past the last block. Individual geometry blocks are defined as follows:

Field Bits Comment
MaxLatDiffBits 6
MaxLonDiffBits 6
MaxGeometrySizeBits 6
MinLat 32 Multiplied by 10e6
MinLon 32 Multiplied by 10e6
GeometryCount 32
Geometry1 (variable) described below
Geometry2 (variable)
... ...

Each geometry is encoded as follows:

Field Bits Comment
MaxLatZigZagBits 6
MaxLonZigZagBits 6
Lat MaxLatDiffBits Relative to MinLat
Lon MaxLonDiffBits Relative to MonLat
GeometrySize MaxGeometrySizeBits
DeltaEncodedGeometry GeometrySize * (MaxLatZigZagBits + MaxLonZigZagBits) described below

DeltaEncodedGeometry is stored as list of latitude-longitude pairs, relative to previous latitude-longitude starting from given Lat and Lon values. Coordinates deltas are stored as zig-zag values.

NAME chunk

Names are organized as blocks and the name blocks are represented using the following structure:

Field Bits Comment
BlockCount 32
BlockOffsets (BlockCount+1)*64 chunk-relative offsets
Block1 (variable) described below
Block2 (variable)
... ...

Note that the number of block offsets is block count + 1. The last offset denotes the offset just past the last block. Individual geometry blocks are defined as follows:

Field Bits Comment
MaxLengthBits 6
NameCount 32
Name (variable) described below

Each name is stored as UTF8 string with the following schema:

Field Bits Comment
Length MaxLengthBits
Value Length * 8 UTF8 encoding

LINK chunk

This section contains information about other packages and nodes (global nodes) in these packages. Global nodes are organized as blocks and the blocks are represented using the following structure:

Field Bits Comment
BlockCount 32
BlockOffsets (BlockCount+1)*64 Chunk-relative offsets
Block1 (variable) described below
Block2 (variable)
... ...

Each individual global node block is encoded as follows:

Field Bits Comment
MaxPackageNameBits 6
MaxPackagesPerNodeBits 6
MaxGlobalNodeBlockBits 6
MaxGlobalNodeIndexBits 6
PackagesCount 32
Package1 (variable) described below
Package2 (variable)
... ...
GlobalNodeCount 32
GlobalNode1 (variable) described below
GlobalNode2 (variable)
... ...

Each Package is encoded as follows:

Field Bits Comment
NodePackagesCount MaxPackagesPerNodeBits
NodePackage1 (variable) described below
NodePackage2 (variable)
... ...

NodePackage is defined as follows:

Field Bits Comment
PackageNameLength MaxPackageNameBits
PackageName PackageNameLength * 8 UTF8 encoding

PackageName here is different from package id and includes versioning information. It is just used for linking multiple packages together.

Each GlobalNode is encoded as follows:

Field Bits Comment
PackageIndex MaxPackagesPerNodeBits referers to previous packages table
BlockIndex MaxGlobalNodeBlockBits
NodeIndex MaxGlobalNodeIndexBits

RTRE chunk

This chunk contains R-Tree with references to graph nodes. It is used to quickly locate nearest nodes based on spatial coordinates. Like the rest of chunks, R-Tree is defined as blocks:

Field Bits Comment
BlockCount 32
BlockOffsets (BlockCount+1)*64 Chunk-relative offsets
Block1 (variable) described below
Block2 (variable)
... ...

Each block has the following structure:

Field Bits Comment
MaxRTreeBlockBits 6
MaxRTreeIndexBits 6
MaxNodeBlockBits 6
MaxSizeBits 6
MaxLatDiffBits 6
MaxLonDiffBits 6
MaxLatDiffBits2 6
MaxLonDiffBits2 6
MinLat 32
MinLon 32
NodeCount 32
Node1 (variable) described below
Node2 (variable)
... ...

Each node is defined as follows:

Field Bits Comment
Leaf 1 1 if this is a leaf node
Count MaxSizeBits
Elem1 (variable) described below
Elem2 (variable)
... ...

If Leaf=1, then the following structure is used for elements:

Field Bits Comment
Lat0 MaxLatDiffBits relative to MinLat
Lon0 MaxLonDiffBits relative to MinLon
Lat1 MaxLatDiffBits2 relative to Lat0
Lon1 MaxLonDiffBits2 relative to Lon0
NodeBlockId MaxNodeBlockBits

Note that leaf nodes refer to node blocks, not individual nodes. This is a deliberate tradeoff in reduced space vs increased runtime.

If Leaf=0, then the following structure is used:

Field Bits Comment
Lat0 MaxLatDiffBits relative to MinLat
Lon0 MaxLonDiffBits relative to MinLon
Lat1 MaxLatDiffBits2 relative to Lat0
Lon1 MaxLonDiffBits2 relative to Lon0
RTreeNodeBlockId MaxRTreeBlockBits
RTreeNodeIndexId MaxRTreeIndexBits
Clone this wiki locally