Struct Graph 

pub struct Graph { /* private fields */ }

Graph structure using CSR (Compressed Sparse Row) for cache efficiency.

Memory layout inspired by Combinatorial BLAS (Buluc et al. 2009):

• Adjacency stored as two flat vectors (CSR format)
• Node labels stored separately (accessed rarely)
• String→NodeId mapping via HashMap (build-time only)

Performance

• Memory: 50-70% reduction vs HashMap (no pointer overhead)
• Cache misses: 3-5x fewer (sequential access pattern)
• SIMD-friendly: Neighbor iteration can use vectorization

Implementations

impl Graph

pub fn new(is_directed: bool) -> Self

Create empty graph.

Arguments

• is_directed - Whether the graph is directed

Examples

use aprender::graph::Graph;

let g = Graph::new(false); // undirected
assert_eq!(g.num_nodes(), 0);

pub fn num_nodes(&self) -> usize

Get number of nodes in graph.

pub fn num_edges(&self) -> usize

Get number of edges in graph.

pub fn is_directed(&self) -> bool

Check if graph is directed.

pub fn neighbors(&self, v: NodeId) -> &[NodeId]

Get neighbors of node v in O(degree(v)) time with perfect cache locality.

Arguments

• v - Node ID

Returns

Slice of neighbor node IDs

Examples

use aprender::graph::Graph;

let g = Graph::from_edges(&[(0, 1), (1, 2)], false);
assert_eq!(g.neighbors(1), &[0, 2]);

pub fn from_edges(edges: &[(NodeId, NodeId)], is_directed: bool) -> Self

Build graph from edge list.

This is the primary construction method. Automatically detects the number of nodes from the edge list and builds CSR representation.

Arguments

• edges - Slice of (source, target) tuples
• is_directed - Whether the graph is directed

Examples

use aprender::graph::Graph;

let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], true);
assert_eq!(g.num_nodes(), 3);
assert_eq!(g.num_edges(), 3);

pub fn from_weighted_edges( edges: &[(NodeId, NodeId, f64)], is_directed: bool, ) -> Self

Build weighted graph from edge list with weights.

Arguments

• edges - Slice of (source, target, weight) tuples
• is_directed - Whether the graph is directed

Examples

use aprender::graph::Graph;

let g = Graph::from_weighted_edges(&[(0, 1, 1.0), (1, 2, 2.5)], false);
assert_eq!(g.num_nodes(), 3);
assert_eq!(g.num_edges(), 2);

pub fn degree_centrality(&self) -> HashMap<NodeId, f64>

Compute degree centrality for all nodes.

Uses Freeman’s normalization (1978): C_D(v) = deg(v) / (n - 1)

Returns

HashMap mapping NodeId to centrality score in [0, 1]

Performance

O(n + m) where n = nodes, m = edges

Examples

use aprender::graph::Graph;

// Star graph: center has degree 3, leaves have degree 1
let g = Graph::from_edges(&[(0, 1), (0, 2), (0, 3)], false);
let dc = g.degree_centrality();

assert_eq!(dc[&0], 1.0); // center connected to all others
assert!((dc[&1] - 0.333).abs() < 0.01); // leaves connected to 1 of 3

pub fn pagerank( &self, damping: f64, max_iter: usize, tol: f64, ) -> Result<Vec<f64>, String>

Compute PageRank using power iteration with Kahan summation.

Uses the PageRank algorithm (Page et al. 1999) with numerically stable Kahan summation (Higham 1993) to prevent floating-point drift in large graphs (>10K nodes).

Arguments

• damping - Damping factor (typically 0.85)
• max_iter - Maximum iterations (default 100)
• tol - Convergence tolerance (default 1e-6)

Returns

Vector of PageRank scores (one per node)

Performance

O(k * m) where k = iterations, m = edges

Examples

use aprender::graph::Graph;

let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], true);
let pr = g.pagerank(0.85, 100, 1e-6).expect("pagerank should converge for valid graph");
assert!((pr.iter().sum::<f64>() - 1.0).abs() < 1e-10); // Kahan ensures precision

pub fn betweenness_centrality(&self) -> Vec<f64>

Compute betweenness centrality using parallel Brandes’ algorithm.

Uses Brandes’ algorithm (2001) with Rayon parallelization for the outer loop. Each source’s BFS is independent, making this “embarrassingly parallel” (Bader & Madduri 2006).

