Алгоритм возврата графа Neo4j

У меня сложный вопрос о Neo4j и о том, что умеет Traversal.

Представьте, что у вас есть следующий график Neo4j

График

Моя идея состоит в том, чтобы обойти весь граф, и если я найду «ложный» узел, распространить этот статус на его соседей и так далее, и, наконец, в этом примере у нас будут все узлы со статусом «ложный». (В реальной жизни у меня есть больше условий, чтобы установить этот статус в true или false во время обхода, но я немного упростил его для вопроса)

Я думаю, что для этого мне нужен какой-то алгоритм возврата, но в Neo4j я не знаю, как это сделать и возможно ли это вообще. Кроме того, этот граф может быть очень огромным графом.

Как бы вы сделали это с Java и Neo4j?

Спасибо.


java neo4j cypher graph-traversal
person jpadilladev    schedule 08.11.2017    source источник
comment
Будет ли достаточно сопоставить любой узел с желаемым свойством как «ложь», а затем изменить все достижимые связанные узлы с этого узла на ложные?   -  person InverseFalcon    schedule 08.11.2017

Ответы (2)


arrow_upward
2
arrow_downward

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

В Neo4j 3.2.x есть эффективное средство для сопоставления со всеми различными доступными узлами посредством сопоставления отношений переменных плюс использование DISTINCT, но для этого требуется верхняя граница отношения переменной длины. Использование подходящего большого числа должно работать. Что-то типа:

MATCH (:SomeLabel{someProperty:false})-[*..999999]->(x)
WITH distinct x
SET x.someProperty = false

В противном случае Процедуры APOC предлагают apoc.path.subgraphNodes(), который также выполняет эффективное сопоставление с доступными узлами в подграфе:

MATCH (start:SomeLabel{someProperty:false})
CALL apoc.path.subgraphNodes(start, {}) YIELD node
SET node.someProperty = false;

РЕДАКТИРОВАТЬ

Чтобы добавить больше деталей для первого варианта (почему бы просто не использовать * и почему использовать DISTINCT), имейте в виду, что по умолчанию Cypher будет соответствовать всем возможным путям, когда мы используем *, даже если эти пути заканчиваются в том же узле, что и ранее сопоставленный путь. Это может стать неэффективным в достаточно связном графе (когда у нас нет разумной верхней границы и мы не используем LIMIT), с возможностью взорвать вашу кучу или зависнуть на неопределенный срок.

Этого особенно следует избегать, когда нас интересуют не все возможные пути, а только все возможные достижимые узлы.

В Neo4j 3.2 была введена оптимизация под названием pruning-var expand, которая изменяет логику обхода в случае, когда выполняются все следующие условия:

  1. У нас есть расширение var-length
  2. Мы никоим образом не ссылаемся на путь (например, устанавливая переменную пути для шаблона соответствия или устанавливая переменную для отношения var-length)
  3. У нас есть верхняя граница расширения var-length
  4. Мы просим РАЗЛИЧНЫЕ узлы или значения, которые можно получить из расширения

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

Затем планировщик будет использовать отбрасывающую переменную расширения (вы можете подтвердить это, проверив план запроса из EXPLAIN или PROFILE) для эффективного сопоставления с доступными узлами.

person InverseFalcon    schedule 09.11.2017
comment
Будет работать только * (ответ Бруно Переса и этот ответ). Почему РАЗЛИЧНЫЙ? - person jpadilladev; 09.11.2017
comment
Добавлены дополнительные сведения об ограничениях использования * на большом графике и об оптимизации сокращения var expand. - person InverseFalcon; 09.11.2017
comment
Потрясающее объяснение! - person Bruno Peres; 09.11.2017
comment
Отличное объяснение! @InverseFalcon Могут ли у меня возникнуть проблемы, если ссылка в моем примере? Насколько я знаю, Neo4j рекомендует делать отношения направленными, а затем игнорировать это направление при обходе. В моем примере у меня может быть [C] -> [F] Будет ли ваш запрос обновлять свойство 'C' на false? - person jpadilladev; 09.11.2017
comment
Если направление не имеет значения во время обхода, просто опустите стрелку. Это будет пересекать как входящие, так и исходящие отношения. - person InverseFalcon; 09.11.2017
comment
Я провел тест с вашим первым запросом без стрелки на графике с 726 узлами. Запрос выполняется бесконечно... - person jpadilladev; 09.11.2017
comment
@jpadilladev Я также могу воспроизвести зависание. Я подниму это с инженерией. В этом случае попробуйте решение APOC. Начните с простого возврата количества отдельных узлов, чтобы увидеть, как это работает в первую очередь, и сколько узлов вы будете записывать. - person InverseFalcon; 09.11.2017

arrow_upward
0
arrow_downward

Я не знаю, полностью ли я понял ваш вопрос, но я считаю, что простого запроса Cypher достаточно. Что-то типа:

MATCH ({someProperty : false})-[*]-(neighbours)
SET neighbours.someProperty = false
person Bruno Peres    schedule 09.11.2017
comment
Это расширит ложное свойство на любую глубину, поэтому я думаю, что это сработает. Мне нужно будет добавить некоторые условия при расширении, но я попробую. В своем вопросе я попросил сделать это с помощью Java (извините, если я не объяснил, но я хотел сделать это с помощью TraversalDescription, Expanders...). Почему Сайфер? Это легче? Спасибо - person jpadilladev; 09.11.2017
comment
@jpadilladev Cypher — естественный выбор при работе с Neo4j, поскольку это язык запросов, который обрабатывает эту базу данных. И да, с Cypher проще работать по сравнению с Java API. Однако Java API обеспечивает большую гибкость и меньшую абстракцию. Если я полностью понял ваше требование, вы пытаетесь динамически добавлять условия во время выполнения пересечения... В этом случае я считаю, что вам нужно будет работать с Java API. - person Bruno Peres; 09.11.2017