CODEWITHSUNDEEP
graphneo4jcypher
robrant
robrant

Reputation: 317

Neo4j/Cypher - find connected nodes that have more than 2 links

I have a graph as follows (removed any labels or link directions for simplicity)

Simple example graph

I would like to start at node (c) and find only those nodes that have more than 2 adjacent edges, and the paths to them from (c).

In the example above, node (b) has 3 adjacent edges (b-a, b-c, b-g) and node (e) has 4 adjacent edges (e-d, e-f, e-h, e-h), so I would like to return the paths to just (b) and (e).

I also do not want to return the path to (a), (f), (h), (g) or (j) - I want to stop the traversal when the count is satisfied.

I've tried the following:

START n=node(c)
MATCH (n)-[r*]-(m)-[rx]-(o)
WITH m AS m, n AS n, r AS r, count(rx) as cnt
WHERE cnt > 2
RETURN n, r, m, cnt;

... but it returns paths to a, g, h, f and j in addition to b and e. It is also very costly for a big graph.

Very grateful for any help.

EDIT:

The example image I provided oversimplifies my data, so the initial suggestion doesn't work (see http://console.neo4j.org/?id=d6feml) so a new image example provided below.

I want: The paths to e an b only - as before.

I don't want: to return the path to h.

enter image description here

Thanks again neo4jers...

Upvotes: 2

Views: 3030

Answers (2)

robrant
robrant

Reputation: 317

Based on Stefans suggestion to look at the traversal framework, I spent a while trying to figure it out in python (neo4j-rest-client). The following snippet now works:

# Retrieve the node at the start of the traveral
seed_node = gdb.nodes(node_id)

# Establish what the traversal should look like
simpleTraversalTemplate = traversals.TraversalDescription().relationships('adjacent')

# Set some un-chainable attributes - work breadth first and set max depth of traversal
simpleTraversalTemplate.breadthFirst()

# This is how far you think it will go before meeting a junction. 100 is high.
simpleTraversalTemplate.max_depth(100)

# Set up a prune evaluator. This by itself (without the filter evaluator)
# returns all traversals up to the point where the link count is > 2. This includes
# the traversals to the nodes before the >2 link_count node. 
simpleTraversalTemplate.prune(value={'body':"parseInt(position.endNode().getProperty('link_count')) > 2;",
                                     'language':'javascript'})

# So, a filter is used with the prune to only return those traversals where the end node link_count 
# is >2. With only this (ie without prune), the traversal would continue and just keep returning
# those nodes with link_count > 2. 
simpleTraversalTemplate.filter(value={'body':"parseInt(position.endNode().getProperty('link_count')) > 2;",
                                     'language':'javascript'})

# Now run the traverser based on the seed node
trav = simpleTraversalTemplate.traverse(seed_node)

Upvotes: 0

Stefan Armbruster
Stefan Armbruster

Reputation: 39925

Interesting one, I've put it into Neo4j console using http://console.neo4j.org/r/qc7log.

The Cypher statement you're looking for is:

START n=node(2) // node c has node id = 2
MATCH p=(n)-[KNOWS*]-(m),(m)-[:KNOWS]-(x)
WITH p, count(x) AS count
WHERE count>2
RETURN p

The trick here is specify the path in the MATCH in two parts. The first part is then used for the aggregation using WITH and for the RETURN.

Upvotes: 4

Related Questions