CODEWITHSUNDEEP
neo4jcyphershortest-path
Erik Hofer
Erik Hofer

Reputation: 2646

Cypher match path with intermediate nodes

I have the following graph with Stop (red) and Connection (green) nodes.

enter image description here

I want to find the shortest path from A to C using a cost property on Connection.

I would like to avoid making Connection a relationship because than I loose the CONTAINS relationship of Foo.

I can match a single hop like this

MATCH p=(:Stop {name:'A'})<-[:BEGINS_AT]-(:Connection)-[:ENDS_AT]->(:Stop {name:'B'}) RETURN p

but this does not work with an arbitrary number of Connections like it would with relationships and [*].

I also tried to make a projection down to simple relationships but it seems like I cannot do something with this without GDS.

MATCH (s1:Stop)<-[:BEGINS_AT]-(c:Connection)-[:ENDS_AT]->(s2:Stop) RETURN id(s1) AS source, id(s2) AS target, c.cost AS cost

Note that the connection is unidirectional, so it must not be possible to go from C to A.

Is there a way to do this without any Neo4j plugins?

Upvotes: 0

Views: 542

Answers (2)

cybersam
cybersam

Reputation: 66989

This should get all usable paths (without plugins):

WITH ['BEGINS_AT', 'ENDS_AT'] AS types
MATCH p=(a:Stop)-[:BEGINS_AT|ENDS_AT*]-(b:Stop)
WHERE a.name = 'A' AND b.name = 'B' AND
  ALL(i IN RANGE(0, LENGTH(p)-1) WHERE TYPE(RELATIONSHIPS(p)[i]) = types[i%2])
RETURN p

To get the shortest path:

WITH ['BEGINS_AT', 'ENDS_AT'] AS types
MATCH p=(a:Stop)-[:BEGINS_AT|ENDS_AT*]-(b:Stop)
WHERE a.name = 'A' AND b.name = 'B' AND
  ALL(i IN RANGE(0, LENGTH(p)-1) WHERE TYPE(RELATIONSHIPS(p)[i]) = types[i%2])
RETURN p
ORDER BY LENGTH(p)
LIMIT 1;

or

WITH ['BEGINS_AT', 'ENDS_AT'] AS types
MATCH p=shortestpath((a:Stop)-[:BEGINS_AT|ENDS_AT*]-(b:Stop))
WHERE a.name = 'A' AND b.name = 'B' AND
  ALL(i IN RANGE(0, LENGTH(p)-1) WHERE TYPE(RELATIONSHIPS(p)[i]) = types[i%2])
RETURN p

Upvotes: 1

Tomaž Bratanič
Tomaž Bratanič

Reputation: 6514

If you want to calculate the weighted shortest path, then it is the easiest to use GDS or even APOC plugin. You could probably create a shortest weighted path function with cypher but it would be not optimized. I can only think of finding all paths between the two nodes and suming the weights. In the next step you would filter the path with the minimum sum of weight. This would not scale well though.

As for the second part of your question I would need more information as I dont know exactly what you want.

Upvotes: 0

Related Questions