Purpose: Interactive GIS routing demo that computes shortest paths from any Redlands street intersection to Esri HQ and visualises the result on a real Leaflet/OpenStreetMap map.
Business problem: Demonstrates routing, graph traversal, spatial reasoning, and algorithm engineering patterns used in roads, utilities, logistics, and network-analysis platforms.
Graph data: ~2,500-node, ~3,190-edge road network derived from a dense OpenStreetMap extract for downtown Redlands and the area around Esri HQ. Nodes are actual OSM points with true WGS84 coordinates — real intersections plus curve vertices chosen by deviation-bounded (Douglas–Peucker) simplification, so no edge strays more than ~4 m from the true road — meaning streets, ramps, and freeway curves all trace their real shape and overlay exactly on the base tiles. Esri HQ is the fixed destination. Stored in RedlandsRoadNetwork (Portfolio.Services/Data). Edge costs are the real along-road distance in km (haversine sum over the underlying OSM geometry).
Frontend Architecture
Page:Pages/Projects/Network/Index.cshtml renders a full-viewport two-column shell: a routing panel and a Leaflet map canvas.
Map: Leaflet 1.9 is loaded from CDN; the map is centred on Redlands (34.055, -117.182) at zoom 14. OpenStreetMap provides the base tile layer at no cost.
Edges: Each road segment is rendered as a light-weight polyline on the Leaflet layer before any route is computed, giving an immediately recognisable street-network context.
Nodes: Every graph node renders as a L.circleMarker. Clicking any non-destination node sets it as the route origin, highlighted in blue. The Esri HQ node renders in green at radius 10.
Graph fetch: On page load GET /api/v1/network/graph returns the full RoadGraphDto (~2,500 nodes, ~3,190 edges, ~435 KB). The client holds the graph in memory, renders it on a canvas-backed Leaflet layer, and submits it with each route request, keeping the API stateless.
Search-space overlay: Each route response includes ExploredNodeIds — every node the algorithm settled. The client paints them as a faint dot layer (teal for A*, amber for Dijkstra), so you can see A*'s heuristic-guided beam versus Dijkstra's uniform flood. A "Show search space" switch toggles it.
Origin selection: Click anywhere on the map to snap to the nearest intersection, or pick from the junction-only dropdown. Mid-curve shape vertices are drawn (for road fidelity) but excluded from the picker and turn-by-turn so the UI stays about real intersections.
Route polyline: The result path coordinate array is rendered as a blue L.polyline with drop-shadow filter; the map auto-fits its bounds.
Algorithm toggle: A* or Dijkstra is selected via a radio button group. A* hints explain the haversine heuristic.
Service area: Reachable nodes are highlighted amber; unreachable nodes dim.
GET /api/v1/network/graph: Returns RoadGraphDto — nodes, edges, destinationNodeId, and graphName. Drives the map and populates the origin selector.
POST /api/v1/network/route: Accepts RouteRequestDto (nodes, edges, start/end ids, algorithm). Returns RouteResultDto with path, total cost, explored-node count, distance km, estimated minutes, and algorithm used.
POST /api/v1/network/service-area: Accepts ServiceAreaRequestDto; returns ServiceAreaResultDto with reachable node ids.
Request size limit: 4 MB per request; the graph payload is ~4 KB so there is plenty of headroom for larger graphs.
Error handling: Invalid graphs, missing nodes, negative costs, and non-finite coordinates map to 400 with { "error": "..." }.
Services and Business Logic
Service:SpatialGraphService owns graph validation, algorithm dispatch, and metric enrichment.
Dijkstra (managed): Standard priority-queue shortest-path, O((V + E) log V). Explores all reachable nodes; guaranteed optimal cost.
A* (managed): Uses haversine great-circle distance to the destination node as an admissible heuristic. Explores fewer nodes than Dijkstra on typical road layouts — the exploredNodes metric demonstrates this in the UI.
Native bridge:SpatialGraphNativeBridge delegates Dijkstra to spatial_graph_engine when the native library is loaded. A* is managed-only because the heuristic requires node coordinates at query time.
Metrics:ExploredNodes counts settled queue entries; DistanceKm sums haversine segments along the coordinate path; EstimatedMinutes divides by 40 km/h average road speed.
Graph data:RedlandsRoadNetwork.Build() constructs a ~2,500-node / ~3,190-edge Redlands network as a RoadGraphDto from a dense OpenStreetMap extract (arterials down to residential/local streets) of downtown Redlands and the Esri HQ area. Straight mid-street runs collapse to genuine junctions, while curved runs keep exactly the vertices a Douglas–Peucker pass needs to hold every edge within ~4 m of the true road — so surface streets, on/off ramps, and freeway curves all follow their real geometry instead of cutting across. The graph is reduced to the largest component that can reach Esri HQ — so every selectable origin routes successfully. Labels are the real cross-street names (e.g. "Orange St & Colton Ave") surfaced in the turn-by-turn panel.
Data Access Layer
Current implementation: No database or repository layer. The ~2,500-node Redlands graph is built once and cached in-memory from RedlandsRoadNetwork, then served on every GET /graph request (microseconds).
Design rationale: For a portfolio demo the graph is static. Persisting it adds EF Core migrations with no user benefit; the client-owned stateless model also makes A* and Dijkstra exploration metrics easy to compare side-by-side.
Scale-out path: A production system would persist a preprocessed graph snapshot in PostgreSQL via IGraphRepository; nodes and edges map naturally to two EF Core entities with spatial columns (PostGIS). Route results could be cached in Redis by graph version + origin/destination pair.
OSM import path:libosmium or osmium-tool can extract a city-scale road network from a PBF extract, normalise node ids, and write to the repository. A* preprocessing (landmark-based ALT or contraction hierarchies) would then bring city-wide sub-second routing.
Infrastructure and Deployment
Map tiles: OpenStreetMap tiles load from the public CDN — no API key or billing required for portfolio use.
Leaflet: Loaded from the jsDelivr CDN with SRI integrity hashes.
Native library:native/spatial_graph_engine/CMakeLists.txt builds the shared library and copies it into the .NET output directory. The managed fallback runs automatically when absent.
Hosted on Render: Free tier; PostgreSQL provided by Render's managed PostgreSQL add-on.
AKS / scale-out: Graph data would migrate to Redis or PostgreSQL; tile requests are client-side so there is no server egress cost.
Engineering Decisions and Tradeoffs
Client-owned graph: The client fetches the full ~2,500-node / ~3,190-edge graph once and submits it with each route request. At this scale the JSON payload is ~435 KB — comfortably under the 4 MB request cap. At city scale (millions of edges) the graph would live server-side and the API would accept only start/end node ids.
A* heuristic admissibility: Haversine straight-line distance never exceeds the real along-road edge cost, so the heuristic is admissible and A* is optimal. The difference in explored-node count between A* and Dijkstra is measurable and visible in the KPI panel.
Offline OSM ingest vs. live curation: The network is preprocessed once from an OpenStreetMap extract — arterials are filtered, mid-street nodes contracted to true junctions, and the result reduced to the component reachable to Esri HQ. This keeps the demo graph honest against the base map while staying small enough to ship to the client each request.
Undirected model: Each OSM road segment is modelled as a bidirectional edge, so both algorithms operate on an undirected graph. Modelling real one-way restrictions and turn penalties from OSM oneway/turn-restriction tags is a natural next step.
No authentication: Routing is anonymous; the Esri HQ destination is fixed. A production system might require OAuth and support user-defined destinations, saved routes, and route history.
Explored-nodes metric: Surfacing this in the KPI panel is intentional — it lets the interviewer ask "why does A* explore fewer nodes?" and drives an on-the-spot discussion of graph search theory.
Interview Discussion Points
Why is A* optimal when using the haversine heuristic? What makes a heuristic admissible?
How would you scale this to city-wide routing over millions of nodes? (Contraction hierarchies, ALT preprocessing, partition-based methods.)
How would you snap an arbitrary map click to the nearest road edge, not just the nearest node?
What changes if you need time-dependent routing (rush-hour speeds)?
How would you store and version a road graph in PostgreSQL to support live edits and cache invalidation?
Why keep the managed C# fallback even after adding native C++ routing?