Настало время раскрыть карты14.12.2022 23:31

Всем здравствуйте, уважаемые Хабровчане!

У меня достаточно давно закралась идея опубликовать свой первый пост, который будет полезен для сообщества, как-то поможет взглянуть на мир привычных вещей иначе, раскроет те технологии, на которые ранее никто не обращал внимания, или недостаточно был усидчив в их изучении.

Начну с небольшого знакомства и расскажу о своем опыте работы. Без малого 13 лет я являюсь исследователем транспортных сетей в телеком индустрии. Работал в одном из крупнейших операторов связи, был экспертом, менеджером, обычным инженером. Строил и свопировал региональные транспортные сети, развернул с коллегами систему мониторинга сетей MBH от Москвы до Владикавказа, крайние два года отдал изучению графовых баз данных, которые позволили решить не решаемую проблему — автодискавери и построение топологии сетей с путями прохождения трафика сервисов мобильной сети и B2B клиентов.

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

Немного тезисов — что нужно понять:

• Граф — это не таблица, со всеми вытекающими.

• Graph Data Science — библиотека с алгоритмами AI, доступная для всех и каждого, написанная сообществом для БД Neo4j

• Поиск информации, основанных на графовых алгоритмах, существенно быстрее, нежели чем в реляционных БД

• Графовые методы работы с информацией только в начале пути, и на них необходимо обратить внимание

  Итак, начну с проблемы, которая меня беспокоила достаточно давно, и которую я хотел решить самостоятельно. Проблема называется — дорожные знаки с наименованиями населенных пунктов с рандомными значениями километража. Часто езжу по югу нашей страны и также часто сталкиваюсь с тем, что указанный километраж не соответствует действительности. Есть два метода проверки — одометр автомобиля, яндекс/гугл карты. Одометр не самый точный инструмент, яндекс/гугл карты показывают разный результат — чему верить? Как говорится в одном еврейском анекдоте — верить нужно только себе и то, после того, как пересчитал деньги. Вторая важная задача -, а как считали? По какому пути, если этих путей несколько…

  Как решить эту прикладную задачу? Очень просто, если понимаешь что такое граф. Итак записываем — список инструментов:

• БД Neo4j (4.3.7 в моем случае)

• Graphlytic (4.0.0 rc-5)

• GDS (Graph Data Science 2.1.6 (совместим с БД Neo4j 4.3.7))

• Немного времени и прямых рук

  Что такое Graphlytic — это UI для БД Neo4j. Выглядит так:

  Graphlytic

  Т.е. Graphlytic это ПО с библиотеками, которое работает с данными из БД Neo4j. На мой взгляд, это самый удачный софт, который решает множество проблем с визуализацией данных, позволяет писать запросы в БД Neo4j непосредственно из UI и использовать код в качестве темплейтов, настраивать оптимальное взаимодействие с БД. CEO Demtec (разработчик Graphlytic) весьма отзывчивый парень, и всегда рад помочь в исследовании проблем, связанных с Graphlytic, дополнять и изменять софт под требования (конечно за деньги). Но гибкость их подхода впечатляет.

  В моем примере используется серверная версия, ее можно получить на временный период. Для домашнего использования на своем компьютере или ноутбуке можно использовать ПО Neo4j Desktop, которое абсолютно бесплатно — https://neo4j.com/download/. В качестве приложения также можно установить Graphlytic. После установки Graphlytic необходимо создать локальную БД Neo4j с необходимой версией. Делается все в пару кликов.

  

Работа с данными

Основная проблема для решения задачи, откуда взять данные и геоточки, по которым построить пути. К примеру, яндекс и гугл для своих карт эту проблему решили с помощью яндекс/гугло-мобилей и цифровых устройств, которые могут передавать геометки. Т.е. отправили автомобиль на маршрут, он проставил геометки, пофоткал все вокруг и приехал с данными на базу, где опреленные люди обработали их. Так получаются цифровые топографические двойники, на которые можно не только смотреть, но и выполнять расчеты. Деньги тратить я категорически не хотел для доступа к картографическим API яндекс/гугл, поэтому точки нанес сам — с помощью Graphlytic установка 730 точек у меня заняла около трех часов.