Performance

• Serial: O(nm) for unweighted graphs
• Parallel: O(nm/p) where p = number of CPU cores
• Expected speedup: ~8x on 8-core CPU for graphs with >1K nodes

Returns

Vector of betweenness centrality scores (one per node)

Examples

use aprender::graph::Graph;

// Path graph: 0 -- 1 -- 2
// Middle node has higher betweenness
let g = Graph::from_edges(&[(0, 1), (1, 2)], false);
let bc = g.betweenness_centrality();
assert!(bc[1] > bc[0]); // middle node has highest betweenness
assert!(bc[1] > bc[2]);

pub fn modularity(&self, communities: &[Vec<NodeId>]) -> f64

Compute modularity of a community partition.

Modularity Q measures the density of edges within communities compared to a random graph. Ranges from -0.5 to 1.0 (higher is better).

Formula: Q = (1/2m) Σ[A_ij - k_i*k_j/2m] δ(c_i, c_j) where:

• m = total edges
• A_ij = adjacency matrix
• k_i = degree of node i
• δ(c_i, c_j) = 1 if nodes i,j in same community, 0 otherwise

Arguments

• communities - Vector of communities, each community is a vector of node IDs

Returns

Modularity score Q ∈ [-0.5, 1.0]

pub fn louvain(&self) -> Vec<Vec<NodeId>>

Detect communities using the Louvain algorithm.

The Louvain method is a greedy modularity optimization algorithm that:

1. Starts with each node in its own community
2. Iteratively moves nodes to communities that maximize modularity gain
3. Aggregates the graph by treating communities as super-nodes
4. Repeats until modularity converges

Performance

• Time: O(m·log n) typical, where m = edges, n = nodes
• Space: O(n + m)

Returns

Vector of communities, each community is a vector of node IDs

Examples

use aprender::graph::Graph;

// Two triangles connected by one edge
let g = Graph::from_edges(&[
    (0, 1), (1, 2), (2, 0),  // Triangle 1
    (3, 4), (4, 5), (5, 3),  // Triangle 2
    (2, 3),                   // Connection
], false);

let communities = g.louvain();
assert_eq!(communities.len(), 2);  // Two communities detected

pub fn closeness_centrality(&self) -> Vec<f64>

Compute closeness centrality for all nodes.

Closeness measures how close a node is to all other nodes in the graph. Uses Wasserman & Faust (1994) normalization: C_C(v) = (n-1) / Σd(v,u)

Returns

Vector of closeness centrality scores (one per node) For disconnected graphs, nodes unreachable from v are ignored in the sum.

Performance

O(n·(n + m)) where n = nodes, m = edges (BFS from each node)

Examples

use aprender::graph::Graph;

// Star graph: center is close to all nodes
let g = Graph::from_edges(&[(0, 1), (0, 2), (0, 3)], false);
let cc = g.closeness_centrality();
assert!(cc[0] > cc[1]); // center has highest closeness

pub fn eigenvector_centrality( &self, max_iter: usize, tol: f64, ) -> Result<Vec<f64>, String>

Compute eigenvector centrality using power iteration.

Eigenvector centrality measures node importance based on the importance of its neighbors. Uses the dominant eigenvector of the adjacency matrix.

Arguments

• max_iter - Maximum power iterations (default 100)
• tol - Convergence tolerance (default 1e-6)

Returns

Vector of eigenvector centrality scores (one per node)

Performance

O(k·m) where k = iterations, m = edges

Examples

use aprender::graph::Graph;

// Path graph: middle nodes have higher eigenvector centrality
let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 3)], false);
let ec = g.eigenvector_centrality(100, 1e-6).unwrap();
assert!(ec[1] > ec[0]); // middle nodes more central

pub fn katz_centrality( &self, alpha: f64, max_iter: usize, tol: f64, ) -> Result<Vec<f64>, String>

Compute Katz centrality with attenuation factor.

Katz centrality generalizes eigenvector centrality by adding an attenuation factor for long-range connections: C_K = Σ(α^k · A^k · 1)

Arguments

• alpha - Attenuation factor (typically 0.1-0.5, must be < 1/λ_max)
• max_iter - Maximum iterations (default 100)
• tol - Convergence tolerance (default 1e-6)

Returns

