Используйте популярную базу данных графиков, чтобы найти лучший путь между двумя станциями метро.
В моем предыдущем руководстве я рассмотрел Создание механизма рекомендаций для ресторанов с использованием Neo4j. В этом руководстве мы собираемся немного подробнее изучить определяемые пользователем процедуры и функции. Такие реализации обычно реализуются на Java и могут быть вызваны напрямую через Cypher. Это дает вам удобный способ создать индивидуальную реализацию любых алгоритмов графа, которые вы предпочитаете, и использовать ее при запросе набора данных в Neo4j.
Начиная с версии 4.1.1, Neo4j поставляется с собственной библиотекой APOC (Awesome Procedure On Cypher). Доступны две версии:
APOC Core
- процедуры и функции, не имеющие внешних зависимостей или требующие настройки.APOC Full
- включает все, что есть вAPOC Core
, помимо дополнительных процедур и функций.
Кроме того, Neo4j также предоставляет свою собственную GDSL (Graph Data Science Library) для разработчиков, работающих над рабочими процессами машинного обучения. Некоторые алгоритмы в этой библиотеке на момент написания все еще находятся в альфа-фазе.
Наш пример проекта будет посвящен планировщику проезда для метро / метро / скоростного общественного транспорта. Незаметно для себя он будет использовать алгоритм поиска пути, предоставленный APOC Core
позже, чтобы найти кратчайший путь от начальной станции до конечного пункта назначения.
Переходим к следующему разделу и приступаем к установке необходимых модулей.
1. Настройка
Прежде чем продолжить, настоятельно рекомендуется ознакомиться со следующим руководством в Руководстве для начинающих по графической платформе Neo4j, если вы новичок в Neo4j.
Ядро APOC
По умолчанию при установке Neo4j используется APOC Core
jar-файл. Вы можете легко найти файл jar в следующем каталоге. NEO4J_HOME
относится к основному каталогу Neo4j на вашем локальном компьютере.
$NEO4J_HOME/labs
Все, что вам нужно сделать, это скопировать и вставить файл jar в следующий каталог
$NEO4J_HOME/plugins
Не забудьте после этого перезапустить Neo4j с помощью следующей команды, чтобы она вступила в силу.
neo4j console
Используйте следующую команду, если вы запускаете ее как фоновую службу.
neo4j start
Вы можете получить доступ к браузеру Neo4j по следующему URL-адресу
http://localhost:7474/browser/
Драйвер Neo4j
Чтобы подключить ваше веб-приложение к базе данных графов Neo4j, вам необходимо установить один из следующих драйверов в зависимости от используемых вами языков программирования:
.NET
- .NET Standard 2.0Java
—Java 8+ (последние выпуски исправлений).JavaScript
- Все LTS-версии Node.JS, особенно среды выполнения серий 4.x и 6.x.Python
- CPython 3.5 и выше.Go
- Работа в процессе. На данный момент официальной даты релиза нет.
В этом руководстве я собираюсь использовать драйвер Python для нашего веб-приложения в FastAPI. Вы можете найти полные инструкции по установке остальных драйверов по следующей ссылке.
Перед установкой пакета настоятельно рекомендуется создать виртуальную среду. Выполните следующую команду в терминале.
pip install neo4j
FastAPI
Наш внутренний сервер будет построен на основе FastAPI. Если вы являетесь пользователем Flask, не стесняйтесь изменять его соответствующим образом, поскольку вы всегда можете перенести его с Flask на FastAPI позже. Установите его через pip install следующим образом:
pip install fastapi
Кроме того, вам понадобится ASGI
сервер. Я собираюсь использовать рекомендованный ASGI
сервер под названием Uvicorn
. В том же терминале выполните следующую команду, чтобы установить его
pip install uvicorn
Набор данных
Я собираюсь использовать следующую карту сети в качестве набора данных для моего варианта использования. Он основан на реальной карте сети одного из операторов общественного транспорта в Сингапуре.
Чтобы упростить наш проект, наш набор данных будет содержать только сокращенную версию карты выше. Следовательно, я собираюсь проигнорировать остальные строки и оставить только следующие 5 строк MRT.
- Линия Восток-Запад (зеленая)
- Линия Север-Юг (красная)
- Северо-восточная линия (пурпурный)
- Линия круга (круг)
- Линия Даунтаун (синяя)
2. База данных Neo4j
В этом разделе мы будем выполнять язык запросов к графам (Cypher) для вставки данных и запроса данных из базы данных графов Neo4j. Вы можете использовать для этого существующую или новую базу данных.
Прежде чем продолжить, давайте перечислим все узлы и отношения для нашего варианта использования. Мы собираемся использовать его для моделирования нашего домена и создания запроса Cypher позже.
Предположение
Для простоты и краткости я сделаю следующие предположения для нашего варианта использования.
- Между остановками не будет времени ожидания. В реальном случае у пассажиров должно быть время ожидания, чтобы выровнялись и сели в поезд.
- При смене линий между пересадками не будет времени в пути. В реальном случае вам придется некоторое время переходить с одной платформы на другую при смене линий.
- Время с
Station A
поStation B
всегда будет одинаковым, независимо от того, путешествуете ли вы по разным маршрутам. В реальном варианте использования время, необходимое для перехода сRaffles Place
наCity Hall
черезEast-West Line
, отличается от времени, затрачиваемого черезNorth-South Line
. - Метрика, используемая в нашем планировщике поездок, основана только на общем времени в пути между станциями. В фактическом случае использования вы должны учитывать необходимость подключаться к станции или выходить из нее, что влияет на стоимость проезда.
Не стесняйтесь изменять и моделировать домен на основе ваших собственных вариантов использования.
Станция (узел)
Каждая станция представляет собой единый Node
со следующими свойствами:
name
- Название станции. Все имена будут в маленьком регистре.mrt
- обозначают линию, на которой расположена станция. Вместо этого я использую сокращенное имя. Следовательно,East-West Line
будетew
, аCircle Line
будетcc
. Вместо этого для развязок он будет помечен какx
. Это свойство будет определять цвет значка позже в приложении React.
TRAVEL_TO (отношения)
Связь между двумя Station
обозначается TRAVEL_TO
со следующим свойством:
time
- представляют время, необходимое для поездки от одной станции к другой. Это исключает время ходьбы для развязок при переходе с одной линии MRT на другую. Набор данных для времени между станциями основан на результатах вывода с сайта TransitLink. Позже он будет использоваться как функция стоимости для алгоритма поиска пути.
Очистить базу данных
Вы можете запустить следующий Cypher для очистки базы данных. Все существующие узлы и их отношения будут полностью удалены из вашей базы данных.
MATCH (n) DETACH DELETE n
Создать набор данных
Вы можете создать два Station
узла и связать их отношениями следующим образом. Я использую строчные буквы в качестве имени, чтобы в дальнейшем стандартизировать входные параметры для вызова API.
CREATE (tuaslink:Station {name:"tuas link", mrt:"ew"})-[:TRAVEL_TO {time: 2}]->(tuaswestroad:Station {name:"tuas west road", mrt:"ew"})
Он создаст два независимых узла с меткой Station
и установит TRAVEL_TO
отношения между ними. К настоящему времени вы должны заметить, что отношения созданы как однонаправленные. Это поведение по умолчанию, поскольку Neo4j позволяет создавать только односторонние отношения между узлами. Однако вы можете указать игнорировать направление при запросе для получения желаемых двунаправленных результатов.
Впоследствии вы можете повторно использовать старый узел Station
через объявленное имя и связать его с новым узлом Station
, как показано ниже.
(tuaswestroad)-[:TRAVEL_TO {time: 8}]->(tuascrescent:Station {name:"tuas crescent", mrt:"ew"})
Вы должны быть осторожны при связывании узлов, так как это приведет к дублированию результата, если существуют два разных отношения от Station A
до Station B
. Например, вы можете подключиться с Raffles Place
к City Hall
через East-West Line
и North-South Line
. После того, как вы объявили следующий Cypher для East-West Line
.
(rafflesplace:Station {name:"raffles place", mrt:"x"})-[:TRAVEL_TO {time: 2}]->(cityhall:Station {name:"city hall", mrt:"x"})
Вы не должны повторно заявлять об этом North-South Line
.
(rafflesplace)-[:TRAVEL_TO {time: 2}]->(cityhall)
Если вы намереваетесь моделировать обе станции как разные объекты, просто создайте два разных узла для одной и той же станции и правильно их соедините.
Давайте объединим весь наш набор данных в один запрос. Следующая суть содержит полный запрос Cypher для этого проекта. Вы можете запустить его прямо в консоли Neo4j.
После выполнения запроса Cypher вы должны увидеть следующий пользовательский интерфейс.
Получить все
Фактически, вы можете запустить следующий запрос, чтобы получить все узлы и их отношения.
MATCH (n) RETURN (n)
В вашем браузере Neo4j вы должны получить следующий результат.
Дейкстра (алгоритм поиска пути)
APOC Core
поставляется с несколькими полезными алгоритмами поиска пути, такими как dijkstra
и astar
. В этом руководстве я собираюсь использовать dijkstra
, поскольку у нас есть только одна функция стоимости. Исходя из официальной документации, принимает следующие входные параметры
startNode
- Начальный узел алгоритма поиска пути.endNode
- конечный целевой узел для алгоритма поиска пути.relationshipTypesAndDirections
- строка представляет отношения между узлами. Вы также можете указать направления.weightPropertyName
- строка представляет имя свойства для функции стоимости.defaultWeight
— Вес по умолчанию для свойства, если его нет в узле.numberOfWantedPaths
- количество возвращаемых путей. Значение по умолчанию - 1.
и вернуть два выходных параметра
path
- Пути для поисков пути.weight
- Общая стоимость путевок.
Вы можете игнорировать параметры defaultWeight
и numberOfWantedPaths
, если ищете только лучший путь из алгоритма.
Лучший путь от А до Б
В следующем примере показано, как Cypher получает наилучший путь от Jurong East
к Dhoby Ghaut
.
MATCH (start:Station {name: 'jurong east'}), (end:Station {name: 'dhoby ghaut'}) CALL apoc.algo.dijkstra(start, end, 'TRAVEL_TO', 'time') YIELD path, weight RETURN path, weight
Вы должны получить следующий результат
Три основных пути от А до Б
Допустим, вы хотели получить 3 лучших пути из алгоритма. Вам следует использовать следующий Cypher
MATCH (start:Station {name: 'jurong east'}), (end:Station {name: 'dhoby ghaut'}) CALL apoc.algo.dijkstra(start, end, 'TRAVEL_TO', 'time', 5, 3) YIELD path, weight RETURN path, weight
После выполнения браузер Neo4j отобразит следующий результат
3. Драйвер Python
В этом разделе мы собираемся создать простую внутреннюю часть FastAPI, которая подключается к базе данных Neo4j через драйвер Python. В своем рабочем каталоге создайте новый файл Python. Я назову это journey.py
.
Импортировать
Добавьте следующее объявление импорта в верхнюю часть файла Python.
from neo4j import GraphDatabase import logging from neo4j.exceptions import ServiceUnavailable
Класс путешествия
Затем создайте новый класс и инициализируйте внутри него следующие функции
class Journey: def __init__(self, uri, user, password): self.driver = GraphDatabase.driver(uri, auth=(user, password)) def close(self): self.driver.close()
Этот класс отвечает за следующие функции:
- вернуть весь список названий станций в базе данных
- вернуть лучший путь на основе начальной и конечной точки назначения с использованием
dijkstra
алгоритма поиска пути
Получить название станций
Продолжите, добавив следующий код внутри класса Journey
. Первая функция инициализирует сеанс через диспетчер контекста. Внутри функции мы вызовем метод read_transaction()
и передадим вторую функцию, которая вернет словарь в качестве результата.
Что касается второй функции, она в основном отвечает за выполнение строки запроса через функцию run()
. Я использую понимание слов и функцию title()
, чтобы вернуть имена в Title
регистре. Рекомендуется объявить эту функцию как staticmethod
на основании официальной документации.
Найдите лучшие пути
Давайте создадим еще две функции для получения наилучших путей с использованием dijkstra
алгоритма. Он принимает следующие параметры:
start_node
- Начальная точка путешествияend_node
- Конечный пункт назначения путешествияcount
- Количество возвращаемых путей
4. Сервер FastAPI
Как я уже упоминал ранее, наш внутренний сервер основан на FastAPI. Создайте новый файл Python с именем myapp.py
в том же каталоге, что и journey.py
.
Импортировать
Вверху файла добавьте следующие операторы импорта.
from fastapi import FastAPI import journey import atexit from fastapi.middleware.cors import CORSMiddleware
journey
- это имя модуля, который мы создали ранее. Если оба файла находятся в разных каталогах, пожалуйста, измените его соответствующим образом.
Я использую atexit
для выполнения функции close()
при выходе из веб-сервера. Для получения дополнительной информации ознакомьтесь со следующим руководством Как создать обработчики выхода для вашего приложения Python.
CORSMiddleware
необходим для предотвращения проблем, когда вы делаете вызов AJAX
или fetch
из любых интерфейсных приложений.
Инициализация
Инициализируйте следующие переменные, которые являются учетными данными для аутентификации в базе данных Neo4j.
uri = "neo4j://localhost:7687" user = "neo4j" password = "neo4j" neo_db = journey.Journey(uri, user, password)
Обработчик выхода
После этого добавьте следующий код, который служит для закрытия соединения с нашей базой данных Neo4j.
def exit_application(): neo_db.close() atexit.register(exit_application)
FastAPI
Как только вы закончите с этим, создайте новый экземпляр FastAPI. Кроме того, давайте укажем переменную для origins
и передадим ее в качестве входных параметров при вызове функции add_middleware()
.
app = FastAPI() origins = [ "http://localhost:3000" ] app.add_middleware( CORSMiddleware, allow_origins=origins, allow_credentials=True, allow_methods=["*"], allow_headers=["*"], )
origins
состоит из списка URL-адресов, которые будут вызывать ваш сервер FastAPI. Допустим, у вас есть приложение React, которое запускается локально на порту 3000. Вы должны добавить следующий URL в список
http://localhost:3000
Создайте новый GET
маршрут, который возвращает все названия станций.
@app.get('/get-station') async def get_station(): result = neo_db.find_all() return result
После этого создайте еще один GET
маршрут для получения наилучшего пути. Мы собираемся связать его с функцией find_journey()
, которая принимает три параметра. Каждая строка состоит из объекта словаря, который содержит параметры path
и weight
. Следует отметить, что узлы внутри path
не в порядке, и вы можете связать их через id
. Первый узел может быть начальной или конечной точкой назначения.
Запуск FastAPI
Выполните следующий код, чтобы запустить сервер FastAPI:
uvicorn myapp:app
Он должен начаться через несколько секунд. Давайте протестируем наш API, чтобы определить оптимальные пути от Jurong East
к Dhoby Ghaut
. Перейдите по следующему URL-адресу в своем браузере.
http://localhost:8000/get-journey?start=jurong%20east&end=dhoby%20ghaut&count=3
У вас должен получиться следующий результат.
[{"path":[{"name":"Jurong East","mrt":"x","time":"start here"},{"name":"Clementi","mrt":"ew","time":"4 minutes"},{"name":"Dover","mrt":"ew","time":"3 minutes"},{"name":"Bouna Vista","mrt":"ew","time":"3 minutes"},{"name":"Holland Village","mrt":"cc","time":"2 minutes"},{"name":"Farrer Road","mrt":"cc","time":"3 minutes"},{"name":"Botanic Gardens","mrt":"cc","time":"2 minutes"},{"name":"Stevens","mrt":"dt","time":"2 minutes"},{"name":"Newton","mrt":"dt","time":"3 minutes"},{"name":"Little India","mrt":"dt","time":"1 minutes"},{"name":"Dhoby Ghaut","mrt":"dt","time":"2 minutes"}],"weight":25.0},{"path":[{"name":"Jurong East","mrt":"x","time":"start here"},{"name":"Clementi","mrt":"ew","time":"4 minutes"},{"name":"Dover","mrt":"ew","time":"3 minutes"},{"name":"Bouna Vista","mrt":"ew","time":"3 minutes"},{"name":"Commonwealth","mrt":"ew","time":"2 minutes"},{"name":"Queenstown","mrt":"ew","time":"2 minutes"},{"name":"Red Hill","mrt":"ew","time":"3 minutes"},{"name":"Tiong Bahru","mrt":"ew","time":"2 minutes"},{"name":"Outram Park","mrt":"ew","time":"3 minutes"},{"name":"Chinatown","mrt":"ew","time":"2 minutes"},{"name":"Clarkequay","mrt":"ne","time":"2 minutes"},{"name":"Dhoby Ghaut","mrt":"ne","time":"2 minutes"}],"weight":28.0},{"path":[{"name":"Jurong East","mrt":"x","time":"start here"},{"name":"Clementi","mrt":"ew","time":"4 minutes"},{"name":"Dover","mrt":"ew","time":"3 minutes"},{"name":"Bouna Vista","mrt":"ew","time":"3 minutes"},{"name":"Holland Village","mrt":"cc","time":"2 minutes"},{"name":"Farrer Road","mrt":"cc","time":"3 minutes"},{"name":"Botanic Gardens","mrt":"cc","time":"2 minutes"},{"name":"Stevens","mrt":"dt","time":"2 minutes"},{"name":"Newton","mrt":"dt","time":"3 minutes"},{"name":"Orchard","mrt":"ns","time":"3 minutes"},{"name":"Somerset","mrt":"ns","time":"2 minutes"},{"name":"Dhoby Ghaut","mrt":"ns","time":"2 minutes"}],"weight":29.0}]
Первая рекомендация предлагает нам перейти с Jurong East
на Bouna Vista
и ехать по Circle Line
до Botanic Gardens
. После этого следуйте по Downtown Line
, пока не дойдете до Little India
и сделайте развязку на Dhoby Ghaut
.
Второй путь ведет нас от Jurong East
к Outram Park
. Затем сделайте развязку на North East Line
и пройдите до Dhoby Ghaut
.
Кроме того, наше третье предложение направляет нас сделать развязку на Bouna Vista
, чтобы достичь Botanic Gardens
. После этого продолжайте Newton
через Downtown Line
. В отличие от первого путешествия, он рекомендует нам сделать развязку на North South Line
с Orchard
на Dhoby Ghaut
.
5. Звонок из Front-end
Все, что вам нужно сделать, это подключить его к любому клиентскому приложению. Вы можете использовать любые фреймворки или компьютерный язык в зависимости от ваших предпочтений. В этом руководстве я просто кратко расскажу, как интегрировать React с сервером FastAPI. Я не буду описывать пользовательский интерфейс, чтобы он не был слишком длинным.
Пример
Если вы ищете вдохновения, взгляните на функции, предоставляемые следующим веб-сайтом. В следующем примере показан пример вывода с Jurong East
на Dhoby Ghaut
.
Как видите, он предлагает только два варианта по сравнению с нашими результатами. Первый вариант - это точно такой же путь, что и вторая рекомендация наших алгоритмов поиска пути.
Вы можете создать приложение React со следующими функциями:
- Макет сетки, разделяющий содержимое на две части. Левая сторона содержит ввод, а правая сторона отображает результат.
- Два входа выбора для начальной и конечной точки
- Кнопка подтверждения
- Результаты будут отображаться в виде гармошки вместе с общим временем, затраченным на поездку. Каждое путешествие будет содержать название станций, а также время в пути между ними.
Окончательное приложение React может выглядеть примерно так. Этот пользовательский интерфейс основан на пользовательском интерфейсе React Material.
Вызов AJAX
Для интеграции вы можете легко реализовать это с помощью AJAX
или fetch
вызова. В этом руководстве я покажу, как вы можете сделать AJAX
вызов вашего FastAPI-сервера.
Заключение
Поздравляем с завершением этого урока.
Подведем итоги тому, что вы узнали сегодня. Мы начали с краткого объяснения Удивительной процедуры в Cypher Library.
После этого мы перешли к установке необходимых модулей, от драйвера Neo4j Python до FastAPI. Кроме того, мы создали и смоделировали наш домен для нашего приложения для планирования путешествий.
Закончив с этим, мы запустили Neo4j как консольное приложение и поигрались с Cypher. Мы очистили базу данных, создали новые записи и попытались запустить djikstra
алгоритм поиска путей, чтобы получить наилучшие пути.
Впоследствии мы создали новый класс Journey, который служит модулем для подключения к базе данных Neo4j через драйвер Python. Мы также создали сервер FastAPI, который действует как внутренний сервер.
Наконец, мы немного подробнее изучили, как интегрировать его с приложением React через вызов AJAX.
Спасибо, что прочитали эту статью. Надеюсь увидеть вас снова в следующей статье!