Настало время раскрыть карты

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

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

Начну с небольшого знакомства и расскажу о своем опыте работы. Без малого 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 это ПО с библиотеками, которое работает с данными из БД 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).

<!DOCTYPE etl SYSTEM "https://scriptella.org/dtd/etl.dtd">
<etl>
<description>Load CSV nodes and rels into Neo4j</description>
<properties>
nodes_with_distance=///nodes_with_distance.csv
c_nodes=///c_nodes.csv

</properties>
<connection id="neo4j" driver="neo4j" url="bolt://x.x.x.x:7687" user="xxx" password="xxx"/>


<!--IMPORT - NODES -->    
<script connection-id="neo4j">
LOAD CSV WITH HEADERS FROM 'file:$c_nodes' AS row
FIELDTERMINATOR ';'
MERGE (c_nodes:c_nodes {uid: row.node_a})
ON CREATE SET
c_nodes.name = row.node_a,
c_nodes.longitude = toFloat(row.longitude_a),
c_nodes.latitude = toFloat(row.latitude_a),
c_nodes.address = row.address
</script>

<!-- Create relationships between nodes -->
<script connection-id="neo4j">
LOAD CSV WITH HEADERS FROM "file:$nodes_with_distance" AS row
FIELDTERMINATOR ';'
MATCH (ch1:c_nodes {uid: row.node_a})
MATCH (ch2:c_nodes {uid: row.node_b})
MERGE (ch1)-[distance:DST]->(ch2)
ON CREATE SET
distance.uid = replace(replace(row.node_a + "-DST-" + row.node_b, "/", "_"), " ", "_"),
distance.distance_m = toInteger(row.distance_m),
distance.distance_km = row.distance_km


</script>

<!-- Create relationships between nodes -->
<script connection-id="neo4j">
LOAD CSV WITH HEADERS FROM "file:$nodes_with_distance" AS row
FIELDTERMINATOR ';'
MATCH (ch1:c_nodes {uid: row.node_a})
MATCH (ch2:c_nodes {uid: row.node_b})
MERGE (ch2)-[distance:DST]->(ch1)
ON CREATE SET
distance.uid = replace(replace(row.node_b + "-DST-" + row.node_a, "/", "_"), " ", "_"),
distance.distance_m = toInteger(row.distance_m),
distance.distance_km = row.distance_km


</script>

</etl>

В 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 км соответственно.

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

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

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