# Available advanced algorithms

If you require procedures designed to solve specific graph problems, there is a number of advanced algorithms available in Memgraph.

Some algorithms are built in, and others are available in the MAGE graph library.

## Built-in algorithms

Algorithms | Lang | Description |
---|---|---|

Depth-first search | C++ | An algorithm for traversing through a graph starting based on nodes' depth (distance from the source node). |

Breadth-first search | C++ | An algorithm for traversing through a graph starting based on nodes' breadth (distance from the source node). |

Weighted shortest path | C++ | The weighted shortest path problem is the problem of finding a path between two nodes in a graph such that the sum of the weights of relationships connecting nodes, or the sum of the weight of some node property on the path, is minimized. |

All shortest paths | C++ | Finding all shortest paths is an expansion of the weighted shortest paths problem. The goal of finding the shortest path is obtaining any minimum sum of weights on the path from one node to the other. |

## Traditional graph algorithms

Algorithms | Lang | Description |
---|---|---|

betweenness_centrality | C++ | The betweenness centrality of a node is defined as the sum of the of all-pairs shortest paths that run through the node, divided by the number of all-pairs shortest paths in the graph. The algorithm has O(nm) time complexity. |

biconnected_components | C++ | Algorithm for calculating maximal biconnected subgraph. A biconnected subgraph is a subgraph with a property that if any vertex were to be removed, the graph will remain connected. |

bipartite_matching | C++ | Algorithm for calculating maximum bipartite matching, where matching is a set of nodes chosen in such a way that no two edges share an endpoint. |

bridges | C++ | A bridge is an edge, which when deleted, increases the number of connected components. The goal of this algorithm is to detect edges that are bridges in a graph. |

collections | C++ | The collections module is a collection manipulation module that offers functions to work with lists in Cypher queries, allowing operations like filtering, sorting, and modification for efficient data handling. |

community_detection | C++ | The Louvain method for community detection is a greedy method for finding communities with maximum modularity in a graph. Runs in O(nlogn) time. |

cycles | C++ | Algorithm for detecting cycles on graphs. |

degree_centrality | C++ | The basic measurement of centrality that refers to the number of edges adjacent to a node. |

distance_calculator | C++ | Module for finding the geographical distance between two points defined with 'lng' and 'lat' coordinates. |

graph_coloring | Python | Algorithm for assigning labels to the graph elements subject to certain constraints. In this form, it is a way of coloring the graph vertices such that no two adjacent vertices are of the same color. |

katz_centrality | C++ | Katz centrality is a centrality measurement that outputs a node's influence based on the number of shortest paths and their weighted length. |

kmeans_clustering | Python | An algorithm for clustering given data. |

map | C++ | The map module offers a versatile toolkit for manipulating collections of key-value pairs, enabling advanced data operations within a graph database context |

max_flow | Python | An algorithm for finding a flow through a graph such that it is the maximum possible flow. |

node_similarity | C++ | A module that contains similarity measures for calculating the similarity between two nodes. |

pagerank | C++ | Algorithm that yields the influence measurement based on the recursive information about the connected nodes influence. |

path | C++ | A module for working with intricate connections in graph-like structures. It provides functions and procedures to navigate and analyze paths, helping users uncover insights from complex data relationships. |

set_cover | Python | An algorithm for finding the minimum cost subcollection of sets that covers all elements of a universe. |

tsp | Python | An algorithm for finding the shortest possible route that visits each vertex exactly once. |

union_find | Python | A module with an algorithm that enables the user to check whether the given nodes belong to the same connected component. |

vrp | Python | Algorithm for finding the shortest route possible between the central depot and places to be visited. The algorithm can be solved with multiple vehicles that represent a visiting fleet. |

weakly_connected_components | C++ | A module that finds weakly connected components in a graph. |

## Streaming graph algorithms

Algorithms | Lang | Description |
---|---|---|

betweenness_centrality_online | C++ | A dynamic algorithm that updates exact betweenness centrality scores of nodes in evolving graphs. Suitable for graph streaming applications. |

