Struct SccCollapseResult 

pub struct SccCollapseResult {
    pub node_to_supernode: AHashMap<i64, i64>,
    pub supernode_members: AHashMap<i64, AHashSet<i64>>,
    pub supernode_edges: Vec<(i64, i64)>,
    pub num_sccs: usize,
}

Result of SCC collapse operation (condensation graph).

Contains the bidirectional mappings between original nodes and supernodes, plus the condensed DAG edges between supernodes.

Fields

• node_to_supernode: Maps each original node ID to its SCC supernode ID
• supernode_members: Maps each supernode ID to the set of original node IDs in that SCC
• supernode_edges: Edges between supernodes in the condensed DAG (sorted, no self-loops)
• num_sccs: Total number of SCCs found (equals number of supernodes)

Example

let collapsed = collapse_sccs(&graph)?;

// Check how many SCCs were found
println!("Found {} SCCs", collapsed.num_sccs);

// Find which SCC a node belongs to
if let Some(supernode) = collapsed.supernode_for(node_id) {
    println!("Node {} is in SCC {}", node_id, supernode);
    if let Some(members) = collapsed.members_of(supernode) {
        println!("SCC members: {:?}", members);
    }
    // Check if this is a trivial SCC (single node, no self-loop)
    if collapsed.is_trivial(supernode) {
        println!("This is a trivial SCC (no cycle)");
    } else {
        println!("This is a non-trivial SCC (contains a cycle)");
    }
}

// Iterate over condensed DAG edges
for &(from, to) in &collapsed.supernode_edges {
    println!("SCC {} -> SCC {}", from, to);
}

Fields

node_to_supernode: AHashMap<i64, i64>

Maps each original node ID to its SCC supernode ID. Use supernode_for() for convenient lookup.

supernode_members: AHashMap<i64, AHashSet<i64>>

Maps each supernode ID to the set of original node IDs in that SCC. Use members_of() for convenient lookup.

supernode_edges: Vec<(i64, i64)>

Edges between supernodes in the condensed DAG. No self-loops (from == to) exist by definition. Sorted for deterministic output.

num_sccs: usize

Total number of SCCs found. Equals the number of supernodes in the condensed graph.

Implementations

impl SccCollapseResult

pub fn supernode_for(&self, node: i64) -> Option<i64>

Gets the supernode ID for a given original node.

Returns Some(supernode_id) if the node exists in the graph, or None if the node is unknown.

Arguments

• node - The original node ID to look up

Returns

Some(i64) with the supernode ID, or None if node not found

Example

let collapsed = collapse_sccs(&graph)?;
if let Some(supernode) = collapsed.supernode_for(node_id) {
    println!("Node {} is in SCC {}", node_id, supernode);
}

pub fn members_of(&self, supernode: i64) -> Option<&AHashSet<i64>>

Gets the set of original node IDs belonging to a supernode.

Returns Some(&AHashSet<i64>) with the member nodes, or None if the supernode ID is unknown.

Arguments

• supernode - The supernode ID to look up

Returns

Some(&AHashSet<i64>) with member nodes, or None if supernode not found

Example

let collapsed = collapse_sccs(&graph)?;
if let Some(members) = collapsed.members_of(supernode_id) {
    println!("SCC {} has {} members:", supernode_id, members.len());
    for &node in members {
        println!("  - Node {}", node);
    }
}

pub fn is_trivial(&self, supernode: i64) -> bool

Checks if an SCC is trivial (single node with no self-loop).

A trivial SCC is a single node that doesn’t participate in a cycle. Non-trivial SCCs have multiple nodes OR a single node with a self-loop, both indicating cyclic behavior.

Arguments

• supernode - The supernode ID to check

Returns

true if the SCC is trivial (single node), false if non-trivial or not found

Example

let collapsed = collapse_sccs(&graph)?;
for (&supernode, members) in &collapsed.supernode_members {
    if collapsed.is_trivial(supernode) {
        println!("SCC {} is trivial (no cycle)", supernode);
    } else {
        println!("SCC {} is non-trivial (contains cycle)", supernode);
    }
}

pub fn non_trivial_count(&self) -> usize

Gets the number of non-trivial SCCs (cycles in the original graph).

Non-trivial SCCs indicate cyclic regions in the original graph. This is useful for detecting mutual recursion or circular dependencies.

Returns

Number of SCCs with more than one member

Example

let collapsed = collapse_sccs(&graph)?;
let cycle_count = collapsed.non_trivial_count();
if cycle_count > 0 {
    println!("Graph contains {} cycles (mutual recursion)", cycle_count);
}

pub fn non_trivial_nodes(&self) -> AHashSet<i64>

Gets all nodes that are part of non-trivial SCCs.

Returns the set of all node IDs that participate in cycles. Useful for identifying which functions are involved in mutual recursion.

Returns

Set of node IDs in non-trivial SCCs

Example

let collapsed = collapse_sccs(&graph)?;
let cyclic_nodes = collapsed.non_trivial_nodes();
if !cyclic_nodes.is_empty() {
    println!("Nodes involved in cycles: {:?}", cyclic_nodes);
}

Trait Implementations

impl Clone for SccCollapseResult

fn clone(&self) -> SccCollapseResult

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SccCollapseResult

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

Formats the value using the given formatter.