Shortest Path Question

Let’s pretend that I have a fleet of drones flying around, each drone has a com device, but they have to be within range of each other. I need to find the shortest path from drone A to Drone X.

I am thinking of using Dijkstra Source-Target Shortest Path. Maybe there is a better way, if so please let me know.

Each drone has its current GPS settings in the graph, but currently weighted relationships between them don’t exist. Weights will be calculated based on power levels and distances when I create these relationships. All these relationships need to be created for each request then removed as the drone positions are, changing..

Questions:

merge (da:Drone{Name:"A"})
merge (db:Drone{Name:"B"})
merge (da)-[:w]-(db)

Creates a directional path from A to B.

Do I need to create a relationship from B to A, or is this algorithm impartial to the direction of the relationships. What about cyclical pathways? Will that be a problem? Is there a better way to do these things?

Thanks for your kindness in helping me learn these things.

Just a note, the Dijkstra algorithm is part of the Graph Data Science framework. This requires you to project your data, then run the algorithm. You would have to project your latest data every time you want to run this algorithm. Does this work for your "pretend" problem?

The documentation does not state anything about directional constraints. It looks to be indifferent.

BTW- when you merge without specifying a direction, neo4j will implement one for you. I believe it will implement an outgoing relationship, i.e. left-to-right in your pattern.

Just a note, the Dijkstra algorithm is part of the Graph Data Science framework. This requires you to project your data, then run the algorithm. You would have to project your latest data every time you want to run this algorithm. Does this work for your "pretend" problem?

Yes, there really is no choice since these entities will be in constant motion.

The documentation does not state anything about directional constraints. It looks to be indifferent.

So who in Neo can we chat with to confirm this sir?

BTW- when you merge without specifying a direction, neo4j will implement one for you. I believe it will implement an outgoing relationship, i.e. left-to-right in your pattern.

Yes sir I know, and you are, correct. So should I create two relationships between each node or will this DSL mechanism process both directions automatically, and will this mess things up by getting us trapped in
cyclical loops? Who can I talk with in Neo?
Thanks Gary

Here is what I am trying, right off the DSL web page and it does not work.. can someone just try and run this? Maybe my neo environment is messed up..

This is taken right from the examples located here:
Dijkstra Single-Source Shortest Path - Neo4j Graph Data Science

Create Graph:
CREATE (a:Location {name: 'A'}),
(b:Location {name: 'B'}),
(c:Location {name: 'C'}),
(d:Location {name: 'D'}),
(e:Location {name: 'E'}),
(f:Location {name: 'F'}),
(a)-[:ROAD {cost: 50}]->(b),
(a)-[:ROAD {cost: 50}]->(c),
(a)-[:ROAD {cost: 100}]->(d),
(b)-[:ROAD {cost: 40}]->(d),
(c)-[:ROAD {cost: 40}]->(d),
(c)-[:ROAD {cost: 80}]->(e),
(d)-[:ROAD {cost: 30}]->(e),
(d)-[:ROAD {cost: 80}]->(f),
(e)-[:ROAD {cost: 40}]->(f);
Yields
(Image would not load but it looks great!)
Lets look at the details:
match (scr)-[r:ROAD]-(dest) return scr.name, r.cost, dest.name
╒════════╤══════╤═════════╕
│scr.name│r.cost│dest.name│
╞════════╪══════╪═════════╡
│"E" │40 │"F" │
├────────┼──────┼─────────┤
│"F" │40 │"E" │
├────────┼──────┼─────────┤
│"A" │50 │"B" │
├────────┼──────┼─────────┤
│"B" │50 │"A" │
├────────┼──────┼─────────┤
│"A" │50 │"C" │
├────────┼──────┼─────────┤
│"C" │50 │"A" │
├────────┼──────┼─────────┤
│"A" │100 │"D" │
├────────┼──────┼─────────┤
│"D" │100 │"A" │
├────────┼──────┼─────────┤
│"B" │40 │"D" │
├────────┼──────┼─────────┤
│"D" │40 │"B" │
├────────┼──────┼─────────┤
│"C" │80 │"E" │
├────────┼──────┼─────────┤
│"E" │80 │"C" │
├────────┼──────┼─────────┤
│"C" │40 │"D" │

