# igraphalg

The **igraphalg** module provides a comprehensive set of thin wrappers around
some of the algorithms present in the igraph (opens in a new tab) 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 |

If you are not satisfied with the performance of algorithms from the igraphalg module, check Memgraph's native implementation of algorithms such as PageRank, shortest path, and others written in C++.

## Procedures

You can execute this algorithm on graph projections, subgraphs or portions of the graph.

`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 returned by the`project()`

function, on which the algorithm is run.`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:

```
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 returned by the`project()`

function, on which the algorithm is run.`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:

```
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 returned by the`project()`

function, on which the algorithm is run.`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 (opens in a new tab) 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:

```
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 returned by the`project()`

function, on which the algorithm is run.`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:

```
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 returned by the`project()`

function, on which the algorithm is run.`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:

```
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 returned by the`project()`

function, on which the algorithm is run.`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:

```
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 returned by the`project()`

function, on which the algorithm is run.`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:

```
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 returned by the`project()`

function, on which the algorithm is run.`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:

```
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 returned by the`project()`

function, on which the algorithm is run.`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 strucutre:

```
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 returned by the`project()`

function, on which the algorithm is run.`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:

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