получить самый длинный путь между двумя узлами с общими узлами

#graph #neo4j #path #nodes #longest-path

#График #neo4j #путь #узлы #самый длинный путь

Вопрос:

У меня есть график, на котором показаны связи друзей и городов, в которых они живут. Соединение друзей указано с помощью черных стрелок, а соединение городов указано пунктирными линиями. Я хочу получить самый длинный путь друзей, которые живут в общем городе, между г-ном А и г-ном D. Ответом будет маршрут: A-> B-> E-> D. Какой запрос должен быть написан для него?

Ответ №1:

Собственный запрос (без использования дополнения APOC):

 MATCH path = (city:City)<-[:LIVES_IN]-(:Person)-[:KNOWS*]->(:Person)-[:LIVES_IN]->(city)
WHERE ALL(person IN nodes(path)[2..-2] WHERE (person)-[:LIVES_IN]->(city))
RETURN nodes(path)[1..-1]
ORDER BY length(path) DESC
LIMIT 1

Для поиска самого длинного пути определенного города (например, P1) измените первую строку на:

 MATCH path = (city:City {name: "P2"})<-[:LIVES_IN]-(:Person)-[:KNOWS*]->(:Person)-[:LIVES_IN]->(city)

Версии APOC могут быть более производительными, но, честно говоря, его нужно будет измерить. Одна из возможностей:

 MATCH (person:Person)-[:LIVES_IN]->(city:City)
WITH city, collect(person) AS persons
CALL apoc.path.expandConfig(persons, {
    relationshipFilter: "KNOWS>",
    whitelistNodes: persons,
    minLevel: 1
})
YIELD path
RETURN nodes(path)
ORDER BY length(path) DESC
LIMIT 1