Project Graph
MATCH (source:Location)-[r:ROAD]->(target:Location)
RETURN gds.graph.project(
'myGraph',
source,
target,
{ relationshipProperties: r { .cost } }
)
Yields the Following:
{
"relationshipCount": 9,
"graphName": "myGraph",
"query": "MATCH (source:Location)-[r:ROAD]->(target:Location)
RETURN gds.graph.project(
'myGraph',
source,
target,
{ relationshipProperties: r { .cost } }
)",
"projectMillis": 108,
"configuration": {
"readConcurrency": 4,
"undirectedRelationshipTypes": ,
"jobId": "ed99ff17-e543-43d2-b340-0e8a3b1ca371",
"logProgress": true,
"query": "MATCH (source:Location)-[r:ROAD]->(target:Location)
RETURN gds.graph.project(
'myGraph',
source,
target,
{ relationshipProperties: r { .cost } }
)",
"inverseIndexedRelationshipTypes": ,
"creationTime": "2024-10-03T13:22:08.120852200Z"
},
"nodeCount": 6
}

Streaming Results
( I tried skipping this step does not seem to matter, inclluding it causes problems on the write out of the inMemory graph)
MATCH (source:Location {name: 'A'})
CALL gds.allShortestPaths.dijkstra.stream('myGraph', {
sourceNode: source,
relationshipWeightProperty: 'cost'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
index,
gds.util.asNode(sourceNode).name AS sourceNodeName,
gds.util.asNode(targetNode).name AS targetNodeName,
totalCost,
[nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS nodeNames,
costs,
nodes(path) as path
ORDER BY index
Mutate the InMemory Graph
This will perform the shortest path calculations on the inMemory Graph called myGraph..
MATCH (source:Location {name: 'A'})
CALL gds.allShortestPaths.dijkstra.mutate('myGraph', {
sourceNode: source,
relationshipWeightProperty: 'cost',
mutateRelationshipType: 'PATH'
})
YIELD relationshipsWritten
RETURN relationshipsWritten
Yeilds
6 relationship written, seems to have worked.. now.. lets write this back to our actual graph so we can look at it..
Write InMemory to Master Graph
MATCH (source:Location {name: 'A'})
CALL gds.allShortestPaths.dijkstra.write('myGraph', {
sourceNode: source,
relationshipWeightProperty: 'cost',
writeRelationshipType: 'PATH',
writeNodeIds: true,
writeCosts: true
})
YIELD relationshipsWritten
RETURN relationshipsWritten
Yields
Neo.ClientError.Procedure.ProcedureCallFailed
Failed to invoke procedure gds.allShortestPaths.dijkstra.write: Caused by: java.lang.IllegalArgumentException: Relationship weight property cost not found in relationship types ['PATH']. Properties existing on all relationship types: []

Any Ideas..

You can also get the algorithm without GDS: apoc.algo.dijkstra - APOC Documentation

THANKS!!!

ray lukas

Emerging Technologies Engineer

MITRE iPhone: 774.407.4524

Personal iPhone: 508.314.4257

Location: Bedford MA 1D606

I also had a friend send me a possible solution which might help us..
I took a look at your Cypher code and I think I can explain what is happening. I believe you are running the example from our Graph Data Science manual on Dykstra Single-Source Shortest Path.

After creating the in-memory graph projection, there are 3 ways to run the Dykstra algorithm: Stream Mode, Mutate Mode & Write Mode.

  • Stream Mode will run the Dykstra algorithm and stream the results back to your Browser.
  • Mutate Mode will run the Dykstra algorithm and "mutate" the in-memory graph by creating new relationships of type PATH between each pair of source/target nodes. The shortest path results will then be stored as properties of those PATH relationships
  • Write Mode will run the Dykstra algorithm and write the results back to the main graph (on disk) by creating new relationships of type PATH between each pair of source/target nodes. The shortest path results will then be stored as properties of those PATH relationships.

The problem you encountered was because you ran Mutate Mode prior to running Write Mode. Mutate Mode created new PATH relationships in the in-memory graph projection. When you subsequently ran the algorithm in Write Mode, it processed those PATH relationships and expected to see a "cost" property which wasn't there.

A way to avoid this is to use relationshipType parameter when creating the projection, and then use the optional relationshipTypes parameter when calling the algorithm, so that it will filter out other relationship types and just consider the one that you specify (here that would be 'ROAD'). For example:

MATCH (source:Location)-[r:ROAD]->(target:Location)
RETURN gds.graph.project(
'myGraph',
source,
target,
{ relationshipType: 'ROAD',
relationshipProperties: r { .cost } }
MATCH (source:Location {name: 'A'})
CALL gds.allShortestPaths.dijkstra.write('myGraph', {
sourceNode: source,
relationshipTypes: ['ROAD'],
relationshipWeightProperty: 'cost',
writeRelationshipType: 'PATH',
writeNodeIds: true,
writeCosts: true
})
YIELD relationshipsWritten
RETURN relationshipsWritten

Thanks.. Maybe this will help someone else understand things..

first... run the projection (you need to add a closing paren, sorry for the typo) then run the shortest path and works great

Thanks Guys.. hope this helps someone else out..