Module algorithms 

Graph algorithms for Graphos.

This module provides high-performance graph algorithm implementations inspired by rustworkx and GRAPE. Algorithms are designed to work with the Graphos LPG store and can be exposed to Python via bridges.

Algorithm Categories

• traversal - BFS, DFS with visitor pattern
• components - Connected components, SCC, topological sort
• shortest_path - Dijkstra, A*, Bellman-Ford, Floyd-Warshall

Usage

use graphos_adapters::plugins::algorithms::{bfs, dfs, connected_components, dijkstra};
use graphos_core::graph::lpg::LpgStore;
use graphos_common::types::NodeId;

let store = LpgStore::new();
// ... populate graph ...

// Run BFS from node 0
let visited = bfs(&store, NodeId::new(0));

// Find connected components
let components = connected_components(&store);

// Run Dijkstra's shortest path
let result = dijkstra(&store, NodeId::new(0), Some("weight"));

Structs

ArticulationPointsAlgorithm

Articulation Points algorithm wrapper.

BellmanFordAlgorithm

Bellman-Ford algorithm wrapper for the plugin registry.

BellmanFordResult

Result of Bellman-Ford algorithm.

BetweennessCentralityAlgorithm

Betweenness centrality algorithm wrapper.

BfsAlgorithm

BFS algorithm wrapper for the plugin registry.

BridgesAlgorithm

Bridges algorithm wrapper.

ClosenessCentralityAlgorithm

Closeness centrality algorithm wrapper.

ConnectedComponentsAlgorithm

Connected components algorithm wrapper.

DegreeCentralityAlgorithm

Degree centrality algorithm wrapper.

DegreeCentralityResult

Result of degree centrality computation.

DfsAlgorithm

DFS algorithm wrapper for the plugin registry.

DijkstraAlgorithm

Dijkstra algorithm wrapper for the plugin registry.

DijkstraResult

Result of Dijkstra’s algorithm.

FloydWarshallAlgorithm

Floyd-Warshall algorithm wrapper for the plugin registry.

FloydWarshallResult

Result of Floyd-Warshall algorithm.

KCoreAlgorithm

K-Core decomposition algorithm wrapper.

KCoreResult

Result of k-core decomposition.

KruskalAlgorithm

Kruskal’s MST algorithm wrapper.

LabelPropagationAlgorithm

Label Propagation algorithm wrapper.

LouvainAlgorithm

Louvain algorithm wrapper.

LouvainResult

Result of Louvain algorithm.

MaxFlowAlgorithm

Max Flow algorithm wrapper.

MaxFlowResult

Result of max flow algorithm.

MinCostFlowAlgorithm

Min Cost Max Flow algorithm wrapper.

MinCostFlowResult

Result of min cost max flow algorithm.

MinScored

Wrapper for priority queue ordering (min-heap behavior).

MstResult

Result of MST algorithms.

PageRankAlgorithm

PageRank algorithm wrapper for the plugin registry.

PrimAlgorithm

Prim’s MST algorithm wrapper.

StronglyConnectedComponentsAlgorithm

Strongly connected components algorithm wrapper.

TopologicalSortAlgorithm

Topological sort algorithm wrapper.

UnionFind

Union-Find (Disjoint Set Union) with path compression and union by rank.

Enums

Control

Control flow for algorithm visitors.

TraversalEvent

Events emitted during graph traversal (BFS/DFS).

Traits

DistanceMap

A map from nodes to distances/costs.

GraphAlgorithm

A graph algorithm that can be executed on an LPG store.

ParallelGraphAlgorithm

A graph algorithm that supports parallel execution.

Functions

articulation_points

Finds articulation points (cut vertices) in the graph.

astar

Runs A* algorithm with a heuristic function.

bellman_ford

Runs Bellman-Ford algorithm from a source node.

betweenness_centrality

Computes betweenness centrality using Brandes’ algorithm.

bfs

Performs breadth-first search from a starting node.

bfs_layers

BFS layers - returns nodes grouped by their distance from the start.

bfs_with_visitor

Performs breadth-first search with a visitor callback.

bridges

Finds bridges (cut edges) in the graph.

closeness_centrality

Computes closeness centrality for all nodes.

community_count

Returns the number of communities detected.

connected_component_count

Returns the number of connected components.

connected_components

Finds connected components in an undirected graph (or weakly connected components in a directed graph).

degree_centrality

Computes degree centrality for all nodes.

degree_centrality_normalized

Computes normalized degree centrality.

dfs

Performs depth-first search from a starting node.

dfs_all

Performs DFS on all nodes, visiting each connected component.

dfs_with_visitor

Performs depth-first search with a visitor callback.

dijkstra

Runs Dijkstra’s algorithm from a source node.

dijkstra_path

Runs Dijkstra’s algorithm to find shortest path to a specific target.

floyd_warshall

Runs Floyd-Warshall algorithm for all-pairs shortest paths.

is_dag

Checks if the graph is a DAG (Directed Acyclic Graph).

k_core

Extracts the k-core subgraph (nodes with core number >= k).

kcore_decomposition

Computes the k-core decomposition of the graph.

kruskal

Computes the Minimum Spanning Tree using Kruskal’s algorithm.

label_propagation

Detects communities using the Label Propagation Algorithm.

louvain

Detects communities using the Louvain algorithm.

max_flow

Computes maximum flow using the Edmonds-Karp algorithm.

min_cost_max_flow

Computes minimum cost maximum flow using successive shortest paths.

pagerank

Computes PageRank for all nodes using power iteration.

prim

Computes the Minimum Spanning Tree using Prim’s algorithm.

strongly_connected_component_count

Returns the number of strongly connected components.

strongly_connected_components

Finds strongly connected components in a directed graph using Tarjan’s algorithm.

topological_sort

Performs topological sort on a directed acyclic graph using Kahn’s algorithm.