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

| Trait               | Value                                                                                                     |
| ------------------- | ------------------- |
| **Module type**     | module              |
| **Implementation**  | C++                 |
| **Graph direction** | directed/undirected |
| **Edge weights**    | unweighted/weighted |
| **Parallelism**     | sequential          |

### Procedures

> **Info**
>
> You can execute this algorithm on [graph projections, subgraphs or portions of the graph](https://memgraph.com/docs/advanced-algorithms/run-algorithms#run-procedures-on-subgraph).

### `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](https://memgraph.com/docs/advanced-algorithms/run-algorithms#run-procedures-on-subgraph) returned by the `project()` function, on which the algorithm is run. 
If subgraph is not specified, the algorithm is computed on the entire graph by default.

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

```cypher
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](https://memgraph.com/docs/advanced-algorithms/run-algorithms#run-procedures-on-subgraph) returned by the `project()` function, on which the algorithm is run. 
If subgraph is not specified, the algorithm is computed on the entire graph by default.

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

```cypher
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](https://memgraph.com/docs/advanced-algorithms/run-algorithms#run-procedures-on-subgraph) returned by the `project()` function, on which the algorithm is run. 
If subgraph is not specified, the algorithm is computed on the entire graph by default.

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

```cypher
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](https://memgraph.com/docs/advanced-algorithms/run-algorithms#run-procedures-on-subgraph) returned by the `project()` function, on which the algorithm is run. 
If subgraph is not specified, the algorithm is computed on the entire graph by default.

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

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

#### Input:

- `subgraph: Graph` (**OPTIONAL**) ➡ A specific subgraph, which is an [object of type Graph](https://memgraph.com/docs/advanced-algorithms/run-algorithms#run-procedures-on-subgraph) returned by the `project()` function, on which the algorithm is run. 
If subgraph is not specified, the algorithm is computed on the entire graph by default.

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

```cypher
CALL graph_util.topological_sort() YIELD sorted_nodes
UNWIND sorted_nodes AS nodes
RETURN nodes.name;
```
Node ordering of a subgraph:

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