sn3fru
sn3fru

Reputation: 106

Detecting short cycles in neo4j property graph

What is the best way to detect for cycles in a graph of a considerable size using cypher.

I have a graph which has about 90000 nodes and about 320000 relationship and I would like to detect cycles in sub graph of about 10k nodes and involving 100k relationships. The cypher I have written is like

start 
  n = node:node_auto_index(some lucene query that returns about 10k nodes)

match
    p =  n-[:r1|r2|r3*]->n
return p

However this is not turning out to be very efficient.

Can somebody suggest a better way to do this.

Upvotes: 4

Views: 2914

Answers (1)

cybersam
cybersam

Reputation: 67044

Unlimited-length path searches are well-known to be slow, since the number of operations grows exponentially with the depth of the search.

If you are willing to limit your cycle search to a reasonably small maximum path depth, then you can speed up the query (although it might still take some time). For instance, to only look at paths up to 5 steps deep:

MATCH p = n-[:r1|r2|r3*..n]->n
RETURN p;

Upvotes: 8

Related Questions