Routing¶

Yoro Maps provides offline routing on an OSM road graph using the A* algorithm.

How routing works¶

Nearest node lookup — Given start/end GPS coordinates, the router finds the closest graph node using an expanding bounding-box search.
A search* — The algorithm explores the graph using a priority queue, with the haversine straight-line distance as the heuristic.
Path reconstruction — Once the destination is reached, the path is traced back through the came_from map.
Result building — The router builds a GeoJSON LineString geometry and turn-by-turn navigation steps.

Route between coordinates¶

import yoromaps

conn = yoromaps.open_db("mali.yoromaps")
result = yoromaps.route(
    conn,
    start_lat=12.6392,
    start_lon=-8.0029,
    end_lat=14.4974,
    end_lon=-4.0077,
)

if result.found:
    print(f"Distance: {result.distance_km} km")
    print(f"Duration: {result.duration_min} min")
    print(f"Nodes:    {len(result.nodes)}")
else:
    print("No route found")

Route between Yoro codes¶

Yoro codes are decoded to GPS coordinates using the yoro library, then routed:

import yoromaps

conn = yoromaps.open_db("mali.yoromaps")
legs = yoromaps.route_from_codes(conn, ["ML-ABC", "ML-XYZ"])

for i, leg in enumerate(legs):
    print(f"Leg {i + 1}: {leg.distance_km} km, {leg.duration_min} min, found={leg.found}")

Multi-leg routes¶

Pass more than 2 codes to get multiple legs:

legs = yoromaps.route_from_codes(conn, ["ML-AAA", "ML-BBB", "ML-CCC", "ML-DDD"])
# Returns 3 legs: AAA->BBB, BBB->CCC, CCC->DDD

total_km = sum(leg.distance_km for leg in legs)
total_min = sum(leg.duration_min for leg in legs)
print(f"Total: {total_km} km, {total_min} min")

CLI routing¶

# Two-point route
yoromaps route mali.yoromaps ML-ABC ML-XYZ

# Multi-leg route
yoromaps route mali.yoromaps ML-AAA ML-BBB ML-CCC

Output is JSON:

{
  "total_distance_km": 642.3,
  "total_duration_min": 578.1,
  "legs": [
    {
      "distance_km": 642.3,
      "duration_min": 578.1,
      "found": true,
      "steps": [
        {"instruction": "Continue on Route Nationale 6", "distance_m": 12340, "name": "Route Nationale 6"},
        {"instruction": "Arrive at destination via RN1", "distance_m": 8500, "name": "RN1"}
      ]
    }
  ]
}

RouteResult object¶

The route() function returns a RouteResult dataclass:

Field	Type	Description
`distance_km`	`float`	Total distance in kilometers
`duration_min`	`float`	Estimated travel time in minutes
`nodes`	`list[int]`	List of graph node IDs along the route
`geometry`	`dict`	GeoJSON LineString with the route coordinates
`steps`	`list[dict]`	Turn-by-turn navigation instructions
`found`	`bool`	Whether a route was found (default `True`)
`from_snap_m`	`float`	Haversine distance (m) from start GPS to its snapped graph node
`to_snap_m`	`float`	Haversine distance (m) from end GPS to its snapped graph node
`from_road`	`str`	Name of the first road of the path, `""` when it has none
`to_road`	`str`	Name of the last road of the path, `""` when it has none
`mode`	`str`	How the journey was travelled

Points that are not on a road¶

Almost none are. A doorway, a stall, a spot in a park: the router joins each end of the journey to the nearest road the mode may actually use, which is not the same as the nearest road. A car standing in a park is not joined to the footpath at its edge — no car may leave a footpath, and a search starting there has nowhere to go, which used to come back as "no route" with the boulevard two hundred metres away.

The walk between the point and that road is part of the answer rather than something dropped on the floor:

from_snap_m / to_snap_m say how far it is;
from_road / to_road say what it leads to and comes back from;
geometry begins and ends at the coordinates you asked about, joined to the road by a straight stub — the direction to walk, not a routed path, because there is no data for the ground it crosses;
the first and last steps carry "access": True so a client can tell the walk apart from the driving.

Stubs shorter than 20 m (routing.ACCESS_LEG_M) are dropped: at that distance they are a wiggle on the end of the line rather than information.

