Finding common complete path between multiple input nodes

Neo4j Graph Platform Cypher
,
1

Hello,
I am pretty new to CYPHER and NEO4J.
My requirement is to find the relations of an array of input nodes.
Example:
graph db

I am using the following query,

WITH ["A", "B","F"] AS names
  UNWIND names AS nn
    MATCH (n {name: nn})
    WITH collect(n) AS nds
  
  UNWIND nds AS n1
    UNWIND nds AS n2
    WITH nds, n1, n2 WHERE id(n1) > id(n2)
      MATCH path = allShortestPaths((n1)-[*]-(n2))
      WITH nds, path WHERE ALL(n IN nds WHERE n IN nodes(path))
  RETURN path ORDER BY length(path) ASC

getting the following output which is correct,
output1

But when I gave input ["A", "B","F","H"] in the query I am getting empty output which is not desired.
The desired output is similar to the above mentioned output but also containing A->H relation.
Please let me know where I am going wrong and what needs to be done.

Thanks in advance,
Krishna Kiriti

2

Hi @kiriti.chinthapalli,

In your example Node G is in between A and H, but is not in your allowed set of values.

The WHERE all near the end of the query requires all nodes in the path to be in the NDA array.

Hope that helps!

3

But the same query works for the inputs "A","B", "H'.

WITH ["A", "B","H"] AS names
UNWIND names AS nn
MATCH (n {name: nn})
WITH collect(n) AS nds

UNWIND nds AS n1
UNWIND nds AS n2
WITH nds, n1, n2 WHERE id(n1) > id(n2)
MATCH path = allShortestPaths((n1)--(n2))
WITH nds, path WHERE ALL(n IN nds WHERE n IN nodes(path))
RETURN path ORDER BY length(path) ASC

Output:
image

4

If you follow your logic this is what is happening

A -> B
A -> F
A -> H
B -> A
B -> F
B -> H
..

If you follow these paths you can see that there is not a single path where all nodes you have selected are present ( A, B, F, H)

That's why it is returning empty path.

For A, B, H the for path matching is B -> H you have all of your selected nodes, that's why you are seeing results.

5

Thanks for the reply. so what I am doing here just retrieving a single common path then. so it will not return multiple paths.
What to do to achieve my requirement ?

6

I'm not sure I'm following this.

The reason why you weren't getting results with A, B, F, and H was because there is no single common path that can connect them all.

A path only has a single start node, and a single end node, and it cannot reuse relationships in the path (relationship isomorphism). Because of this, F and H are dead ends. Once you reach there, the path cannot continue. So you can go B-A-F, or B-A-G-H, or F-A-G-H (or the reverse of any of those). But you cannot go B-A-F-A-G-H because it reuses the relationship between A and F.

So you cannot return the graph you want with a single path. It would require an approach that generates multiple paths, and the graph formed by those multiple paths would include all 4 nodes.