Самое время сказать, какие пути считаем — расстояние от села Белая Глина до города Ростов-на-Дону составляет 174 км, если верить дорожным знакам. Ну что ж, проверим, так ли это в действительности.

Пруф фото

Поговорим об алгоритмах, которые помогут рассчитать пути. Как я писал ранее, буду использовать библиотеку GDS и алгоритм Йена. Этот алгоритм найдет не только кротчайшие пути, но и все альтернативные пути, которые существуют в графе. Т.к. этот алгоритм использует веса ребер графа в качестве расчетных значений, то необходимо их проставить. В качестве весов ребер графа будем использовать расстояния между точками графа. Т.к. мы знаем координаты точек, то не составит труда рассчитать расстояния между точками — для быстроты расчета я использовал Excel и формулу:

=2*6371*ASIN(КОРЕНЬ(СТЕПЕНЬ(SIN((РАДИАНЫ(D2-A2))/2);2)+СТЕПЕНЬ(SIN((РАДИАНЫ(E2-B2))/2);2)*COS(РАДИАНЫ(E2))*COS(РАДИАНЫ(B2))))

Получилась таблица с расстояниями от одной ноды графа к другой:

Ну и вторая табличка только с нодами:

Самое время внести данные с расстояниями в БД Neo4j. Для этого я написал коротенький код на языке Cypher (язык запросов к БД Neo4j).

Load CSV nodes and rels into Neo4j

nodes_with_distance=///nodes_with_distance.csv
c_nodes=///c_nodes.csv





    

В Graphlytic появились ноды со связями, в свойствах которых прописаны расстояния от одной ноды к другой — параметр distance_m, distance_km

Всю необходимую информацию собрали, переходим к расчету путей с помощью алгоритма Йена.

Для начала, необходимо создать подграф, с которым будет взаимодействовать алгоритм. Делается это с помощью запроса ниже, где 'myGraph' — имя подграфа, 'c_nodes' — тип нод (указывается произвольно при создании основного графа), 'DST' — тип релейшншипов между нодами (также указывается произвольно при создании), relationshipProperties: 'distance_m' — свойство релейшншипа, которое будет браться в расчет — в нашем случае указано расстояние в метрах.

CALL gds.graph.project(
    'myGraph',
    'c_nodes',
    'DST',
    {
        relationshipProperties: 'distance_m'
    }
)

Сообщение об успешном создании подграфа

Настал момент истины — какое расстояние покажет алгоритм Йена от Белой Глины до Ростова-на-Дону? Как можно видеть на скрине сверху, я сделал два пути — напрямую по главной дороге Кировская — Мокрый Батай — Батайск — Ростов-на-Дону, и через второстепенную дорогу Кировская — Березовая Роща — Новонатальино — Ростов-на-Дону. Т.к. Ростов-на-Дону — это не точка на карте, то точкой финиша маршрута я выбрал центральную точку левого берега Дона между Ворошиловским мостом и Аксайским мостом. Также будут отображены расстояния до въездов в город.

Алгоритм Йена, где source — отправная точка в Белой Глине, target — финиш в Ростове, k — кол-во вычисляемых маршрутов.

MATCH (source:c_nodes {uid: 'e1225897-1c15-4a6f-964b-7a82e3898b8d'}), (target:c_nodes {uid: '9f7422e2-af9a-417c-b47d-b54dd16e1ef0'})
CALL gds.shortestPath.yens.stream('myGraph', {
    sourceNode: source,
    targetNode: target,
    k: 3,
    relationshipWeightProperty: 'distance_m'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
    index,
    gds.util.asNode(sourceNode).address AS sourceNodeName,
    gds.util.asNode(targetNode).address AS targetNodeName,
    totalCost,
    [nodeId IN nodeIds | gds.util.asNode(nodeId).address] AS nodeNames,
    costs,
    nodes(path) as path
ORDER BY index

Результат запроса. Обратите внимание на время работы запроса — 105 мс.

Обрабатываем результат. Если вернуться к постановке проблемы, и посмотреть на знак в Белой Глине на выезде из села, то увидим 174 км до Ростова. В действительности расстояние составило 191 км по короткому пути через Новонатальино и 194 км напрямую до финиша.

До въезда в город как по короткому пути, так и по 'длинному' пути 186 км и 186,5 км соответственно.

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

На этом все, успехов!

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

© Habrahabr.ru