1

I would like to know if there is a way to find two nodes such that the shortest path between them is of a specific length, say, 10.

All my nodes have the same label; "n1", and the shortest path can be through any edge type.

So far i have been doing this manually, by finding the shortest path between node n and node m, and constantly changing n and m and stop when i find a path of length 10.

Here is the Cypher query:

match sp = shortestpath((startNode)-[*]->(endNode)) where id(startNode) = 1 and id(endNode) = 2 return sp

Note, i do not specify the node label since i only have one label in the graph.

So i just continuously change the start and end nodes and run it until i find a path of the desired length.

I'm sure there is an easier way to do this, but since i am a Neo beginner i am struggling to figure it out.

I have also tried this:

MATCH (n1), (n2)
WHERE n1 <> n2 and shortestPath((n1)-[*]-(n2)) = 5
RETURN n1, n2
LIMIT 2

However, i don't believe this is correct because shortest paths of length 5 is very common in my graph, and it is taking a long time to execute...

David Makogon
  • 69,407
  • 21
  • 141
  • 189
nav
  • 33
  • 5

2 Answers2

2

[UPDATED]

This query should be more performant. It avoids using a cartesian product, places an upper bound on the variable-length relationship pattern, and does not even use shortestpath.

MATCH p=(n1)-[*10]->(n2)
WHERE n1 <> n2 AND NOT (n1)-[*..9]->(n2)
RETURN n1, n2
LIMIT 1
cybersam
  • 63,203
  • 6
  • 53
  • 76
  • Thanks for the reply. My query below gives me results instantaneously for some values. whereas this one has been running for a bit now on the same values. Maybe something is wrong with the query? (I'm not sure) My query, and the query above hasn't terminated for a path of length 10 yet. I think 10 (or 9) might be the longest shortest-path i have. Is it true that if there doesn't exists a path of length 10, then these queries will run for a very long time? – nav Feb 14 '23 at 22:27
  • Interesting. OK, try my updated query. – cybersam Feb 14 '23 at 22:33
  • Finding a shortest path of length 9 finished in around 10 seconds in my query. In this updated query, it is yet to finish, I do like the logic in your query though! I'm not sure why it is taking so long? (i replaced the 10 with a 9 and replaced the 9 with an 8) – nav Feb 14 '23 at 23:04
  • You probably lucked out by having one of the first n1/n2 pairs tried just happen to work. You cannot rely on that working forever. Try changing `LIMIT 1` to `LIMIT 3`. – cybersam Feb 14 '23 at 23:26
0

This has worked for me!

MATCH (n1), (n2)
WHERE n1 <> n2 and length(shortestPath((n1)-[*]->(n2))) = 10
RETURN n1, n2
LIMIT 1
nav
  • 33
  • 5
  • This is a very expensive query (due to the `MATCH` using a cartesian product, and the unbound variable-length `shortestpath` pattern). If you have enough data the server can run out of memory and/or take forever to execute. See my answer for one suggested refinement. – cybersam Feb 14 '23 at 18:40