Skip to content

Parallel Processing

Graphina provides multi-threaded implementations of common algorithms using Rayon. This allows you to leverage all CPU cores for processing large graphs.

Enabling Parallel Support

The parallel feature must be enabled in your Cargo.toml (if not enabled by default):

[dependencies]
graphina = { version = "0.4.0-alpha.4", features = ["parallel"] }

Available Algorithms

The graphina::parallel module mirrors many algorithms from the main modules but executes them in parallel.

Parallel PageRank

Significantly faster than the single-threaded version for graphs with millions of nodes. Rank is distributed in proportion to edge weight, so results match the sequential pagerank in the centrality module.

use graphina::core::types::Digraph;
use graphina::parallel::pagerank_parallel;

let mut g = Digraph::<&str, f64>::new();
// Add a few nodes
let n1 = g.add_node("A");
let n2 = g.add_node("B");
g.add_edge(n1, n2, 1.0);

let ranks = pagerank_parallel(&g, 0.85, 100, 1e-6, None);

Parallel Connected Components

Finds connected components in parallel.

use graphina::parallel::connected_components_parallel;

let components = connected_components_parallel(&g);

Parallel Breadth-First Search (BFS)

Performing BFS from multiple sources concurrently.

use graphina::core::types::Digraph;
use graphina::parallel::bfs_parallel;

let mut g = Digraph::<&str, f64>::new();
let n1 = g.add_node("A");
let n2 = g.add_node("B");

let start_nodes = vec![n1, n2];
// Returns a Vec<Vec<NodeId>> containing the traversal order from each source
let visited = bfs_parallel(&g, &start_nodes);

Parallel Closeness Centrality

Computes closeness centrality scores in parallel using Wasserman-Faust correction for disconnected graphs.

use graphina::parallel::closeness_centrality_parallel;

let closeness = closeness_centrality_parallel(&g).unwrap();

Parallel All Pairs Shortest Path Length

Computes the shortest path lengths between all pairs of nodes in parallel.

use graphina::parallel::all_pairs_shortest_path_length_parallel;

let (node_ordering, matrix) = all_pairs_shortest_path_length_parallel(&g);

When to Use Parallelism?

Parallelism implies overhead. Use it when:

  • The graph has > 100,000 nodes.
  • The algorithm is computationally intensive (e.g., Betweenness Centrality).

Thread Safety

Graphina's Graph and Digraph types are thread-safe (implement Sync) as long as the node attributes (A) and edge weights (W) are also Sync. This allows them to be shared across threads efficiently.