finding isolated relationship cypher

Question

I want to find isolated relationship in a graph. For example, let's say I have 7 nodes. (n1 to n7). n1 only knows n2, and n2 only knows n1 and n3-n6 knows each other. And n7 knows n6 and n6 knows n7.

I want to return n1 and n2 only. (because they are only connect to each other once and have no other out going connection. (different than n7 and n6 which n6 has out going connection besides n7) I search the stack overflow and find this Neo4j - Cypher return 1 to 1 relationships. However the solution doesn't seem to be working in my case because of the bi-directional relationship between two nodes.

This can be very easily accomplish using traverse api, but I want to see whether it can be done in cypher or not

Here is the neo4j console. I use this query to return nodes have only 1 connection http://console.neo4j.org/r/hvq7wr

Answer 1

Looks like this query solves my problem, but open to other suggestion also

match (a:Node)-[:KNOWS]-> (b:Node)
with a, count(*) as count
where count = 1
match (a)-[r:KNOWS]->(c)-[r1:KNOWS]->(d:Node)
where id(a)<id(c)
with a,c, collect(r1) as rs
where length(rs)=1
return a,c

I'd probably use count in the second part too:

MATCH (a:Node)-[:KNOWS]->(b:Node) 
WITH a, count(*) AS count 
WHERE count = 1 
MATCH (a)-[r:KNOWS]->(c)-[r1:KNOWS]->(d:Node) 
WHERE id(a)<id(c) 
WITH a,c, count(DISTINCT r1) AS rs 
WHERE rs=1 
RETURN a,c

Answer 2

I thought I'd try to come up with an alternative that works also if the relationships are not symmetric, or if you want to represent symmetry by leaving out relationship direction in your queries rather than with double relationships in the database (thousands of bytes are at stake, like Jack Bauer would say). My first idea was a bust, but I think this works:

MATCH p=(a:Node)-[:KNOWS]-(b:Node)-[r:KNOWS*0..1]-(c:Node)
WHERE NOT (a)-[:KNOWS*3]-() AND NOT (b)-[:KNOWS*3]-() 
WITH a, reduce(
    allNodes = [], path in collect(p) | allNodes + filter(
        n in nodes(path) WHERE NOT n IN allNodes
    )
) as allNodes
WHERE length(allNodes) = 2
RETURN a

When I run this query in a Neo4j console I am told I am doing something exceptional (thanks!), it says Error: org.neo4j.kernel.guard.GuardOperationsCountException: max ops (ops=10001). Maybe that's a hint to improve the query (?), but it works fine when I run it locally.

Basically I figured, if not

(a)-[:KNOWS]->(b) => (b)-[:KNOWS]->(a)

then you can get false positives with your query when (b:Node) has exactly one outgoing relationship but it is not to (a:Node), and false negatives when (b:Node) has no outgoing relationships.

(a)-[:KNOWS]->(b)-[:KNOWS]->(c) AND a<>c    // false positive
(a)-[:KNOWS]->(b) AND NOT (b)-[:KNOWS]->()  // false negative

A different way to think of the criteria is that the pattern you want is a) one or two relationships deep, b) not part of a longer pattern, c) contains only two distinct nodes, so that's what I tried to describe in my alternative version above. The first two criteria were easy to state, but the third was less obvious than I had thought. I feel like there's probably a much simpler way, do edit or comment if you see it. (I first tried using distinct rather than filter() but I must be confused because I couldn't get that to work).