cypher query for shortest paths between set of nodes

Question

I am trying to work out a cypher query to determine the shortest paths between a set of nodes, such as the set identified as follows,

MATCH (u:User) WITH u ORDER by u.score DESC LIMIT 10 RETURN u

assuming a graph of the form

(:User)-[:Owns]-(:Box)

The first restriction is that I only want to return paths between users matching the first query.

The second restriction is that I do not want to include Box elements where there is a link to only one user in the user set. I am only interested in Box elements where there is more that one matching User who Owns the Box. There may be other Users not selected linked to the Box, but I have no interest in them.

In a sense, it seems to me that I am seeking to extract a subnetwork of all nodes/paths linking the matching user set, but I am new to Cypher/Neo4j and can not work this out.

Any pointers gratefully received.

Are you saying that you want a result of the shortest path for every permutation of those top 10 users? — Brian Underwood
yes. I had approached the problem with queries of the form: "WITH u ORDER BY u.score DESC LIMIT 10 MATCH u-[r]->(c:Box) WITH u,c,r, count(r) as rc WHERE rc > 1 RETURN u,r,c", in other words trying to include only Boxes linked to more than one user, but this of course includes Boxes linked to Users not in my selection. Then I thought about shortestPath, but note that this can be applied only to two identified nodes. So yes, I am in effect seeking to identify the shortest path between each selected User, although that strikes me as possibly an inefficient way to go abotu it? — esjmb
I have also tried the MATCH p=(u)-[:Owns]-(m), m-[]-(:User) type of structure, but ever attempt I make includes Box nodes linked to only one of my User selection set. That essentially is my problem. how to scope the Box set. I am clearly missing something :) — esjmb

Brian Underwood Brian Underwood · Accepted Answer · 2015-10-14T10:45:43

MATCH (u:User)
WITH u ORDER by u.score DESC LIMIT 10
WITH collect(ID(u)) AS user_ids
MATCH (user1:User), (user2:User)
MATCH path=allShortestPaths((user1)-[*0..3]-(user2))
WHERE ID(user1) IN user_ids AND ID(user2) IN user_ids AND user1 <> user2
RETURN path

You can increase the variable path length (3 in this case) but performance may degrade rapidly depending on your network.

The above query doesn't filter out paths which have Box elements which only match greater than one user. It's much easier if you just want the direct links through one box, though I'm not sure if that's what you want. If it is you could just do:

MATCH (u:User)
WITH u ORDER by u.score DESC LIMIT 10
WITH collect(ID(u)) AS user_ids
MATCH path=(user1:User)-[:Owns]-(box:Box)-[:Owns]-(user2:User)
WHERE ID(user1) IN user_ids AND ID(user2) IN user_ids AND user1 <> user2
RETURN path, user1, box, user2

Honestly, maybe that is what you want. You might need to process the results after the query is returned. It depends on what you're doing with them, I suppose ;)

cypher query for shortest paths between set of nodes

1 Answers