Graph Tile structure #5469

culebron-ala · 2025-08-22T09:46:02Z

culebron-ala
Aug 22, 2025

I'm trying to read shapes of the edges in graph tiles. I parsed the graph tile struct, and have the offsets (edge_info_offset, and directed edges count). I wonder what goes where in the edge structs -- Directed edge, or edge info?

I see directededge.h has a 25-bit offset of the edgeinfo struct. Does this mean DirectedEdges go first, then at some offset, there are EdgeInfos?

I wonder where do DirectedEdges begin in the file?

Answered by kinkard

Aug 22, 2025

A small project of mine does C++-to-Rust bindings and I've started it to solve exactly same problem - https://github.com/kinkard/valhalla-rs

View full answer

culebron-ala · 2025-08-22T11:26:36Z

culebron-ala
Aug 22, 2025
Author

I made a calculation of the size of the header, and wonder if it's correct, and if my assumptions are correct.

As I understand, the data should be like this:

Graph Tile Header. ? bytes.
inside the graph tile header struct, there are following counts:

number of nodes
number of directed edges
...some more counts

I conclude that nodes follow the header and then the directed edges.

If I understand correctly, edge infos start and a given offset, and in each directed edge, there's the offset to its edge info, and therein lies the shape. Am I correct?

My only problem with the sizes right now is that in my calculations the header ends being 272 bytes, rather than a round number.

Please, tell me, what did I get wrong?

0 
	graph_id, uint, 46
	46 density?, uint, 4
	50 name quality, uint, 4
		54 speed quality, uint, 4
	58 exit quality, uint, 4
	62 has elevation, bool, 1
	63 has ext directed edge, bool, 1 => 64 / 8 = 8

8 lat lon 8 => 16
16 max version size  16 => 32
32 dataset id 8 => 40

40
	number of nodes 21i
	number of directed edges 21i
	number of predictive speed records 21i
	spare 1i => 64/8 = 8 => 48
48
	transition count (transitions in nodes) 22
	spare 10 => 4 => 52 

52 turn lane count 21 spare 11 = 32/4 = 4 => 56

56 
	transfer count 16,
	spare 7 => 23
	departure count 24 => 47
	stop count 16 => 63
	spare 1 => 64 

64
	sign count 24
	spare 16
	access_restriction_count 24 = 8 => 72
72

	admin count 16
	spare 24 => 40/8 = 5!!!!!
    (having read the comments in .h, and looking at the binary data of a tile, 
    I figured out this spare must be 8 bytes. Hence, sparewords start at 80.)

80
	sparewords 128/8=16

96 complex restriction forward offset 4
100 complex restriction backward offset 4
104 edge info offset 4
108 text list offset 4

112 date created 4
116 k bin count 4*25 = 100 => 216
216 lane connectivity offset 4
220 predicted speeds offset 4
224 tile size 4
228 empty slots 4*11=>44 => 272???

I actually read tile size (bytes 224-228), and in every tile I checked, it's exactly the same as the file size. So, all data up to 228 is correct. The question is why are the empty slots so oddly aligned?

0 replies

kinkard · 2025-08-22T12:55:11Z

kinkard
Aug 22, 2025
Collaborator

DirectedEdge contains hot edge information that is used in graph expansion, while EdgeInfo contains cold edge information that is used when path was found. They have a bit different structure - DirectedEdge is fixed size, while EdgeInfo is not.

valhalla/valhalla/baldr/graphtile.h

Lines 802 to 803 in 59ad155

    
           // List of directed edges. Fixed size structure indexed by Id within the tile. 
        
           DirectedEdge* directededges_{};

valhalla/valhalla/baldr/graphtile.h

Lines 850 to 852 in 59ad155

    
           // List of edge info structures. Since edgeinfo is not fixed size we 
        
           // use offsets in directed edges. 
        
           char* edgeinfo_{};

There is a good graph reading example in the code base as well:

valhalla/src/mjolnir/way_edges_processor.cc

