У меня есть эта проблема, я думаю, вы можете помочь мне.
PS Я не знаю, как это назвать, поэтому, если кто-то найдет более подходящее название, пожалуйста, отредактируйте.
Фон
- Я делаю это приложение для поиска автобусных транзитных линий.
- Автобусные линии представляют собой трехзначное число, они уникальны и никогда не изменятся.
- Требуется уметь искать строки от остановки А до остановки Б.
- Пользовательский интерфейс уже успешно намекает пользователю использовать только действительные имена остановок.
- Требуется уметь отображать, есть ли у маршрута прямая линия, а если нет, отображать комбинацию из 2 и даже 3 строк.
Пример:
Мне нужно добраться из пункта А в пункт D. Программа должна показать:
- Если есть прямая линия AD.
- Если нет, отобразите альтернативу, 2-строчные комбинации, такие как AC, CD.
- Если нет двухстрочных комбинаций, найдите трехстрочные комбинации: AB, BC, CD.
Конечно, приложение должно отображать номера шинных линий, а также когда переключать шины.
Что я имею:
Моя база данных структурирована следующим образом (упрощенно, фактическая база данных включает местоположения и время и тому подобное):
+-----------+
| bus_stops |
+----+------+
| id | name |
+----+------+
+-------------------------------+
| lines_stops_relationship |
+-------------+---------+-------+
| bus_line | stop_id | order |
+-------------+---------+-------+
Где lines_stops_relationship
описывают отношения «многие ко многим» между автобусными линиями и остановками.
Порядок означает порядок, в котором остановки отображаются в одной строке. Не все строки идут вперед и назад, и порядок имеет значение (точка A с порядком 2 идет после точки B с порядком 1).
Проблема
- Мы выясняем, может ли линия пройти по маршруту достаточно легко. Просто найдите одну линию, которая проходит через обе точки в правильном порядке.
- Как я могу найти, если есть 2/3 строки комбо? Я думал о том, чтобы найти линию, которая соответствует исходной остановке, и одну для конечной остановки, и посмотреть, смогу ли я получить общую остановку между ними, где пользователь может переключать автобусы. Как я помню эту остановку?
- Комбинация из 3 строк еще сложнее, я нахожу строку для источника и строку для пункта назначения, и что дальше? Я думаю, что искать строку с 2 остановками, но опять же, Как мне запомнить остановки?
ТЛ; др
Как я помню результаты запроса, чтобы иметь возможность использовать его снова? Я надеюсь достичь этого в одном запросе (для каждого - запрос для 1-строчных маршрутов, запрос для 2-х и запрос для 3-строчных комбинаций).
Примечание: я не против, если кто-то предложит совершенно иной подход, чем тот, который у меня есть, я открыт для любых решений.
Наградит любую помощь с cookie и upvote. Заранее спасибо!
Ответы:
Возможно, вы не захотите вносить радикальные изменения в этот момент, но то, что вы описываете, является именно примером использования для баз данных графиков . Графовые базы данных основаны на теории графов, к которой вы обращаетесь, пытаясь найти путь между «X» и «Y» через ориентированный граф автобусных маршрутов.
Если вы еще не знакомы с ним, взгляните на что-то вроде Neo4J . У него есть REST API, и вы можете найти для него PHP-клиентов .
Вы найдете кучу людей Stack Overflow , которые могли бы помочь с стороной реализации вещей.
источник
Допустим, пользователь хочет перейти
$start_id
к$end_id
(оба являются действительными значениями stop_id). Вы можете использовать эти запросы , чтобы найти правильный маршрут от$start_id
до$end_id
:Поиск прямого маршрута (одиночная линия):
Если по предыдущему запросу результата нет, ищите маршрут, используя 2 строки:
Замените
*
поля, которые вам действительно нужно получить.источник
bus_stops bs5
) для завершения маршрута?