Neo4j Cypher: check attributes of not consecutive nodes in path

Question

I have got a graph that represents several bus/train stops in different cities. Lets assume I want to go from city A (with stops a1, a2, a3...) to city Z (with stops z1, z2...)

There are several routes (relations) between the nodes and I want to get all paths between the start and the end node. My cost vector would be complex (travel time and waiting time and price and and and...) in reality, therefore I cannot use shortestpaths etc. I managed to write a (quite complex) query that does what I want: In general it is looking for each match with start A and end Z that is available.

I try to avoid looping by filter out results with special characteristics, e. g.

MATCH (from{name:'a1'}), (to{name:'z1'}),
path = (from)-[:CONNECTED_TO*0..8]->(to)    
WHERE ALL(b IN NODES(path) WHERE SINGLE(c IN NODES(path) WHERE b = c))

Now I want to avoid the possiblity to visit one city more than once, e. g. instead of a1-->a2-->d2-->d4-->a3-->a4-->z1 I want to get a1-->a4-->z1.

Therefore I have to check all nodes in the path. If the value of n.city is the same for consecutive nodes, everything is fine. But If I got a path with nodes of the same city that are not consecutive, e. g. cityA--> cityB-->cityA I want to throw away that path.

How can I do that? Is something possible?

I know, that is not really a beatiful approach, but I invested quite a lot of time in finding a better one without throwing away the whole data structure but I could not find one. Its just a prototype and Neo4j is not my focus. I want to test some tools and products to build some knowledge. I will go ahead with a better approach next time.

cybersam cybersam · Accepted Answer · 2017-04-09T00:03:09

Interesting question. The important thing to observe here is that a path that never revisits a city (after leaving it) must have fewer transitions between cities than the number of distinct cities. For example:

AABBC (a "good" path) has 3 distinct cities and 2 transitions
ABBAC (a "bad" path) also has 3 distinct cities but 3 transitions

With this observation in mind, the following query should work (even if the start and end nodes are the same):

MATCH path = ({name:'a1'})-[:CONNECTED_TO*0..8]->({name:'z1'})
WITH path, NODES(path) as ns
WITH path, ns,
  REDUCE(s = {cnt: 0, last: ns[0].city}, x IN ns[1..] |
    CASE WHEN x.city = s.last THEN s ELSE {cnt: s.cnt+1, last: x.city} END).cnt AS nTransitions
UNWIND ns AS node
WITH path, nTransitions, COUNT(DISTINCT node.city) AS nCities
WHERE nTransitions < nCities
RETURN path;

The REDUCE function is used to calculate the number of transitions in a path.

Neo4j Cypher: check attributes of not consecutive nodes in path

1 Answers