facett-graphview/src/analysis/cycles.rs
//! **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.
///
/// **Bounded work.** This is a plain simple-path DFS (no Johnson blocking), so the number
/// of paths it walks — not the number of cycles it finds — is exponential on a graph
/// with many paths and few short cycles. MEASURED 2026-10-02 (lane F): a generated
/// 120-node SBM (`sbm:120:1`, 3 out-edges per node) as a lineage graph never returned
/// from `GraphNav::state_json` (minutes, release), and froze the browser tab that
/// mounted it. The walk therefore stops after [`CYCLE_STEPS`] DFS steps in total and
/// returns what it found: the cycle browser is a sample of the cycles, which it already
/// was (`limit`), now bounded in time as well as in count.
#[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();
let mut steps = CYCLE_STEPS;
let mut on_path = vec![false; g.n];
for start in 0..g.n {
let mut path = Vec::new();
dfs_cycles(g, start, start, &mut on_path, &mut path, &mut out, &mut seen, limit, &mut steps);
if out.len() >= limit || steps == 0 {
break;
}
}
out
}
/// The DFS step budget of [`find_cycles`] (one step = one node entered).
pub const CYCLE_STEPS: usize = 200_000;
#[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,
steps: &mut usize,
) {
if out.len() >= limit || *steps == 0 {
return;
}
*steps -= 1;
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, steps);
}
}
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);
}
}
/// A graph with exponentially many simple paths and one long cycle: 30 layers of 4
/// nodes, every node wired to every node of the next layer (4^29 paths), and one
/// edge from the last layer back to node 0. The unbounded walk never returned on
/// shapes like this; the budget makes it return, and depth-first still finds the cycle.
#[test]
fn the_walk_is_bounded_on_a_graph_with_exponentially_many_paths() {
let (layers, w) = (30usize, 4usize);
let mut e = Vec::new();
for l in 0..layers - 1 {
for a in 0..w {
for b in 0..w {
e.push((l * w + a, (l + 1) * w + b));
}
}
}
e.push(((layers - 1) * w, 0));
let g = Adjacency::from_edges(layers * w, &e);
let t = std::time::Instant::now();
let c = find_cycles(&g, 64);
assert!(!c.is_empty(), "depth-first reaches the back edge");
assert!(t.elapsed().as_secs_f64() < 5.0, "bounded: {:?}", t.elapsed());
}
#[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());
}
}