cancel
Showing results for 
Search instead for 
Did you mean: 

Join the community at Nodes 2022, our free virtual event on November 16 - 17.

Limit single source shortest path algorithm results by relationships orientation

nico_pelissero
Node Clone

Hello everybody,
I have this simple graph:
2X_a_abe87badbf3f9eafc4dc6ee92a4d57a3f9245b45.png

And I perform single source shortest path algorithm on it to obtain all the path cost, for all the nodes, from one node. I run this following query (starting from node 'T' for the example) :

MATCH (n{name: 'T'})  
CALL gds.alpha.shortestPath.deltaStepping.stream({
nodeProjection: ['DIGITAL_SUBSYSTEM','PHYSICAL_SUBSYSTEM'], 
relationshipProjection: {link: {type: '*', properties: 'exposure', orientation: 'NATURAL'}},
startNode: n, relationshipWeightProperty: 'exposure', delta: 1.0})  
YIELD nodeId, distance
RETURN gds.util.asNode(nodeId).name AS node , distance AS cost ORDER BY cost

I obtain the following table:

I'm pretty satisfied with the results but I would like to remove from my query the nodes linked with a REVERSE relationship orientation (with a cost value "infinity" in my table) .

Maybe I should use nodeQuery and relationshipQuery instead of nodeProjection and relationshipProjection ?
Like this example I have found in Neo4j shortest path algorithm documentation (not single source):

MATCH (start:Loc {name: 'A'}), (end:Loc {name: 'F'})
CALL gds.alpha.shortestPath.write({
  nodeQuery:'MATCH(n:Loc) WHERE NOT n.name = "c" RETURN id(n) AS id',
  relationshipQuery:'MATCH(n:Loc)-[r:ROAD]->(m:Loc) RETURN id(n) AS source, id(m) AS target, r.cost AS weight',
  startNode: start,
  endNode: end,
  relationshipWeightProperty: 'weight',
  writeProperty: 'sssp'
})
YIELD nodeCount, totalCost
RETURN nodeCount,totalCost

Other question, I specified orientation: NATURAL in my initial query, why it doesn't remove the node "P3" that is linked to "PLC2" with a REVERSE relationship ?

Thanks for your help,

Nicolas.

1 ACCEPTED SOLUTION

nico_pelissero
Node Clone

For the person who would have the same problem.

I find the solution: I just modify my initial query by adding WHERE gds.util.isFinite(distance)

So my initial query become :

MATCH (n{name: 'T'})  CALL gds.alpha.shortestPath.deltaStepping.stream({
nodeProjection: ['DIGITAL_SUBSYSTEM','PHYSICAL_SUBSYSTEM'], 
relationshipProjection: {link: {type: '*', properties: 'exposure', orientation: 'NATURAL'}},
startNode: n, relationshipWeightProperty: 'exposure', delta: 1.0})  
YIELD nodeId, distance
WHERE gds.util.isFinite(distance) 
RETURN gds.util.asNode(nodeId).name AS node , distance AS cost  ORDER BY cost

I find the solution here https://neo4j.com/docs/graph-algorithms/current/labs-algorithms/all-pairs-shortest-path/ and here https://neo4j.com/docs/graph-algorithms/current/labs-procedures/

View solution in original post

3 REPLIES 3

Joel
Ninja
Ninja

Looking through the documentation here, and seeing your results, my best guess is that this algorithm is calculating the shortest path to every node?

A distance of Infinity would say that the node is unreachable (via NATURAL graph paths) right?

Yes that's right. Maybe I just have to limit the results with a condition on my "cost" parameter.

nico_pelissero
Node Clone

For the person who would have the same problem.

I find the solution: I just modify my initial query by adding WHERE gds.util.isFinite(distance)

So my initial query become :

MATCH (n{name: 'T'})  CALL gds.alpha.shortestPath.deltaStepping.stream({
nodeProjection: ['DIGITAL_SUBSYSTEM','PHYSICAL_SUBSYSTEM'], 
relationshipProjection: {link: {type: '*', properties: 'exposure', orientation: 'NATURAL'}},
startNode: n, relationshipWeightProperty: 'exposure', delta: 1.0})  
YIELD nodeId, distance
WHERE gds.util.isFinite(distance) 
RETURN gds.util.asNode(nodeId).name AS node , distance AS cost  ORDER BY cost

I find the solution here https://neo4j.com/docs/graph-algorithms/current/labs-algorithms/all-pairs-shortest-path/ and here https://neo4j.com/docs/graph-algorithms/current/labs-procedures/