facett-graphview 0.1.12

//! **Cycles & ordering** — directed cycle detection, a topological sort (Kahn),
//! and elementary-cycle enumeration (Johnson-style, bounded). Directed, over the
//! `out` view.

use std::collections::VecDeque;

use super::Adjacency;

/// `true` iff the directed graph has a cycle (a back-edge in DFS). Iterative
/// three-colour DFS, so it survives deep graphs.
#[must_use]
pub fn has_cycle(g: &Adjacency) -> bool {
    const WHITE: u8 = 0;
    const GRAY: u8 = 1;
    const BLACK: u8 = 2;
    let mut color = vec![WHITE; g.n];
    for start in 0..g.n {
        if color[start] != WHITE {
            continue;
        }
        // Stack of (node, neighbour-cursor).
        let mut stack: Vec<(usize, usize)> = vec![(start, 0)];
        color[start] = GRAY;
        while let Some(&(v, ci)) = stack.last() {
            if ci < g.out[v].len() {
                stack.last_mut().unwrap().1 += 1;
                let w = g.out[v][ci].0;
                match color[w] {
                    GRAY => return true, // back-edge to an ancestor on the stack
                    WHITE => {
                        color[w] = GRAY;
                        stack.push((w, 0));
                    }
                    _ => {}
                }
            } else {
                color[v] = BLACK;
                stack.pop();
            }
        }
    }
    false
}

/// **Topological order** (Kahn's algorithm) over the directed graph, or `None` if a
/// cycle exists (no valid order). Deterministic: ties broken by lowest index.
#[must_use]
pub fn topological_sort(g: &Adjacency) -> Option<Vec<usize>> {
    let mut indeg = vec![0usize; g.n];
    for i in 0..g.n {
        for &(j, _) in &g.out[i] {
            indeg[j] += 1;
        }
    }
    // A min-ordered queue (via a sorted ready set) for determinism.
    let mut ready: VecDeque<usize> = (0..g.n).filter(|&i| indeg[i] == 0).collect();
    let mut order = Vec::with_capacity(g.n);
    while !ready.is_empty() {
        // Pop the lowest-index ready node.
        let mut best = 0;
        for (k, &v) in ready.iter().enumerate() {
            if v < ready[best] {
                best = k;
            }
        }
        let v = ready.remove(best).unwrap();
        order.push(v);
        for &(w, _) in &g.out[v] {
            indeg[w] -= 1;
            if indeg[w] == 0 {
                ready.push_back(w);
            }
        }
    }
    (order.len() == g.n).then_some(order)
}

/// **Elementary cycles** (Johnson-style DFS from each start over higher-index nodes),
/// each returned as a node list `[a, b, …, a-implied]` (the closing edge back to the
/// first node is implicit). `limit` caps how many are collected (a guard for dense
/// graphs). Cycles are canonicalised to start at their lowest node so each distinct
/// cycle is reported once.
#[must_use]
pub fn find_cycles(g: &Adjacency, limit: usize) -> Vec<Vec<usize>> {
    let mut out = Vec::new();
    if limit == 0 {
        return out;
    }
    let mut seen = std::collections::HashSet::new();
    for start in 0..g.n {
        let mut on_path = vec![false; g.n];
        let mut path = Vec::new();
        dfs_cycles(g, start, start, &mut on_path, &mut path, &mut out, &mut seen, limit);
        if out.len() >= limit {
            break;
        }
    }
    out
}

#[allow(clippy::too_many_arguments)]
fn dfs_cycles(
    g: &Adjacency,
    start: usize,
    v: usize,
    on_path: &mut [bool],
    path: &mut Vec<usize>,
    out: &mut Vec<Vec<usize>>,
    seen: &mut std::collections::HashSet<Vec<usize>>,
    limit: usize,
) {
    if out.len() >= limit {
        return;
    }
    on_path[v] = true;
    path.push(v);
    let mut nbrs: Vec<usize> = g.out[v].iter().map(|&(w, _)| w).collect();
    nbrs.sort_unstable();
    for w in nbrs {
        if w == start && path.len() >= 2 {
            // Found a cycle back to the start — canonicalise + dedupe.
            let canon = canonical_cycle(path);
            if seen.insert(canon.clone()) {
                out.push(canon);
                if out.len() >= limit {
                    break;
                }
            }
        } else if w > start && !on_path[w] {
            // Only explore higher-index nodes so each cycle is found from its min node.
            dfs_cycles(g, start, w, on_path, path, out, seen, limit);
        }
    }
    path.pop();
    on_path[v] = false;
}

/// Rotate a cycle so it begins at its lowest-index node (its canonical form).
fn canonical_cycle(path: &[usize]) -> Vec<usize> {
    let min_pos = (0..path.len()).min_by_key(|&i| path[i]).unwrap_or(0);
    let mut c: Vec<usize> = path[min_pos..].to_vec();
    c.extend_from_slice(&path[..min_pos]);
    c
}

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

    #[test]
    fn detects_a_directed_cycle() {
        let cyc = Adjacency::from_edges(3, &[(0, 1), (1, 2), (2, 0)]);
        assert!(has_cycle(&cyc));
        let dag = Adjacency::from_edges(3, &[(0, 1), (1, 2), (0, 2)]);
        assert!(!has_cycle(&dag));
    }

    #[test]
    fn topo_sort_orders_a_dag_and_rejects_a_cycle() {
        let dag = Adjacency::from_edges(4, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
        let order = topological_sort(&dag).expect("a DAG has a topo order");
        // 0 before 1,2,3; 3 last.
        let pos: std::collections::HashMap<usize, usize> = order.iter().enumerate().map(|(i, &v)| (v, i)).collect();
        assert!(pos[&0] < pos[&1] && pos[&0] < pos[&2]);
        assert!(pos[&1] < pos[&3] && pos[&2] < pos[&3]);
        let cyc = Adjacency::from_edges(3, &[(0, 1), (1, 2), (2, 0)]);
        assert!(topological_sort(&cyc).is_none(), "a cyclic graph has no topo order");
    }

    #[test]
    fn find_cycles_reports_each_cycle_once() {
        // Two overlapping cycles: 0→1→2→0 and 0→1→3→0.
        let g = Adjacency::from_edges(4, &[(0, 1), (1, 2), (2, 0), (1, 3), (3, 0)]);
        let cycles = find_cycles(&g, 100);
        assert_eq!(cycles.len(), 2, "two elementary cycles: {cycles:?}");
        // Each is canonicalised to start at 0 (its min node).
        for c in &cycles {
            assert_eq!(c[0], 0);
        }
    }

    #[test]
    fn no_cycles_in_a_dag() {
        let dag = Adjacency::from_edges(4, &[(0, 1), (0, 2), (1, 3), (2, 3)]);
        assert!(find_cycles(&dag, 100).is_empty());
    }
}