Function compute_order

atomic-core/src/output/alive/order.rs:454–489

Compute the output order using Tarjan's SCC algorithm. This function: 1. Runs Tarjan's algorithm to find all SCCs 2. Builds the conflict tree 3. Identifies forward edges # Arguments `graph` - The alive graph (will be modified to set SCC indices) # Returns An `OrderResult` containing SCCs and conflict information. # Example ```rust,ignore use atomic_core::output::alive::{AliveGraph, compute_

(graph: &mut AliveGraph)

/// println!("Found {} SCCs", order.num_sccs());
/// ```
pub fn compute_order(graph: &mut AliveGraph) -> OrderResult {
    let mut result = OrderResult::new();

    if graph.is_empty() {
        return result;
    }

    let mut state = TarjanState::new(graph.len_vertices());

    // Run Tarjan's algorithm starting from span 1 (root)
    // Skip span 0 which is DUMMY
    for i in 1..graph.len_vertices() {
        let vid = VertexId::new(i);
        if !graph.get_vertex(vid).is_visited() {
            tarjan_visit(graph, vid, &mut state, &mut result);
        }
    }

    // Count cyclic conflicts
    result.cyclic_conflicts = result.sccs.iter().filter(|scc| scc.len() > 1).count();

    // Build a simple conflict tree (can be enhanced later for nested conflicts)
    build_conflict_tree(graph, &mut result);

    // Structural invariant: the SCCs must partition the alive vertices. A
    // violation here is the root of the silent duplication/omission class of
    // bugs, so fail loudly (in debug/test builds) at the point of origin
    // rather than letting corruption reach disk.
    debug_assert!(
        result.validate_partition(graph.len_vertices()).is_ok(),
        "compute_order did not produce a vertex partition: {:?}",
        result.validate_partition(graph.len_vertices())
    );

    result
}

/// Internal state for Tarjan's algorithm.
struct TarjanState {