Simple search ticket emulator on Rust (Just test exercise )
Основная концепция - мультиграф. Почему? Потому-что возможны перелеты в обе стороны => необходим неориентированный граф.
В БД записываются данные по билетам где ключ определяется как МД5 (не надежный зато самый быстрый) от 4х значений полей:
{
departure_code: String,
arrival_code: String,
departure_time: u32,
arrival_time: u32,
}
Почему отсутствует цена ? Чтобы при вставке переписать билет в случае изменения цены при прочих равных.
Если передается ИД то структура записывается напрямую без подсчета хэш-суммы (не реализовано)
На втором этапе можно использовать алгоритм дейкстры для определение кратчайшего маршрута Разбиение графа на кластера не требуется (наверно) в силу возможности хранения всего графа в оперативной памяти.
Необходимо строить и поддерживать мультиграф, где вершины это точки маршрута, а ребра это структура FlightWeight. В ней храниться вектор МД5 хэшей билетов и вес перелета для нахождения кратчайшего маршрута. (см допущение А)
- (А) Так как в нашем батче инсерте билетов отсутствует поле distance (расстояние между двумя точками), то считаем что весом будет разница между departure_time - arrival_time. Вес нам необходимо для определения кратчайшего маршрута.
- Нужна хэшмапа всех нод на их NodeIndex чтобы O1 при поиске NodeIndex. В обратном случае приходиться проходиться по списку всех нод графа для проверки - есть ли уже надо с таким индексом или нет - что плохо. Пока что делаем проходы.
- Переехать с u32 на SystemTime