Advanced algorithms
Available algorithms
igraphalg

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.

Source code
TraitValue
Module typemodule
ImplementationPython
Graph directiondirected/undirected
Edge weightsweighted/unweighted
Parallelismsequential
💡

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

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

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. 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 (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. 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:

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

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

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

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

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

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