Gds allShortestPaths return ArrayIndexOutOfBoundsException

Neo4j Graph Platform Graph Algorithms/Graph Data Science
1

Hi guys and gals,
I'm working on a wee project trying to route between points of interest and parking spaces in a car park. My data is exported from OpenStreetMap, and I've relied a lot on the info from Craig Taverner and William Lyon in the Going Spatial Talk...
So far things are working pretty well. I can route between nodes and export the results as GeoJSON when using the old shortestPath functions.. I can even ger results from the gds alShortestPaths. What I can't do is define which target nodes should be looked for.

I assumed that the nodeProjection in an anonymous graph would dictate which types of nodes would be searches as a target.. Am I wrong in this assumption? When I run the following query:

MATCH(x:PointOfInterest)-[:TAGS]-(t:OSMTags) WHERE t.name contains('Sunrise')
CALL gds.beta.allShortestPaths.dijkstra.stream(
    {
        sourceNode:id(x),
        nodeProjection: ["ParkingSpaceNode"],
        relationshipProjection:{
            all:{
                    type:"ROUTE",
                    properties:"distance",
                    orientation:"UNDIRECTED"
            }
        },
        relationshipWeightProperty:"distance"
    })
    YIELD  targetNode, totalCost, nodeIds
    RETURN  targetNode, totalCost, nodeIds```

This should, in my opinion, return a list of targetNodes of Type "ParkingSpaceNode", with costs and an array of nodes along the paths.

But I get the following error:

Failed to invoke procedure gds.beta.allShortestPaths.dijkstra.stream: Caused by: java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 179


Of course, there are exactly 179 ParkingSpaceNodes in the DB.

Can anyone see from my query where I might be going wrong?
The ParkingSpaces are reachable from the specified source node using only the ROUTE relationship, by the way..

Many thanks in advance for any and all help!
Mike
2

Can you try this with our newest preview release? You can grab it from the download center: https://neo4j.com/download-center/#algorithms (version 1.6).

We promoted Dijkstra to the product tier, and we did a big of bug fixing, so if you could check if that release didn't throw the same error, that would be a huge help in sorting out the problem. Thank you! :pray:

3

Hi Alicia,
thanks for the tip. I tried the procure with the 1.6 Preview, but with the same results :frowning:
What does work, although I'm assuming it's not entirely efficient is running asp on all nodes and Matching the required nodes based on their id afterwards:

MATCH(x:PointOfInterest)-[:TAGS]-(t:OSMTags) WHERE t.name contains('Sunrise')
CALL gds.beta.allShortestPaths.dijkstra.stream(
{
    sourceNode:id(x),
    nodeProjection: '*',
    relationshipProjection:{
        all:{
                type:'ROUTE',
                properties:'distance',
                orientation:'UNDIRECTED'
        }
    },
    relationshipWeightProperty:'distance'
})
YIELD  targetNode, totalCost, nodeIds
WITH  totalCost, 
    nodeIds, 
    targetNode,  
    [nodeId IN nodeIds | gds.util.asNode(nodeId).location] as locs
MATCH(p:ParkingSpaceNode{reserved:false, occupied:false}) WHERE id(p) = targetNode
WITH p, 
    totalCost, 
    locs
ORDER By totalCost  LIMIT 1
UNWIND locs as pts
RETURN pts.x as lat, pts.y as lon
4

Taking a closer look at this ....

allShortestPaths finds the shortest path between your start node, and any other node in the graph. You can't specify target nodes (like you can with source/target). In your first example, when you specify ParkingSpaceNode for your node projection, you're essentially only allowing the shortest path algorithm to visit ParkingSpaceNodes and traverse ROUTE relationships.

The reason your second algorithm call works is you're allowing the algorithm to traverse any sort of node in your graph, and then filtering on a specific set of targets - I'm guessing the results traverse various node labels in between the source and target nodes.

I think there are two things we (Neo4j GDS team) can do here:

  • Better error messaging in the first case, and
  • You're really asking for a variant of the allShortestPaths algorithm where you supply a source node and a set of target nodes.

For now, my recommendation would be to use your second call - or better yet, use a named graph so you can run multiple individual shortestPath calls between source & specified target.

We'll take a look at better error messaging and documentation, and I'll add your feature request to our backlog :slight_smile:

5

Hi alicia,
yes, you're right, that's not strictly what a Dijkstra ASP should do ;)
It wasn't quite clear for me to start with how the nod projection should be used.
Speaking from my end-user side(my developer side is hitting me as I write this :slight_smile: ) any extra error messaging is always appreciated!

my second query works fine for my use-case. Thanks again for your input!

Mike

6

@edurodmic001 Thanks for reporting this. We improved the error message on missing source and target nodes. It'll be part of the 1.6 release.

1 Like