Cypher: how to find all chains of single nodes that are not repeated?
I want to find ALL paths starting and ending from / to a specific node. I would like each node in the path to appear only once.
For example, in a graph like this:
(a)-[:REL]->(b)-[:REL]->(c)-[:REL]->(a)
(a)-[:REL]->(e)-[:REL]->(f)-[:REL]->(a)
(e)-[:REL]->(b)
Graphically:
e → b
↙ ↖ ↗ ↘
f → a ← c
Cypher code:
CREATE (a { name:'A' })-[:REL]->(b {name:'B'})-[:REL]->(c { name:'C' })
-[:REL]->(a)-[:REL]->(e {name:'E'})-[:REL]->(f {name:'F'})-[:REL]->(a),
(e)-[:REL]->(b)
I would like the exploration of chains starting with (a) to return
(a)->(b)->(c)->(a)
(a)->(e)->(f)->(a)
(a)->(e)->(b)->(c)->(a)
starting at (f) only returns
(f)->(a)->(e)->(f)
and NOT
(f)->(a)->(b)->(c)->(a)->(e)->(f)
as it goes through node (a) twice.
I tried:
MATCH p=(a {name:'F'})-[:REL*1..]->(a)
WHERE SINGLE(e1 IN TAIL(NODES(p)) WHERE SINGLE(e2 IN TAIL(NODES(p)) WHERE e1=e2))
RETURN p
but I have no result. The best I could achieve is not to repeat just the beginning of a node with this query:
MATCH p=(a {name:'F'})-[:REL*1..]->(a)
WHERE SINGLE(e IN TAIL(NODES(p)) WHERE e=a)
RETURN p
but obviously this is not what I want because it returns as well
(f)->(a)->(b)->(c)->(a)->(e)->(f)
this is a path including node (a) twice.
Can anyone suggest me a solution?
Thanks in advance.
PS The version of Neo4j I am using is 2.0
source to share
On the shoulders of those who came before, I came up with:
MATCH (a { name:'A' })
MATCH (a)-[p:REL]->(s)
WITH a, s
MATCH p = s-[r:REL*]->a
WITH [a] + nodes(p) AS ns
WHERE ALL (n IN ns
WHERE 1=LENGTH(FILTER(m IN TAIL(ns)
WHERE m = n)))
RETURN ns
It uses an idea from @FrobberOfBits to do the initial steps and then a query related to Michael to do a filter by paths. I suppose HYLE could be ignored if you also refused:
WITH [a] + nodes(p) AS ns
What this request could do:
MATCH (a { name:'A' })
MATCH (a)-[p:REL]->(s)
WITH a, s
MATCH p = s-[r:REL*]->a
WITH a, nodes(p) AS ns
WHERE ALL (n IN ns
WHERE 1=LENGTH(FILTER(m IN ns
WHERE m = n)))
RETURN [a] + ns
The tricky, or at least slightly difficult to read, part of the query is ALL
when combined with FILTER
which "basically" for all values in ns (WHERE ALL (n in ns)
counts the number of occurrences compared to all other values in array ( m IN ns WHERE m = n
) and completely filters the result if the resulting array does not contain one element ( 1=LENGTH
).
I've added your example to the console here .
source to share
So, here's some data calculated to copy your example:
$ create (a:T {label:"A"})-[:REL]->(b:T)-[:REL]->(c:T)-[:REL]->(a);
+-------------------+
| No data returned. |
+-------------------+
Nodes created: 3
Relationships created: 3
Properties set: 1
Labels added: 3
20 ms
neo4j-sh (?)$ match (a:T {label:"A"})
> CREATE a-[:REL]->(e:T)-[:REL]->(f:T)-[:REL]->(a);
+-------------------+
| No data returned. |
+-------------------+
Nodes created: 2
Relationships created: 3
Labels added: 2
27 ms
Now, here's a query that will get you there (but that needs some explanation).
match (a:T {label: "A"})-[:REL]->(somethingElse),
p=shortestPath((somethingElse)-[:REL*]->(a))
return p;
OK, so it seems to me that you want the shortest path from (a) back to yourself. But this is tricky because the shortest path from node to itself is always an empty path of length 0. So, if you do something like this shortestPath((a)-[:REL*]->(a))
, the result will always be empty, which is not what you want.
So instead, I mapped one :REL
hop to the next element ( somethingElse
) and then followed the shortest path from it to A. The returned return path p
is exactly the path you want, except it lacks the original hop from a-->somethingElse
. If you factor in this extra jump, then the combination a-->somethingElse
with p
should be the answer you're looking for.
source to share