Join the community at Nodes 2022, our free virtual event on November 16 - 17.
β11-06-2020 12:38 AM
Hello everybody,
I have this simple graph:
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.
Solved! Go to Solution.
β11-09-2020 12:51 AM
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/
β11-06-2020 10:33 AM
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?
β11-07-2020 08:15 AM
Yes that's right. Maybe I just have to limit the results with a condition on my "cost" parameter.
β11-09-2020 12:51 AM
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/