Статьи

Neo4j: поиск всех кратчайших путей

Декабрь 21, 2018

Одна из особенностей языка Cypher, которую мы показываем в учебных курсах Neo4j, — это функция кратчайшего пути, которая позволяет найти кратчайший путь с точки зрения количества отношений между двумя узлами.

Используя график фильма, который вы можете импортировать с помощью команды «: play movies» в браузере, мы сначала создадим отношения «KNOWS» между любыми людьми, которые появлялись в одном фильме:

1
2
MATCH (p1:Person)-[:ACTED_IN]->()<-[:ACTED_IN]-(p2:Person)
MERGE (p1)-[:KNOWS]-(p2)

Теперь, когда у нас есть эти отношения, мы можем легко найти кратчайший путь между двумя людьми, скажем, Том Круз и Том Хэнкс:

1
2
3
MATCH (p1:Person {name: "Tom Hanks"}), (p2:Person {name: "Tom Cruise"}),
      path = shortestpath((p1)-[:KNOWS*]-(p2))
RETURN path

граф-18

Это работает довольно хорошо, но что если мы хотим найти самый длинный кратчайший путь между любыми двумя людьми на графике? Мы можем рассчитать это так:

1
2
3
4
5
MATCH (p1:Person), (p2:Person),
      path = shortestpath((p1)-[:KNOWS*]-(p2))
RETURN path
ORDER BY LENGTH(path) DESC
LIMIT 1

граф-19

Так что это 6 прыжков, что на самом деле является числом Бэкона — я ожидаю, что мы, вероятно, увидим меньшее максимальное значение, если мы импортируем все фильмы.

И в заключение, что, если мы хотим найти самый короткий кратчайший путь из 10 человек, которые снимались в большинстве фильмов? Мы могли бы начать со следующего запроса, который, похоже, должен выполнить свою работу:

01
02
03
04
05
06
07
08
09
10
11
MATCH (p1:Person)-[:ACTED_IN]->()
  
WITH p1, COUNT(*) AS appearances
ORDER BY appearances DESC
LIMIT 10
  
WITH p1 AS p1, p1 AS p2
MATCH path = shortestpath((p1)-[:KNOWS*]-(p2))
RETURN path
ORDER BY LENGTH(path) DESC
LIMIT 1

К сожалению, если мы выполним этот запрос, мы не получим возвращаемых строк, потому что ‘p1’ и ‘p2’ всегда ссылаются на один и тот же узел. Вместо этого мы можем рассчитать кратчайший путь между самыми трудолюбивыми людьми, создав перекрестный продукт, используя COLLECT и UNWIND:

01
02
03
04
05
06
07
08
09
10
11
12
MATCH (p1:Person)-[:ACTED_IN]->()
  
WITH p1, COUNT(*) AS appearances
ORDER BY appearances DESC
LIMIT 10
  
WITH COLLECT(p1) AS ps
UNWIND ps AS p1 UNWIND ps AS p2
MATCH path = shortestpath((p1)-[:KNOWS*]-(p2))
RETURN path
ORDER BY LENGTH(path) DESC
LIMIT 1

граф-20

На этом пока все!

Ссылка: Neo4j: Поиск всех кратчайших путей от нашего партнера по JCG Марка Нидхэма в блоге Марка Нидхэма .
72
Share: