# Path-finding algorithms in Neptune Analytics
Path-finding algorithms are a category of graph algorithms that focus on finding a path, a connected set of nodes and edges, between two or more sets of nodes within a graph. They are often used to find available or optimized paths based on the existence, quantity, or quality of the paths and the values of properties along those paths.
By efficiently determining the best route between two nodes, path-finding algorithms enable you to model real-world systems like roads or social networks as interconnected nodes and edges. Finding the shortest paths between various points is crucial in applications like route planning for GPS systems, logistics optimization, and even in solving complex problems in fields like biology or engineering.
# Breadth-first search (BFS) path finding algorithms
Breadth-first search (BFS) path-finding algorithms search for nodes in breadth-first order, starting from a single vertex. They can also, in the multi-source case, start from more than one vertex.
They can systematically explore and evaluate all neighboring nodes from a starting point before moving on to the neighbors of those nodes, which ensures that the algorithm searches the shallowest levels of the graph first.
Breadth-first-search is used in computer networking to find the shortest path between two devices, and in social networks to understand how information spreads through connections, and in games to explore possible moves and strategies.
**Time complexity** – The time complexity of breadth-first search algorithms is `O(|V|+|E|)`, where `|V|` is the number of vertices in the graph and `|E|` is the number of edges in the graph.
A breadth-first algorithm can be invoked as a *standalone* operation whose inputs are explicitly defined, or as a *query-algorithm integration* which takes as its input the output of an immediately preceding `MATCH` clause.
Neptune Analytics supports these BFS algorithms:
+ [`.bfs`](bfs-standard.md) – This standard breadth-first search algorithm starts from the source vertex of the graph and returns a column of visited vertices.
+ [`.bfs.parents`](bfs-parents.md) – This variant of BFS starts from a source vertex or vertices and finds the parent of each vertex during the search. It returns a key column of the vertices and a value column of the parents of the key vertices.
+ [`.bfs.levels`](bfs-levels.md) – This variant of BFS starts from a source vertex or vertices and finds the levels of each vertex during the search. It returns a key column of the vertices and a value column of integers that are the level values of the key vertices.
Note that the level of a source vertex is 0.
# Standard breadth-first search (BFS) algorithm
Standard breadth-first search (BFS) is an algorithm for finding nodes from a starting node or nodes in a graph in breadth-first order.
It returns the source node or nodes that it started from, and all of the nodes visited by each search.
**Note**
Because every source node passed in leads to its own execution of the algorithm, your queries should limit the number of source nodes as much as possible.
## `.bfs` syntax
```
CALL neptune.algo.bfs(
[source-node list (required)],
{
edgeLabels: [list of edge labels for filtering (optional)],
vertexLabel: a node label for filtering (optional),
maxDepth: maximum number of hops to traverse from a source node (optional),
traversalDirection: traversal direction (optional),
concurrency: number of threads to use (optional)
}
)
YIELD the outputs to generate (source and/or node)
RETURN the outputs to return
```
## `.bfs` inputs
+ **a source node list** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The source-node list contains the node or nodes used as the starting locations for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source-node list is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source-node list for the algorithm.
+
**a configuration object that contains:**
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **vertexLabel** *(optional)* – *type:* `string`; *example:* `"airport"`; *default:* no node filtering.
If you provide a node label to filter on then only nodes matching that label will be traversed. This does not, however, filter out any nodes in the source node list.
+ **maxDepth** *(optional)* – *type:* positive integer or 0 or -1; *default:* -1.
The maximum number of hops to traverse from a source node. If set at `-1` then there's no maximum depth limit. If set to `0`, only the nodes in the source node list are returned.
+ **traversalDirection** *(optional)* – *type:* `string`; *default:*` "outbound"`.
The direction of edge to follow. Must be one of: `"inbound"`, `"outbound"`, or `"both"`.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## `.bfs` outputs
The `.bfs` algorithm returns:
+ **source** – *type:* `Node[]`.
The source nodes.
+ **node** – *type:* `Node[]`.
The nodes that the algorithm traversed from each source node.
## `.bfs` query examples
This is a standalone example, where the query provides an explicit source node list.
```
CALL neptune.algo.bfs(
["101", "102"],
{
edgeLabels: ["route"],
vertexLabel: "airport",
maxDepth: 11,
traversalDirection: "both",
concurrency: 2
}
)
YIELD node
```
You can run that query using the `execute-query` operation in the AWS CLI like this:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string 'CALL neptune.algo.bfs(["101", "102"],
{edgeLabels: ["route"], vertexLabel: "airport", maxDepth: 11,
traversalDirection: "both", concurrency: 2})' \
--language open_cypher \
/tmp/out.txt
```
A query like this one would return an empty result because the source list is empty:
```
CALL neptune.algo.bfs([], {edgeLabels: ["route"]})
```
By default, both the source nodes (`"source"` output) and the visited nodes (`"node"` output) are returned. You can use `YIELD` to specify which of those outputs you would like to see. For example, to see only the `"node"` outputs:
```
CALL neptune.algo.bfs(["101"], {edgeLabels: ["route"]}) YIELD node
```
The examples below are query integration examples, where `.bfs` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node list:
```
MATCH (n) WITH n LIMIT 5
CALL neptune.algo.bfs(n, {edgeLabels: ["route"]})
YIELD node
RETURN node
```
The `MATCH` clause can also explicitly specify a starting node list using the `id()` function, like this:
```
MATCH (n) where id(n)="101"
CALL neptune.algo.bfs(n, {edgeLabels: ["route"]})
YIELD node
RETURN node
```
Also:
```
MATCH (n) where id(n) IN ["101", "102"]
CALL neptune.algo.bfs(n, {edgeLabels: ["route"]})
YIELD node
RETURN COUNT(node)
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes is returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.bfs` output
Here is an example of the output returned by .bfs when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string "CALL neptune.algo.bfs(['101'], {maxDepth: 1}) yield source, node return source, node limit 2" \
--language open_cypher \
/tmp/out.txt
cat /tmp/out.txt
{
"results": [{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.681099891662599,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"lon": 100.74700164794901,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "1483",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 39.490000000000002,
"elev": 4557,
"longest": 9186,
"city": "Ordos",
"type": "airport",
"region": "CN-15",
"desc": "Ordos Ejin Horo Airport",
"code": "DSN",
"lon": 109.861388889,
"country": "CN",
"icao": "ZBDS",
"runways": 1
}
}
}, {
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.681099891662599,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"lon": 100.74700164794901,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "103",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 55.972599029541001,
"elev": 622,
"longest": 12139,
"city": "Moscow",
"type": "airport",
"region": "RU-MOS",
"desc": "Moscow, Sheremetyevo International Airport",
"code": "SVO",
"lon": 37.414600372314503,
"country": "RU",
"icao": "UUEE",
"runways": 2
}
}
}]
}
```
# Parents breadth-first search (BFS) algorithm
The `parents` variant of breadth-first search is an algorithm for finding nodes from a starting node or vertices in breadth-first order and then performing a breadth-first search for the parent of each node.
It returns a key column of vertices, and a value column of the vertices that are the parents of the key vertices. The parent of a source node is itself.
**Note**
Because every source node passed in initiates its own execution of the algorithm, your queries should limit the number of source nodes as much as possible.
## `.bfs.parents` syntax
```
CALL neptune.algo.bfs.parents(
[source-node list (required)],
{
edgeLabels: [list of edge labels for filtering (optional)],
vertexLabel: a node label for filtering (optional),
maxDepth: maximum number of hops to traverse from a source node (optional),
traversalDirection: traversal direction (optional),
concurrency: number of threads to use (optional)
}
)
YIELD the outputs to generate (source and/or node and/or parent)
RETURN the outputs to return
```
## `.bfs.parents` inputs
+ **a source node list** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The source-node list contains the node or nodes used as the starting locations for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source-node list is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source-node list for the algorithm.
+
**a configuration object that contains:**
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **vertexLabel** *(optional)* – *type:* `string`; *example:* `"airport"`; *default:* no node filtering.
If you provide a node label to filter on then only vertices matching that label will be traversed. This does not, however, filter out any nodes in the source node list.
+ **maxDepth** *(optional)* – *type:* positive integer or 0 or -1; *default:* -1.
The maximum number of hops to traverse from a source node. If set at `-1` then there's no maximum depth limit. If set to `0`, only the vertices in the source node list are returned.
+ **traversalDirection** *(optional)* – *type:* `string`; *default:*` outbound`.
The direction of edge to follow. Must be one of: `inbound`, `outbound`, or `both`.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## `.bfs.parents` outputs
The `.bfs.parents` algorithm returns:
+ **source** – *type:* `Node[]`.
The source nodes.
+ **node** – *type:* `Node[]`.
The vertices that the algorithm traversed from each source node.
+ **parent** – *type:* `Node[]`.
The parents of those traversed nodes.
## `.bfs.parents` query examples
This is a standalone example, where the source node list is explicitly provided in the query:
```
CALL neptune.algo.bfs.parents(
["105", "113"],
{
edgeLabels: ["route"],
vertexLabel: "airport",
maxDepth: 2,
traversalDirection: "both",
concurrency: 2
}
)
YIELD node, parent
```
A query like this one would return an empty result because the source list is empty:
```
CALL neptune.algo.bfs.parents([], {edgeLabels: ["route"]})
```
This is a query integration example, where `.bfs.parents` follows a `MATCH` clause that provides the source node list for `.bfs.parents`:
```
Match (n) with n LIMIT 5
CALL neptune.algo.bfs.parents(n, {edgeLabels: ["route"]})
YIELD node
RETURN n, node
```
This query is an example of aliasing the algorithm output:
```
MATCH (n {code: "AUS"})
CALL neptune.algo.bfs.parents(n, { edgeLabels: ["route"], maxDepth: 2})
YIELD node AS ReachedNode
RETURN ReachedNode
```
This query searches for routes to BFS from BKK, returning the starting node (BKK), 5 visited vertices, and their parents:
```
MATCH (n) where n.code CONTAINS "BKK"
CALL neptune.algo.bfs.parents(n, {edgeLabels: ["route"]})
YIELD node, parent
RETURN n, node, parent
LIMIT 5
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes is returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.bfs.parents` output
Here is an example of the output returned by .bfs.parents when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string "CALL neptune.algo.bfs.parents(['101'], {maxDepth: 1})
YIELD source, node, parent
RETURN source, node, parent
LIMIT 2" \
--language open_cypher \
/tmp/out.txt
cat /tmp/out.txt
{
"results": [
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"lon": 100.747001647949,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "1483",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 39.49,
"elev": 4557,
"longest": 9186,
"city": "Ordos",
"type": "airport",
"region": "CN-15",
"desc": "Ordos Ejin Horo Airport",
"code": "DSN",
"lon": 109.861388889,
"country": "CN",
"icao": "ZBDS",
"runways": 1
}
},
"parent": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"lon": 100.747001647949,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
}
},
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"lon": 100.747001647949,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "103",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 55.972599029541,
"elev": 622,
"longest": 12139,
"city": "Moscow",
"type": "airport",
"region": "RU-MOS",
"desc": "Moscow, Sheremetyevo International Airport",
"code": "SVO",
"lon": 37.4146003723145,
"country": "RU",
"icao": "UUEE",
"runways": 2
}
},
"parent": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"lon": 100.747001647949,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
}
}
]
}
```
# Levels breadth-first search (BFS) algorithm
The `levels` variant of breadth-first search is an algorithm for searching nodes from a starting node or nodes in breadth-first order. From there it performs a breadth-first search and records the hop level from the starting node of each node that it finds.
It returns a key column of nodes, and a value column containing the level values of those key nodes.
The level of a source node is 0. Note that because every source node passed into breadth-first search `levels` initiates its own execution of the algorithm, your queries should filter to a subset of the graph before executing BFS `levels` whenever possible.
## `.bfs.levels` syntax
```
CALL neptune.algo.bfs.levels(
[source-node list (required)],
{
edgeLabels: [list of edge labels for filtering (optional)],
vertexLabel: a node label for filtering (optional),
maxDepth: maximum number of hops to traverse from a source node (optional),
traversalDirection: traversal direction (optional),
concurrency: number of threads to use (optional)
}
)
YIELD the outputs to generate (source and/or node)
RETURN the outputs to return
```
## `.bfs.levels` inputs
+ **a source node list** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The source-node list contains the node or nodes used as the starting locations for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source-node list is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source-node list for the algorithm.
+
**a configuration object that contains:**
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **vertexLabel** *(optional)* – *type:* `string`; *example:* `"airport"`; *default:* no node filtering.
If you provide a node label to filter on then only nodes matching that label will be traversed. This does not, however, filter out any nodes in the source node list.
+ **maxDepth** *(optional)* – *type:* positive integer or 0 or -1; *default:* -1.
The maximum number of hops to traverse from a source node. If set at `-1` then there's no maximum depth limit. If set to `0`, only the nodes in the source node list are returned.
+ **traversalDirection** *(optional)* – *type:* `string`; *default:*` "outbound"`.
The direction of edge to follow. Must be one of: `"inbound"`, `"outbound"`, or `"both"`.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## `.bfs.levels` outputs
The `.bfs.levels` algorithm returns:
+ **source** – *type:* `Node[]`.
The source nodes.
+ **node** – *type:* `Node[]`.
The nodes that the algorithm traversed from each source node.
+ **level** – *type:* `integer[]`.
The hop levels of those traversed nodes.
## `.bfs.levels` standalone query examples
The examples below are standalone examples, where the query provides an explicit source node list.
A query like this one would return an empty result because the source list is empty:
```
CALL neptune.algo.bfs.levels(
["101", "102"],
{
edgeLabels: ["route"],
vertexLabel: "airport",
maxDepth: 6,
traversalDirection: "both",
concurrency: 2
}
)
YIELD node
```
You can run the algorithm using the `execute-query` operation in the AWS CLI like this:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string 'CALL neptune.algo.bfs.levels(["101", "102"], {edgeLabels: ["route"]})' \
--language open_cypher \
/tmp/out.txt
```
By default, all the outputs are generated. You can use `YIELD` to specify which of those outputs to generate. For example, to generate only the `"node"` and `level` outputs:
```
CALL neptune.algo.bfs.levels(["101"], {edgeLabels: ["route"]}) YIELD node, level
```
## `.bfs.levels` query integration examples
The examples below are query integration examples, where `.bfs.levels` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node list:
```
MATCH (n) WITH n LIMIT 5
CALL neptune.algo.bfs.levels(n, {edgeLabels: ["route"]})
YIELD node, level
RETURN n, node, level
```
This query illustrates various ways to constrain the input and output:
```
MATCH (n) where id(n)="101"
CALL neptune.algo.bfs.levels(n, { edgeLabel: "route", maxDepth: 2})
YIELD node, level WHERE node.city CONTAINS "New"
RETURN n.city, node.city, level
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes is returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.bfs.levels` output
Here is an example of the output returned by .bfs.levels when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string "CALL neptune.algo.bfs.levels(['101'], {maxDepth: 1}) yield source, node, level return source, node, level limit 2" \
--language open_cypher \
/tmp/out.txt
cat /tmp/out.txt
{
"results": [
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"lon": 100.747001647949,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "1483",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 39.49,
"elev": 4557,
"longest": 9186,
"city": "Ordos",
"type": "airport",
"region": "CN-15",
"desc": "Ordos Ejin Horo Airport",
"code": "DSN",
"lon": 109.861388889,
"country": "CN",
"icao": "ZBDS",
"runways": 1
}
},
"level": 1
},
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"lon": 100.747001647949,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "103",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 55.972599029541,
"elev": 622,
"longest": 12139,
"city": "Moscow",
"type": "airport",
"region": "RU-MOS",
"desc": "Moscow, Sheremetyevo International Airport",
"code": "SVO",
"lon": 37.4146003723145,
"country": "RU",
"icao": "UUEE",
"runways": 2
}
},
"level": 1
}
]
}
```
# Single-source shortest-path algorithms
A single-source-shortest-path algorithm finds the shortest paths (or the distance of the shortest paths) between a given vertex and all reachable vertices in the graph (including itself).
By determining the most efficient routes from a single starting node to all other nodes in the graph, single-source-shortest-path can be used to calculate the shortest distances or lowest cost required to reach each destination. This is applicable in GPS systems to find the fastest routes between a starting point and different destinations, and in logistics to optimize delivery routes, and in transportation planning for efficient navigation through road networks.
Neptune Analytics supports the following single-source-shortest-path (SSSP) algorithms:
+ [`.sssp.bellmanFord`](sssp-bellmanFord.md) – Computes the shortest path distances from a source vertex to all other vertices in the graph using the [Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) algorithm. Positive edge weights must be provided using the `edgeWeightProperty`, and the traversal direction must not be set to `both`.
+ [`.sssp.bellmanFord.parents`](sssp-bellmanFord-parents.md) – Identifies the parent vertices along the shortest paths from the source vertex to all other vertices in the graph using the Bellman-Ford algorithm. Positive edge weights must be provided using the `edgeWeightProperty`, and the traversal direction must not be set to `both`.
+ [`.sssp.bellmanFord.path`](sssp-bellmanFord-path.md) – Finds the shortest path between a given source vertex and a target vertex in the graph using the [Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) algorithm. To compute all shortest paths from a given source vertex, the regular SSSP algorithm can be used. Positive edge weights must be provided using the `edgeWeightProperty`, and the traversal direction must not be set to `both`.
+ [`.sssp.deltaStepping`](sssp-deltaStepping.md) – Computes the shortest path distances from a source vertex to all other vertices in the graph using a [delta-stepping](https://en.wikipedia.org/wiki/Parallel_single-source_shortest_path_algorithm#Delta_stepping_algorithm) algorithm. Positive edge weights must be provided using the `edgeWeightProperty`, and the traversal direction must not be set to `both`.
+ [`.sssp.deltaStepping.parents`](sssp-deltaStepping-parents.md) – Identifies the parent vertices along the shortest paths from the source vertex to all other vertices in the graph using a delta-stepping algorithm. Positive edge weights must be provided using the `edgeWeightProperty`, and the traversal direction must not be set to `both`.
+ [`.sssp.deltaStepping.path`](sssp-deltaStepping-path.md) – Finds the shortest path between a given source vertex and a target vertex in the graph using the delta-stepping algorithm. To compute all shortest paths from a given source vertex, the regular SSSP algorithm can be used. Positive edge weights must be provided using the `edgeWeightProperty`, and the traversal direction must not be set to `both`.
+ [`.topksssp`](topk-sssp.md) – The TopK hop-limited single source shortest path algorithm finds the single-source weighted shortest paths starting from a source vertex to all its `maxDepth` neighbors. The distance or cost from the source vertex to each target vertex is accumulated on the edge weights of the path. The topK distances of the paths are sorted in descending or ascending order.
The algorithm can be run unweighted as well as weighted. When you run it unweighted, it's equivalent to [`.bfs.levels`](bfs-levels.md).
# Bellman-Ford single source shortest path (SSSP) algorithm
The `.sssp.bellmanFord` algorithm computes the shortest path distances from a single source vertex to all other vertices in the graph using the [Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) algorithm.
Neptune Analytics implements the algorithm such that:
+ Positive edge weights must be provided using the `edgeWeightProperty` field
+ Negative edge weights are not supported.
+ The traversal direction cannot be set to `both`.
## `.sssp.bellmanFord` syntax
```
CALL neptune.algo.sssp.bellmanFord(
[source-node list (required)],
{
edgeWeightProperty: edge weight predicate for traversal (required)
edgeWeightType: numeric type of the edge weight property (required)
edgeLabels: [list of edge labels for filtering (optional)],
vertexLabel: a node label for filtering (optional),
traversalDirection: traversal direction (optional),
concurrency: number of threads to use (optional)
}
)
YIELD the outputs to generate (source and/or node)
RETURN the outputs to return
```
## `.sssp.bellmanFord` inputs
+ **a source node list** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the starting location(s) for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source-node list is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source-node list for the algorithm.
+
**a configuration object that contains:**
+ **edgeWeightProperty** *(required)* – *type:* `string`; *default: none*.
The edge weight predicate for traversal.
+ **edgeWeightType** *(required)* – *type:* `string`; *valid values:* `"int"`, `"long"`, `"float"`, `"double"`.
The numeric data type of the values in the property specified by `edgeWeightProperty`.
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **vertexLabel** *(optional)* – *type:* `string`; *example:* `"airport"`; *default:* no node filtering.
A node label for node filtering. If a node label is provided, vertices matching the label are the only vertices that are included, including vertices in the input list.
+ **traversalDirection** *(optional)* – *type:* `string`; *default:*` "outbound"`.
The direction of edge to follow. Must be one of: `"inbound"` or `"outbound"`.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## Outputs for the `.sssp.bellmanFord` algorithm
For every node that can be reached from the specified source list, the algorithm returns:
+ **source** – The source node.
+ **node** – A node found traversing from the source.
+ **distance** – The distance between the source node and the found node.
## `.sssp.bellmanFord` query examples
This is a standalone query, where a source node (or nodes) is explicitly provided:
```
CALL neptune.algo.sssp.bellmanFord(
["101"],
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int"
}
)
```
This is a query integration example, where `.sssp.bellmanFord` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node list:
```
MATCH (source:airport {code: 'ANC'})
CALL neptune.algo.sssp.bellmanFord(
source,
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int",
vertexLabel: "airport",
traversalDirection: "outbound",
concurrency: 1
}
)
YIELD node, parent, distance
RETURN source, node, parent, distance
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes is returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.sssp.bellmanFord` output
Here is an example of the output returned by .sssp.bellmanFord when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string "CALL neptune.algo.sssp.bellmanFord(['101'],
{edgeWeightProperty: 'dist', edgeWeightType: 'int'})
yield source, node, distance
return source, node, distance
limit 2" \
--language open_cypher \
/tmp/out.txt
cat /tmp/out.txt
{
"results": [
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "2709",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 65.4809036254883,
"elev": 49,
"longest": 8711,
"city": "Nadym",
"type": "airport",
"region": "RU-YAN",
"desc": "Nadym Airport",
"code": "NYM",
"prscore": 0.00016044313088059425,
"degree": 18,
"lon": 72.6988983154297,
"wccid": 2357352929951779,
"country": "RU",
"icao": "USMM",
"runways": 1
}
},
"distance": 3812
},
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "2667",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 56.8567008972168,
"elev": 2188,
"longest": 6562,
"city": "Ust-Kut",
"type": "airport",
"region": "RU-IRK",
"desc": "Ust-Kut Airport",
"code": "UKX",
"prscore": 0.000058275499999999997,
"degree": 4,
"lon": 105.730003356934,
"wccid": 2357352929951779,
"country": "RU",
"icao": "UITT",
"runways": 1
}
},
"distance": 2993
}
]
}
```
# Bellman-Ford single source shortest path (SSSP) parents algorithm
The `.sssp.bellmanFord.parents` algorithm uses the [Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) algorithm to find the parent nodes along with the shortest path distances from the source node to all other nodes in the graph.
Neptune Analytics implements the algorithm such that:
+ Positive edge weights must be provided using the `edgeWeightProperty` field
+ Negative edge weights are not supported.
+ The traversal direction cannot be set to `both`.
## `.sssp.bellmanFord.parents` syntax
```
CALL neptune.algo.sssp.bellmanFord.parents(
[source-node list (required)],
{
edgeWeightProperty: edge weight predicate for traversal (required)
edgeWeightType: numeric type of the edge weight property (required)
edgeLabels: [list of edge labels for filtering (optional)],
vertexLabel: a node label for filtering (optional),
traversalDirection: traversal direction (optional),
concurrency: number of threads to use (optional)
}
)
YIELD the outputs to generate (source and/or node)
RETURN the outputs to return
```
## `.sssp.bellmanFord.parents` inputs
+ **a source node list** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the starting location(s) for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source-node list is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source-node list for the algorithm.
+
**a configuration object that contains:**
+ **edgeWeightProperty** *(required)* – *type:* `string`; *example:* `"distnce"`; *default: none*.
The edge weight predicate for traversal.
+ **edgeWeightType** *(required)* – *type:* `string`; *valid values:* `"int"`, `"long"`, `"float"`, `"double"`.
The numeric data type of the values in the property specified by `edgeWeightProperty`.
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **vertexLabel** *(optional)* – *type:* `string`; *example:* `"airport"`; *default:* no node filtering.
A node label for node filtering. If a node label is provided, vertices matching the label are the only vertices that are included, including vertices in the input list.
+ **traversalDirection** *(optional)* – *type:* `string`; *default:*` "outbound"`.
The direction of edge to follow. Must be one of: `"inbound"` or `"outbound"`.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## Outputs for the `.sssp.bellmanFord.parents` algorithm
For every node that can be reached from the specified source list, the algorithm returns:
+ **source** – The source node.
+ **node** – A node found traversing from the source.
+ **distance** – The distance between the source node and the found node.
+ **parent** – The parent of the found node. Note that the parent of the source vertex is itself.
## `.sssp.bellmanFord.parents` query examples
This is a standalone query, where a source node (or nodes) is explicitly provided:
```
CALL neptune.algo.sssp.bellmanFord.parents(
["101"],
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int"
}
)
```
This is a query integration example, where where `.sssp.bellmanFord.parents` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node list:
```
MATCH (source:airport {code: 'ANC'})
CALL neptune.algo.sssp.bellmanFord.parents(
source,
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int",
vertexLabel: "airport",
traversalDirection: "outbound",
concurrency: 1
}
)
YIELD node, parent, distance
RETURN source, node, parent, distance
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes is returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.sssp.bellmanFord.parents` output
Here is an example of the output returned by .sssp.bellmanFord.parents when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string "CALL neptune.algo.sssp.bellmanFord.parents(['101'],
{edgeWeightProperty: 'dist', edgeWeightType: 'int'})
yield source, node, parent
return source, node, parent
limit 2" \
--language open_cypher \
/tmp/out.txt
cat /tmp/out.txt
{
"results": [
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "2709",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 65.4809036254883,
"elev": 49,
"longest": 8711,
"city": "Nadym",
"type": "airport",
"region": "RU-YAN",
"desc": "Nadym Airport",
"code": "NYM",
"prscore": 0.00016044313088059425,
"degree": 18,
"lon": 72.6988983154297,
"wccid": 2357352929951779,
"country": "RU",
"icao": "USMM",
"runways": 1
}
},
"parent": {
"~id": "810",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 55.0125999450684,
"elev": 365,
"longest": 11818,
"city": "Novosibirsk",
"type": "airport",
"region": "RU-NVS",
"desc": "Tolmachevo Airport",
"code": "OVB",
"prscore": 0.0012910010991618038,
"degree": 162,
"lon": 82.6507034301758,
"wccid": 2357352929951779,
"country": "RU",
"icao": "UNNT",
"runways": 2
}
}
},
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "2667",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 56.8567008972168,
"elev": 2188,
"longest": 6562,
"city": "Ust-Kut",
"type": "airport",
"region": "RU-IRK",
"desc": "Ust-Kut Airport",
"code": "UKX",
"prscore": 0.000058275499999999997,
"degree": 4,
"lon": 105.730003356934,
"wccid": 2357352929951779,
"country": "RU",
"icao": "UITT",
"runways": 1
}
},
"parent": {
"~id": "1038",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 52.2680015563965,
"elev": 1675,
"longest": 10384,
"city": "Irkutsk",
"type": "airport",
"region": "RU-IRK",
"desc": "Irkutsk Airport",
"code": "IKT",
"prscore": 0.0008466026629321277,
"degree": 84,
"lon": 104.388999938965,
"wccid": 2357352929951779,
"country": "RU",
"icao": "UIII",
"runways": 1
}
}
}
]
}
```
# Bellman-Ford single source single target shortest path algorithm
The `.sssp.bellmanFord.path` algorithm uses the Bellman-Ford algorithm to find the shortest path along with the shortest path distances from a source node to a target node in the graph. If there are multiple shortest paths between the source node and the target node, only one will be returned. The algorithm can run only weighted, with `edgeWeightProperty` provided.
Neptune Analytics implements the algorithm such that:
+ Positive edge weights must be provided using the `edgeWeightProperty` field.
+ Negative edge weights are not supported.
+ The traversal direction cannot be set to `both`.
## `.sssp.bellmanFord.path` syntax
```
CALL neptune.algo.sssp.bellmanFord.path(
[source node(s) (required)], [target node(s) (required)]
{
edgeWeightProperty: edge weight predicate for traversal (required)
edgeWeightType: numeric type of the edge weight property (required)
edgeLabels: [list of edge labels for filtering (optional)],
vertexLabel: a node label for filtering (optional),
traversalDirection: traversal direction (optional),
concurrency: number of threads to use (optional)
}
)
YIELD the outputs to generate (source and/or node)
RETURN the outputs to return
```
## `.sssp.bellmanFord.path` inputs
+ **source node(s)** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the starting location(s) for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source node(s) is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source node(s) for the algorithm.
+ **target node(s)** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the ending location(s) for the algorithm.
+ Each source-target node pair produces an output of the algorithm.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the target node(s) for the algorithm.
+
**a configuration object that contains:**
+ **edgeWeightProperty** *(required)* – *type:* `string`; *default: none*.
The edge weight predicate for traversal.
+ **edgeWeightType** *(required)* – *type:* `string`; *valid values:* `"int"`, `"long"`, `"float"`, `"double"`.
The numeric data type of the values in the property specified by `edgeWeightProperty`.
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **vertexLabel** *(optional)* – *type:* `string`; *example:* `"airport"`; *default:* no node filtering.
A node label for node filtering. If a node label is provided, vertices matching the label are the only vertices that are included, including vertices in the input list.
+ **traversalDirection** *(optional)* – *type:* `string`; *default:*` "outbound"`.
The direction of edge to follow. Must be one of: `"inbound"` or `"outbound"`.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## Outputs for the `.sssp.bellmanFord.path` algorithm
For every pair of source and target nodes, the algorithm returns:
+ **source** – The source vertex.
+ **target** – The target vertex.
+ **distance** – The total shortest path distance from source to target.
+ **vertexPath** – A list of vertices in the path in visit order (including the source and the target).
+ **allDistances** – A list of cumulative distances to the vertices in the traversal path (including the source and the target).
+ **path** – An openCypher path object representing the shortest path between the source and the target. (A list of vertices from the source vertex to the target vertex, interleaved with the corresponding edges, representing the shortest path. Sequence of vertex id (source), edge id, vertex id, edge id, ..., vertex id (target)).
+ Starts and ends with a vertex, and has edges in between each vertex.
+ Includes the source and the target vertices.
## `.sssp.bellmanFord.path` query examples
This is a standalone query, where a source node and target node are explicitly provided:
```
CALL neptune.algo.sssp.bellmanFord.path(
"9", "37",
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int"
}
)
```
This is a query integration example, where `.sssp.bellmanFord.path` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node(s) and target node(s):
```
MATCH (source:airport {code: 'FLL'})
MATCH (target:airport {code: 'HNL'})
CALL neptune.algo.sssp.bellmanFord.path(
source, target,
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int",
vertexLabel: "airport",
traversalDirection: "outbound",
concurrency: 1
}
)
YIELD distance, vertexPath, allDistances, path
RETURN source, target, distance, vertexPath, allDistances, path
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes are returned; and that every source-target node pair produces an output, which can result in a very large query output if a large number of nodes are returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.sssp.bellmanFord.path` output
Here is an example of the output returned by .sssp.bellmanFord.path when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string "MATCH (n:airport {code: 'FLL'})
MATCH (m:airport {code: 'HNL'})
CALL neptune.algo.sssp.bellmanFord.path(n, m, {
edgeWeightProperty: "dist",
edgeWeightType: "int",
edgeLabels: ["route"],
vertexLabel: "airport",
traversalDirection: "outbound",
concurrency: 1
})
YIELD source, target, distance, vertexPath, allDistances, path
RETURN source, target, distance, vertexPath, allDistances, path" \
--language open_cypher \
/tmp/out.txt
cat /tmp/out.txt
{
"results": [{
"source": {
"~id": "9",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-FL",
"runways": 2,
"country": "US",
"city": "Fort Lauderdale",
"type": "airport",
"icao": "KFLL",
"lon": -80.152702331542997,
"code": "FLL",
"lat": 26.0725994110107,
"longest": 9000,
"elev": 64,
"desc": "Fort Lauderdale/Hollywood International Airport"
}
},
"target": {
"~id": "37",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-HI",
"runways": 4,
"country": "US",
"city": "Honolulu",
"type": "airport",
"icao": "PHNL",
"lon": -157.92199707031199,
"code": "HNL",
"lat": 21.318700790405298,
"longest": 12312,
"elev": 13,
"desc": "Honolulu International Airport"
}
},
"distance": 4854,
"vertexPath": [{
"~id": "9",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-FL",
"runways": 2,
"country": "US",
"city": "Fort Lauderdale",
"type": "airport",
"icao": "KFLL",
"lon": -80.152702331542997,
"code": "FLL",
"lat": 26.0725994110107,
"longest": 9000,
"elev": 64,
"desc": "Fort Lauderdale/Hollywood International Airport"
}
}, {
"~id": "11",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-TX",
"runways": 5,
"country": "US",
"city": "Houston",
"type": "airport",
"icao": "KIAH",
"lon": -95.341400146484403,
"code": "IAH",
"lat": 29.984399795532202,
"longest": 12001,
"elev": 96,
"desc": "George Bush Intercontinental"
}
}, {
"~id": "37",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-HI",
"runways": 4,
"country": "US",
"city": "Honolulu",
"type": "airport",
"icao": "PHNL",
"lon": -157.92199707031199,
"code": "HNL",
"lat": 21.318700790405298,
"longest": 12312,
"elev": 13,
"desc": "Honolulu International Airport"
}
}],
"allDistances": [0, 964, 4854],
"path": [{
"~id": "9",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-FL",
"runways": 2,
"country": "US",
"city": "Fort Lauderdale",
"type": "airport",
"icao": "KFLL",
"lon": -80.152702331542997,
"code": "FLL",
"lat": 26.0725994110107,
"longest": 9000,
"elev": 64,
"desc": "Fort Lauderdale/Hollywood International Airport"
}
}, {
"~id": "neptune_reserved_1_1152921504607567884",
"~entityType": "relationship",
"~start": "9",
"~end": "11",
"~type": "route",
"~properties": {
"dist": 964
}
}, {
"~id": "11",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-TX",
"runways": 5,
"country": "US",
"city": "Houston",
"type": "airport",
"icao": "KIAH",
"lon": -95.341400146484403,
"code": "IAH",
"lat": 29.984399795532202,
"longest": 12001,
"elev": 96,
"desc": "George Bush Intercontinental"
}
}, {
"~id": "neptune_reserved_1_1152921508902600717",
"~entityType": "relationship",
"~start": "11",
"~end": "37",
"~type": "route",
"~properties": {
"dist": 3890
}
}, {
"~id": "37",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-HI",
"runways": 4,
"country": "US",
"city": "Honolulu",
"type": "airport",
"icao": "PHNL",
"lon": -157.92199707031199,
"code": "HNL",
"lat": 21.318700790405298,
"longest": 12312,
"elev": 13,
"desc": "Honolulu International Airport"
}
}]
}]
}
```
# Delta-stepping single source shortest path (SSSP) algorithm
The `.sssp.deltaStepping` algorithm computes the shortest path distances from a single source vertex to all other vertices in the graph using a [delta-stepping](https://en.wikipedia.org/wiki/Parallel_single-source_shortest_path_algorithm#Delta_stepping_algorithm) algorithm.
Neptune Analytics implements the algorithm such that:
+ Positive edge weights must be provided using the `edgeWeightProperty` field
+ Negative edge weights are not supported.
+ The traversal direction cannot be set to `both`.
## `.sssp.deltaStepping` syntax
```
CALL neptune.algo.sssp.deltaStepping(
[source-node list (required)],
{
edgeWeightProperty: edge weight predicate for traversal (required)
edgeWeightType: numeric type of the edge weight property (required)
delta: the stepping delta (optional)
edgeLabels: [list of edge labels for filtering (optional)],
vertexLabel: a node label for filtering (optional),
traversalDirection: traversal direction (optional),
concurrency: number of threads to use (optional)
}
)
YIELD the outputs to generate (source and/or node)
RETURN the outputs to return
```
## `.sssp.deltaStepping` inputs
+ **a source node list** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the starting location(s) for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source-node list is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source-node list for the algorithm.
+
**a configuration object that contains:**
+ **edgeWeightProperty** *(required)* – *type:* `string`; *default: none*.
The edge weight predicate for traversal.
+ **edgeWeightType** *(required)* – *type:* `string`; *valid values:* `"int"`, `"long"`, `"float"`, `"double"`.
The numeric data type of the values in the property specified by `edgeWeightProperty`.
+ **delta** *(optional)* – *type:* float; *example:* `3.0`; *default:* `2.0`.
The delta stepping value.
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **vertexLabel** *(optional)* – *type:* `string`; *example:* `"airport"`; *default:* no node filtering.
A node label for node filtering. If a node label is provided, vertices matching the label are the only vertices that are included, including vertices in the input list.
+ **traversalDirection** *(optional)* – *type:* `string`; *default:*` "outbound"`.
The direction of edge to follow. Must be one of: `"inbound"` or `"outbound"`.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## Outputs for the `sssp.deltaStepping` algorithm
For every node that can be reached from the specified source list, the algorithm returns:
+ **source** – The source node.
+ **node** – A node found traversing from the source.
+ **distance** – The distance between the source node and the found node.
## `.sssp.deltaStepping` query examples
This is a standalone query, where a source node (or nodes) is explicitly provided:
```
CALL neptune.algo.sssp.deltaStepping(
["101"],
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int"
}
)
```
This is a query integration example, where where `.sssp.deltaStepping` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node list:
```
MATCH (source:airport {code: 'ANC'})
CALL neptune.algo.sssp.deltaStepping(
source,
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int",
vertexLabel: "airport",
traversalDirection: "outbound",
concurrency: 1
}
)
YIELD node, parent, distance
RETURN source, node, parent, distance
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes is returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.sssp.deltaStepping` output
Here is an example of the output returned by .sssp.deltaStepping when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string "CALL neptune.algo.sssp.deltaStepping(['101'],
{edgeWeightProperty: 'dist', edgeWeightType: 'int'})
yield source, node, distance
return source, node, distance
limit 2" \
--language open_cypher \
/tmp/out.txt
cat /tmp/out.txt
{
"results": [
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "2709",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 65.4809036254883,
"elev": 49,
"longest": 8711,
"city": "Nadym",
"type": "airport",
"region": "RU-YAN",
"desc": "Nadym Airport",
"code": "NYM",
"prscore": 0.00016044313088059425,
"degree": 18,
"lon": 72.6988983154297,
"wccid": 2357352929951779,
"country": "RU",
"icao": "USMM",
"runways": 1
}
},
"distance": 3812
},
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "2667",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 56.8567008972168,
"elev": 2188,
"longest": 6562,
"city": "Ust-Kut",
"type": "airport",
"region": "RU-IRK",
"desc": "Ust-Kut Airport",
"code": "UKX",
"prscore": 0.000058275499999999997,
"degree": 4,
"lon": 105.730003356934,
"wccid": 2357352929951779,
"country": "RU",
"icao": "UITT",
"runways": 1
}
},
"distance": 2993
}
]
}
```
# Delta-stepping single source shortest path (SSSP) parents algorithm
The `.sssp.deltaStepping.parents` algorithm computes the shortest path distances from a single source vertex to all other vertices in the graph using a [delta-stepping](https://en.wikipedia.org/wiki/Parallel_single-source_shortest_path_algorithm#Delta_stepping_algorithm) algorithm.
Neptune Analytics implements the algorithm such that:
+ Positive edge weights must be provided using the `edgeWeightProperty` field
+ Negative edge weights are not supported.
+ The traversal direction cannot be set to `both`.
## `.sssp.deltaStepping.parents` syntax
```
CALL neptune.algo.sssp.deltaStepping.parents(
[source-node list (required)],
{
edgeWeightProperty: edge weight predicate for traversal (required)
edgeWeightType: numeric type of the edge weight property (required)
delta: the stepping delta (optional)
edgeLabels: [list of edge labels for filtering (optional)],
vertexLabel: a node label for filtering (optional),
traversalDirection: traversal direction (optional),
concurrency: number of threads to use (optional)
}
)
YIELD the outputs to generate (source and/or node)
RETURN the outputs to return
```
## `.sssp.deltaStepping.parents` inputs
+ **a source node list** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the starting location(s) for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source-node list is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source-node list for the algorithm.
+
**a configuration object that contains:**
+ **edgeWeightProperty** *(required)* – *type:* `string`; *default: none*.
The edge weight predicate for traversal.
+ **edgeWeightType** *(required)* – *type:* `string`; *valid values:* `"int"`, `"long"`, `"float"`, `"double"`.
The numeric data type of the values in the property specified by `edgeWeightProperty`.
+ **delta** *(optional)* – *type:* float; *example:* `3.0`; *default:* `2.0`.
The delta stepping value.
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **vertexLabel** *(optional)* – *type:* `string`; *example:* `"airport"`; *default:* no node filtering.
A node label for node filtering. If a node label is provided, vertices matching the label are the only vertices that are included, including vertices in the input list.
+ **traversalDirection** *(optional)* – *type:* `string`; *default:*` "outbound"`.
The direction of edge to follow. Must be one of: `"inbound"` or `"outbound"`.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## Outputs for the `sssp.deltaStepping.parents` algorithm
For every node that can be reached from the specified source list, the algorithm returns:
+ **source** – The source node.
+ **node** – A node found traversing from the source.
+ **distance** – The distance between the source node and the found node.
+ **parent** – The parent of the found node. Note that the parent of the source vertex is itself.
## `.sssp.deltaStepping.parents` query examples
This is a standalone query, where a source node (or nodes) is explicitly provided:
```
CALL neptune.algo.sssp.deltaStepping.parents(
["101"],
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int"
}
)
```
This is a query integration example, where where `.sssp.deltaStepping.parents` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node list:
```
MATCH (source:airport {code: 'ANC'})
CALL neptune.algo.sssp.deltaStepping.parents(
source,
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int",
vertexLabel: "airport",
traversalDirection: "outbound",
concurrency: 1
}
)
YIELD node, parent, distance
RETURN source, node, parent, distance
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes is returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.sssp.deltaStepping.parents` output
Here is an example of the output returned by .sssp.deltaStepping.parents when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string "CALL neptune.algo.sssp.deltaStepping.parents(['101'],
{edgeWeightProperty: 'dist', edgeWeightType: 'int'})
yield source, node, distance
return source, node, distance
limit 2" \
--language open_cypher \
/tmp/out.txt
cat /tmp/out.txt
{
"results": [
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "2709",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 65.4809036254883,
"elev": 49,
"longest": 8711,
"city": "Nadym",
"type": "airport",
"region": "RU-YAN",
"desc": "Nadym Airport",
"code": "NYM",
"prscore": 0.00016044313088059425,
"degree": 18,
"lon": 72.6988983154297,
"wccid": 2357352929951779,
"country": "RU",
"icao": "USMM",
"runways": 1
}
},
"parent": {
"~id": "810",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 55.0125999450684,
"elev": 365,
"longest": 11818,
"city": "Novosibirsk",
"type": "airport",
"region": "RU-NVS",
"desc": "Tolmachevo Airport",
"code": "OVB",
"prscore": 0.0012910010991618038,
"degree": 162,
"lon": 82.6507034301758,
"wccid": 2357352929951779,
"country": "RU",
"icao": "UNNT",
"runways": 2
}
}
},
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "2667",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 56.8567008972168,
"elev": 2188,
"longest": 6562,
"city": "Ust-Kut",
"type": "airport",
"region": "RU-IRK",
"desc": "Ust-Kut Airport",
"code": "UKX",
"prscore": 0.000058275499999999997,
"degree": 4,
"lon": 105.730003356934,
"wccid": 2357352929951779,
"country": "RU",
"icao": "UITT",
"runways": 1
}
},
"parent": {
"~id": "1038",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 52.2680015563965,
"elev": 1675,
"longest": 10384,
"city": "Irkutsk",
"type": "airport",
"region": "RU-IRK",
"desc": "Irkutsk Airport",
"code": "IKT",
"prscore": 0.0008466026629321277,
"degree": 84,
"lon": 104.388999938965,
"wccid": 2357352929951779,
"country": "RU",
"icao": "UIII",
"runways": 1
}
}
}
]
}
```
# DeltaStepping single source single target shortest path algorithm
The `.sssp.deltaStepping.path` algorithm uses the deltaStepping algorithm to find the shortest path along with the shortest path distances from a source node to a target node in the graph. If there are multiple shortest paths between the source node and the target node, only one will be returned. The algorithm can run only weighted, with `edgeWeightProperty` provided.
Neptune Analytics implements the algorithm such that:
+ Positive edge weights must be provided using the `edgeWeightProperty` field.
+ Negative edge weights are not supported.
+ The traversal direction cannot be set to `both`.
## `.sssp.deltaStepping.path` syntax
```
CALL neptune.algo.sssp.deltaStepping.path(
[source node(s) (required)], [target node(s) (required)]
{
edgeWeightProperty: edge weight predicate for traversal (required)
edgeWeightType: numeric type of the edge weight property (required),
delta: the stepping delta (optional)
edgeLabels: [list of edge labels for filtering (optional)],
vertexLabel: a node label for filtering (optional),
traversalDirection: traversal direction (optional),
concurrency: number of threads to use (optional)
}
)
YIELD the outputs to generate (source and/or node)
RETURN the outputs to return
```
## `.sssp.deltaStepping.path` inputs
+ **source node(s)** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the starting location(s) for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source node(s) is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source node(s) for the algorithm.
+ **target node(s)** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the ending location(s) for the algorithm.
+ Each source-target node pair produces an output of the algorithm.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the target node(s) for the algorithm.
+
**a configuration object that contains:**
+ **edgeWeightProperty** *(required)* – *type:* `string`; *default: none*.
The edge weight predicate for traversal.
+ **edgeWeightType** *(required)* – *type:* `string`; *valid values:* `"int"`, `"long"`, `"float"`, `"double"`.
The numeric data type of the values in the property specified by `edgeWeightProperty`.
+ **delta** *(optional)* – *type:* `float`; *example:* `3.0`; *default:* 2.0
The delta stepping value.
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **vertexLabel** *(optional)* – *type:* `string`; *example:* `"airport"`; *default:* no node filtering.
A node label for node filtering. If a node label is provided, vertices matching the label are the only vertices that are included, including vertices in the input list.
+ **traversalDirection** *(optional)* – *type:* `string`; *default:*` "outbound"`.
The direction of edge to follow. Must be one of: `"inbound"` or `"outbound"`.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## Outputs for the `.sssp.deltaStepping.path` algorithm
For every pair of source and target nodes, the algorithm returns:
+ **source** – The source vertex.
+ **target** – The target vertex.
+ **distance** – The total shortest path distance from source to target.
+ **vertexPath** – A list of vertices in the path in visit order (including the source and the target).
+ **allDistances** – A list of cumulative distances to the vertices in the traversal path (including the source and the target).
+ **path** – An openCypher path object representing the shortest path between the source and the target. (A list of vertices from the source vertex to the target vertex, interleaved with the corresponding edges, representing the shortest path. Sequence of vertex id (source), edge id, vertex id, edge id, ..., vertex id (target)).
+ Starts and ends with a vertex, and has edges in between each vertex.
+ Includes the source and the target vertices.
## `.sssp.deltaStepping.path` query examples
This is a standalone query, where a source node and target node are explicitly provided:
```
CALL neptune.algo.sssp.deltaStepping.path(
"9", "37",
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int",
delta: 2.0
}
)
```
This is a query integration example, where `.sssp.deltaStepping.path` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node(s) and target node(s):
```
MATCH (source:airport {code: 'FLL'})
MATCH (target:airport {code: 'HNL'})
CALL neptune.algo.sssp.deltaStepping.path(
source, target,
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
delta: 2.0,
edgeWeightType: "int",
vertexLabel: "airport",
traversalDirection: "outbound",
concurrency: 1
}
)
YIELD distance, vertexPath, allDistances, path
RETURN source, target, distance, vertexPath, allDistances, path
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes are returned; and that every source-target node pair produces an output, which can result in a very large query output if a large number of nodes are returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.sssp.deltaStepping.path` output
Here is an example of the output returned by .sssp.deltaStepping.path when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier} \
--query-string "MATCH (n:airport {code: 'FLL'})
MATCH (m:airport {code: 'HNL'})
CALL neptune.algo.sssp.deltaStepping.path(n, m, {
edgeWeightProperty: "dist",
edgeWeightType: "int",
delta: 2.0,
edgeLabels: ["route"],
vertexLabel: "airport",
traversalDirection: "outbound",
concurrency: 1
})
YIELD source, target, distance, vertexPath, allDistances, path
RETURN source, target, distance, vertexPath, allDistances, path" \
--language open_cypher \
/tmp/out.txt
cat /tmp/out.txt
{
"results": [{
"source": {
"~id": "9",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-FL",
"runways": 2,
"country": "US",
"city": "Fort Lauderdale",
"type": "airport",
"icao": "KFLL",
"lon": -80.152702331542997,
"code": "FLL",
"lat": 26.0725994110107,
"longest": 9000,
"elev": 64,
"desc": "Fort Lauderdale/Hollywood International Airport"
}
},
"target": {
"~id": "37",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-HI",
"runways": 4,
"country": "US",
"city": "Honolulu",
"type": "airport",
"icao": "PHNL",
"lon": -157.92199707031199,
"code": "HNL",
"lat": 21.318700790405298,
"longest": 12312,
"elev": 13,
"desc": "Honolulu International Airport"
}
},
"distance": 4854,
"vertexPath": [{
"~id": "9",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-FL",
"runways": 2,
"country": "US",
"city": "Fort Lauderdale",
"type": "airport",
"icao": "KFLL",
"lon": -80.152702331542997,
"code": "FLL",
"lat": 26.0725994110107,
"longest": 9000,
"elev": 64,
"desc": "Fort Lauderdale/Hollywood International Airport"
}
}, {
"~id": "11",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-TX",
"runways": 5,
"country": "US",
"city": "Houston",
"type": "airport",
"icao": "KIAH",
"lon": -95.341400146484403,
"code": "IAH",
"lat": 29.984399795532202,
"longest": 12001,
"elev": 96,
"desc": "George Bush Intercontinental"
}
}, {
"~id": "37",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-HI",
"runways": 4,
"country": "US",
"city": "Honolulu",
"type": "airport",
"icao": "PHNL",
"lon": -157.92199707031199,
"code": "HNL",
"lat": 21.318700790405298,
"longest": 12312,
"elev": 13,
"desc": "Honolulu International Airport"
}
}],
"allDistances": [0, 964, 4854],
"path": [{
"~id": "9",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-FL",
"runways": 2,
"country": "US",
"city": "Fort Lauderdale",
"type": "airport",
"icao": "KFLL",
"lon": -80.152702331542997,
"code": "FLL",
"lat": 26.0725994110107,
"longest": 9000,
"elev": 64,
"desc": "Fort Lauderdale/Hollywood International Airport"
}
}, {
"~id": "neptune_reserved_1_1152921504607567884",
"~entityType": "relationship",
"~start": "9",
"~end": "11",
"~type": "route",
"~properties": {
"dist": 964
}
}, {
"~id": "11",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-TX",
"runways": 5,
"country": "US",
"city": "Houston",
"type": "airport",
"icao": "KIAH",
"lon": -95.341400146484403,
"code": "IAH",
"lat": 29.984399795532202,
"longest": 12001,
"elev": 96,
"desc": "George Bush Intercontinental"
}
}, {
"~id": "neptune_reserved_1_1152921508902600717",
"~entityType": "relationship",
"~start": "11",
"~end": "37",
"~type": "route",
"~properties": {
"dist": 3890
}
}, {
"~id": "37",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-HI",
"runways": 4,
"country": "US",
"city": "Honolulu",
"type": "airport",
"icao": "PHNL",
"lon": -157.92199707031199,
"code": "HNL",
"lat": 21.318700790405298,
"longest": 12312,
"elev": 13,
"desc": "Honolulu International Airport"
}
}]
}]
}
```
# TopK hop-limited single source (weighted) shortest path algorithm
The `.topksssp`algorithm finds the single-source weighted shortest paths from a source node to its neighbors out to the distance specified by `maxDepth`. It accumulates the path lengths using the edge weights along the paths and then returns a sorted list of the shortest paths.
## `.topksssp` syntax
```
CALL neptune.algo.topksssp(
[source-node list (required)],
{
hopCount: maximum hops on the shortest path (required),
perHopLimits: [a list of the maximum number of nodes to carry forward at each hop (required)],
edgeLabels: [list of edge labels for filtering (optional)],
edgeWeightProperty: a numeric edge property to weight the traversal (optional),
edgeWeightType: numeric type of the specified edgeWeightProperty (optional),
vertexLabel: a node label for filtering (optional),
traversalDirection: traversal direction (optional, default: outbound),
costFunction: determines whether the topK distances are in ascending or descending order (optional),
concurrency: number of threads to use (optional)
}
)
YIELD source, node, distance
RETURN source, node, distance
```
## Inputs for the `topksssp` algorithm
+ **a source node list** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the starting location(s) for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source-node list is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source-node list for the algorithm.
+
**a configuration object that contains:**
+ **hopCount** *(required)* – *type:* positive integer; *default:* none.
Restricts the number of hops on a shortest path, which restricts the number of iterations of the SSSP algorithm to be used.
+ **perHopLimits** *(required)* – *type: a list of integers*; *valid values:* positive integers, or `-1` meaning unlimited; *default:* none.
Each integer represents the maximum number of candidate vertices to carry to the next hop.
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **edgeWeightProperty** *(optional)* – *type:* `string`; *default: none*.
The edge weight predicate to for traversal. If no property is specified then the algorithm runs unweighted. If multiple properties exist on an edge having the specified name, then one of them is selected at random for the weight value.
+ **edgeWeightType** *(optional)* – *type:* `string`; *valid values:* `"int"`, `"long"`, `"float"`, `"double"`.
The numeric data type of the values in the property specified by `edgeWeightProperty`. If the `edgeWeightProperty` is not present, `edgeWeightType` is ignored and the algorithm runs unweighted. If an edge contains a property specified by `edgeWeightProperty` that has a numeric type different from what is specified in `edgeWeightType`, the property value is typecast to the type specified by `edgeWeightType`.
+ **vertexLabel** *(optional)* – *type:* `string`; *default: none*.
A node label for node filtering. If a node label is provided, vertices matching the label are the only vertices that are included, including vertices in the input list.
+ **costFunction** *(optional)* – *type:* `string`; *valid values:* `"min"`, `"max"`; *default: `"min"`*.
Specifies the ordering of the topK distances returned. A `"min"` value indicates that the topK distances between the source and target vertices should be returned in descending order, whereas a `"max"` value indicates that they should be returned in ascending order.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## Outputs for the `topksssp` algorithm
For every node that can be reached from the specified source list, the algorithm returns:
+ **source** – The source node.
+ **node** – A node found traversing from the source.
+ **distance** – The distance between the source node and the found node.
## `.topksssp` query examples
This is a standalone query, where the source node list is explicitly provided in the query:
```
CALL neptune.algo.topksssp(
["101"],
{
edgeLabels: ["route"],
hopCount: 3,
perHopLimits: [10, 100, 1000],
edgeWeightProperty: "dist",
edgeWeightType: "int"
}
)
```
This is a query integration example, where `.topksssp` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node list:
```
MATCH (n) WHERE id(n) IN ["108","109"]
CALL neptune.algo.topksssp(
n,
{
edgeLabels: ["route"],
edgeWeightProperty: "dist",
edgeWeightType: "int",
hopCount: 5,
perHopLimits: [5,10,15,20,25]
}
)
YIELD distance
RETURN n, collect(distance) AS distances'
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes is returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.topksssp` output
Here is an example of the output returned by .topksssp when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier}
--query-string "CALL neptune.algo.topksssp(['101'], {hopCount: 2, perHopLimits: [3, 5]})
YIELD source, node, distance
RETURN source, node, distance limit 2" \
--language open_cypher
/tmp/out.txt
cat /tmp/out.txt
{
"results": [
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "170",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 40.8860015869,
"elev": 294,
"longest": 8622,
"city": "Naples",
"type": "airport",
"region": "IT-72",
"desc": "Naples International Airport",
"code": "NAP",
"prscore": 0.001119577675126493,
"degree": 222,
"lon": 14.2908000946,
"wccid": 2357352929951779,
"country": "IT",
"icao": "LIRN",
"runways": 1
}
},
"distance": 2.0
},
{
"source": {
"~id": "101",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 13.6810998916626,
"elev": 5,
"longest": 13123,
"city": "Bangkok",
"type": "airport",
"region": "TH-10",
"desc": "Suvarnabhumi Bangkok International Airport",
"code": "BKK",
"prscore": 0.002498496090993285,
"degree": 308,
"lon": 100.747001647949,
"wccid": 2357352929951779,
"country": "TH",
"icao": "VTBS",
"runways": 2
}
},
"node": {
"~id": "12",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"lat": 40.63980103,
"elev": 12,
"longest": 14511,
"city": "New York",
"type": "airport",
"region": "US-NY",
"desc": "New York John F. Kennedy International Airport",
"code": "JFK",
"prscore": 0.002885053399950266,
"degree": 403,
"lon": -73.77890015,
"wccid": 2357352929951779,
"country": "US",
"icao": "KJFK",
"runways": 4
}
},
"distance": 2.0
}
]
}
```
# Egonet algorithms
The EgoNet algorithm finds the (filtered) EgoNet of a vertex to its hopCount-neighbors. An EgoNet, also known as the egocentric network, is a subgraph of a social network that encapsulates the connections of a single individual, known as the ego, and all the people they are socially connected to, known as alters. EgoNet can be used for further analysis in social networks.
Neptune Analytics supports the following EgoNet algorithms:
+ [.egonet](egonet.md) – The EgoNet algorithm finds the (filtered) EgoNet of a vertex to its hopCount-neighbors. An EgoNet, also known as the egocentric network, is a subgraph of a social network that encapsulates the connections of a single individual, known as the ego, and all the people they are socially connected to, known as alters.
+ [.egonet.edgeList](egonet-edgelist.md) – This variant of EgoNet returns the edge list of the ego network instead of the node list, using a different output schema.
# .egonet
This `EgoNet` algorithm finds the (filtered) EgoNet of a vertex to its hopCount-neighbors. An EgoNet, also known as the egocentric network, is a subgraph of a social network that encapsulates the connections of a single individual, known as the ego, and all the people they are socially connected to, known as alters.
For each hop, the algorithm gets the `topK` (K is specified per hop by the user via `perHopMaxNeighbor`) neighbors those have the highest/lowest (based on the `costFunction`) edge weights, and these neighbors become the source vertices for the next hop. The algorithm assumes the graph is an edge weighted graph.
## `.egonet` syntax
```
CALL neptune.algo.egonet(
[source/ego-node list (required)],
{
hopCount: fixed hops of traversal (required),
perHopMaxNeighbor: [list of the max number of top neighbor vertices at each hop (required)],
perHopEdgeWeightProperty: [list of edge weight predicates at each hop (required)],
edgeWeightType: numeric type of the specified edgeWeightProperty (required),
edgeLabels: [list of edge labels for filtering (optional)],
perHopVertexLabel: [list of node labels for filtering at each hop(optional)],
perHopTraversalDirection: [list of traversal directions at each hop (optional, default: outbound)],
costFunction: determines whether the edges having the maximum weights or the minimum weight will be included in the EgoNet (optional),
concurrency: number of threads to use (optional)
}
)
YIELD egoNode, nodeList, edgeList
RETURN egoNode, nodeList, edgeList
```
## Inputs for the `.egonet` algorithm
+ **a source/ego node list** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the starting location(s) for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source-node list is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source-node list for the algorithm.
+
**a configuration object that contains:**
+ **hopCount** *(required)* – *type:* positive integer; *valid values:* 1, 2 or 3; other values will be rejected. *default:* none.
Restricts the number of hops during traversal.
+ **perHopMaxNeighbor** *(required)* – *type: a list of integers*; *valid values:* positive integers, or `-1` meaning unlimited; *default:* none.
Each integer represents the maximum number of candidate vertices to carry to the next hop. It should have the same size as the value of `hopCount`.
+ **perHopEdgeWeightProperty** *(required)* – *type: a list of strings*; *default:* none.
The edge weight predicate for traversal at each hop. If multiple properties exist on an edge having the specified name, then one of them is selected at random for the weight value. It should have the same size as the value of `hopCount`.
+ **edgeWeightType** *(required)* – *type: string*; *valid values:* "int", "long", "float", "double"; *default:* none.
The numeric data type of the values in the property specified by `perHopEdgeWeightProperty`. If an edge contains a property specified by `perHopEdgeWeightProperty` that has a numeric type different from what is specified in `edgeWeightType`, the property value is typecast to the type specified by `edgeWeightType`.
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **perHopVertexLabel** *(optional)* – *type:* a list of vertex label strings; *default: none*.
A list of node labels for node filtering at each hop. At each hop, if a node label is provided, vertices matching the label are the only vertices that are included, including vertices in the input list. It should have the same size as the value of `hopCount`.
+ **perHopTraversalDirection** *(optional)* – *type:* a list of strings; *valid values:* "inbound","outbound", or "both"; *default:* outbound.
The direction of edge to follow at each hop. It should have the same size as the value of `hopCount`.
+ **costFunction** *(optional)* – *type:* `string`; *valid values:* `"min"`, `"max"`; *default: `"max"`*.
This determines whether the edges having the maximum weights or the minimum weight will be included in the EgoNet adhering the `perHopMaxNeighbor` limits. A `min` value indicates that the edge with minimum weights will be included in the EgoNet, whereas a `max` value indicates that the edge with maximum weights will be included in the EgoNet.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## Outputs for the `.egonet` algorithm
The .egonet algorithm returns:
+ **egoNode** – The ego vertex for the egonet.
+ **nodeList** – A list of traversed vertices from the ego vertex.
+ **edgeList** – A list of traversed edges from the ego vertex.
## `.egonet` query examples
This is a standalone query, where the source node list is explicitly provided in the query:
```
CALL neptune.algo.egonet(["101"], {
hopCount: 2,
perHopMaxNeighbor: [-1,-1],
edgeLabels: ["route"],
perHopEdgeWeightProperty: ["dist", "dist"],
edgeWeightType: "int",
perHopVertexLabel: ["airport", "airport"],
perHopTraversalDirection: ["outbound", "outbound"],
costFunction: "max",
concurrency: 1
})
YIELD egoNode, nodeList, edgeList
RETURN egoNode, nodeList, edgeList
```
This is a query integration example, where `.egonet` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node list:
```
MATCH (n:airport {code: 'ANC'})
CALL neptune.algo.egonet(n, {
hopCount: 2,
perHopMaxNeighbor: [-1,-1],
edgeLabels: ["route"],
perHopEdgeWeightProperty: ["dist", "dist"],
edgeWeightType: "int",
perHopVertexLabel: ["airport", "airport"],
perHopTraversalDirection: ["outbound", "outbound"],
costFunction: "max",
concurrency: 1
})
YIELD nodeList, edgeList
RETURN n, nodeList, edgeList
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes is returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.egonet` output
Here is an example of the output returned by .egonet when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier}
--query-string "CALL neptune.algo.egonet(["1"], \
{perHopEdgeWeightProperty: ["dist"], \
edgeWeightType: "int", \
hopCount: 1, \
perHopMaxNeighbor: [3], \
perHopTraversalDirection: ["both"]}) \
yield egoNode, edgeList, nodeList \
return egoNode, edgeList, nodeList" \
--language open_cypher
/tmp/out.txt
cat /tmp/out.txt
{
"results": [{
"egoNode": {
"~id": "1",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-GA",
"runways": 5,
"country": "US",
"city": "Atlanta",
"type": "airport",
"icao": "KATL",
"lon": -84.4281005859375,
"code": "ATL",
"lat": 33.6366996765137,
"longest": 12390,
"elev": 1026,
"desc": "Hartsfield - Jackson Atlanta International Airport"
}
},
"edgeList": [{
"~id": "neptune_reserved_1_1152921770894950415",
"~entityType": "relationship",
"~start": "67",
"~end": "1",
"~type": "route",
"~properties": {
"dist": 7640
}
}, {
"~id": "neptune_reserved_1_1152922020003053583",
"~entityType": "relationship",
"~start": "126",
"~end": "1",
"~type": "route",
"~properties": {
"dist": 8434
}
}, {
"~id": "neptune_reserved_1_1152921521787699214",
"~entityType": "relationship",
"~start": "1",
"~end": "58",
"~type": "route",
"~properties": {
"dist": 7581
}
}],
"nodeList": [{
"~id": "126",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "ZA-GT",
"runways": 2,
"country": "ZA",
"city": "Johannesburg",
"type": "airport",
"icao": "FAJS",
"lon": 28.2460002899,
"code": "JNB",
"lat": -26.139200210599999,
"longest": 14495,
"elev": 5558,
"desc": "Johannesburg, OR Tambo International Airport"
}
}, {
"~id": "67",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "CN-31",
"runways": 2,
"country": "CN",
"city": "Shanghai",
"type": "airport",
"icao": "ZSPD",
"lon": 121.80500030517599,
"code": "PVG",
"lat": 31.1434001922607,
"longest": 13123,
"elev": 13,
"desc": "Shanghai - Pudong International Airport"
}
}, {
"~id": "58",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "AE-DU",
"runways": 2,
"country": "AE",
"city": "Dubai",
"type": "airport",
"icao": "OMDB",
"lon": 55.364398956300001,
"code": "DXB",
"lat": 25.2527999878,
"longest": 13124,
"elev": 62,
"desc": "Dubai International Airport"
}
}, {
"~id": "1",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-GA",
"runways": 5,
"country": "US",
"city": "Atlanta",
"type": "airport",
"icao": "KATL",
"lon": -84.4281005859375,
"code": "ATL",
"lat": 33.6366996765137,
"longest": 12390,
"elev": 1026,
"desc": "Hartsfield - Jackson Atlanta International Airport"
}
}]
}]
}
```
# .egonet.edgeList
This `EgoNet EdgeList` algorithm is the same as the standard `EgoNet` algorithm, except that this variant has a different output schema, which returns the `EgoNet` in an edge list form.
## `.egonet.edgeList` syntax
```
CALL neptune.algo.egonet.edgeList(
[source/ego-node list (required)],
{
hopCount: fixed hops of traversal (required),
perHopMaxNeighbor: [list of the max number of top neighor vertices at each hop (required)],
perHopEdgeWeightProperty: [list of edge weight predicates at each hop (required)],
edgeWeightType: numeric type of the specified edgeWeightProperty (required),
edgeLabels: [list of edge labels for filtering (optional)],
perHopVertexLabel: [list of node labels for filtering at each hop(optional)],
perHopTraversalDirection: [list of traversal directions at each hop (optional, default: outbound)],
costFunction: determines whether the edges having the maximum weights or the minimum weight will be included in the EgoNet (optional),
concurrency: number of threads to use (optional)
}
)
YIELD egoNode, source, target, weight
RETURN egoNode, source, target, weight
```
## Inputs for the `.egonet.edgeList` algorithm
+ **a source/ego node list** *(required)* – *type:* `Node[]` or `NodeId[]`; *default: none*.
The node or nodes to use as the starting location(s) for the algorithm.
+ Each starting node triggers its own execution of the algorithm.
+ If the source-node list is empty then the query result is also empty.
+ If the algorithm is called following a `MATCH` clause (this is known as query-algorithm integration), the output of the `MATCH` clause is used as the source-node list for the algorithm.
+
**a configuration object that contains:**
+ **hopCount** *(required)* – *type:* positive integer; *valid values:* 1, 2 or 3; other values will be rejected. *default:* none.
Restricts the number of hops during traversal.
+ **perHopMaxNeighbor** *(required)* – *type: a list of integers*; *valid values:* positive integers, or `-1` meaning unlimited; *default:* none.
Each integer represents the maximum number of candidate vertices to carry to the next hop. It should have the same size as the value of `hopCount`.
+ **perHopEdgeWeightProperty** *(required)* – *type: a list of strings*; *default:* none.
The edge weight predicate for traversal at each hop. If multiple properties exist on an edge having the specified name, then one of them is selected at random for the weight value. It should have the same size as the value of `hopCount`.
+ **edgeWeightType** *(required)* – *type: string*; *valid values:* "int", "long", "float", "double"; *default:* none.
The numeric data type of the values in the property specified by `perHopEdgeWeightProperty`. If an edge contains a property specified by `perHopEdgeWeightProperty` that has a numeric type different from what is specified in `edgeWeightType`, the property value is typecast to the type specified by `edgeWeightType`.
+ **edgeLabels** *(optional)* – *type:* a list of edge label strings; *example:* `["route", ...]`; *default:* no edge filtering.
To filter on one more edge labels, provide a list of the ones to filter on. If no `edgeLabels` field is provided then all edge labels are processed during traversal.
+ **perHopVertexLabel** *(optional)* – *type:* a list of vertex label strings; *default: none*.
A list of node labels for node filtering at each hop. At each hop, if a node label is provided, vertices matching the label are the only vertices that are included, including vertices in the input list. It should have the same size as the value of `hopCount`.
+ **perHopTraversalDirection** *(optional)* – *type:* a list of strings; *valid values:* "inbound","outbound", or "both"; *default:* outbound.
The direction of edge to follow at each hop. It should have the same size as the value of `hopCount`.
+ **costFunction** *(optional)* – *type:* `string`; *valid values:* `"min"`, `"max"`; *default: `"max"`*.
This determines whether the edges having the maximum weights or the minimum weight will be included in the EgoNet adhering the `perHopMaxNeigbor` limits. A `min` value indicates that the edge with minimum weights will be included in the EgoNet, whereas a `max` value indicates that the edge with maximum weights will be included in the EgoNet.
+ **concurrency** *(optional)* – *type:* 0 or 1; *default:* 0.
Controls the number of concurrent threads used to run the algorithm.
If set to `0`, uses all available threads to complete execution of the individual algorithm invocation. If set to `1`, uses a single thread. This can be useful when requiring the invocation of many algorithms concurrently.
## Outputs for the `.egonet.edgeList` algorithm
The .egonet.edgeList algorithm returns:
+ **egoNode** – The ego vertex of the egonet.
+ **source** – The source vertex of an edge in the weighted edge list.
+ **target** – The source vertex of an edge in the weighted edge list.
+ **weight** – The edge weight of the source-target edge in the weighted edge list.
## `.egonet.edgeList` query examples
This ia a standalone query, where the source node list is explicitly provided in the query:
```
CALL neptune.algo.egonet.edgeList(["101"], {
hopCount: 2,
perHopMaxNeighbor: [-1,-1],
edgeLabels: ["route"],
perHopEdgeWeightProperty: ["dist", "dist"],
edgeWeightType: "int",
perHopVertexLabel: ["airport", "airport"],
perHopTraversalDirection: ["outbound", "outbound"],
costFunction: "max",
concurrency: 1
})
YIELD egoNode, source, target, weight
RETURN egoNode, source, target, weight
```
This is a query integration example, where `.egonet.edgeList` follows a `MATCH` clause and uses the output of the `MATCH` clause as its source node list:
```
MATCH (n:airport {code: 'ANC'})
CALL neptune.algo.egonet.edgeList(n, {
hopCount: 2,
perHopMaxNeighbor: [-1,-1],
edgeLabels: ["route"],
perHopEdgeWeightProperty: ["dist", "dist"],
edgeWeightType: "int",
perHopVertexLabel: ["airport", "airport"],
perHopTraversalDirection: ["outbound", "outbound"],
costFunction: "max",
concurrency: 1
})
YIELD source, target, weight
RETURN n, source, target, weight
```
**Warning**
It is not good practice to use `MATCH(n)` without restriction in query integrations. Keep in mind that every node returned by the `MATCH(n)` clause invokes the algorithm once, which can result in a very long-running query if a large number of nodes is returned. Use `LIMIT` or put conditions on the `MATCH` clause to restrict its output appropriately.
## Sample `.egonet.edgeList` output
Here is an example of the output returned by .egonet.edgeList when run against the [ sample air-routes dataset [nodes]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-nodes.csv), and [ sample air-routes dataset [edges]](https://github.com/krlawrence/graph/blob/main/sample-data/air-routes-latest-edges.csv), when using the following query:
```
aws neptune-graph execute-query \
--graph-identifier ${graphIdentifier}
--query-string "CALL neptune.algo.egonet(["1"], \
{perHopEdgeWeightProperty: ["dist", "dist"], \
edgeWeightType: "int", \
hopCount: 2, \
perHopMaxNeighbor: [30, 30], \
perHopTraversalDirection: ["both", "both"]}) \
YIELD egoNode, source, target, weight \
RETURN egoNode, source, target, weight limit 2" \
--language open_cypher
/tmp/out.txt
cat /tmp/out.txt
{
"results": [{
"egoNode": {
"~id": "1",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-GA",
"runways": 5,
"country": "US",
"city": "Atlanta",
"type": "airport",
"icao": "KATL",
"lon": -84.4281005859375,
"code": "ATL",
"lat": 33.6366996765137,
"longest": 12390,
"elev": 1026,
"desc": "Hartsfield - Jackson Atlanta International Airport"
}
},
"source": {
"~id": "1",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-GA",
"runways": 5,
"country": "US",
"city": "Atlanta",
"type": "airport",
"icao": "KATL",
"lon": -84.4281005859375,
"code": "ATL",
"lat": 33.6366996765137,
"longest": 12390,
"elev": 1026,
"desc": "Hartsfield - Jackson Atlanta International Airport"
}
},
"target": {
"~id": "27",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-CA",
"runways": 3,
"country": "US",
"city": "Long Beach",
"type": "airport",
"icao": "KLGB",
"lon": -118.15200040000001,
"code": "LGB",
"lat": 33.817699429999998,
"longest": 10003,
"elev": 60,
"desc": "Long Beach Airport"
}
},
"weight": 2460
}, {
"egoNode": {
"~id": "1",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-GA",
"runways": 5,
"country": "US",
"city": "Atlanta",
"type": "airport",
"icao": "KATL",
"lon": -84.4281005859375,
"code": "ATL",
"lat": 33.6366996765137,
"longest": 12390,
"elev": 1026,
"desc": "Hartsfield - Jackson Atlanta International Airport"
}
},
"source": {
"~id": "134",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "PE-LIM",
"runways": 1,
"country": "PE",
"city": "Lima",
"type": "airport",
"icao": "SPIM",
"lon": -77.1143035889,
"code": "LIM",
"lat": -12.021900176999999,
"longest": 11506,
"elev": 113,
"desc": "Lima, Jorge Chavez International Airport"
}
},
"target": {
"~id": "1",
"~entityType": "node",
"~labels": ["airport"],
"~properties": {
"region": "US-GA",
"runways": 5,
"country": "US",
"city": "Atlanta",
"type": "airport",
"icao": "KATL",
"lon": -84.4281005859375,
"code": "ATL",
"lat": 33.6366996765137,
"longest": 12390,
"elev": 1026,
"desc": "Hartsfield - Jackson Atlanta International Airport"
}
},
"weight": 3189
}]
}
```