Dijkstra shortest path on a subset of Graph

[jacek213]

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 to CONNECTS 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: 9.4.2. The Shortest Path algorithm - 9.4. Path finding algorithms

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

[clair_sullivan]

There is definitely a way to do this using the Graph Data Science library. (In fact, the Graph Algorithms library that you are using via algo.x is now deprecated in favor of GDS.) One of the great things about GDS is the ability to create in-memory graphs, as described here, which allows you to create subgraphs of your complete graph based on things such as a given node type. Once you have the in-memory graph, you can then run a variety of algorithms on it, including a whole host of path-finding algorithms, including shortest path via Dijkstra, A*, etc.

That being said, I note that you are using Neo4j 3.4. In order to take advantage of GDS you will need to upgrade to at least 3.5 as per the list of supported versions here. If upgrading is a possibility for you, then I would recommend going to the latest version (Neo4j 4.2.x) because it allows you to use the latest versions of GDS, which have a lot of more sophisticated algorithms and a variety of bugs have been fixed along the way.

Please let us know if you are not able to upgrade beyond 3.4 and we can discuss further.

[jacek213]

@clair.sullivan thank you for your reply. I could try upgrading to 3.5, but as I'm currently using Ruby client v9.6.2 I won't be able to upgrade to any higher version than 3.5 right now (GitHub - neo4jrb/activegraph: An active model wrapper for the Neo4j Graph Database for Ruby.). Also I'd be grateful for getting a confirmation, that the solution I'm looking for would be possible with GDS and Neo4j v3.5, as the docs state that the shortest path algorithms are still in alpha. Would you be so kind to help me with writing appropriate query?

[jacek213]

So the above I've solved within the application (ruby) code - it simply required splitting returned results into groups and finding truly shortest path between EntrancePoints.

However, there's another problem that's been bothering me. My relationshipQuery looks like this right now:

MATCH(n:Point)-[r:CONNECTS]-(m:Point) RETURN id(n) as source, id(m) as target, r.distance as weight'

The thing is, that there's a need for implementing Portal node, which can be located between Points.

So, an example path to traverse between start and end point might now looks like this (Portal can happen between Points, but also might not):

(start:Point)-[:CONNECTS]-(:Point)-[:CONNECTS]-(:Point)-[:CONNECTS]-(portal:Portal)-[:CONNECTS]-(end:Point)`

How can I put Portal it into relationshipQuery and mark it as optional?