Vector of Katz centrality scores

Performance

O(k·m) where k = iterations, m = edges

Examples

use aprender::graph::Graph;

let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], true);
let kc = g.katz_centrality(0.1, 100, 1e-6).unwrap();
assert_eq!(kc.len(), 3);

pub fn harmonic_centrality(&self) -> Vec<f64>

Compute harmonic centrality for all nodes.

Harmonic centrality is the sum of reciprocal distances to all other nodes. More robust than closeness for disconnected graphs (Boldi & Vigna 2014).

Formula: C_H(v) = Σ(1/d(v,u)) for all u ≠ v

Returns

Vector of harmonic centrality scores

Performance

O(n·(n + m)) where n = nodes, m = edges

Examples

use aprender::graph::Graph;

// Star graph: center has highest harmonic centrality
let g = Graph::from_edges(&[(0, 1), (0, 2), (0, 3)], false);
let hc = g.harmonic_centrality();
assert!(hc[0] > hc[1]); // center most central

pub fn density(&self) -> f64

Compute graph density.

Density is the ratio of actual edges to possible edges. For undirected: d = 2m / (n(n-1)) For directed: d = m / (n(n-1))

Returns

Density in [0, 1] where 1 is a complete graph

Examples

use aprender::graph::Graph;

// Complete graph K4 has density 1.0
let g = Graph::from_edges(&[(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)], false);
assert!((g.density() - 1.0).abs() < 1e-6);

pub fn diameter(&self) -> Option<usize>

Compute graph diameter (longest shortest path).

Returns None if graph is disconnected.

Returns

Some(diameter) if connected, None otherwise

Performance

O(n·(n + m)) - runs BFS from all nodes

Examples

use aprender::graph::Graph;

// Path graph 0--1--2--3 has diameter 3
let g = Graph::from_edges(&[(0,1), (1,2), (2,3)], false);
assert_eq!(g.diameter(), Some(3));

pub fn clustering_coefficient(&self) -> f64

Compute global clustering coefficient.

Measures the probability that two neighbors of a node are connected. Formula: C = 3 × triangles / triads

Returns

Clustering coefficient in [0, 1]

Performance

O(n·d²) where d = average degree

Examples

use aprender::graph::Graph;

// Triangle has clustering coefficient 1.0
let g = Graph::from_edges(&[(0,1), (1,2), (2,0)], false);
assert!((g.clustering_coefficient() - 1.0).abs() < 1e-6);

pub fn assortativity(&self) -> f64

Compute degree assortativity coefficient.

Measures correlation between degrees of connected nodes. Positive: high-degree nodes connect to high-degree nodes Negative: high-degree nodes connect to low-degree nodes

Returns

Assortativity coefficient in [-1, 1]

Performance

O(m) where m = edges

Examples

use aprender::graph::Graph;

// Star graph has negative assortativity
let g = Graph::from_edges(&[(0,1), (0,2), (0,3)], false);
assert!(g.assortativity() < 0.0);

pub fn shortest_path( &self, source: NodeId, target: NodeId, ) -> Option<Vec<NodeId>>

Compute shortest path between two nodes using BFS.

Finds the shortest path (minimum number of hops) from source to target using breadth-first search. Works for both directed and undirected graphs.

Algorithm

Uses BFS with predecessor tracking (Pohl 1971, bidirectional variant).

Arguments

• source - Starting node ID
• target - Destination node ID

Returns

• Some(path) - Shortest path as vector of node IDs from source to target
• None - No path exists between source and target

Complexity

• Time: O(n + m) where n = nodes, m = edges
• Space: O(n) for predecessor tracking

Examples

use aprender::graph::Graph;

let edges = vec![(0, 1), (1, 2), (2, 3), (0, 3)];
let g = Graph::from_edges(&edges, false);

// Shortest path from 0 to 3
let path = g.shortest_path(0, 3).unwrap();
assert_eq!(path.len(), 2); // 0 -> 3 (direct edge)
assert_eq!(path[0], 0);
assert_eq!(path[1], 3);

// Path 0 to 2
let path = g.shortest_path(0, 2).unwrap();
assert!(path.len() <= 3); // Either 0->1->2 or 0->3->2

pub fn dijkstra( &self, source: NodeId, target: NodeId, ) -> Option<(Vec<NodeId>, f64)>

