Нахождение самой длинной ветви дерева в Neo4j

Question

У меня в настоящее время есть структура данных дерева только для добавления в Java. Основная цель этого дерева - поддерживать указатель на самую длинную ветвь. Я реализовал это, имея ссылку на последние узлы в самой длинной ветви (ветвях), которая обновляется после вставки новых узлов в дерево.

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

Какое решение в Neo4j является предпочтительным, чтобы найти самую длинную ветвь в таком дереве?

• сохранить указатель на последние узлы, как я делаю в моей реализации Java?
• Разработка алгоритма, чтобы найти самый длинный путь и реализовать его с помощью API обхода или с помощью запроса шифра?
• какой-то встроенный функционал в Neo4j, который я еще не нашел?

Answer 1

Нет встроенной функциональности для поиска самого длинного пути.

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

В cypher это должно быть сделано с чем-то похожим на:

MATCH (root:Root)-[:HAS_CHILD*]->(n:Node)
WHERE size((n)-[:HAS_CHILD]->())=0
RETURN n
ORDER BY size(RELS(p)) DESC
LIMIT 1

Лучшим подходом является вычисление всех этих путей в одном действии с обходом. Вы можете взглянуть на APOC с apoc.path.expand процедура. Спектакли будут лучше.

Последнее решение - создать собственный алгоритм с пользовательским обходом, который сокращает ветку, если вы уже нашли самую длинную. (Это можно сделать с помощью Evaluator). Этот алгоритм будет иметь лучшую среднюю производительность, чем предыдущее решение, но в худшем случае сложность та же.

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

Выбор за вами, и зависит от производительности, которую вы хотите достичь для чтения и записи.

ура