Lines 31 to 60 in d59ce43

    
           for (auto edge_id : reader.GetTileSet()) { 
        
             // If tile does not exist, skip 
        
             if (!reader.DoesTileExist(edge_id)) { 
        
               continue; 
        
             } 
        
             // Trim reader if over-committed 
        
             if (reader.OverCommitted()) { 
        
               reader.Trim(); 
        
             } 
        
             baldr::graph_tile_ptr tile = reader.GetGraphTile(edge_id); 
        
             for (uint32_t n = 0; n < tile->header()->directededgecount(); n++, ++edge_id) { 
        
               const baldr::DirectedEdge* edge = tile->directededge(edge_id); 
        
               // Skip transit, connection, and shortcut edges 
        
               if (edge->IsTransitLine() || edge->use() == baldr::Use::kTransitConnection || 
        
                   edge->use() == baldr::Use::kEgressConnection || 
        
                   edge->use() == baldr::Use::kPlatformConnection || edge->is_shortcut()) { 
        
                 continue; 
        
               } 
        
               // Skip if the edge does not allow auto use 
        
               if (!(edge->forwardaccess() & baldr::kAutoAccess)) { 
        
                 continue; 
        
               } 
        
               // Get the way Id and store edge information 
        
               uint64_t wayid = tile->edgeinfo(edge).wayid(); 
        
               ways_edges[wayid].push_back({edge->forward(), edge_id});

There are several projects that did a bit of reverse engineering and where you can read Valhalla's tile structure if C++ is too obscure, for example https://github.com/stadiamaps/valinor/blob/main/valhalla-graphtile/src/graph_tile/directed_edge.rs#L252
Although, C++-to-your-language bindings would probably work better because from time to time some previously unused hot bits receive new use cases...

3 replies

culebron-ala Aug 22, 2025
Author

Oh, thanks a lot! I may just take Rust implementation and use it, at least for now I need just a dirty prototype.

kinkard Aug 22, 2025
Collaborator

A small project of mine does C++-to-Rust bindings and I've started it to solve exactly same problem - https://github.com/kinkard/valhalla-rs

Answer selected by culebron-ala

ianthetechie Aug 22, 2025

Yeah, I just saw your project recently too @kinkard; very cool!

Glad to see more rust projects and tooling in the ecosystem!

culebron-ala · 2025-08-28T11:45:17Z

culebron-ala
Aug 28, 2025
Author

Follow up question: I read how you decode the shape, and can't figure out:

Is it just a vec of pairs of 32-bit integers? (I read in the comments that there's no end mark in it.)
What kind of value should encoded shape size have? I get values like 11, 12, 51, etc. I thought that it's number of vetice in the LineString, but in the Rust code I see it's actually the shape slice size. I wonder if they must be multiple to 4 or 8 bytes.

3 replies

culebron-ala Aug 28, 2025
Author

I managed to get the rust code running and see the edges and their shapes. A 16-bytes shape (my reverse-engineered code has read it correctly as [167, 210, 207, 7, 153, 253, 182, 33, 225, 2, 205, 3, 205, 1, 141, 2]), contains linestring of 3 coordinates: LINESTRING(-35.053388999999996 -7.992468,-35.053619999999995 -7.9926449999999996,-35.053754999999995 -7.992748).

So, it's variable-length ints. I've written such encoding-decoding myself earlier.

kinkard Aug 28, 2025
Collaborator

Great that you were able to solve this mystery on your own! If you want to learn more about the polyline5 and polyline6 format please consider this doc from the format authors - https://developers.google.com/maps/documentation/utilities/polylinealgorithm

There also a few open source tools to visualise such polyline5/6 encoded shapes, for example https://valhalla.github.io/demos/polyline/

Btw, not checking for the end of shape during decoding might lead to really bad errors. One should consider handling this error or simply dropping the mailformed tail. There are plenty of Rust crates that follow one or another approach.

culebron-ala Aug 28, 2025
Author

yes, I have implemented the same encoding myself.

culebron-ala · 2025-08-29T09:32:29Z

culebron-ala
Aug 29, 2025
Author

Got it working, thanks a lot for your help, @kinkard!

0 replies

Graph Tile structure #5469

Uh oh!

Uh oh!

culebron-ala Aug 22, 2025

Replies: 4 comments · 6 replies

Uh oh!

Uh oh!

culebron-ala Aug 22, 2025 Author

Uh oh!

Uh oh!

kinkard Aug 22, 2025 Collaborator

Uh oh!

Uh oh!

culebron-ala Aug 22, 2025 Author

Uh oh!

kinkard Aug 22, 2025 Collaborator

Uh oh!

ianthetechie Aug 22, 2025

Uh oh!

Uh oh!

culebron-ala Aug 28, 2025 Author

Uh oh!

Uh oh!

culebron-ala Aug 28, 2025 Author

Uh oh!

kinkard Aug 28, 2025 Collaborator

Uh oh!

culebron-ala Aug 28, 2025 Author

Uh oh!

culebron-ala Aug 29, 2025 Author

culebron-ala
Aug 22, 2025

Replies: 4 comments 6 replies

culebron-ala
Aug 22, 2025
Author

kinkard
Aug 22, 2025
Collaborator

culebron-ala Aug 22, 2025
Author

kinkard Aug 22, 2025
Collaborator

culebron-ala
Aug 28, 2025
Author

culebron-ala Aug 28, 2025
Author

kinkard Aug 28, 2025
Collaborator

culebron-ala Aug 28, 2025
Author

culebron-ala
Aug 29, 2025
Author