Directed acylic graphs: longest paths
Directed acylic graphs: longest paths

I have a graph in which the connection of the friends and the cities where they live are shown. The connection of the friends is specified by means of black arrows and that of the cities is specified with dotted lines. I want to get the longest path of friends who live in a common city, between Mr. A and Mr. D. The answer would be the route: A-> B-> E-> D. What query should be written for it?


Modified 2 years, 11 months ago

Viewed 120 times


  • Does the direction of relationship matter in your case? Can it also be D -> E -> B -> A ? Sep 27, 2020 at 11:45
  • Yes, the direction matters Sep 28, 2020 at 7:21

1 Answer

Native query (without using APOC add-on):

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

To search for the longest path of a specific city (e.g. P1), change the first line to:

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

APOC versions might be more performant, but, honestly, it would need to be measured. One of the possibilities:

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

  • I have 183678 cities and 5058 person . When I use your suggested query, it takes too long to answer the query. Sep 29, 2020 at 7:08

You are watching: get longest path between two nodes with common nodes. Info created by GBee English Center selection and synthesis along with other related topics.