Skip to main content

betweenness

reddb_server::storage::engine::graph_algorithms

Function betweenness 

Source 
pub fn betweenness<N: Clone + Ord>(
    nodes: &[N],
    edges: &[(N, N, Weight)],
) -> Vec<(N, f64)>
Expand description

Betweenness centrality over an abstract undirected, unweighted graph using Brandes’ algorithm.

Inputs mirror connected_components: nodes declares the universe and edges are treated as UNDIRECTED (weights ignored; endpoints absent from nodes still join the universe). The score of node v is the number of shortest paths between all other unordered pairs {s, t} that pass through v. Each unordered pair is counted once (the raw directed accumulation is halved), so an isolated node and both endpoints of a bridge score 0.0.

Output: one (node, score) pair per distinct node, ordered by node ascending.

Determinism (guaranteed and tested): the node universe is a sorted, deduped BTreeSet; BFS explores neighbours in ascending index order; the accumulation visits vertices in reverse-BFS-distance order with stable per-level ordering. Identical input always produces identical output.