CODEWITHSUNDEEP
neo4j
Ondra
Ondra

Reputation: 57

Neo4J find route thru more points

I am creating simple graph db for tranportation between few cities. My structure is:

I need to find route from city A to city C, but i has no direct stopconnection, but they are connected thru city B. see picture please, as new user i cant post images to question.

How can I get router from City A with STOP 1 connect RIDE 1 to STOP 2 then STOP 2 connected by same City B to STOP3 and finnaly from STOP3 by RIDE2 to STOP4 (City C)?

Thank you.

UPDATE

Solution from Vince is ok, but I need set filter to STOP nodes for departure time, something like

MATCH p=shortestPath((a:City {name:'A'})-[*{departuretime>xxx}]-(c:City {name:'C'})) RETURN p

Is possible to do without iterations all matches collection? because its to slow.

Upvotes: 1

Views: 615

Answers (2)

Vince
Vince

Reputation: 2181

Ah ok, if the requirement is to find paths through the graph where the departure time at every stop is no earlier than the departure time of the previous stop, this should work:

MATCH p=(:City {name:'A'})-[*]-(:City {name:'C'})
MATCH (a:Stop) where a in nodes(p)
MATCH (b:Stop) where b in nodes(p)
WITH p, a, b order by b.time
WITH p as ps, collect(distinct a) as as, collect(distinct b) as bs
WHERE as = bs
WITH ps, last(as).time - head(as).time as elapsed 
RETURN ps, elapsed ORDER BY elapsed ASC

This query works by matching every possible path, and then collecting all the stops on each matched path twice over. One of these collections of stops is ordered by departure time, while the other is not. Only if the two collections are equal (i.e. number and order) is the path admitted to the results. This step evicts invalid routes. Finally, the paths themselves are ordered by least elapsed time between the first and last stop, so the quickest route is first in the list.

Normal warnings about performance, etc. apply :)

Upvotes: 1

Vince
Vince

Reputation: 2181

If you are simply looking for a single route between two nodes, this Cypher query will return the shortest path between two City nodes, A and C.

MATCH p=shortestPath((a:City {name:'A'})-[*]-(c:City {name:'C'})) RETURN p

In general if you have a lot of potential paths in your graph, you should limit the search depth appropriately:

MATCH p=shortestPath((a:City {name:'A'})-[*..4]-(c:City {name:'C'})) RETURN p

If you want to return all possible paths you can omit the shortestPath clause:

MATCH p=(a:City {name:'A'})-[*]-(c:City) {name:'C'}) RETURN p

The same caveats apply. See the Neo4j documentation for full details

Update After your subsequent comment.

I'm not sure what the exact purpose of the time property is here, but it seems as if you actually want to create the shortest weighted path between two nodes, based on some minimum time cost. This is different of course to shortestPath, because that minimises on the number of edges traversed only, not the cost of those edges.

You'd normally model the traversal cost on edges, rather than nodes, but your graph has time only on the STOP nodes (and not for example on the RIDE edges, or the CITY nodes). To make a shortest weighted path query work here, we'd need to also model time as a property on all nodes and edges. If you make this change, and set the value to 0 for all nodes / edges where it isn't relevant then the following Cypher query does what I think you need.

MATCH p=(a:City {name: 'A'})-[*]-(c:City {name:'C'})
RETURN p AS shortestPath, 
   reduce(time=0, n in nodes(p) | time + n.time) AS m,
   reduce(time=0, r in relationships(p) | time + r.time) as n 
   ORDER BY m + n ASC
   LIMIT 1

In your example graph this produces a least cost path between A and C:

(A)->(STOP1)-(STOP2)->(B)->(STOP5)->(STOP6)->(C)

with a minimum time cost of 230.

This path includes two stops you have designated "bad", though I don't really understand why they're bad, because their traversal costs are less than other stops that are not "bad".

Or, use Dijkstra

This simple Cypher will probably not be performant on densely connected graphs. If you find that performance is a problem, you should use the REST API and the path endpoint of your source node, and request a shortest weighted path to the target node using Dijkstra's algorithm. Details here

Upvotes: 2

Related Questions