Refactor graph code

[dabreegster]

This isn't really related to Sev Snape, I'm just exploring this idea here first.

I'm duplicating lots of backend code between projects to turn OSM data into a graph, do point-to-point routing, and floodfill / calculate isochrones. Some projects are starting to need multiple modes as well, like a-b-street/severance_snape#18 here. If there was something more generic, what would it look like?

Requirements

• https://github.com/a-b-street/severance_snape
  • NodeMap, Mercator, and Tags already definitely common
  • RoadID and IntersectionID types, array lookups
  • Snap a point to nearest intersection (or road)
  • Isochrone floodfill, giving costs per road
  • Calculating a boundary polygon and showing inverted form
  • Bounds of area
  • The roads/intersection structs need the basic graph info, and the geometry. Also track OSM provenance. Then some custom stuff.
  • A-to-B routing with a CH. Custom cost functions, of course. Managing the PathCalculator caching. Plenty of custom code, but at least a higher-level way to get the semantic road edges back would be nice.
  • Scraping OSM is definitely shareable. split_edges particularly.
  • Geometry is stored in Mercator, always transformed back in WASM
• https://github.com/a-b-street/ltn
  • Much more complex; stores multiple routers (the CH itself, node map, closest intersection mapping (but that shouldn't really be there))
  • Also Mercator geometry
  • Otherwise pretty similar, feels like much could be shared
• https://github.com/a-b-street/osm2streets/
  • Doesn't use raw geo now, but should ideally
  • Does complex graph manipulations now, but maybe shouldn't
  • Has this complex planar blockfinding routine, which could be generally useful?
• https://github.com/Urban-Analytics-Technology-Platform/od2net
  • The most different. Meant to be used over huge areas
  • So geometry is kept in WGS84
  • Doesn't invent IDs; raw OSM IDs are used. So the edge object doesn't have a node1 and node2, because the key has it
  • Extremely custom cost functions for routing
  • The detailed route output could use help gluing together geometry maybe, but the core routing logic is deliberately quite custom and barebones
• Could also be used in this nascent 15m revival tool idea
• Maybe could help with part of https://github.com/alan-turing-institute/acbm

[dabreegster]

A first idea

Just start very concretely by refactoring code in this project, see if it helps substantially, and then try using in the LTN tool also.

[dabreegster]

Decided to take a simpler approach to start. Instead of serving up a generic graph, just make some common functions that can be used. It's the caller's responsibility to transform the resulting structs into their own objects. Embedding custom data made the final code less structured, and the scraping was simple only for sev snape, not LTN

[dabreegster]

Could consider using in:

• [ ] https://github.com/acteng/atip-data-prep/blob/main/gradient/src/main.rs
• [ ] od2net (ignoring or disabling the mercator transform)
• [ ] https://github.com/dabreegster/route_snapper/blob/d65a21d321db651616a3cb6e76cbfb0f7e2adb0d/osm-to-route-snapper/src/lib.rs#L83