Используйте популярную базу данных графиков, чтобы найти лучший путь между двумя станциями метро.

В моем предыдущем руководстве я рассмотрел Создание механизма рекомендаций для ресторанов с использованием 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.0
  • Java —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.

Спасибо, что прочитали эту статью. Надеюсь увидеть вас снова в следующей статье!

использованная литература

  1. Сайт Neo4j
  2. Драйвер Neo4j Python
  3. Пользовательский интерфейс React Material