The search algorithm changed because the planner's question changed. Early code could find a route on one bundle and rank the resulting Trip objects. The current engine has directed services, typed transfers, query-specific overlay edges, and a two-ride product limit. Keeping the old search shape would have hidden those distinctions.

This is also why the current implementation should not be described as “Pareto-optimal reverse Dijkstra.” It uses a scalar score with deterministic tie-break dimensions, labels for transfer count, and a packed priority queue. It still allocates arrays and result objects. The code is more structured than the old search, not magically allocation-free.

Four useful stopping points

Each change below moved one responsibility to a more suitable boundary. The diagram is a chronology of shapes, not a claim that each intermediate search was a production contract.

The first multimodal graph work, recorded in 50dc376, built a general graph and router under the earlier multimodal module. The August 20 planner work then kept separate bus and jeepney candidate paths and added practical ranking. Commit 89cad3b replaced that request-time shape with the compiled planner image and current graph modules. Commit 8366918 moved the preparation work into the browser worker.

The old ranking code is useful because it shows the product concern before it became a hard selection boundary. In 3dfa11b, walking was grouped into manageable and long bands before ride count, first-bus availability, and exact walking distances were compared. The following is a partial historical excerpt:

That code ranked trips after they existed. It did not define which graph edges were legal, and its preference bands are not current planner constants. The current selector uses fixed access caps and a ride-sequence check instead. The experiment kept the useful idea, that walking and ride count are passenger facts, while moving the decision to a boundary the graph cannot bypass.

The current search state

The current search starts from the destination. For every state it follows reverse CSR entries, which are the incoming base edges, and then follows incoming overlay arcs. A label therefore describes a suffix from a node to the destination. When an origin access arc is turned into a candidate, the remaining path is already available through the label chain.

Each base node has two states. State zero has used no transfer. State one has used one transfer. The state count is deliberately small because the current product allows at most two rides. Transfer relaxation also checks that the suffix begins with a ride, so the graph cannot produce a transfer-only prefix.

The following is a partial excerpt from the current search initialization:

Source: planner-search.ts. The queue capacity is based on two states for the base edges and overlay arcs. The queue itself stores numeric values, but createLabels allocates Float64Array fields for score and distances, Uint32Array fields for references and versions, and a transfer-count array.

The label comparison first checks score. Ties are broken by total walking, longest walking leg, transfer walking, transfer count, ride distance, and then path identity. Those values let the search choose a stable predecessor without throwing away every path that differs in one passenger-relevant dimension.

Path reconstruction is explicit

A label stores the next arc reference and next state reference. Candidate construction starts from the access arc and follows those references until it reaches the destination state:

The following is a partial excerpt from the current candidate path traversal:

Source: planner-select.ts. The path references are not the final user output. Materialization resolves service IDs, geometry ranges, stop names, walking legs, and transfer instructions after selection.

This extra step matters when a path is valid but should not be shown. Search can return a candidate with too much access walking, a repeated service, or a transfer above the current limit. Selection sees the complete arc sequence and can reject it without changing the base graph.

What the experiments actually measured

The checked-in profile script measures the current mounted planner, not a controlled comparison of every historical algorithm. It loads the current public manifest and image, mounts the image, runs named city-core, north-south, Buhangin regression, off-route, and outside-service-area scenarios in bus, jeepney, and both modes, and records the result and elapsed planning time. The command is:

That gives a repeatable shape for a future benchmark, but the repository does not preserve comparable hardware, sample counts, warm-up conditions, or historical timing output for the old iterations. Earlier records include claims of 850 ms, 40 MB, 120 ms, sub-40 ms, and zero-GC behavior; those figures are not carried forward.

The current regression suite checks behavior instead of a single speed target. It runs known pins through the mounted image, checks forward and reverse jeepney results, checks bus trips between official stops, checks mixed-mode transfer bounds, and keeps the 25-metre same-place and service-area cases. Those tests define what the current search must preserve. They do not prove that it is optimal for every possible Davao trip.

What stayed and what was rejected

The compiled graph stayed because static topology is reused across requests. Reverse traversal stayed because destination suffixes make access candidates easier to evaluate. State expansion stayed because transfer count changes the meaning of a node. Packed numeric queue storage stayed because the queue does not need object-shaped entries.

The stronger claims did not stay. The current code does not show a zero-GC search. It allocates label arrays, overlay maps, candidate arrays, and materialized trip objects. It does not establish a global Pareto frontier for every combination of time, walking, transfers, mode, and service identity. It finds candidates under the current score and label comparison, then applies rider policy.

That boundary is the useful result of the experiment. Search answers which paths the graph can produce under a bounded state model. Selection answers which of those paths belong in the product. The distinction is what lets the planner fix the Buhangin case without teaching the graph that every long walk is invalid everywhere.

For the current graph model, read Trip Planner Engine. For the rider rule that followed the graph-valid incident, read Graph-valid but rider-absurd route.