Compute shortest path using Dijkstra’s algorithm for weighted graphs.

Finds the shortest path from source to target using Dijkstra’s algorithm with a binary heap priority queue. Handles both weighted and unweighted graphs.

Algorithm

Uses Dijkstra’s algorithm (1959) with priority queue for O((n+m) log n) complexity.

Arguments

• source - Starting node ID
• target - Destination node ID

Returns

• Some((path, distance)) - Shortest path and total distance
• None - No path exists

Panics

Panics if graph contains negative edge weights.

Complexity

• Time: O((n + m) log n)
• Space: O(n) for distance tracking and priority queue

Examples

use aprender::graph::Graph;

let g = Graph::from_weighted_edges(&[(0, 1, 1.0), (1, 2, 2.0), (0, 2, 5.0)], false);
let (path, dist) = g.dijkstra(0, 2).unwrap();
assert_eq!(dist, 3.0); // 0->1->2 is shorter than 0->2

pub fn all_pairs_shortest_paths(&self) -> Vec<Vec<Option<usize>>>

Compute all-pairs shortest paths using repeated BFS.

Computes the shortest path distance between all pairs of nodes. Uses BFS for unweighted graphs (O(nm)) which is faster than Floyd-Warshall (O(n³)) for sparse graphs.

Algorithm

Runs BFS from each node (Floyd 1962 for weighted, BFS for unweighted).

Returns

Distance matrix where [i][j] = shortest distance from node i to node j. Returns None if nodes are not connected.

Complexity

• Time: O(n·(n + m)) for unweighted graphs
• Space: O(n²) for distance matrix

Examples

use aprender::graph::Graph;

let g = Graph::from_edges(&[(0, 1), (1, 2)], false);
let dist = g.all_pairs_shortest_paths();

assert_eq!(dist[0][0], Some(0));
assert_eq!(dist[0][1], Some(1));
assert_eq!(dist[0][2], Some(2));

pub fn a_star<F>( &self, source: NodeId, target: NodeId, heuristic: F, ) -> Option<Vec<NodeId>>

where F: Fn(NodeId) -> f64,

Compute shortest path using A* search algorithm with heuristic.

Finds the shortest path from source to target using A* algorithm with a user-provided heuristic function. The heuristic must be admissible (never overestimate) for optimality guarantees.

Algorithm

Uses A* search (Hart et al. 1968) with f(n) = g(n) + h(n) where:

• g(n) = actual cost from source to n
• h(n) = estimated cost from n to target (heuristic)

Arguments

• source - Starting node ID
• target - Destination node ID
• heuristic - Function mapping NodeId to estimated distance to target

Returns

• Some(path) - Shortest path as vector of node IDs
• None - No path exists

Complexity

• Time: O((n + m) log n) with admissible heuristic
• Space: O(n) for tracking

Examples

use aprender::graph::Graph;

let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 3)], false);

// Manhattan distance heuristic (example)
let heuristic = |node: usize| (3 - node) as f64;

let path = g.a_star(0, 3, heuristic).unwrap();
assert_eq!(path, vec![0, 1, 2, 3]);

pub fn dfs(&self, source: NodeId) -> Option<Vec<NodeId>>

Depth-First Search (DFS) traversal starting from a given node.

Returns nodes in the order they were visited (pre-order traversal). Only visits nodes reachable from the source node.

Arguments

• source - Starting node for traversal

Returns

Vector of visited nodes in DFS order, or None if source is invalid

Time Complexity

O(n + m) where n = number of nodes, m = number of edges

Examples

use aprender::graph::Graph;

let g = Graph::from_edges(&[(0, 1), (1, 2), (0, 3)], false);
let visited = g.dfs(0).expect("valid source");
assert_eq!(visited.len(), 4); // All nodes reachable
assert_eq!(visited[0], 0); // Starts at source

pub fn connected_components(&self) -> Vec<usize>

Find connected components using Union-Find algorithm.

Returns a vector where each index is a node ID and the value is its component ID. Nodes in the same component have the same component ID.

For directed graphs, this finds weakly connected components (ignores edge direction).

Returns

Vector mapping each node to its component ID (0-indexed)

Time Complexity

O(m·α(n)) where α is the inverse Ackermann function (effectively constant)

Examples

use aprender::graph::Graph;