community_detection_online | C++ | A dynamic community detection algorithm suitable for large-scale graphs based upon label propagation. Runs in O(m) time and has O(mn) space complexity. |

katz_centrality_online | C++ | Online implementation of the Katz centrality. Outputs the approximate result for Katz centrality while maintaining the order of rankings. |

node2vec_online | Python | An algorithm for calculating node embeddings as new edges arrive. |

pagerank_online | C++ | A dynamic algorithm made for calculating PageRank in a graph streaming scenario. |

## Graph ML algorithms

Algorithms | Lang | Description |
---|---|---|

link_prediction with GNN | Python | Module for predicting links in the graph by using graph neural networks. |

node_classification with GNN | Python | Graph neural network-based node classification module |

node2vec | Python | An algorithm for calculating node embeddings on static graph. |

temporal_graph_networks | Python | A graph neural network (GNN) algorithm that can learn to predict new edges and node labels from the graph structure and available node and edge features. |

## Utility algorithms

Algorithms | Lang | Description |
---|---|---|

conditional_execution | C++ | Define conditions not expressible in Cypher and and use them to control query execution. |

create | C++ | The create module is a set of powerful tools that provide additional capabilities for creating nodes and relationships in the Memgraph graph database. |

convert | Python | A module used for conversion from one data type to another. |

date | C++ | The `date` module provides various utilities to handle date and time operations within the Cypher query language. |

export_util | Python | A module for exporting the graph database in different formats (JSON). |

graph_analyzer | Python | This Graph Analyzer query module offers insights about the stored graph or a subgraph. |

graph_util | C++ | A module with common graph algorithms and graph manipulation utilities |

import_util | Python | A module for importing data from different formats (JSON). |

json_util | Python | A module for loading JSON from a local file or remote address. |

labels | C++ | The `label` module provides an array of utilities for working with labels. |

llm_util | Python | A module that contains procedures describing graphs in a format best suited for large language models (LLMs). |

meta | C++ | Provides information about graph nodes and relationships. |

meta_util | Python | A module that contains procedures describing graphs on a meta-level. |

migrate | Python | A module that can access data from a MySQL, SQL Server or Oracle database. |

neighbors | C++ | The neighbors module allows users to interact with and query nodes that have direct relationships to a specified node. |

node | C++ | A module that provides a comprehensive toolkit for managing graph nodes, enabling creation, deletion, updating, merging, and more. |

nodes | C++ | A module that provides a comprehensive toolkit for managing multiple graph nodes, enabling linking, updating, type deduction and more. |

periodic | C++ | A module containing procedures for periodically running difficult and/or memory/time consuming queries. |

refactor | C++ | The refactor module provides utilities for changing nodes and relationships. |

rust_example (opens in a new tab) | Rust | Example of a basic module with input parameters forwarding, made in Rust. |

schema | C++ | A module which offers procedures that allow you to interact with and retrieve information about the database schema. |

temporal | Python | A module that provides functions to handle temporal (time-related) operations and offers extended capabilities compared to the date module. |

text | The `text` module offers a toolkit for manipulating strings. | |

util_module | C++ | A module which offers a range of functions for tasks such as validation and creating cryptographic hash values. This module serves as a practical resource for streamlining a variety of tasks related to database operations. |

uuid_generator | C++ | A module that generates a new universally unique identifier (UUID). |

xml_module | Python | A module which enhances graph database capabilities by providing support for loading and parsing XML data. |

## Integrations

Algorithms | Lang | Description |
---|---|---|

cugraph | CUDA | Collection of NVIDIA GPU-powered algorithms integrated in Memgraph. Includes centrality measures, link analysis and graph clusterings. |

elasticsearch | Python | A module used for synchronizing Memgraph and Elasticsearch. |

igraph | Python | A module that provides igraph integration with Memgraph and implements many igraph algorithms. |

nxalg | Python | A module that provides NetworkX integration with Memgraph and implements many NetworkX algorithms. |