Graph algorithms

Filtering Variable Length Paths

Cypher supports only simple filtering when matching variable length paths. For example:

MATCH (n)-[edge_list:Type * {x: 42}]-(m);

This will produce only those paths whose edges have the required Type and x property value. Edges that compose the produced paths are stored in a symbol named edge_list. Naturally, the user could have specified any other symbol name.

Memgraph extends openCypher with a syntax for arbitrary filter expressions during path matching. The next example filters edges which have property x between 0 and 10.

MATCH (n)-[edge_list * (edge, node | 0 < edge.x < 10)]-(m);

Here we introduce a lambda function with parentheses, where the first two arguments, edge and node, correspond to each edge and node during path matching. 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 pipe (|) character is an arbitrary expression which must produce a boolean value. If True, matching continues, otherwise the path is discarded.

The previous example can be written using the all function:

MATCH (n)-[edge_list *]-(m) WHERE all(edge IN edge_list WHERE 0 < edge.x < 10);

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.

Breadth First Search

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:

MATCH (a {id: 723})-[edge_list:Type *bfs..10]-(b {id: 882}) RETURN *;

The above query will find all paths of length up to 10 between nodes a and b. The edge type and maximum path length are used in the same way like in variable length expansion.

To find only the shortest path, simply append LIMIT 1 to the RETURN clause.

MATCH (a {id: 723})-[edge_list:Type *bfs..10]-(b {id: 882}) RETURN * LIMIT 1;

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 y whose property is less than 3:

MATCH (a {id: 723})-[*bfs..10 (e, n | e.x > 12 AND n.y < 3)]-() RETURN *;

The filter is defined as a lambda function over e and 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 a specialized 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.

Weighted Shortest Path

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:

MATCH (a {id: 723})-[
        edge_list *wShortest 10 (e, n | e.weight) total_weight
    ]-(b {id: 882})
RETURN *;

The above query will find the shortest path of length up to 10 nodes between nodes a and 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':

MATCH (a {id: 723})-[
        edge_list *wShortest 10 (e, n | log(e.weight)) total_weight
    ]-(b {id: 882})
RETURN exp(total_weight);

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 12 and nodes whose y property is less than 3:

MATCH (a {id: 723})-[
        edge_list *wShortest 10 (e, n | e.weight) total_weight (e, n | e.x > 12 AND n.y < 3)
    ]-(b {id: 882})
RETURN exp(total_weight);

Both weight and filter expression are defined as lambda functions over e and n, which denote the edge and the node being expanded over in the weighted shortest path search.