# 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. (opens in a new tab)

TraitValue
Module typemodule
ImplementationC++
Graph directiondirected/undirected
Edge weightsunweighted/weighted
Parallelismsequential

### `ancestors(node)`

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

#### Input:

• `node: Vertex` ➡ node for which we want to find ancestors

#### Output:

• `ancestors: List[Vertex]` ➡ List of ancestors from which a path to the source node exists

#### Usage:

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

### `chain_nodes(nodes, edge_type)`

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

#### Input:

• `nodes: List[Vertex]` ➡ List of nodes between which we want to create corresponding relationships between them
• `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:

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

### `connect_nodes(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:

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

### `descendants(node)`

Find the descendant nodes of the input node. Descendant nodes are all the nodes to which there exists a path from the input node.

#### Input:

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

#### Output:

• `descendants: List[Vertex]` ➡ List of descendants to which a path from the source node exists

#### Usage:

``````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.

#### Input:

• there is no input to this graph. 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

#### Usage:

Usage on the whole graph:

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

Usage on a graph projection:

``````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;``````