Feature Request: Breadth-first search with parameterized match limit

[neo4j-contrib]

Feature Request: Breadth-first search with parameterized match limit

[jexp]

I'm not sure I understand all of it :)

At least allShortestPaths and also dijkstra should be lazy, i.e. if you only pull X results (with LIMIT x) then the others are never pulled from the database in the first place.

If you look into the implementation it turns the results from the dijkstra-pathfinder into a (lazy) stream of results.

You are right when you don't know the end-node the path-expander is what you need but afaik it also uses an lazy iterator from the database (using the Traversal Framework) and turns that into a lazy stream.

Do you have any indication / evidence that would state the contrary?

[jexp]

@InverseFalcon can you elaborate perhaps with a simple example.

[InverseFalcon]

Sure. I'm still trying to see if this is actually an issue, or if I'm overlooking something that already does this, rendering my request unnecessary.

We can tweak the example movie database to set up an example.

After creating the movie database, let's change a fraction of the people in our graph to :Doctors.

MATCH (p:Person)
WHERE rand() < .1
REMOVE p:Person
SET p:Doctor

I'm after a query to show all :People in the graph paired with the closest :Doctor (by traversing any relationships), and the number of relationship hops to reach that :Doctor.

As far as I can tell, if we try using shortestPath(), we can't use LIMIT 1, as we can only use it in a WITH or a RETURN, which affects the entire result set (if we could use this within a subquery with shortestPath(), then our problem would be solved).

Because we don't have a definite end node for shortestPath, it will generate shortest paths to ALL :Doctors in the graph, and it's up to us to perform sorting based on the length of the path so we collect the doctors (sorted in relationship distance order) and grab the first in the list:

match (p:Person)
match path = shortestPath((p)-[*]-(doc:Doctor))
with p, doc, length(path) as hops
order by hops asc
return p, head(collect(doc)), hops

That's a lot of extra work, and the cost grows as the graph grows, as paths are calculated to all doctors instead of stopping after getting the single closest.

Likewise, we can't use Dijkstra, since it requires inputing start and end nodes, which would end up matching :Person start nodes to ALL :Doctor end nodes, which is pretty much a repeat of the above.

APOC's PathExpander has a neat means of indicating the label of an end-node for the expansion ('/Doctor' as the label filter, in this case), but that only prevents the expander from continuing down that particular path...it will still look down all other paths (note that changing max traversals to 10 can result in a hang), still leaving us with the responsibility of sorting the paths by length and getting the head:

match (p:Person)
call apoc.path.expand(p, null, '/Doctor', 0, 5) yield path
with p, last(nodes(path)) as end, length(path) as hops
order by hops asc
return p, head(collect(end)), hops

What I'm looking for is some means of either performing a subquery with its own limit (so we can only grab the single closest :Doctor for each :Person from a shortestPath() function with LIMIT 1...is something like this present in neo4j 3.1+?), or an APOC Procedure that will do the equivalent, stopping once we have the specified limit of results.

While subquery support would pretty much solve the issue, these could work, to a degree, in the meantime:

match (p:Person)
// new shortestPath with the limit of shortestPaths per start/end as a parameter
// ideally this should respect a predicate too
match path = shortestPath( (p)-[*]-(doc:Doctor), 1 )
return p, doc, length(path) as hops

or this

match (p:Person)
// path expander with new optional parameter for the limit of paths to find before stopping
call apoc.path.expand(p, null, '/Doctor', 0, 5, 1) yield path
return p, last(nodes(path)) as end, length(path) as hops

[InverseFalcon]

Fulfilled by #326 , which provides a limit to path expansion results.