Cypher supports only simple filtering when matching variable length paths. For example:
This will produce only those paths whose edges have the required
property value. Edges that compose the produced paths are stored in a symbol
edge_list. Naturally, the user could have specified any other symbol
Memgraph extends openCypher with a syntax for arbitrary filter expressions
during path matching. The next example filters edges which have property
Here we introduce a lambda function with parentheses, where the first two
node, correspond to each edge and node during path
node is the destination node we are moving to across the current
edge. The last
node value will be the same value as
m. Following the
|) character is an arbitrary expression which must produce a boolean
True, matching continues, otherwise the path is discarded.
The previous example can be written using the
However, filtering using a lambda function is more efficient because paths may be discarded earlier in the traversal. Furthermore, it provides more flexibility for deciding what kind of paths are matched due to more expressive filtering capabilities. Therefore, filtering through lambda functions should be preferred whenever possible.
A typical graph use-case is searching for the shortest path between nodes. The openCypher standard does not define this feature, so Memgraph provides a custom implementation, based on the edge expansion syntax.
Finding the shortest path between nodes can be done using breadth-first expansion:
The above query will find all paths of length up to 10 between nodes
The edge type and maximum path length are used in the same way like in variable
To find only the shortest path, simply append
LIMIT 1 to the
Breadth-first expansion allows an arbitrary expression filter that determines
if an expansion is allowed. Following is an example in which expansion is
allowed only over edges whose
x property is greater than
12 and nodes
whose property is less than
The filter is defined as a lambda function over
n, which denote the edge
and node being expanded over in the breadth first search. Note that if the user
omits the edge list symbol (
edge_list in previous examples) it will not be included
in the result.
There are a few benefits of the breadth-first expansion approach, as opposed to
shortestPath function. For one, it is possible to inject
expressions that filter on nodes and edges along the path itself, not just the final
destination node. Furthermore, it's possible to find multiple paths to multiple destination
nodes regardless of their length. Also, it is possible to simply go through a node's
neighbourhood in breadth-first manner.
Currently, it isn't possible to get all shortest paths to a single node using Memgraph's breadth-first expansion.
Another standard use-case in a graph is searching for the weighted shortest path between nodes. The openCypher standard does not define this feature, so Memgraph provides a custom implementation, based on the edge expansion syntax.
Finding the weighted shortest path between nodes is done using the weighted shortest path expansion:
The above query will find the shortest path of length up to 10 nodes between
b. The length restriction parameter is optional.
Weighted Shortest Path expansion allows an arbitrary expression that determines the weight for the current expansion. Total weight of a path is calculated as the sum of all weights on the path between two nodes. Following is an example in which the weight between nodes is defined as the product of edge weights (instead of sum), assuming all weights are greater than '1':
Weighted Shortest Path expansions also allows an arbitrary expression filter
that determines if an expansion is allowed. Following is an example in which
expansion is allowed only over edges whose
x property is greater than
and nodes whose
y property is less than
Both weight and filter expression are defined as lambda functions over
n, which denote the edge and the node being expanded over in the weighted
shortest path search.