Spaces:
Sleeping
Sleeping
| """Independent reference engine: Connection Scan Algorithm (CSA). | |
| A deliberately *different* algorithm from RAPTOR — it sweeps a single | |
| time-ordered list of elementary connections instead of scanning routes in | |
| rounds. Over the same network it must yield identical earliest-arrival labels, | |
| so it's used by scripts/validate.py to cross-check RAPTOR for correctness. | |
| Not used in production; clarity over speed. | |
| """ | |
| from __future__ import annotations | |
| from config import MAX_ACCESS_WALK_MIN, WALK_SPEED_MPS | |
| from engine.model import Network | |
| from engine.raptor import ROUTE_TYPE_MODE, _access_straight, _access_walk | |
| INF = 10 ** 12 | |
| def build_connections(net: Network): | |
| """Flatten every trip into elementary connections, sorted by departure. | |
| Returns parallel arrays (dep_time, dep_stop, arr_time, arr_stop, mode). | |
| Static for a network, so build once and reuse across queries. | |
| """ | |
| dep_t, dep_s, arr_t, arr_s, mode = [], [], [], [], [] | |
| for route in net.routes: | |
| m = ROUTE_TYPE_MODE.get(route.route_type, "bus") | |
| stops = route.stops | |
| for ti in range(route.n_trips): | |
| dep = route.dep[ti] | |
| arr = route.arr[ti] | |
| for i in range(len(stops) - 1): | |
| dep_t.append(dep[i]) | |
| dep_s.append(stops[i]) | |
| arr_t.append(arr[i + 1]) | |
| arr_s.append(stops[i + 1]) | |
| mode.append(m) | |
| order = sorted(range(len(dep_t)), key=lambda k: dep_t[k]) | |
| return ( | |
| [dep_t[k] for k in order], | |
| [dep_s[k] for k in order], | |
| [arr_t[k] for k in order], | |
| [arr_s[k] for k in order], | |
| [mode[k] for k in order], | |
| ) | |
| def _bisect_dep(dep_t, value): | |
| lo, hi = 0, len(dep_t) | |
| while lo < hi: | |
| mid = (lo + hi) // 2 | |
| if dep_t[mid] < value: | |
| lo = mid + 1 | |
| else: | |
| hi = mid | |
| return lo | |
| def csa_isochrone(net, connections, origin_lat, origin_lon, departure_sec, budget_sec, | |
| allowed_modes=None, walk_graph=None): | |
| """Earliest-arrival labels via Connection Scan. Returns {stop_index: arrival}.""" | |
| dep_t, dep_s, arr_t, arr_s, c_mode = connections | |
| n = net.n_stops | |
| cutoff = departure_sec + budget_sec | |
| arr = [INF] * n | |
| # access (identical to RAPTOR): the first walk may use the whole budget | |
| access_sec = min(budget_sec, MAX_ACCESS_WALK_MIN * 60) | |
| access = [] | |
| if walk_graph is not None: | |
| access = _access_walk(walk_graph, origin_lon, origin_lat, access_sec) | |
| if not access: | |
| access = _access_straight(net, origin_lat, origin_lon, access_sec * WALK_SPEED_MPS) | |
| for s, walk_sec in access: | |
| t = departure_sec + int(walk_sec) | |
| if t < arr[s] and t <= cutoff: | |
| arr[s] = t | |
| # (no footpaths from access stops — walk access is already complete; transfers | |
| # are single-hop and applied only after a transit connection, matching RAPTOR) | |
| # sweep connections in departure-time order | |
| for k in range(_bisect_dep(dep_t, departure_sec), len(dep_t)): | |
| dt = dep_t[k] | |
| if dt > cutoff: | |
| break | |
| if allowed_modes is not None and c_mode[k] not in allowed_modes: | |
| continue | |
| ds = dep_s[k] | |
| if arr[ds] <= dt: # already at the departure stop in time | |
| na = arr_t[k] | |
| if na <= cutoff: | |
| a_stop = arr_s[k] | |
| if na < arr[a_stop]: | |
| arr[a_stop] = na | |
| # seed single-hop footpaths from this transit arrival (na) even | |
| # if na isn't a_stop's best label — matches RAPTOR's round_transit | |
| for t2, w in net.transfers[a_stop]: | |
| cand = na + int(w) | |
| if cand <= cutoff and cand < arr[t2]: | |
| arr[t2] = cand | |
| return {s: arr[s] for s in range(n) if arr[s] <= cutoff} | |