If you find this interesting, definitely consider checking out contraction hierarchies. One of the early algorithms used by mapping software to enable calculating fastest routes between any pair of places. It's exact, and it's orders of magnitude faster than graph search algorithms like Dijkstra.<p>This webpage has a very intuitive graphical explanation of how it works: <a href="https://www.mjt.me.uk/posts/contraction-hierarchies/" rel="nofollow">https://www.mjt.me.uk/posts/contraction-hierarchies/</a><p>(I had the joy of implementing this in Python with OSM data a few years ago. Planning a three hour car trip with software I wrote and having it come back with the same path recommended by Google Maps in a matter of milliseconds was a very rewarding feeling.)
Nice. Very light-weight compared to proper local routers like Graphhopper, OSRM, etc., which can be overkill for simple tasks. Although the 'routing' here is nx.shortest_path, which is just Dijkstra, so pretty slow compared to other easy to implement routing algorithms (even just bi-directional Dijkstra or A*... although contraction hierarchies would be huge gain here since edge weights are fixed). Also not sure why readme describes it as an approximation? Dijkstra is guaranteed to return lowest cost path. Maybe approximation because assuming free-flow, or if the NAR dataset is incomplete?
From poking around in the source code I found this 282M SQLite database:<p><pre><code> wget https://services.arcgis.com/xOi1kZaI0eWDREZv/arcgis/rest/services/NTAD_North_American_Roads/FeatureServer/replicafilescache/NTAD_North_American_Roads_3862439624850511818.geodatabase
</code></pre>
I can't figure out how to read it though. I get this error:<p><pre><code> Connection to NTAD_North_American_Roads_3862439624850511818.geodatabase failed check: no such module: VSRS
</code></pre>
As far as I can tell VSRS is a proprietary Esri thing.
Nice. Clean and lightweight compared to full routing stacks like OSRM or Graphhopper, which can be a bit much for smaller/local tasks. Curious why the README calls it an "approximation" though — Dijkstra gives exact shortest paths unless you're simplifying inputs. Maybe that's referring to free-flow assumptions or limitations in the underlying network data? Still, cool to see a focused US-only tool.
Edit: thanks very much for the suggestions, especially adding the Python version to the uv command line. I totally missed that, and that totally fixed it. Apologies for the OT tech support derailment.<p>--------------<p>Question for those familiar with uv. US Routing apparently requires a very specific Python version (3.11 and nothing else), but my system has Python 3.10.9 installed at the moment and I'd rather not upgrade the global version just now. My understanding from reading a lot of uv evangelism on HN and elsewhere is that uv fixes this type of dilemma. But, having just tried to use it to install this package, it's just giving me the same old Python version errors:<p><pre><code> C:\devel\us-routing-master\us_routing>uv venv
Using CPython 3.10.9 interpreter at: c:\WinPython-31090
\python-3.10.9.amd64\python.exe
Creating virtual environment at: .venv
Activate with: .venv\Scripts\activate
C:\devel\us-routing-master\us_routing>.venv\Scripts\activate
(us_routing) C:\devel\us-routing-master\us_routing>uv pip
install us-routing
x No solution found when resolving dependencies:
`-> Because the current Python version (3.10.9) does not
satisfy Python>=3.11,<3.12 and us-routing==0.1.0
depends on Python>=3.11,<3.12, we can conclude that us-
routing==0.1.0 cannot be used.
And because only us-routing==0.1.0 is available and you
require us-routing, we can conclude that your
requirements are unsatisfiable.
</code></pre>
Am I misunderstanding the whole uv thing, or just doing something wrong? Or is us-routing somehow incompatible with it?