When a search fails, one end is re-snapped past the piece of road it landed on, if that piece turns out to be an isolated stub — OpenStreetMap is full of tracks behind compounds that nobody joined to the street, and a journey should not be refused over twelve unmapped segments. The re-snap will not move an end more than 2 km (routing.MAX_ESCAPE_M): past that it would be answering a different question, and "there is no road between these two places" is a true answer that has to survive.

distance_km and duration_min remain the road's alone. Adding a guess at walking pace to a measured figure would make both unreadable.

GeoJSON output¶

The geometry field is a standard GeoJSON LineString that can be displayed on any map:

import json

result = yoromaps.route(conn, start_lat=12.6, start_lon=-8.0, end_lat=14.5, end_lon=-4.0)

# Save as GeoJSON Feature
feature = {
    "type": "Feature",
    "geometry": result.geometry,
    "properties": {
        "distance_km": result.distance_km,
        "duration_min": result.duration_min,
    },
}

with open("route.geojson", "w") as f:
    json.dump(feature, f)

This GeoJSON can be loaded directly in QGIS, geojson.io, or rendered on a Leaflet map.

Graph object (recommended for multiple routes)¶

The route() convenience function reloads the graph on every call. For applications that compute many routes (e.g. a Django API), load the graph once and reuse it:

import yoromaps

conn = yoromaps.open_db("mali.yoromaps")
graph = yoromaps.Graph.from_db(conn)  # load once (~20s for Mali)

# Route many times — fast
r1 = graph.route(12.639, -8.003, 14.489, -4.197)  # Bamako → Mopti
r2 = graph.route(12.639, -8.003, 11.317, -5.667)  # Bamako → Sikasso
r3 = graph.route(12.63, -8.00, 12.65, -7.98)  # short urban route

In Django, load the graph once at startup:

# apps.py or a module-level singleton
import yoromaps

_graph = None


def get_graph():
    global _graph
    if _graph is None:
        conn = yoromaps.open_db("/data/mali.yoromaps")
        _graph = yoromaps.Graph.from_db(conn)
    return _graph


# views.py
def route_view(request):
    graph = get_graph()
    r = graph.route(lat1, lon1, lat2, lon2)
    ...

Performance (tested on real data)¶

The graph is loaded entirely into memory for fast routing. Tested results:

Mali (6.4M nodes, 6.7M edges)¶

Route	Distance	Duration	Compute time
Bamako → Mopti	551.8 km	11h21	6.3s
Bamako → Sikasso	338.1 km	7h18	2.4s
Bamako → Segou	325.9 km	5h56	2.6s
Bamako → Kayes	501.0 km	10h00	3.4s
Bamako → Tombouctou	812.2 km	20h38	6.6s
Court (Bamako centre)	3.8 km	6 min	0.5s

Graph loading: ~20s. Memory: ~200 MB.

Togo (2.2M nodes, 2.3M edges)¶

Route	Distance	Duration	Compute time
Lome → Kara	411.8 km	4h40	3.0s
Court (Lome centre)	7.4 km	10 min	0.2s

Graph loading: ~7s. Memory: ~100 MB.

Urban routing

Most real-world usage will be intra-city routing (e.g. within Bamako, Ouagadougou, Niamey). These routes are short (<20 km) and compute in under 1 second. Combined with Yoro precision p=19 (~1.35m), this gives door-to-door directions.

Roads missing from OpenStreetMap¶

A deployment can graft roads its users contributed onto a bundle's graph:

from yoromaps import ContributedWay, add_contributed_ways, remove_contributed_ways, stamp_nodes

piste = ContributedWay(
    ref=42,  # your own stable, positive id
    coords=[(12.6000, -8.0000), (12.6001, -7.9900), (12.6000, -7.9800)],  # (lat, lon)
    tags={"highway": "track", "name": "Piste de Kati", "surface": "unpaved"},
)
add_contributed_ways(conn, [piste])
stamp_nodes(conn, "ML")  # codes for the new nodes only

Tags are read exactly as extraction reads OSM ones (one-way, access, surface). A drawn vertex within 15 m of an existing node becomes that node, so the road joins the network. Contributed nodes have negative ids; remove_contributed_ways(conn) takes them all back out, which is how a bundle is re-seeded without being rebuilt.