// Two disconnected components: (0,1) and (2,3)
let g = Graph::from_edges(&[(0, 1), (2, 3)], false);
let components = g.connected_components();

assert_eq!(components[0], components[1]); // Same component
assert_ne!(components[0], components[2]); // Different components

pub fn strongly_connected_components(&self) -> Vec<usize>

Find strongly connected components using Tarjan’s algorithm.

A strongly connected component (SCC) is a maximal set of vertices where every vertex is reachable from every other vertex in the set.

Only meaningful for directed graphs. For undirected graphs, use connected_components().

Returns

Vector mapping each node to its SCC ID (0-indexed)

Time Complexity

O(n + m) - single-pass DFS

Examples

use aprender::graph::Graph;

// Directed cycle: 0 -> 1 -> 2 -> 0
let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0)], true);
let sccs = g.strongly_connected_components();

// All nodes in same SCC
assert_eq!(sccs[0], sccs[1]);
assert_eq!(sccs[1], sccs[2]);

pub fn topological_sort(&self) -> Option<Vec<NodeId>>

Topological sort for directed acyclic graphs (DAGs).

Returns a linear ordering of vertices where for every directed edge (u,v), u appears before v in the ordering.

Only valid for DAGs. If the graph contains a cycle, returns None.

Returns

Some(Vec) with nodes in topological order, or None if graph has cycles

Time Complexity

O(n + m) - DFS-based approach

Examples

use aprender::graph::Graph;

// DAG: 0 -> 1 -> 2
let g = Graph::from_edges(&[(0, 1), (1, 2)], true);
let order = g.topological_sort().expect("DAG should have topological order");

// 0 comes before 1, 1 comes before 2
assert!(order.iter().position(|&x| x == 0) < order.iter().position(|&x| x == 1));
assert!(order.iter().position(|&x| x == 1) < order.iter().position(|&x| x == 2));

pub fn common_neighbors(&self, u: NodeId, v: NodeId) -> Option<usize>

Count common neighbors between two nodes (link prediction metric).

Returns the number of neighbors shared by both nodes u and v. Used for link prediction: nodes with many common neighbors are more likely to form a connection.

Arguments

• u - First node
• v - Second node

Returns

Number of common neighbors, or None if either node is invalid

Time Complexity

O(min(deg(u), deg(v))) - intersection of neighbor sets

Examples

use aprender::graph::Graph;

// Triangle: 0-1, 0-2, 1-2
let g = Graph::from_edges(&[(0, 1), (0, 2), (1, 2)], false);

// Nodes 1 and 2 share neighbor 0
assert_eq!(g.common_neighbors(1, 2), Some(1));

pub fn adamic_adar_index(&self, u: NodeId, v: NodeId) -> Option<f64>

Adamic-Adar index for link prediction between two nodes.

Computes a weighted measure of common neighbors, where neighbors with fewer connections are weighted more heavily. This captures the intuition that sharing a rare neighbor is more significant than sharing a common one.

Formula: AA(u,v) = Σ 1/log(deg(z)) for all common neighbors z

Arguments

• u - First node
• v - Second node

Returns

Adamic-Adar index score, or None if either node is invalid

Time Complexity

O(min(deg(u), deg(v))) - intersection of neighbor sets

Examples

use aprender::graph::Graph;

// Graph with shared neighbors
let g = Graph::from_edges(&[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)], false);

// Adamic-Adar index for nodes 1 and 2
let aa = g.adamic_adar_index(1, 2).expect("valid nodes");
assert!(aa > 0.0);

pub fn label_propagation( &self, max_iter: usize, seed: Option<u64>, ) -> Vec<usize>

Label propagation algorithm for community detection.

Iteratively assigns each node the most common label among its neighbors. Nodes with the same final label belong to the same community.

Arguments

• max_iter - Maximum number of iterations (default: 100)
• seed - Random seed for deterministic tie-breaking (optional)

Returns

Vector mapping each node to its community label (0-indexed)

Time Complexity

O(max_iter · m) where m = number of edges

Examples

use aprender::graph::Graph;

// Graph with two communities: (0,1,2) and (3,4,5)
let g = Graph::from_edges(
    &[(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (2, 3)],
    false
);

let communities = g.label_propagation(100, Some(42));
// Nodes in same community have same label
assert_eq!(communities[0], communities[1]);

Trait Implementations

impl Debug for Graph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.