Struct CallGraph 

pub struct CallGraph {
    pub total_callee_names: usize,
    pub resolved_callee_names: usize,
    /* private fields */
}

Call graph for a codebase.

Uses an index-based representation: node strings are interned into a Vec<String> and all adjacency, BFS, and PageRank structures operate on u32 indices. This avoids per-BFS-call HashMap<String, …> allocations that otherwise grow unbounded under approximate betweenness (k=256 calls × ~400 MB/call).

Fields

total_callee_names: usize

Total callee names found in ASTs across all functions

resolved_callee_names: usize

Callee names that resolved to a known internal function ID

Implementations

impl CallGraph

pub fn new() -> Self

Create an empty call graph

pub fn intern(&mut self, id: String) -> u32

Intern a node string, returning its u32 index (allocated if new).

pub fn node_count(&self) -> usize

Number of nodes in the graph.

pub fn edge_count(&self) -> usize

Total number of directed edges in the graph.

pub fn contains(&self, id: &str) -> bool

Returns true if id is a node in this graph.

pub fn callees_of<'a>( &'a self, id: &str, ) -> Option<impl Iterator<Item = &'a str>>

Returns an iterator over callee IDs for the given function, or None if not found.

pub fn add_adj(&mut self, caller_idx: u32, callee_idx: u32)

Add a directed edge from caller_idx to callee_idx (index-based, no interning).

Both indices must already be interned. Used by lib.rs during fast graph construction to avoid redundant string lookups after intern has already been called.

pub fn all_ids(&self) -> impl Iterator<Item = &str>

Iterate over all interned function IDs in the graph.

pub fn add_node(&mut self, function_id: String)

Add a function to the graph (interning its ID).

pub fn add_edge(&mut self, caller: String, callee: String)

Add a call edge (caller -> callee), interning both nodes.

pub fn fan_in(&self, function_id: &str) -> usize

Calculate fan-in for a function (number of callers).

pub fn fan_out(&self, function_id: &str) -> usize

Calculate fan-out for a function (number of callees).

pub fn pagerank( &self, damping: f64, max_iterations: usize, epsilon: f64, ) -> HashMap<String, f64>

Calculate PageRank for all functions.

Uses Vec indexed by node index with swap-buffer iteration — no per-iteration HashMap allocations.

Arguments

• damping - Damping factor (typically 0.85)
• max_iterations - Upper bound on iterations (typically 20-50)
• epsilon - Convergence threshold; stop early when max delta < epsilon (e.g. 1e-6)

pub fn betweenness_centrality_approx(&self, k: usize) -> HashMap<String, f64>

Calculate betweenness centrality using pivoted source sampling (approximate).

Uses systematic k-source sampling: selects k sources evenly spaced through the sorted node list and scales contributions by N/k. This gives an unbiased estimator of exact betweenness with O(k × (N+E)) complexity instead of O(N × (N+E)).

Falls back to exact computation when self.node_count() <= k.

BFS working buffers (stack, pred, sigma, dist, delta) are pre-allocated once and reused across all k iterations via .clear() / .fill() — RSS is flat regardless of k.

Arguments

• k - Number of pivot sources to sample (higher = more accurate, more time)

pub fn betweenness_centrality(&self) -> HashMap<String, f64>

Calculate betweenness centrality for all functions (exact).

Uses Brandes’ algorithm: O(N × (N+E)). For large graphs use betweenness_centrality_approx instead.

BFS working buffers are pre-allocated once and reused across all N iterations.

pub fn find_strongly_connected_components( &self, ) -> HashMap<String, (usize, usize)>

Find strongly connected components using iterative Tarjan’s algorithm.

Returns a map from function ID to (scc_id, scc_size). Functions in the same SCC form a cyclic dependency group.

pub fn compute_dependency_depth(&self) -> HashMap<String, Option<usize>>

Compute dependency depth for all functions.

Returns a map from function ID to depth (0 = entry point, None = unreachable).

pub fn build_fan_in_map(&self) -> HashMap<String, usize>

Build a map from function ID to its fan-in count in O(N + E).

pub fn is_entry_point(&self, function_id: &str) -> bool

Check if a function is likely an entry point.

pub fn metrics_for( &self, function_id: &str, pagerank_scores: &HashMap<String, f64>, betweenness_scores: &HashMap<String, f64>, ) -> GraphMetrics

Calculate all graph metrics for a function.

Trait Implementations

impl Clone for CallGraph

fn clone(&self) -> CallGraph

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for CallGraph

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

Formats the value using the given formatter.

impl Default for CallGraph

fn default() -> Self

Returns the “default value” for a type.