Using the algo.allShortestPaths.stream algorithm on a subset of nodes

Neo4j Graph Platform Graph Algorithms/Graph Data Science
1

Hi,
I am new to the Neo4j community and have a question about the algo.allShortestPaths.stream algorithm.

I have modelled a warehouse graph in neo4j, in which I have the following Node types:

  • AisleLocation: a location in an aisle on which you can walk. (with property 'name')
  • Rack: a rack where products are stored. (with property 'name')

Nodes are connected by the relationship CONNECTS, which has a property 'distance' describing the distance between each of the connected nodes.

Rack nodes are never connected directly to each other, but always connected via an AisleLocation.

I now want to find the shortest path (weighted on 'distance') for each possible combination of a list of Rack locations. So for example, if I have a list of Rack location names ['x', 'y', 'z'] , I want to find the shortest path distances for:
'x' --> 'y'
'x' --> 'z'
'y' --> 'x'
'y' --> 'z'
'z' --> 'x'
'z' --> 'y'

I guess I need to use the algo.allShortestPaths.stream algorithm, but I couldn't find a way to tackle my problem just yet.

Thanks in advance.

Loek

2

Hi Loek,

This might help:

with ['x',"y","z"] as rackNames
unwind rackNames as rackName
match (r: Rack {name: rackName})
with collect(distinct r) as racks
unwind racks as rack1
unwind racks as rack2
with rack1, rack2 where rack1 <> rack2
CALL algo.shortestPath.stream(rack1, rack2, 'distance',{ relationshipQuery:'CONNECTS', direction:'OUTGOING'})
YIELD nodeId, cost
return algo.asNode(nodeId).name AS name, cost

Seyed

3

Thanks Seyed, this works. I btw also found another way. With large amounts of locations, this query is actually faster:

CALL 
      algo.allShortestPaths.stream("distance", {{
        nodeQuery:'MATCH (n) RETURN id(n) as id',
        relationshipQuery:'MATCH (n)-[r]-(p) RETURN id(n) as source, id(p) as target, r.distance as weight',
        graph:'cypher'}})
    YIELD 
      sourceNodeId, targetNodeId, distance
    WITH 
      sourceNodeId, targetNodeId, distance
    WHERE
      algo.isFinite(distance) = true
    
    MATCH 
      (source), 
      (target)
    WHERE 
      id(source) = sourceNodeId
      AND source.name in $locations
      AND id(target) = targetNodeId
      AND target.name in $locations
    
    WITH
      source, target, distance 
    WHERE
      source <> target
    RETURN 
      source.name AS source, 
      target.name AS target, 
      distance

In which $locations is an array of locations.

4

No problem @lbotman

The only concern I have with your cypher is that you first find all shortest paths between all nodes, and then filter out those that are not in locations. If you have a large graph, this might actually be quite expensive.

5

I agree. I actually fixed it now by adding a filter in the nodeQuery, which works for my specific case. But indeed, the query is quite expensive in case I don't apply the filter.