Finding paths between multiple nodes

[kaptenh]

Hi!
I have a large graph of say, Person, and the relations between them are FRIEND.

Given a couple of Persons, say 3 or 4 of them, I want to find all paths between all of them of length 4, and I just want simple paths.
That is, say the persons are A, B and C. Then I want a path of length at most 4 between A and B, having at least one node in common with a path from A to C and a path from B to C.. or one could say i want the graph of persons connected to all of A, B and C with at most a certain distance..

I have been looking at the graph algorithms and stuff, and spanningTree would give me one path between all of them, and between any given pair of Persons there are path finding algorithms, but cant figure out a good way to do it for 4 Persons..

Any great suggestions? 🙂

[tony_chiboucas]

Could you redefine your problem a bit, and provide some greater specificity?

• All paths of length 4, or length at most 4?
• Do you really want all paths?
  • (One cycle between 3 nodes becomes 6 potentially matching paths)
• Could you provide a visual for your graph? Screenshot of the Browser? Something from Arrows?
• How do expect a path of length 4 from this?
  • 

[kaptenh]

Hi,

1. All paths of length at most 4, or some other number.
2. thats what i meant with simple paths.. no path should contain the same node twice (NODE_PATH uniqueness in the apoc algorithms)
3. I'll attach an image with 7 nodes. Say I call my query with A, B, C and looking for paths of length 3, then I would like the paths
   A->d->B
   C->d->B
   returned

Does this clarify it?

To be honest Im not 100% certain what I want, but I want the "smallest" subgraph containing the nodes I specify, and the relations between them.. to sort of get the gist of how a subset of nodes are related and not miss any interconnectedness/

[tony_chiboucas]

First, a couple quick notes:

• Paths are counted by relationship, not node. (A)->(d)->(B) is a path of length 2.
• The subgraph solution for the problem you described:
  • (A)->(d)
  • (C)->(d)
  • (d)->(B)
• The list of paths solution to the problem you described, which can be reduced by restricting relationship directionality:
  • (A)->(d)->(B)
  • (A)->(d)<-(C)
  • (B)<-(d)<-(A)
  • (B)<-(d)<-(C)
  • (C)->(d)<-(A)
  • (C)->(d)->(B)

Match Intersection

The term for this is "match intersection," and there are many ways to go about it. Desired results, and the existing graph data, will dictate which methods are possible and perform better.

Neo4j Graph Database Platform

Performing match intersection - Neo4j Graph Database Platform

Match intersection is a common use case where you’re searching for nodes which have relationships to all of a set of input nodes. For the rest of the article we’ll use the built-in movies graph for demonstration. The example use…...

Neo4j Graph Database Platform

Neo4j GraphGists

Learn how to model & explore data as a graph for your use case or industry.

Simple Cypher-only intersection

Any of these will solve the problem, each has different applications.

// can do intersections for lists of As, Bs, and Cs.
MATCH (a {name:"A"})-[]->(x)-[]->(b {name: "B"})
WITH a, b, x
MATCH (x)-[]->(c {name: "C"})
RETURN a, b, c, x

// Better for handling paths, and multiple hops
MATCH (a {name:"A"}), (b {name: "B"}), (c {name: "C"})
MATCH p1=(a)-[*2..3]-(b)
MATCH p2=(b)-[*2..3]-(c)
MATCH p3=(c)-[*2..3]-(a)
WITH a, b, c, apoc.coll.intersection(nodes(p1), nodes(p2)) as n1, nodes(p3) as n2
WITH a, b, c, apoc.coll.intersection(n1, n2) as n0
UNWIND n0 as n
MATCH p1=(a)-[]->(n)-[]->(b)
MATCH p2=(b)-[]->(n)-[]->(c)
MATCH p3=(c)-[]->(n)-[]->(a)
RETURN a, b, c, n, p1, p2, p3