igraphalg

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

tip

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

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.

`get_all_simple_paths(v, to, cutoff)`

Returns all simple paths in the graph G from source to target. A simple path is a path with no repeated nodes.

Input:

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:

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

`spanning_tree(weights, directed)`

Returns a minimum spanning tree on a graph G. A minimum spanning tree is a subset of the edges of a connected graph that connects all of the vertices without any cycles.

Input:

weights: string (default=NULL) ➡ Data key to use for edge 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:

CALL igraphalg.spanning_tree() 
YIELD *
RETURN tree;

`pagerank(damping, weights, directed,implementation)`

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 links. It was originally designed as an algorithm to rank web pages.

Input:

damping: double (default=0.85) ➡ Damping parameter for PageRank.
weights: string (default="weight") ➡ Edge data key to use 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 or arpack.

Output:

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

Usage:

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

`get_shortest_path(source, target, weights, directed)`

Compute the shortest path in the graph.

Input:

source: Vertex (default=NULL) ➡ Path's starting node.
target: Vertex (default=NULL) ➡ Path's ending node.
weights: string (default=NULL) ➡ If None, every edge has weight/distance/cost 1. If the value is a property name, use that property as the edge weight. If an edge 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:

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

Usage:

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

`shortest_path_length(source, target, weights, directed)`

Compute the shortest path length in the graph.

Input:

source: Vertex (default=NULL) ➡ Path's starting node.
target: Vertex (default=NULL) ➡ Path's ending node.
weights: string (default=NULL) ➡ If None, every edge has weight/distance/cost 1. If the value is a property name, use that property as the edge weight. If an edge 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:

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

`topological_sort(mode)`

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:

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

Output:

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

Usage:

CALL igraphalg.topological_sort() YIELD *
RETURN nodes;

`maxflow(source, target, capacity)`

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

Input:

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") ➡ Edge property which is used as the flow capacity of the edge.

Output:

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

Usage:

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

`mincut(source, target, capacity,directed)`

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

Input:

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") ➡ Edge property which is used as the capacity of the edge.

Output:

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

Usage:

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

`community_leiden(objective_function, weights, resolution_parameter, beta, initial_membership, n_iterations, node_weights)`

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

Input:

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 edge attribute as the edge weight if it isn't edge 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 vertex weights used in the Leiden algorithm. If this is not provided, it will be automatically determined based on the objective_function.

Output:

node: Vertex ➡ Vertex in graph.
community_id: int ➡ Id of community where node belongs.

Usage:

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

`all_shortest_path_lengths( weights, directed)`

Compute all shortest path lengths in the graph.

Input:

weights: string (default=NULL) ➡ If None, every edge has weight/distance/cost 1. If the value is a property name, use that property as the edge weight. If an edge 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 ➡ Source node.
dest_node: Vertex ➡ Destination node.
length: double ➡ If true, the graph is directed, otherwise, it's undirected.

Usage:

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

Procedures​

get_all_simple_paths(v, to, cutoff)​

Input:​

Output:​

Usage:​

spanning_tree(weights, directed)​

Input:​

Output:​

Usage:​

pagerank(damping, weights, directed,implementation)​

Input:​

Output:​

Usage:​

get_shortest_path(source, target, weights, directed)​

Input:​

Output:​

Usage:​

shortest_path_length(source, target, weights, directed)​

Input:​

Output:​

Usage:​

topological_sort(mode)​

Input:​

Output:​

Usage:​

maxflow(source, target, capacity)​

Input:​

Output:​

Usage:​

mincut(source, target, capacity,directed)​

Input:​

Output:​

Usage:​

community_leiden(objective_function, weights, resolution_parameter, beta, initial_membership, n_iterations, node_weights)​

Input:​

Output:​

Usage:​

all_shortest_path_lengths( weights, directed)​

Input:​

Output:​

Usage:​

Procedures

`get_all_simple_paths(v, to, cutoff)`

Input:

Output:

Usage:

`spanning_tree(weights, directed)`

Input:

Output:

Usage:

`pagerank(damping, weights, directed,implementation)`

Input:

Output:

Usage:

`get_shortest_path(source, target, weights, directed)`

Input:

Output:

Usage:

`shortest_path_length(source, target, weights, directed)`

Input:

Output:

Usage:

`topological_sort(mode)`

Input:

Output:

Usage:

`maxflow(source, target, capacity)`

Input:

Output:

Usage:

`mincut(source, target, capacity,directed)`

Input:

Output:

Usage:

`community_leiden(objective_function, weights, resolution_parameter, beta, initial_membership, n_iterations, node_weights)`

Input:

Output:

Usage:

`all_shortest_path_lengths( weights, directed)`

Input:

Output:

Usage: