Остановите обход Cypher, когда условие, когда на Reduce больше не может быть выполнено

Question

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

Предположим теперь, что я хочу найти все возможные пути между узлом с идентификатором A и узлом с идентификатором B, с верхней границей длины пути (например, 10), так что общая стоимость пути ниже или равна заданной константе (например, 20),

Код Cypher для достижения этой цели следующий (и он работает):

START a = node(A), b = node(B)
MATCH (a) -[r*0..10]-> (b)
WITH extract(x in r | x.cost) as costs, reduce(acc = 0, x in r | acc + x.cost) as totalcost
WHERE totalcost < 20
RETURN costs, totalcost

Проблема с этим запросом состоит в том, что он не использует тот факт, что затраты неотрицательны, и, следовательно, пути, по которым пройден общий лимит затрат, могут быть сокращены. Вместо этого он перечисляет все возможные пути длиной от 0 до 10 между узлами A и B (что может быть до смешного дорого), вычисляет общие затраты и затем отфильтровывает пути, которые превышают лимит. Сокращение путей во времени приведет к значительному улучшению производительности.

Я знаю, что это возможно с помощью инфраструктуры обхода, используя BranchStates и предотвращая расширение при необходимости, но я хотел бы найти решение Cypher (в основном из-за причин, представленных здесь).

Я в настоящее время использую версию 2.2.2, если это имеет значение.

Answer 1

Будет ли достаточна сумма затрат на отношения до выписки?

START a = node(A), b = node(B)
MATCH (a)-[r*0..10]->(b)
WHERE sum(r.cost) < 20
WITH extract(x in r | x.cost) as costs, reduce(acc = 0, x in r | acc + x.cost) as totalcost
RETURN costs, totalcost

Кстати, желание обрезать означает, что вы хотите императивный путь!

Также, пожалуйста, помогите Cypher немного, используйте ярлыки