cancel
Showing results for 
Search instead for 
Did you mean: 

Does path matching with a LIMIT clause guarantee to find the closest node?

SimonThordal
Node Clone

I am matching a variable length pattern and would like to find the node that is closest in that pattern, so I add a LIMIT 1. If Neo4J searches BFS then I am guaranteed to get the closest result, but I cannot find this in the documentation.
The query for reference
MATCH (p:Person)-[:HAS*1..5]->(c:Car) RETURN c LIMIT 1

1 ACCEPTED SOLUTION

Hi @SimonThordal !

Neo4j traverses through every possible path from every :Person node, with the limit you're only telling Neo4j to bring the first result that matches the pattern in your query, which will be, most likely, a relationship of only one hop from :Person to a :Car node, returning just the :one :Car node. 

If we where to focus our search for a specific :Person and move through their relationships without fixing a :Car, with your query we may find one of the possible one-hopped relationships, if multiple of these existed. But this may not happen always, I have tested with the Cybersecurity DB in Sandbox a query that searches for every possible path between an user and a resource, returning the first one (as your query) and it wasn't the shortest one. If you open an account and create a Cybersecurity project in Sandbox you may try it with this query:

MATCH (u:User {name:'PiedadFlatley255@TestCompany.Local' })
// Match a high value object (we call it "crown jewel")
MATCH (crownJewel:HighValue)

MATCH path = (u)-[*..100]->(crownJewel)

RETURN path LIMIT 1

Here you can see that when looking for shortest paths the algorithm used actually depends on the predicates used, if the query uses global conditions (as your example) it uses a breadth-first approach. 

So, I guess it actually depends on the complexity of the query, I'd suggest to test with your approach and also @glilienfield 's one. Using the shortestPath() function also to compare results.

Hope this helps!

PS: You can do both breath first and depth first searches with GDS. 

View solution in original post

4 REPLIES 4

glilienfield
Ninja
Ninja

You should do something like the following to ensure you get the shortest path:

MATCH path=(p:Person)-[:HAS*1..5]->(c:Car) 
RETURN c 
ORDER BY length(path) asc
LIMIT 1

SimonThordal
Node Clone

Thank you, but this doesn't really answer my question.

What I want to know is whether Neo4J matches paths breadth first, depth first or without any guarantee of either. If it is breath first then it should be enough to add the LIMIT 1 clause to my query to be guaranteed that Neo4J will return one of the closest Cars in my example. 

Hi @SimonThordal !

Neo4j traverses through every possible path from every :Person node, with the limit you're only telling Neo4j to bring the first result that matches the pattern in your query, which will be, most likely, a relationship of only one hop from :Person to a :Car node, returning just the :one :Car node. 

If we where to focus our search for a specific :Person and move through their relationships without fixing a :Car, with your query we may find one of the possible one-hopped relationships, if multiple of these existed. But this may not happen always, I have tested with the Cybersecurity DB in Sandbox a query that searches for every possible path between an user and a resource, returning the first one (as your query) and it wasn't the shortest one. If you open an account and create a Cybersecurity project in Sandbox you may try it with this query:

MATCH (u:User {name:'PiedadFlatley255@TestCompany.Local' })
// Match a high value object (we call it "crown jewel")
MATCH (crownJewel:HighValue)

MATCH path = (u)-[*..100]->(crownJewel)

RETURN path LIMIT 1

Here you can see that when looking for shortest paths the algorithm used actually depends on the predicates used, if the query uses global conditions (as your example) it uses a breadth-first approach. 

So, I guess it actually depends on the complexity of the query, I'd suggest to test with your approach and also @glilienfield 's one. Using the shortestPath() function also to compare results.

Hope this helps!

PS: You can do both breath first and depth first searches with GDS. 

Thank you, Luis! I think `shortestPath will do the trick in this case.