Date: 2026-06-05
Time: 13:49
google-maps/map_routing.py — Map Routing ServiceThis file implements a map routing service — the core pathfinding engine behind a Google Maps-style system design. It owns the responsibility of modeling a road network as a weighted graph and computing routes through it, including shortest-path queries, alternative routes, ETA estimation, turn-by-turn directions, and basic map tile serving. It's a self-contained single-file implementation designed to demonstrate the key algorithmic and architectural concepts you'd discuss in a system design interview for Google Maps.
Four @dataclass types define the domain:
Node — An intersection or waypoint, identified by node_id with geographic coordinates (lat, lon) and an optional name for geocoding.Edge — A road segment connecting two nodes. Carries distancekm, speedlimitkmh (default 50), and a oneway flag. Note: Edge is only used as input to add_edge — internally the service stores edge data as plain dicts.RouteStep — A single instruction in turn-by-turn directions (e.g., "Turn right onto Main St").Route — The complete result: a list of RouteSteps, aggregate distance/duration, and the raw node path._haversine(lat1, lon1, lat2, lon2) — Computes great-circle distance in km between two points. Used as the A* heuristic and is critical for heuristic admissibility — haversine never overestimates road distance since roads can't be shorter than the straight-line distance._bearing(lat1, lon1, lat2, lon2) — Computes compass bearing in degrees (0–360) between two points. Used to determine turn directions at intersections.turninstruction(bearing_change) — Maps a bearing delta to one of three instructions: "Continue straight" (±30°), "Turn right" (>30°), or "Turn left" (<-30°). The threshold of 30° is a simplification — real systems use finer buckets (slight left, sharp right, U-turn).MapServiceThe main class. Three internal data structures:
| Field | Type | Role |
|-------|------|------|
| self.nodes | dict[str, Node] | Node lookup by ID |
| self.adj | dict[str, dict[str, dict]] | Adjacency list — adj[u][v] is edge data dict |
| self.geocode_map | dict[str, tuple] | Name-to-coordinates index (lowercased) |
Graph construction:
add_node(node) — Registers a node, initializes its adjacency entry, and indexes its name for geocoding.addedge(edge) — Adds the edge to the adjacency list. If not oneway, adds both directions with identical data — the same dict object is shared, which means both directions always have the same speed limit and distance.Pathfinding:
getweight(edge_data, optimize) — Dual-mode weight function. For "time", returns travel time in minutes (distance / speed * 60). For anything else (including "distance"), returns raw km.heuristic(nodeid, goal_id, optimize) — A* heuristic. For distance optimization, it's just haversine. For time optimization, it divides haversine distance by the global maximum speed limit — this ensures admissibility but can be a weak heuristic on networks with heterogeneous speed limits.findpath(startid, endid, algorithm, optimize, blockededges) — The core search. Implements both Dijkstra (algorithm != "astar") and A* (default) via a priority queue. The blockededges parameter supports Yen's algorithm by excluding specific directed edges. Returns (path, cost) or (None, None).shortestpath(startid, endid, ...) — Public API wrapping findpath + build_route.Alternative routes:
alternativeroutes(startid, end_id, k=3) — Implements Yen's K-shortest paths algorithm. Iteratively finds the next-shortest path by blocking edges from previously-found paths at each spur node, then selecting the shortest candidate from a heap. Always optimizes for distance (hardcoded).Route construction:
buildroute(path, optimize) — Converts a raw node-ID path into a Route with turn-by-turn RouteSteps. The first step always says "Head onto {road}". Subsequent steps compute bearing changes between consecutive triplets of nodes to determine turns. If the road name hasn't changed and the bearing is straight, it coalesces into a "Continue on" instruction.Supporting features:
eta(startid, endid) — Convenience method: finds the time-optimized route and returns duration in minutes.getdirections(startid, end_id) — Returns just the RouteStep list from the distance-optimized route.gettile(lat, lon, tilesize=0.01) — Returns all nodes/edges within a rectangular tile. The tile is axis-aligned and defined by flooring the input coordinates to tile_size increments. This models the concept of map tile serving for rendering.geocode(name) — Case-insensitive name lookup returning {lat, lon, node_id}.1. Graph as adjacency dict — Rather than a formal graph class, the road network is a nested dict (adj[u][v] = {roadname, distancekm, speedlimitkmh}). This is the standard Python idiom for weighted directed graphs and keeps edge lookup O(1).
2. Strategy pattern via optimize parameter — The weight function and heuristic both branch on optimize, allowing the same algorithm to serve both shortest-distance and fastest-time queries without code duplication.
3. Yen's algorithm for K-shortest paths — A well-known algorithm choice for alternative routes. The implementation blocks edges (not nodes) from previously found paths, which is the edge-disjoint variant.
4. Input types vs. internal representation — Edge dataclass is used only at the API boundary (add_edge). Internally, edges are plain dicts. This avoids coupling internal traversal to the input schema.
5. Dual-mode A*/Dijkstra — The heuristic is conditionally zero, which collapses A* to Dijkstra. One code path, two algorithms.
Imports: Only standard library — heapq for the priority queue, math for trig/geo calculations, dataclasses for the data models. No external dependencies.
Imported by: testmaprouting.py — the test suite. No other modules in the repo depend on this.
A typical usage sequence:
1. Build graph: Call addnode() for each intersection, then addedge() for each road segment.
2. Query a route: Call shortest_path("A", "B", optimize="time").
findpath runs A* using the priority queue, expanding nodes by lowest g(n) + h(n).prev dict.buildroute walks the path, looks up each edge, computes bearings between consecutive node triplets, and generates RouteStep instructions.3. Alternative routes: alternative_routes("A", "B", k=3) iterates: for each prefix of the best path, it blocks the edge that was taken and re-runs A* from the spur node. Candidate paths are kept in a min-heap sorted by total distance.
heuristic never overestimates true cost. For distance, haversine ≤ road distance (triangle inequality on a sphere). For time, haversine / maxspeed ≤ actual travel time (using the fastest possible speed as the divisor).one_way=True, every road is traversable in both directions with identical cost.findpath returns (None, None) on failure: Both unreachable destinations and missing node IDs produce the same sentinel. Callers must null-check.buildroute rounds totals to 10 decimal places: round(total_dist, 10) — this avoids floating-point drift in cumulative sums while preserving precision.Error handling is minimal and follows the "return None" convention:
findpath returns (None, None) if start or end node isn't in self.nodes. No exception raised.(None, None) is returned.shortestpath returns None if pathfinding fails. Callers (like eta) must check: route.totalduration_min if route else None.get_directions returns [] on failure.getweight), or self-loop edges. The code trusts its callers.geocode returns None for unknown names.There are no exceptions raised anywhere in this module — all failures are communicated via None or empty collections.
google-maps/testmaprouting.py — See how the road network is constructed in tests and what edge cases are covered (disconnected graphs, one-way streets, alternative routes)google-maps/maprouting.py:alternativeroutes — Yen's K-shortest paths has subtle correctness requirements around edge blocking and spur node selection; worth verifying against the reference algorithma-star-heuristic-tightness — The time-optimized heuristic uses global max speed, which can be very loose on mixed-speed networks; explore how contraction hierarchies or ALT heuristics improve thisgoogle-maps/plan.md — The design plan likely discusses system-level concerns (tile serving, caching, partitioning) that this implementation simplifies awayyen-vs-penalty-method — Alternative route algorithms: Yen's finds K-shortest, but real map apps use penalty-based or plateau methods to find *meaningfully different* routes, not just slightly different onesastar-heuristic-admissible — The A* heuristic is admissible: distance mode uses haversine (always ≤ road distance), time mode uses haversine divided by the global maximum speed limit (always ≤ actual travel time)find-path-returns-none-pair-on-failure — findpath returns (None, None) for both missing nodes and unreachable destinations; it never raises exceptionsbidirectional-edges-share-same-dict — When one_way=False, both directions of an edge reference the same data dict, so modifying one direction's data mutates the otheralternative-routes-always-optimizes-distance — alternative_routes hardcodes optimize="distance" for both the initial path and all spur paths, ignoring any time-based optimizationgeocode-last-writer-wins — If multiple nodes share the same name, only the last one added is retained in the geocode index; earlier entries are silently overwritten