0

How to do Breadth-first Search in a Paginated Manner using Neo4J Cypher?

For example, I have the following vertices

Vertex A, Vertex B1, B2, B3, ...., Bn(m B vertices), Vertex C1, C2, C3, ..., Cn(n C vertices) and Vertex D1, D2, D3, ..., Dn(k D vertices)

Now A is the root and A's children are all B vertices and for each B vertex there are n C vertices as children and finally for each C vertex there are K D vertices as children. so the direction is simply top to bottom.

Now I want to find out all the vertices starting from say Vertex C1 and do BFS in a paginated manner because the Graph is huge. any idea how to accomplish this using Cypher?

user1870400
  • 6,028
  • 13
  • 54
  • 115

1 Answers1

2

Keep in mind that ordering is not guaranteed unless you have an ORDER BY clause.

Also, Cypher expansions use DFS by default, only shortestPath() and shortestPath() usage does BFS, and these aren't applicable for this case.

You can have more control over how the expansion behaves using the traversal API, which can be used from a stored procedure. Thankfully, APOC Procedures already has that done for you in its path expander procs, and default to using BFS.

You'll want to ensure you have the relationship type and directions correct when using the procedure.

Let's say that your graph only has outgoing relationships from root to leaf. In that case here's an example of usage:

MATCH (start:Vertex {name:$startVertex})
CALL apoc.path.subgraphNodes(start, {relationshipFilter:'>'}) YIELD node
RETURN node
SKIP $skip
LIMIT 100

You can pass startVertex and skip as parameters when calling the query.

InverseFalcon
  • 29,576
  • 4
  • 38
  • 51
  • Thanks. How do I do it for both incoming and outgoing? – user1870400 Jul 09 '19 at 21:37
  • Also why not add BFS expansion to Cypher? Stored Procedures seems more like glue than having it support natively. – user1870400 Jul 09 '19 at 21:57
  • [This is a good answer for that decision](https://stackoverflow.com/a/2626251/92359). BFS has greater space complexity, meaning it could use significantly more heap per query depending on the branching factor and depth. That said, more control would be great. As we approach Neo4j 4.0, and as OpenCypher and GQL develop we are looking at more options for controlling expansion behavior. Not sure if it will end up in the final spec, but I'm hoping so. – InverseFalcon Jul 09 '19 at 23:34
  • If you need both incoming and outgoing, you can leave off the filter entirely, but I don't think that would be what you want? It would expand everything, every node reachable in the tree. – InverseFalcon Jul 09 '19 at 23:36
  • Yes that's what I want except I want it in a paginated fashion because the entire graph can be huge. – user1870400 Jul 10 '19 at 08:02