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 theproject()
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 theproject()
function, on which the algorithm is run.weights: string (default=NULL)
➡ Property used for relationship weights.directed: bool (default=False)
➡ IfTrue
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 theproject()
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. IfNone
, weights are set to 1.directed: bool (default=True)
➡ IfTrue
the graph is directed, otherwise it's undirected.implementation: string (default="prpack")
➡ Algorithm used for calculating PageRank values. The algorithm can be eitherprpack
, which uses the PRPACK library (opens in a new tab) orarpack
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 theproject()
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)
➡ IfNone
, 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)
➡ IfTrue
, the graph is directed, otherwise, it's undirected.
Output:
path: List[Vertex]
➡ Path betweensource
node andtarget
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 theproject()
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)
➡ IfNone
, 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)
➡ IfTrue
, the graph is directed, otherwise, it's undirected.
Output:
length: double
➡ Shortest path length between thesource
node andtarget
node. If there is no path it returnsinf
.
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 theproject()
function, on which the algorithm is run.mode: string (default="out")
➡ Specifies how to use the direction of the relationships. Forout
, the sorting order ensures that each node comes before all nodes to which it has relationships, so nodes with no incoming relationships go first. Forin
, 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 theproject()
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 theproject()
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)
➡ IfTrue
the graph is directed, otherwise, it's undirected.
Output:
node: Vertex
➡ Vertex in graph.partition_id: int
➡ ID of the partition wherenode
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 theproject()
function, on which the algorithm is run.objective_function: string (default="CPM")
➡ Whether to use the Constant Potts Model (CPM) or modularity. Must be eitherCPM
ormodularity
.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 theobjective_function
.
Output:
node: Vertex
➡ Node in graph.community_id: int
➡ ID of community wherenode
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 theproject()
function, on which the algorithm is run.weights: string (default=NULL)
➡ IfNone
, 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)
➡ IfTrue
, the graph is directed, otherwise, it's undirected.
Output:
src_node: Vertex
➡ The source node.dest_node: Vertex
➡ The destination node.length: double
➡ IfTrue
, 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;