breadth-first-search.ts

let destinationLines = this.getDestinationLines(destination);
let queues = this.getReachableTripSegments(origin, departureTime);
let numTransfers = 0;
let earliestArrival = Infinity;
let results = new QueryResults();

while (!queues.empty(numTransfers)) {
    // for each trip segment in the queue at this depth
    for (const tripSegment of queues.get(numTransfers)) {
        const {trip, b, e} = tripSegment;

        // for each line that takes us to our destination and is connected using the current trip
        for (const [line, i, footpathTime] of destinationLines.get(trip, [])) {
            // the line arrives before the potential destination (on the same line)
            // and it improves the final arrival time
            if (b < i && trip.stops[i].arrivalTime + footpathTime < earliestArrival) {
                // update the earliest arrival and store the result
                earliestArrival = trip.stops[i].arrivalTime + footpathTime;
                results.add(queues.extractJourney(tripSegment.upTo(i)));
            }
        }

        // if the next stop arrives before our best arrival time, look at more relevant transfers
        if (trip.stops[b + 1].arrivalTime < earliestArrival) { 
            // for every stop after the start of the trip segment, up to and including the end
            for (let i = b + 1; i < e + 1; i++) {
                // add any transfers from this stop
                for (const transfer of this.transfers.getIn([trip, i], [])) {
                    queues.add(transfer.tripU, transfer.stopJ, numTransfers + 1, tripSegment.upTo(i));
                }
            }
        }
    }

    numTransfers++;
}

return results;