@ Shortest Path (unWeighted) with Neo4j
------------------------------------------------
['the unweighted shortest path from Amsterdam to London']
***************************************
MATCH (source:Place {id: "Amsterdam"}),
(destination:Place {id: "London"})
CALL gds.alpha.shortestPath.stream({
startNode: source,
endNode: destination,
nodeProjection: "*",
relationshipProjection: {
all: {
type: "*",
orientation: "UNDIRECTED"
}
}
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).id AS place, cost;
-----------------------------------------------------------
-----------------------------------------------------------------
The following procedure calculates the shortest unweighted path and then works out what the actual cost of that path would be:
****************************************************************
MATCH (source:Place {id: "Amsterdam"}),
(destination:Place {id: "London"})
CALL gds.alpha.shortestPath.stream({
startNode: source,
endNode: destination,
nodeProjection: "*",
relationshipProjection: {
all: {
type: "*",
orientation: "UNDIRECTED"
}
}
})
YIELD nodeId, cost
WITH collect(gds.util.asNode(nodeId)) AS path
UNWIND range(0, size(path)-1) AS index
WITH path[index] AS current, path[index+1] AS next
WITH current, next, [(current)-[r:EROAD]-(next) | r.distance][0] AS distance
WITH collect({current: current, next:next, distance: distance}) AS stops
UNWIND range(0, size(stops)-1) AS index
WITH stops[index] AS location, stops, index
RETURN location.current.id AS place,
reduce(acc=0.0,
distance in [stop in stops[0..index] | stop.distance] |
acc + distance) AS cost;
----------------------------------------------------------------------
@ Shortest Path (Weighted) with Neo4j
************************************
MATCH (source:Place {id: "Amsterdam"}),
(destination:Place {id: "London"})
CALL gds.alpha.shortestPath.stream({
startNode: source,
endNode: destination,
nodeProjection: "*",
relationshipProjection: {
all: {
type: "*",
properties: "distance",
orientation: "UNDIRECTED"
}
},
relationshipWeightProperty: "distance"
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).id AS place, cost;
-----------------------------------------------
@ A * algorithm -shortest path between Den Haag and London
@ latitude & longtitude of each nodee
********************************
MATCH (source:Place {id: "Den Haag"}),
(destination:Place {id: "London"})
CALL gds.alpha.shortestPath.astar.stream({
startNode: source,
endNode: destination,
nodeProjection: "*",
relationshipProjection: {
all: {
type: "*",
properties: "distance",
orientation: "UNDIRECTED"
}
},
relationshipWeightProperty: "distance",
propertyKeyLat: "latitude",
propertyKeyLon: "longitude"
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).id AS place, cost;
----------------------------------------------------------
@Yen's K-shortest Path - also find alternatives
*********************************************
MATCH (start:Place {id:"Gouda"}),
(end:Place {id:"Felixstowe"})
CALL gds.alpha.kShortestPaths.stream({
startNode: start,
endNode: end,
nodeProjection: "*",
relationshipProjection: {
all: {
type: "*",
properties: "distance",
orientation: "UNDIRECTED"
}
},
relationshipWeightProperty: "distance",
k: 5
})
YIELD index, sourceNodeId, targetNodeId, nodeIds, costs, path
RETURN index,
[node in gds.util.asNodes(nodeIds[1..-1]) | node.id] AS via,
reduce(acc=0.0, cost in costs | acc + cost) AS totalCost;
--------------------------------------------------------------------
visualize the path
MATCH (a),(b),(c),(d)
WHERE a.id = 'Gouda' AND b.id = 'Rotterdam' AND c.id = 'Hoek van Holland' AND d.id='Felixstowe'
RETURN a,b,c,d
All Pairs Shortest Path( ASAP）
when to use: understand alternate route when the shortest route is blocked or becomes suboptimal
• Optimizing the location of urban facilities and the distribution of goods. One
example of this is determining the traffic load expected on different segments of a
transportation grid.
• Finding a network with maximum bandwidth and minimal latency as part of a
data center design algorithm.
******************************************
1. distance between two nodes
CALL gds.alpha.allShortestPaths.stream({
nodeProjection: "*",
relationshipProjection: {
all: {
type: "*",
properties: "distance",
orientation: "UNDIRECTED"
}
}
})
YIELD sourceNodeId, targetNodeId, distance
WHERE sourceNodeId < targetNodeId
RETURN gds.util.asNode(sourceNodeId).id AS source,
gds.util.asNode(targetNodeId).id AS target,
distance
ORDER BY distance DESC
LIMIT 10;
*************************************
2. all shortest path（weight)- all shortest paths-from farthest to shortest
CALL gds.alpha.allShortestPaths.stream({
nodeProjection: "*",
relationshipProjection: {
all: {
type: "*",
properties: "distance",
orientation: "UNDIRECTED"
}
},
relationshipWeightProperty: "distance"
})
YIELD sourceNodeId, targetNodeId, distance
WHERE sourceNodeId < targetNodeId
RETURN gds.util.asNode(sourceNodeId).id AS source,
gds.util.asNode(targetNodeId).id AS target,
distance
ORDER BY distance DESC
LIMIT 10;
Single Source Shortest Path （SSSP)
when to use:
when you need to evaluate the optimal route from a fixed start point to all other individual nodes. Because the route is chosen based on the total path weight from the root, it’s useful for finding the best path to each node, but not necessarily when anodes need to be visited in a single trip
MATCH (n:Place {id:"London"})
CALL gds.alpha.shortestPath.deltaStepping.stream({
startNode: n,
nodeProjection: "*",
relationshipProjection: {
all: {
type: "*",
properties: "distance",
orientation: "UNDIRECTED"
}
},
relationshipWeightProperty: "distance",
delta: 1.0
})
YIELD nodeId, distance
WHERE gds.util.isFinite(distance)
RETURN gds.util.asNode(nodeId).id AS destination, distance
ORDER BY distance;
Minimum Spanning Tree (weight)
note ： SSSP evaluates the shortest path based on cumulative totals from the root, whereas Minimum Spanning Tree only looks at the cost of the next step.
when to use:
when you need the best route to visit all nodes. Because the route is chosen based on the cost of each next step, it’s useful when you must visit all nodes in a single walk.
• Minimizing the travel cost of exploring a country.
• Visualizing correlations between currency returns.
• Tracing the history of infection transmission in an outbreak.
The following query finds a spanning tree starting from Amsterdam:
MATCH (n:Place {id:"Amsterdam"})
CALL gds.alpha.spanningTree.minimum.write({
startNodeId: id(n),
nodeProjection: "*",
relationshipProjection: {
EROAD: {
type: "EROAD",
properties: "distance",
orientation: "UNDIRECTED"
}
},
relationshipWeightProperty: "distance",
writeProperty: 'MINST',
weightWriteProperty: 'cost'
})
YIELD createMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN createMillis, computeMillis, writeMillis, effectiveNodeCount;
If we want to return the minimum weight spanning tree we can run the following query:
MATCH path = (n:Place {id:"Amsterdam"})-[:MINST*]-()
WITH relationships(path) AS rels
UNWIND rels AS rel
WITH DISTINCT rel AS rel
RETURN startNode(rel).id AS source,
endNode(rel).id AS destination,
rel.cost AS cost;
Random Walk
when to use:
Use the Random Walk algorithm as part of other algorithms or data pipelines when you need to generate a mostly random set of connected nodes.
Example use cases include:
• As part of the node2vec and graph2vec algorithms, that create node embeddings. These node embeddings could then be used as the input to a neural network.
• As part of the Walktrap and Infomap community detection. If a random walk returns a small set of nodes repeatedly, then it indicates that node set may have a community structure.
• As part of the training process of machine learning models.
MATCH (source:Place {id: "London"})
CALL gds.alpha.randomWalk.stream({
start: id(source),
nodeProjection: "*",
relationshipProjection: {
all: {
type: "*",
properties: "distance",
orientation: "UNDIRECTED"
}
},
steps: 5,
walks: 1
})
YIELD nodeIds
UNWIND gds.util.asNodes(nodeIds) as place
RETURN place.id AS place
