facett-graphview 0.1.11

//! **Connected components** — undirected (union-find) + strongly-connected
//! (Tarjan, directed). Both return a labelling `Vec<usize>` (`comp[i]` = component id,
//! compact `0..count`) plus the component `count`.

use super::Adjacency;

/// A component labelling: `of[i]` is node `i`'s component (compact `0..count`).
#[derive(Clone, Debug, PartialEq)]
pub struct Components {
    pub of: Vec<usize>,
    pub count: usize,
}

impl Components {
    /// Group node indices by component, ordered by component id.
    #[must_use]
    pub fn groups(&self) -> Vec<Vec<usize>> {
        let mut g = vec![Vec::new(); self.count];
        for (i, &c) in self.of.iter().enumerate() {
            g[c].push(i);
        }
        g
    }
    /// Size of the largest component (`0` when empty).
    #[must_use]
    pub fn largest(&self) -> usize {
        self.groups().iter().map(Vec::len).max().unwrap_or(0)
    }
}

/// **Weakly / undirected connected components** via union-find. Two nodes share a
/// component iff a path connects them ignoring edge direction.
#[must_use]
pub fn connected(g: &Adjacency) -> Components {
    let n = g.n;
    let mut uf = UnionFind::new(n);
    for i in 0..n {
        for &(j, _) in &g.und[i] {
            uf.union(i, j);
        }
    }
    compactify(&(0..n).map(|i| uf.find(i)).collect::<Vec<_>>())
}

/// **Strongly connected components** (Tarjan, directed). Two nodes share an SCC iff
/// each is reachable from the other following edge direction. Iterative (no recursion
/// blowout on deep graphs). Component ids are compact `0..count`.
#[must_use]
pub fn strongly_connected(g: &Adjacency) -> Components {
    let n = g.n;
    let mut index = vec![usize::MAX; n];
    let mut low = vec![0usize; n];
    let mut on_stack = vec![false; n];
    let mut stack: Vec<usize> = Vec::new();
    let mut comp = vec![usize::MAX; n];
    let mut next_index = 0usize;
    let mut next_comp = 0usize;

    // Iterative Tarjan: a work stack of (node, next-neighbour-cursor).
    for start in 0..n {
        if index[start] != usize::MAX {
            continue;
        }
        let mut work: Vec<(usize, usize)> = vec![(start, 0)];
        while let Some(&(v, ci)) = work.last() {
            if ci == 0 {
                index[v] = next_index;
                low[v] = next_index;
                next_index += 1;
                stack.push(v);
                on_stack[v] = true;
            }
            if ci < g.out[v].len() {
                // Advance this frame's cursor, then recurse / relax the child.
                work.last_mut().unwrap().1 += 1;
                let w = g.out[v][ci].0;
                if index[w] == usize::MAX {
                    work.push((w, 0));
                } else if on_stack[w] {
                    low[v] = low[v].min(index[w]);
                }
            } else {
                // Done with v: if it's a root, pop its SCC.
                if low[v] == index[v] {
                    loop {
                        let w = stack.pop().unwrap();
                        on_stack[w] = false;
                        comp[w] = next_comp;
                        if w == v {
                            break;
                        }
                    }
                    next_comp += 1;
                }
                work.pop();
                if let Some(&(p, _)) = work.last() {
                    low[p] = low[p].min(low[v]);
                }
            }
        }
    }
    // Tarjan emits SCCs in reverse-topological order; relabel to compact ids as-is.
    Components { of: comp, count: next_comp }
}

/// Relabel arbitrary root ids into compact `0..count` (stable by first appearance).
fn compactify(roots: &[usize]) -> Components {
    let mut map = std::collections::HashMap::new();
    let mut of = Vec::with_capacity(roots.len());
    let mut count = 0;
    for &r in roots {
        let id = *map.entry(r).or_insert_with(|| {
            let id = count;
            count += 1;
            id
        });
        of.push(id);
    }
    Components { of, count }
}

/// Union-find with path compression + union by size.
struct UnionFind {
    parent: Vec<usize>,
    size: Vec<usize>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        Self { parent: (0..n).collect(), size: vec![1; n] }
    }
    fn find(&mut self, x: usize) -> usize {
        let mut r = x;
        while self.parent[r] != r {
            r = self.parent[r];
        }
        // Path compression.
        let mut c = x;
        while self.parent[c] != r {
            let nxt = self.parent[c];
            self.parent[c] = r;
            c = nxt;
        }
        r
    }
    fn union(&mut self, a: usize, b: usize) {
        let (ra, rb) = (self.find(a), self.find(b));
        if ra == rb {
            return;
        }
        let (big, small) = if self.size[ra] >= self.size[rb] { (ra, rb) } else { (rb, ra) };
        self.parent[small] = big;
        self.size[big] += self.size[small];
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn connected_finds_two_islands() {
        // {0,1,2} linked; {3,4} linked; separate.
        let g = Adjacency::from_edges(5, &[(0, 1), (1, 2), (3, 4)]);
        let c = connected(&g);
        assert_eq!(c.count, 2);
        assert_eq!(c.of[0], c.of[2], "0 and 2 are in one component");
        assert_ne!(c.of[0], c.of[3], "the islands are distinct");
        assert_eq!(c.largest(), 3);
    }

    #[test]
    fn scc_collapses_a_cycle_but_splits_a_chain() {
        // 0→1→2→0 is one SCC; 3→4 splits into two singletons.
        let g = Adjacency::from_edges(5, &[(0, 1), (1, 2), (2, 0), (3, 4)]);
        let scc = strongly_connected(&g);
        assert_eq!(scc.of[0], scc.of[1]);
        assert_eq!(scc.of[1], scc.of[2], "the 3-cycle is one SCC");
        assert_ne!(scc.of[3], scc.of[4], "an acyclic chain is two singleton SCCs");
        assert_eq!(scc.count, 3, "one cycle-SCC + two singletons");
    }

    #[test]
    fn scc_of_a_dag_is_all_singletons() {
        let g = Adjacency::from_edges(4, &[(0, 1), (1, 2), (2, 3), (0, 3)]);
        let scc = strongly_connected(&g);
        assert_eq!(scc.count, 4, "a DAG has no non-trivial SCC");
    }

    #[test]
    fn empty_graph_has_isolated_components() {
        let g = Adjacency::from_edges(3, &[]);
        assert_eq!(connected(&g).count, 3);
        assert_eq!(strongly_connected(&g).count, 3);
    }
}