graph_util

Graph util is a collection of Memgraph's utility graph algorithms. The algorithms that are included in this module are the ones that may suit a developer's day-to-day job while prototyping new solutions, with various graph manipulation tools to accelerate development.

Procedures

ancestors()

Find the ancestor nodes of the input node. Ancestor nodes are all the nodes from which there is a path to the input node.

Input:

• node: Vertex ➡ The node you want to find ancestors for.

Output:

• ancestors: List[Vertex] ➡ List of ancestor nodes with a path to the source node.

Usage:

List ancestors of the node with id 1.

MATCH (n {id:1})
CALL graph_util.ancestors(n)
YIELD ancestors
UNWIND ancestors AS ancestor
RETURN ancestor;

chain_nodes()

Creates a relationship between each of the neighboring nodes in the input list, nodes. Each of the relationships gets the relationship type from the second input parameter edge_type.

Input:

• nodes: List[Vertex] ➡ List of nodes between which we want to create corresponding relationships.
• edge_type: String ➡ The name of the relationship that will be created between nodes.

Output:

• connections: List[Edge] ➡ List of relationships that connect the nodes. Each node is connected with the node following it in the input list, using the relationship type specified as the second input parameter.

Usage:

Create relationships of type MY_EDGE between nodes.

MATCH (n)
WITH collect(n) AS nodes
CALL graph_util.chain_nodes(nodes, "MY_EDGE")
YIELD connections
RETURN nodes, connections;

connect_nodes()

Returns a list of relationships that connect the list of inputted nodes. Typically used to create a subgraph from returned nodes.

Input:

• nodes: List[Vertex] ➡ List of nodes for which we want to find corresponding connections, i.e., relationships between them.

Output:

• connections: List[Edge] ➡ List of relationships that connect the starting graph's input nodes.

Usage:

List all relationships connecting collected nodes.

MATCH (n)
WITH collect(n) AS nodes
CALL graph_util.connect_nodes(nodes)
YIELD connections
RETURN nodes, connections;

descendants()

Find the descendant nodes of the input node. Descendant nodes are all the nodes with an existing path from the input node.

Input:

• node: Vertex ➡ The node for which we want to find descendants.

Output:

• descendants: List[Vertex] ➡ List of descendants with a path from the source node.

Usage:

List descendants of the node with id 1.

MATCH (n {id:1})
CALL graph_util.descendants(n)
YIELD descendants
UNWIND descendants AS descendant
RETURN descendant;

topological_sort()

The topological sort algorithm takes a directed graph and returns an array of the nodes where each node appears before all the nodes it points to. The ordering of the nodes in the array is called a topological ordering. The sort is done either on the whole graph, or a graph projection.

Output:

• sorted_nodes: List[Vertex] ➡ Node ordering in which each node appears before all nodes to which it points to.

Usage:

Node ordering of the whole graph:

CALL graph_util.topological_sort() YIELD sorted_nodes
UNWIND sorted_nodes AS nodes
RETURN nodes.name;

Node ordering of a subgraph:

MATCH p=(sl:SomeLabel)-[*bfs]->(al:AnotherLabel)
WITH project(p) AS graph
CALL graph_util.topological_sort(graph) YIELD sorted_nodes
UNWIND sorted_nodes AS nodes
RETURN nodes.name;