consider making the road network a combination of a graph and datascript

[carocad]

Currently our graph representation is a single Datascript atom with both OSM and GTFS data.

Although this allowed us to treat all pieces of information the same, it also made it more complicated to understand from an outsider perspective.

Most graph representation representations use

• map of id -> node
• node -> edges
• edges -> meta, node

This is a standard, AdjacencyList model.

We used to use that model but dropped it in favor of Datascript since it was easier to think of it all as a single unit. This works in general but given the size of some GTFS feeds, we were forced to give up most of its usefulness in enchange for speed.

Given that most of its usefulness is gone in favor of speed, I think we should consider switching back to a combined AdjacencyList + Datascript model.

This should also make it easier for external contributors to understand our code base as it would use a standard approach for routing.

Our previous implementation used to take around 50 ms for pedestrian routing in Saarland. The current one takes around 200 ms for the same.

see benchmark history: https://github.com/hiposfer/kamal/commits/master/resources/benchmark.txt

PROBLEMS:

• how to find the nearest neighbour without looping over the complete graph?
• where to store the ways?
• where to store the relation between ways and nodes?

[carocad]

NOTE: see history around https://github.com/hiposfer/kamal/commits/42fdc64f2f43f8a62d135ef797c2650a5322207b

[carocad]

IDEA:

instead of making them a combination. We can create an graph like before that simply mirrors the data in datascript.

This way we get the best of both worlds:

• fast queries through a standard graph implementation
• queryable and organized data through datascript