Search code examples
neo4jcyphergraph-theorygraph-traversal

Traversing Relationships a Variable Number of Times in Cypher

I have a graph of Airports, Routes between them and Airlines that carry it. I created routes as separate nodes, rather than just a relationship, so that I can connect each with an Airline, and other nodes.

Each Route node has an IS_FROM relationship with the origin airport and an IS_TO relationship with the destination. It also has an IS_BY relationship with its airline: enter image description here

I am trying to traverse this tree, n times, for routes between two airports. For example, if n = 3, I want to get all the routes, that will lead from LAX to LHR, with 3 or fewer connections.

So basically, my result would be a union of the following: No Connecting Airports:

MATCH (a1:Airport {iata : 'LAX'})<-[:IS_FROM]-(r:Route)-[:IS_TO]->(a2:Airport {iata : 'LHR'}), (r)-[:IS_BY]->(ai:Airline) return a1 , r , a2 , ai;

1 Connecting airports:

MATCH (a1:Airport {iata : 'LAX'})<-[:IS_FROM]-(r:Route)-[:IS_TO]->(a2:Airport)<-[IS_FROM]-(r2:Route)-[:IS_TO]->(a3:Airport {iata: 'LHR'}), (r2)-[:IS_BY]->(ai:Airline) return a1 , r , a2 , a3 , r2 , ai;

and so on.

So the query should dynamically traverse the (:Airport)<-[:IS_FROM]-(:Route)-[:IS_TO]->(:Airport) pattern n times, and return the nodes (I am more interested in returning the Airlines that connect to those routes.

Solution

  • You can first extract all the paths between Airports that are 3 or less hops away, and then use OPTIONAL MATCH to see which of the nodes in the path are Routes, and which Airlines are offering them.

    MATCH path = (:Airport {iata:$start_airport})-[*2..6]-(:Airport {iata:$end_airport})
WITH path,nodes(path) as path_airports_and_connecting_routes
UNWIND path_airports_and_connecting_routes as node
OPTIONAL MATCH (node)-[:IS_BY]-(airline:Airline)
WITH collect(node) as airports_and_routes,airline
RETURN airports_and_routes + [airline]

    Caveat: Variable-length paths don't allow passing parameters, so you can't do something like [*2..2*n].