neo4j: shortest path with minimal relationship property variance

Question

I created the following graph to model a transit network, where stops are connected to other stops via service nodes (service nodes define specific days of service). The relationships have distinct types and properties. Specifically GOES_TO relationships have an id property which identifies a trip (e.g. bus) travelling between the stops.

neo4j graph model

I wish to find the shortest path with the minimum number of distinct id values among all :GOES_TO relationships on the path.

In the case above, the shortest path should be:

(A)-[:USES]-(1:Service)-[:GOES_TO {id:7}]->(B)-[:USES]-(2:Service)-[:GOES_TO {id:7}]->(D)

This path uses a single id:7 to get from A to D.

Note that the condition applies only for :GOES_TO relationships. :USES relationships do not have and id property at all.

I have tried several approaches but cannot seem to get this seemingly simple problem resolved with cypher.

Did you solved your problem? Can you describe, How did you solved? — user3566301

Eve Freeman Eve Freeman · Accepted Answer · 2013-12-05T19:53:08

Cypher can't do weighted shortest paths efficiently yet (hopefully soon!), but a workaround is to use reduce to aggregate over the path--the caveat being that it will need to look at all of the paths. Maybe something like this:

MATCH p=(a:Stop)-[*]->(d:Stop)
WHERE a.name='A' and d.name='D'
RETURN p, 
  length(reduce(acc=[], r in rels(p)| acc + 
  case 
    when type(r) = "GOES_TO" 
     and NOT r.id IN acc 
    then r.id 
    else [] 
  end)) as distinctIds
ORDER BY distinctIds ASC;

If it's not fast enough for you, you can get this to work pretty easily with the dijskstra's algorithm in an unmanaged extension on the server via the graphalgo package (or in embedded).

neo4j: shortest path with minimal relationship property variance

1 Answers