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

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

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

• `subgraph: Graph` (OPTIONAL) ➡ A specific subgraph, which is an object of type Graph returned by the `project()` function, on which the algorithm is run.
• `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:

• `subgraph: Graph` (OPTIONAL) ➡ A specific subgraph, which is an object of type Graph returned by the `project()` function, on which the algorithm is run.
• `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:

• `subgraph: Graph` (OPTIONAL) ➡ A specific subgraph, which is an object of type Graph returned by the `project()` function, on which the algorithm is run.
• `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:

• `subgraph: Graph` (OPTIONAL) ➡ A specific subgraph, which is an object of type Graph returned by the `project()` function, on which the algorithm is run.
• `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;``````