I'm running Neo4j 3.4.18 with graph-algorithms-algo-3.4.12.7. I need to find a shortest path between two given nodes, but only running through nodes with a specific type, that is on a subset of Graph.
Let me first briefly describe the data model first. My graph represents a building, it consist of:
- Map - representation of a concrete building instance
- Floor - self explanatory - a single floor in the building
- Room - a single room located on the floor
- EntrancePoint / Point - point in space with cartesian coordinates which marks an entrance to the Room. Room can have one or more of them
- RoutePoint / Point - point in space with cartesian coordinates which is a part of Route, by which a person can travel through the building - from one room to another
All Point subtypes (EntrancePoint. RoutePoint) are linked with a :CONNECTS
relationship, which has a distance
attribute.
Sample data:
MERGE (map:Map {name:'Building'})
MERGE (map)<-[:IS_PART_OF]-(floor:Floor {level: 0, name: 'Ground Floor'})
MERGE (floor)<-[:BELONGS_TO]-(r1:Room {name: 'Kitchen'})
MERGE (floor)<-[:BELONGS_TO]-(r2:Room {name: 'Garage'})
MERGE (floor)<-[:BELONGS_TO]-(r3:Room {name: 'Living Room'})
MERGE (e1:Point:EntrancePoint {x: 5, y: 10})-[:GIVES_ACCESS_TO]->(r1)
MERGE (e2:Point:EntrancePoint {x: 10, y: 20})-[:GIVES_ACCESS_TO]->(r1)
MERGE (e3:Point:EntrancePoint {x: 20, y: 30})-[:GIVES_ACCESS_TO]->(r2)
MERGE (e4:Point:EntrancePoint {x: 30, y: 40})-[:GIVES_ACCESS_TO]->(r3)
MERGE (rp1:Point:RoutePoint {x: 7, y: 5})-[:CONNECTS {distance: 5}]->(e1)
MERGE (rp2:Point:RoutePoint {x: 12, y: 5})-[:CONNECTS {distance: 3}]->(rp1)
MERGE (rp3:Point:RoutePoint {x: 30, y: 8})-[:CONNECTS {distance: 8}]->(rp2)
MERGE (rp4:Point:RoutePoint {x: 40, y: 12})-[:CONNECTS {distance: 12}]->(rp3)
MERGE (rp4)<-[:CONNECTS {distance: 13}]-(rp5:Point:RoutePoint {x: 0, y: 10})-[:CONNECTS {distance: 26}]->(rp3)
MERGE (rp4)-[:CONNECTS {distance: 20}]->(e3)
MERGE (e2)-[:CONNECTS {distance: 15}]->(rp3)
MERGE (e4)-[:CONNECTS {distance: 2}]->(rp4)
Visual representation:
So the task is to find the shortest route from one Room to Another, for example from r1 (Kichten) to r2 (Garage). Assumptions:
- travel happens only through
CONNECTS
relationships, which link EntrancePoints of Rooms - Dijkstra must use
distance
attribute assigned toCONNECTS
rels
Wanted results - a full list of Points between two Rooms, including EntrancePoints and RoutePoints; a table like in this docs example would be great: https://neo4j.com/docs/graph-algorithms/current/labs-algorithms/shortest-path/#algorithms-shortest-path-sample
Edit:
Partially solved with a query:
MATCH (start:Room {name: 'Living Room'})-[:GIVES_ACCESS_TO]-(ep_start:EntrancePoint), (end:Room {name: 'Garage'})-[:GIVES_ACCESS_TO]-(ep_end:EntrancePoint)
CALL algo.shortestPath.stream(ep_start, ep_end, 'distance',{
nodeQuery:'MATCH(n) RETURN id(n) as id',
relationshipQuery:'MATCH(n:Point)-[r:CONNECTS]-(m:Point) RETURN id(n) as source, id(m) as target, r.distance as weight',
direction: 'both',
graph:'cypher'})
YIELD nodeId, cost
RETURN nodeId, cost
However, when a Room has multiple EntrancePoints (that is the case with Living Room
), the results contains both shortest paths - starting from both EntrancePoints, that is:
[[183, 0.0], [187, 5.0], [199, 8.0], [200, 16.0], [201, 28.0], [185, 48.0], [184, 0.0], [200, 15.0], [201, 27.0], [185, 47.0]]
An ideal solution would be to return only one truely shortest path, starting from any EntrancePoint
, thus when Rooms would be entered as start and end arguments to algo.shortestPath.stream
, but I don't know how to build relationshipQuery to make it work.
Example failed attempt:
MATCH (start:Room {name: 'Kitchen'}), (end:Room {name: 'Garage'})
CALL algo.shortestPath.stream(start, end, 'distance',{
defaultValue: 0.0,
nodeQuery:'MATCH (n) RETURN id(n) as id',
relationshipQuery:'MATCH (r1:Room)-[:GIVES_ACCESS_TO]-(Point)-[r:CONNECTS]-(Point)-[:GIVES_ACCESS_TO]-(r2:Room) RETURN id(r1) as source, id(r2) as target, r.distance as weight',
graph:'cypher'})
YIELD nodeId, cost
RETURN nodeId, cost