stable_toposort 0.1.1

//! Condensation (DAG of SCCs) and topological sort of strongly connected components.

use std::collections::HashSet;

use crate::scc;
use crate::stable_toposort;

/// The condensation of a directed graph: one node per SCC, edges between components.
///
/// The condensation is always a DAG. Node indices refer to `components`: edge `(i, j)`
/// means there is at least one edge from some node in `components[i]` to some node in
/// `components[j]`.
#[derive(Debug, Clone)]
pub struct Condensation<N> {
    /// The strongly connected components; index `i` corresponds to component `i`.
    pub components: Vec<Vec<N>>,
    /// Edges between components as pairs of component indices `(from, to)`.
    pub edges: Vec<(usize, usize)>,
}

/// Builds the condensation of the graph (DAG of strongly connected components).
///
/// Each element of `components` is a strongly connected component. The `edges` list
/// contains pairs of component indices: `(i, j)` means there exists an edge from some
/// node in `components[i]` to some node in `components[j]`. The order of components
/// and of nodes within a component is unspecified; use [`condensation_by_key`] for
/// a deterministic order.
///
/// # Examples
///
/// ```rust
/// use stable_toposort::condensation;
///
/// let nodes = [1, 2, 3];
/// let edges = [(1, 2), (2, 3)];
/// let cond = condensation(nodes, edges);
/// assert_eq!(cond.components.len(), 3);
/// assert_eq!(cond.edges.len(), 2);
/// ```
pub fn condensation<N>(
    nodes: impl IntoIterator<Item = N>,
    edges: impl IntoIterator<Item = (N, N)>,
) -> Condensation<N>
where
    N: Eq + std::hash::Hash + Clone,
{
    let nodes: Vec<N> = nodes.into_iter().collect();
    let edges: Vec<(N, N)> = edges.into_iter().collect();

    let components = scc(nodes.clone(), edges.iter().cloned());
    let comp_of: std::collections::HashMap<N, usize> = components
        .iter()
        .enumerate()
        .flat_map(|(i, c)| c.iter().map(move |n| (n.clone(), i)))
        .collect();

    let mut edge_set: HashSet<(usize, usize)> = HashSet::new();
    for (a, b) in &edges {
        if let (Some(&i), Some(&j)) = (comp_of.get(a), comp_of.get(b)) {
            if i != j {
                edge_set.insert((i, j));
            }
        }
    }
    let edges = edge_set.into_iter().collect();

    Condensation { components, edges }
}

/// Builds the condensation with components and nodes within each component ordered by `key`.
///
/// Same as [`condensation`], but the order of components and the order of nodes within
/// each component are determined by sorting with `key`.
pub fn condensation_by_key<N, K>(
    nodes: impl IntoIterator<Item = N>,
    edges: impl IntoIterator<Item = (N, N)>,
    key: impl Fn(&N) -> K,
) -> Condensation<N>
where
    N: Eq + std::hash::Hash + Clone,
    K: Ord,
{
    let mut cond = condensation(nodes, edges);
    for comp in &mut cond.components {
        comp.sort_by_key(&key);
    }
    cond
}

/// Returns strongly connected components in topological order.
///
/// Computes the condensation (DAG of SCCs) and then topologically sorts it. The result
/// is a vector of components (each a `Vec<N>`), in an order such that all edges between
/// components go from an earlier component to a later one. The order of nodes within
/// each component is unspecified; use [`stable_toposort_scc_by_key`] to fix it.
///
/// The graph's condensation is always a DAG, so this never returns an error.
///
/// # Examples
///
/// ```rust
/// use stable_toposort::stable_toposort_scc;
///
/// let nodes = ["a", "b", "c"];
/// let edges = [("a", "b"), ("b", "c")];
/// let sccs = stable_toposort_scc(nodes, edges);
/// assert_eq!(sccs.len(), 3);
/// ```
pub fn stable_toposort_scc<N>(
    nodes: impl IntoIterator<Item = N>,
    edges: impl IntoIterator<Item = (N, N)>,
) -> Vec<Vec<N>>
where
    N: Eq + std::hash::Hash + Clone,
{
    let cond = condensation(nodes, edges);
    let order = stable_toposort(
        0..cond.components.len(),
        cond.edges.iter().copied(),
    )
    .expect("condensation is a DAG");
    order
        .into_iter()
        .map(|i| cond.components[i].clone())
        .collect()
}

/// Returns strongly connected components in topological order, with nodes ordered by `key`.
///
/// Same as [`stable_toposort_scc`], but nodes within each component are sorted by
/// `key`, giving a fully deterministic result.
///
/// # Examples
///
/// ```rust
/// use stable_toposort::stable_toposort_scc_by_key;
///
/// let nodes = ["C", "A", "B"];
/// let edges = [("A", "B"), ("B", "C")];
/// let sccs = stable_toposort_scc_by_key(nodes, edges, |n| *n);
/// assert_eq!(sccs, vec![vec!["A"], vec!["B"], vec!["C"]]);
/// ```
pub fn stable_toposort_scc_by_key<N, K>(
    nodes: impl IntoIterator<Item = N>,
    edges: impl IntoIterator<Item = (N, N)>,
    key: impl Fn(&N) -> K,
) -> Vec<Vec<N>>
where
    N: Eq + std::hash::Hash + Clone,
    K: Ord,
{
    let mut sccs = stable_toposort_scc(nodes, edges);
    for comp in &mut sccs {
        comp.sort_by_key(&key);
    }
    sccs
}

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

    #[test]
    fn dag_components_singleton() {
        let cond = condensation([1, 2], [(1, 2)]);
        assert_eq!(cond.components.len(), 2);
        assert_eq!(cond.edges.len(), 1);
    }

    #[test]
    fn by_key_sorts_components() {
        let nodes = ["B", "A", "C"];
        let edges = [("A", "B"), ("B", "C"), ("C", "A")];
        let cond = condensation_by_key(nodes, edges, |n| *n);
        assert_eq!(cond.components.len(), 1);
        assert_eq!(&cond.components[0], &["A", "B", "C"]);
    }

    #[test]
    fn stable_toposort_scc_by_key_orders_within_components() {
        let nodes: [&str; 3] = ["C", "A", "B"];
        let edges = [("A", "B"), ("B", "C")];
        let sccs = super::stable_toposort_scc_by_key(nodes, edges, |n: &&str| *n);
        assert_eq!(sccs.len(), 3);
        assert_eq!(sccs[0], ["A"]);
        assert_eq!(sccs[1], ["B"]);
        assert_eq!(sccs[2], ["C"]);
    }
}