# igraphalg

The  **igraphalg** module provides a comprehensive set of thin wrappers around
some of the algorithms present in the [igraph](https://igraph.org/) package. The
wrapper functions can create an igraph compatible graph-like object that can
stream the native database graph directly, significantly lowering memory usage.

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

> **Note**
>
> If you are not satisfied with the performance of algorithms from the igraphalg
> module, check Memgraph's native implementation of algorithms such as
> [PageRank](https://memgraph.com/docs/advanced-algorithms/available-algorithms/pagerank), [shortest
> path](https://memgraph.com/docs/advanced-algorithms/deep-path-traversal), and
> [others](https://memgraph.com/docs/advanced-algorithms/available-algorithms) written in C++.

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

### `get_all_simple_paths()`

Returns all simple paths in the graph `G` from source to target. A simple path
is a path with no repeated 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.

- `v: Vertex` ➡ Path's starting node.
- `to: Vertex` ➡ Path's ending node.
- `cutoff: int (default=-1)` ➡ Maximum length of the considered path. If negative, paths of all lengths are considered.

#### Output:

- `path: List[Vertex]` ➡ List of vertices for a certain path. If there are no paths between the source and the target within the given cutoff, there is no output.

#### Usage:

Use the following query to get all simple paths:

```cypher
MATCH (n:Label), (m:Label)
CALL igraphalg.get_all_simple_paths(n, m, 5) 
YIELD path
RETURN path;
```

### `spanning_tree()`

Returns a minimum spanning tree on a graph `G`.
A *minimum spanning tree* is a subset of the relationships of a connected graph that connects all of the nodes without any cycles.

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

- `weights: string (default=NULL)` ➡ Property used for relationship weights.
- `directed: bool (default=False)` ➡ If `True` the graph is directed, otherwise it's undirected.

#### Output:

- `tree: List[List[Vertex]]` ➡ A minimum spanning tree or forest.

#### Usage:

Use the following query to return a minimum spanning tree:

```cypher
CALL igraphalg.spanning_tree() 
YIELD tree
RETURN tree;
```

### `pagerank()`

Returns the PageRank of the nodes in the graph.

PageRank computes a ranking of the nodes in graph G based on the structure of the incoming relationships.

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

- `damping: double (default=0.85)` ➡ Damping parameter for PageRank.
- `weights: string (default="weight")` ➡ Property used as a weight. If `None`, weights are set to 1.
- `directed: bool (default=True)` ➡ If `True` the graph is directed, otherwise it's undirected.
- `implementation: string (default="prpack")` ➡ Algorithm used for calculating
  PageRank values. The algorithm can be either `prpack`, which uses the [PRPACK
  library](https://github.com/dgleich/prpack) or `arpack` using ARPACK library.

#### Output:

- `node: Vertex` ➡ Node for which the PageRank is calculated.
- `rank: double` ➡ Node's PageRank value.

#### Usage:

Use the following query to compute the PageRank:

```cypher
CALL igraphalg.pagerank() 
YIELD node, rank
RETURN node, rank;
```

### `get_shortest_path()`

Compute the shortest path in the graph.

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

- `source: Vertex (default=NULL)` ➡ Path's starting node.
- `target: Vertex (default=NULL)` ➡ Path's ending node. 
- `weights: string (default=NULL)` ➡ If `None`, every relationship has
  weight/distance/cost 1. If the value is a property name, use that property as
  the relationship weight. If a relationship doesn't have that property, the
  value defaults to 1.
- `directed: bool (default=True)` ➡ If `True`, the graph is directed, otherwise,
  it's undirected.

#### Output:

* `path: List[Vertex]` ➡  Path between `source` node and `target` node.

#### Usage:

Use the following query to compute the shortest path:

```cypher
MATCH (n:Label), (m:Label)
CALL igraphalg.get_shortest_path(n, m) 
YIELD path
RETURN path;
```

### `shortest_path_length()`

Compute the shortest path length in the graph.

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

- `source: Vertex (default=NULL)` ➡ Path's starting node.
- `target: Vertex (default=NULL)` ➡ Path's ending node. 
- `weights: string (default=NULL)` ➡ If `None`, every relationship has
  weight/distance/cost 1. If the value is a property name, use that property as
  the relationship weight. If a relationship doesn't have a property, the value
  defaults to 1.
- `directed: bool (default=True)` ➡ If `True`, the graph is directed, otherwise,
  it's undirected.

#### Output:

* `length: double` ➡ Shortest path length between the `source` node and `target`
  node. If there is no path it returns `inf`.

#### Usage:

Use the following query to compute the shortest path length:

```cypher
MATCH (n:Label), (m:Label)
CALL igraphalg.shortest_path_length(n, m) 
YIELD length
RETURN length;
```

### `topological_sort()`

Returns nodes in topologically sorted order. A *topological sort* is a
non-unique permutation of the nodes such that an edge from `u` to `v` implies
that `u` appears before `v` in the topological sort order.

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

- `mode: string (default="out")` ➡ Specifies how to use the direction of the
  relationships. For `out`, the sorting order ensures that each node comes
  before all nodes to which it has relationships, so nodes with no incoming
  relationships go first. For `in`, it is quite the opposite: each node comes
  before all nodes from which it receives relationships. Nodes with no outgoing
  relationships go first.

#### Output:

- `nodes: List[Vertex]` ➡ A list of nodes in topological sorted order.

#### Usage:

Use the following query to sort nodes topologically:

```cypher
CALL igraphalg.topological_sort() 
YIELD nodes
RETURN nodes;
```

### `maxflow()`

The maximum flow problem consists of finding a flow through a graph such that it is the maximum possible flow.

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

- `source: Vertex` ➡ Source node from which the maximum flow is calculated.
- `target: Vertex` ➡ Sink node to which the max flow is calculated.
- `capacity: string (default="weight")` ➡ Relationship property which is used as the flow capacity of the relationship.

#### Output:

- `max_flow: Number` ➡ Maximum flow of the network, from source to sink.

#### Usage:

Use the following query to fin the maximum flow:

```cypher
MATCH (source {id: 0}), (sink {id: 5})
CALL igraphalg.maxflow(source, sink, "weight")
YIELD max_flow
RETURN max_flow;
```

### `mincut()`

Minimum cut calculates the minimum st-cut between two vertices in a graph.

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

- `source: Vertex` ➡ Source node from which the minimum cut is calculated.
- `target: Vertex` ➡ Sink node to which the minimum cut is calculated.
- `capacity: string (default="weight")` ➡ Relationship property which is used as the capacity of the relationship.
- `directed: bool (default=True)` ➡ If `True` the graph is directed, otherwise,
  it's undirected.

#### Output:

* `node: Vertex` ➡ Vertex in graph.
* `partition_id: int` ➡ ID of the partition where `node` belongs after min-cut.

#### Usage:

Use the following query to fin the minimum cut:

```cypher
  MATCH (source {id: 0}), (sink {id: 5})
  CALL igraphalg.mincut(source, sink)
  YIELD node, partition_id 
  RETURN node, partition_id;
```

### `community_leiden()`

Finding community structure of a graph using the Leiden algorithm of Traag, van Eck & Waltman.

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

- `objective_function: string (default="CPM")` ➡ Whether to use the Constant
  Potts Model (CPM) or modularity. Must be either `CPM` or `modularity`.
- `weights: string (default=NULL)` ➡ If a string is present, use this property
  as the relationship weight if it isn't the weights default to 1.
- `resolution_parameter: float (default=1.0)` ➡ Higher resolutions lead to
  smaller communities, while lower resolutions lead to fewer larger communities.
- `beta: float (default=0.01)` ➡ Parameter affecting the randomness in the
  Leiden algorithm. This affects only the refinement step of the algorithm.
- `initial_membership: List[int](default=NULL)` ➡  If provided, the Leiden
  algorithm will try to improve this provided membership. If no argument is
  provided, the algorithm simply starts from the singleton partition.
- `n_iterations: int (default=2)` ➡ The number of iterations to iterate the
  Leiden algorithm. Each iteration may improve the partition further.
- `vertex_weights: List[float] (default=NULL)` ➡ The node weights used in the
  Leiden algorithm. If this is not provided, it will be automatically determined
  based on the `objective_function`.

#### Output:

- `node: Vertex` ➡ Node in graph.
- `community_id: int` ➡ ID of community where `node` belongs.

#### Usage:

Use the following query to find the community structure:

```cypher
    CALL igraphalg.community_leiden() 
    YIELD node, community_id
    RETURN node, community_id;
```

### `all_shortest_path_lengths()`

Compute all shortest path lengths in the graph.

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

- `weights: string (default=NULL)` ➡ If `None`, every relationship has
  weight/distance/cost 1. If the value is a property name, use that property as
  the relationship weight. If a relationship doesn't have a property, the value
  defaults to 1.
- `directed: bool (default=True)` ➡ If `True`, the graph is directed, otherwise,
  it's undirected.

#### Output:

- `src_node: Vertex` ➡ The source node.
- `dest_node: Vertex` ➡ The destination node.
- `length: double` ➡ If `True`, the graph is directed, otherwise, it's undirected.

#### Usage:

Use the following query to compute all shortest path lengths: 

```cypher
CALL igraphalg.all_shortest_path_length()
  YIELD src_node, dest_node, length
  RETURN src_node, dest_node, length;
```