How do I find pairs of nodes that are not connected in n hops?

1
votes

As the title says, I have a graph of nodes which are interconnected with a relationship N. I now want to find all pairs of nodes which are further than 20 hops away from each other.

A naive approach with the following cypher query is far too slow:

MATCH (n:CELL) 
WITH n 
MATCH (k:CELL) 
WHERE NOT (n)-[:N*1..20]->(k) 
RETURN n, k

I could create a second relationship K with a "distance" property and then match that, but to do so for every Node doesn't exactly scale well (I've got 18k nodes, so I would need more than 160 million new relationships).

Is there any other way to solve this in neo4j?

2
neo4jcypher

2 Answers

2
votes

You could try to use shortest-path which is more efficient.

MATCH (n:CELL) 
WHERE shortestPath((n)-[:N*..20]->(k:CELL)) IS NULL
RETURN n, k
0
votes

What about something like this:

MATCH p=((n:CELL-[:N*..20]->(k:CELL))
WITH n, k, min(length(p)) as minDinstance
WHERE minDinstance > 20/2 AND n <> k
RETURN DISTINCT n, k, minDinstance