# 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

### Procedures​

info

If you want to execute this algorithm on graph projections, subgraphs or portions of the graph, be sure to check out the guide on How to run a MAGE module on subgraphs.

### 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 ancestorsUNWIND ancestors AS ancestorRETURN 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 nodesCALL graph_util.chain_nodes(nodes, "MY_EDGE")YIELD connectionsRETURN 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 nodesCALL graph_util.connect_nodes(nodes)YIELD connectionsRETURN 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 descendantsUNWIND descendants AS descendantRETURN 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_nodesUNWIND sorted_nodes AS nodesRETURN nodes.name;

Usage on a graph projection:

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