Spaces:
Sleeping
Sleeping
File size: 3,877 Bytes
e855a27 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | """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}
|