Path with two different relationship labels. One label option another required

[cvjones17]

Consider a simple graph like:

A-[:label1]->B-[:label2]->C-[:label1]->D-[:label1]->E-[:label2]->F

I'd like to find paths in the graph that have both label1 and label2, e.g.,

MATCH r=(n1)-[x:label1|label2*]->(n2)

In addition, if a node x has a relationship of type 'label2', e.g., x-[:label2]->y then if x is in the path, I need y to be included as well. This restriction doesn't apply to label1.

So for the graph in question, a path of form A->B->C is acceptable, but path A->B is not.

I've tried something like:

MATCH r=(n1)-[x:label1|label2*]->(n2)
WITH nodes(r) as allnodes, n1, n2
WHERE
none (y in allnodes where exists ((y)-[q:label2]->(z)) AND not (z in allnodes))

RETURN allnodes,n1,n2

But the syntax checker doesn't like it, saying:

Variable q not defined (line 6, column 40 (offset: 260))
"none (y in allnodes where exists ((y)-[q:label2]->(z)) AND not (z in allnodes))"

I'm sure there's a simple way to do this in Cypher, but I haven't yet figured it out.

Thanks in advance for your help.

[terryfranklin82]

The logic of your query may still need tweaking, but for the syntax error have you simply tried removing the q? Once you move into the conditional part of a query (WHERE..) I don't believe you can introduce new variables in this way (and probably don't need to).

[cvjones17]

cvjones17:

MATCH r=(n1)-[x:label1|label2*]->(n2)
WITH nodes(r) as allnodes, n1, n2
WHERE
none (y in allnodes where exists ((y)-[q:label2]->(z)) AND not (z in allnodes))

RETURN allnodes,n1,n2

Dear Terry:

Thanks for the help. I tried removing 'q' (and 'z', since that doesn't work either), and tried the following query:

MATCH r=(n1)-[x:label1|label2*]->(n2)
WITH r, nodes(r) as allnodes, n1, n2
WHERE
none (y in allnodes where exists ((y)-[:label2]->()) )

RETURN r

This query returns a single edge, C->D, which is not allowed since there's a 'label2' edge connected to C. A valid response would be B->C->D

Here's cypher code to create the sample graph:

CREATE (a:Node {name:'A' })
CREATE (b:Node {name:'B'})
CREATE (a)-[:label1 ]->(b)

CREATE (c:Node {name:'C' })
CREATE (b)-[:label2 ]->(c)
CREATE (d:Node {name:'D' })
CREATE (c)-[:label1 ]->(d)

CREATE (e:Node {name:'E' })
CREATE (d)-[:label1 ]->(e)
CREATE (f:Node {name:'F' })
CREATE (e)-[:label2 ]->(f)

[cvjones17]

Here's another unsuccessful attempt using apoc.path.expand:

MATCH (p:Node)
CALL apoc.path.expand(p, "label2>|label1>", null,0,10)
YIELD path
where length(path) > 0
return nodes(path) as allnodes

"allnodes" │
╞══════════════════════════════════════════════════════════════════════╡
│[{"name":"A"},{"name":"B"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"A"},{"name":"B"},{"name":"C"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"A"},{"name":"B"},{"name":"C"},{"name":"D"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"A"},{"name":"B"},{"name":"C"},{"name":"D"},{"name":"E"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"A"},{"name":"B"},{"name":"C"},{"name":"D"},{"name":"E"},{"na│
│me":"F"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"B"},{"name":"C"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"B"},{"name":"C"},{"name":"D"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"B"},{"name":"C"},{"name":"D"},{"name":"E"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"B"},{"name":"C"},{"name":"D"},{"name":"E"},{"name":"F"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"C"},{"name":"D"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"C"},{"name":"D"},{"name":"E"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"C"},{"name":"D"},{"name":"E"},{"name":"F"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"D"},{"name":"E"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"D"},{"name":"E"},{"name":"F"}] │
├──────────────────────────────────────────────────────────────────────┤
│[{"name":"E"},{"name":"F"}] │
└───────────────────────────

This is a superset of the desired response. The rows that need to be filtered out are:

A->B
A->B->C->D->E
C->D
C->D->E->F
D->E

[cvjones17]

The following query, using 'CALL' seems to work:

MATCH r=(n1)-[x:label1|label2*]->(n2)
WITH relationships(r) as allpaths, nodes(r) as allnodes,n1,n2
CALL {
    WITH allpaths, allnodes,n1,n2
    OPTIONAL MATCH (n2)-[:label2]->(n3)
    OPTIONAL MATCH (n4)-[:label2]->(n1)
    RETURN n1 as nx, n2 as ny, n3, n4, allnodes as allnodesx,allpaths as allpathsx
}
WITH nx,ny,n3, n4, allnodesx, allpathsx
WHERE n3 is null and n4 is null
RETURN n4,nx,ny,n3, allnodesx, allpathsx

Is there an easier way to do this?

[andrew_bowman]

Yes, there should be a much easier way to do this.

Sounds like all you need to make sure of is that your start and end nodes don't have any associated :label2 relationships. We can do this by excluding patterns like that in the WHERE clause:

MATCH path = (start:Node)-[:label1|label2*]->(end:Node)
WHERE NOT ()-[:label2]->(start) AND NOT (end)-[:label2]->()
RETURN [node in nodes(path) | node.name] as pathNodes 

You can also just return the path variable if that's easier.