Пути переменной длины: *1..3

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

Путь переменной длины — паттерн вида -[:REL*1..3]->, который сопоставляется маршрутам из одного, двух или трёх рёбер указанного типа.

Когда глубина заранее неизвестна

«Друзья на расстоянии до трёх рукопожатий» — мы не знаем, через одного, двух или трёх посредников связаны люди. Перечислять ()-[:ЗНАЕТ]->()-[:ЗНАЕТ]->()... вручную мучительно. Cypher даёт квантификатор длины:

MATCH (a:Person {name:'Алиса'})-[:ЗНАЕТ*1..3]->(b:Person)
RETURN DISTINCT b.name AS reachable

*1..3 значит «от 1 до 3 рёбер :ЗНАЕТ подряд». Это все, до кого Алиса дойдёт за три шага дружбы. Обратите внимание: записать тот же запрос фиксированными паттернами пришлось бы тремя отдельными MATCH с UNION — для одного, двух и трёх шагов. Квантификатор сворачивает это в один компактный паттерн, и движок сам перебирает все длины в диапазоне.

Зачем это нужно на практике

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

Маленькая, но важная деталь: квантификатор можно комбинировать с фильтрами и сбором пути. «Все, до кого Алиса дойдёт за 2–4 шага, и сама длина маршрута»:

MATCH p = (a:Person {name:'Алиса'})-[:ЗНАЕТ*2..4]->(b:Person)
WHERE b.city = 'Москва'
RETURN DISTINCT b.name AS name, min(length(p)) AS nearest
ORDER BY nearest

Здесь min(length(p)) для каждого b оставит длину самого короткого из найденных маршрутов — потому что до одного человека ведёт несколько путей разной длины.

Варианты квантификатора

Кратчайший путь

Часто нужен не любой, а самый короткий маршрут. Для этого есть shortestPath:

MATCH p = shortestPath(
  (a:Person {name:'Алиса'})-[:ЗНАЕТ*]-(b:Person {name:'Глеб'})
)
RETURN [n IN nodes(p) | n.name] AS chain, length(p) AS degrees

Это знаменитая задача «сколько рукопожатий между двумя людьми». nodes(p) достаёт узлы пути, list-comprehension собирает их имена в цепочку. Есть и парный вариант — allShortestPaths, который вернёт все кратчайшие маршруты одной длины (если их несколько), а не первый попавшийся. Это полезно, когда важно показать, что путей минимальной длины несколько.

Наглядно: фронт обхода

Чтобы прочувствовать разницу между «найти все пути» и «найти кратчайший», представьте волну, расходящуюся от старта. Обычный обход * идёт в глубину и перечисляет каждую ветку до упора; shortestPath расширяет фронт по уровням и замирает, едва коснувшись цели:

уровень 0:      [Алиса]
уровень 1:   [Боб] [Вера] [Глеб?]
уровень 2:  ...   ...   ✓ дошли — BFS останавливается

Обычный обход на этой же картинке не остановился бы на уровне 2 — он продолжил бы разворачивать все ветки уровней 3, 4, 5, собирая каждый альтернативный маршрут до Глеба. Отсюда и пропасть в стоимости.

Опасность взрыва обхода

Голая звёздочка * без верхней границы на плотном графе — это бомба. Число путей растёт экспоненциально с глубиной: при средней степени узла 100 и глубине 5 потенциально 100^5 = 10 миллиардов путей. Поэтому правило: всегда ставьте верхнюю границу (*1..4) и предпочитайте shortestPath, когда нужен один маршрут, а не все.

Сравним стоимость наглядно для средней степени 100:

Каждый дополнительный шаг умножает работу на среднюю степень. Поэтому даже верхняя граница в 5–6 на плотном социальном графе может быть неподъёмной — границы 3–4 обычно достаточно для практических задач вроде рекомендаций.

Как работает под капотом

Обычный обход переменной длины — это поиск в глубину/ширину, перечисляющий все подходящие пути; отсюда и взрыв. А shortestPath использует поиск в ширину (BFS) и останавливается, найдя первый (кратчайший) маршрут, — он принципиально дешевле. Neo4j также не повторяет рёбра внутри одного пути (нет циклов по тому же ребру), что ограничивает зацикливание, но не спасает от комбинаторного роста без верхней границы.

Важная тонкость про уникальность: по умолчанию Cypher применяет правило relationship isomorphism — в пределах одного найденного пути ни одно ребро не используется дважды. Это спасает от тривиальных циклов «туда-обратно по одному ребру», но узлы при этом повторяться могут, и большой запутанный граф всё равно даёт множество длинных путей. Не путайте это с защитой от взрыва — она лишь отсекает буквальное хождение по тому же ребру, а не комбинаторный рост в целом.

И ещё про планировщик: shortestPath можно использовать только в одном паттерне на MATCH и обычно с уже привязанными концами (известны и старт, и финиш). Если же концы не зафиксированы, движок не сможет применить дешёвый BFS и откатится к полному перебору — поэтому shortestPath между «Алисой» и «Глебом» дёшев, а между «любым A» и «любым B» — нет.

Частые ошибки

• Использовать * без верхней границы. На плотном графе запрос зависнет. Ставьте *1..N.
• Брать любой путь вместо кратчайшего. Если нужен один маршрут — shortestPath, а не обход всех путей.
• Забыть DISTINCT на концевых узлах. До одного узла ведёт много путей разной длины — повторы неизбежны.
• shortestPath с незакреплёнными концами. Если старт и финиш не привязаны, дешёвый BFS не применится и запрос скатится к полному перебору. Фиксируйте оба конца.
• Слишком большая верхняя граница. Даже *1..6 на плотном графе может оказаться неподъёмным — для рекомендаций обычно хватает 3–4 шагов.

Итоги

• -[:REL*1..3]-> ищет маршруты переменной длины — обходы неизвестной глубины.
• Квантификаторы: *2, *1..3, *..5, *3.., голый *.
• shortestPath через BFS находит кратчайший маршрут дёшево — «рукопожатия».
• Всегда ограничивайте глубину: без верхней границы обход взрывается экспоненциально.