xgraph 3.0.0

//! Topological ordering, written once against [`GraphView`].
//!
//! A topological order lists every node before all the nodes it points at, which exists
//! exactly when the graph is acyclic. Scheduling, dependency resolution and any
//! "what has to happen first" question rests on it, and the library had no such ordering.

use crate::core::view::{GraphView, NodeId};
use std::collections::{HashMap, VecDeque};

/// Why a topological order could not be produced.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum TopologicalError {
    /// The graph contains a cycle, so no ordering exists.
    ///
    /// The nodes reported are those left unordered — every one of them lies on, or
    /// downstream of, a cycle. That is what a caller needs in order to say *which*
    /// dependencies are circular.
    #[error("The graph has a cycle, so {} node(s) cannot be ordered", .unordered.len())]
    Cyclic {
        /// The nodes that could not be placed.
        unordered: Vec<NodeId>,
    },
    /// The graph is undirected, where a topological order is not defined.
    #[error("A topological order is only defined for a directed graph")]
    Undirected,
}

/// Topological ordering, available on every [`GraphView`].
pub trait TopologicalSort: GraphView {
    /// Orders the nodes so that every node precedes the nodes it points at.
    ///
    /// Uses Kahn's algorithm: repeatedly take a node nothing points at any more. Among
    /// those available, the lowest identifier is taken first, so the ordering is
    /// reproducible rather than dependent on hash iteration order.
    ///
    /// # Returns
    /// - `Ok(order)` listing every node exactly once.
    /// - `Err(TopologicalError::Cyclic)` naming the nodes that could not be placed.
    /// - `Err(TopologicalError::Undirected)` on an undirected graph.
    fn topological_order(&self) -> Result<Vec<NodeId>, TopologicalError> {
        if !self.is_directed() {
            return Err(TopologicalError::Undirected);
        }

        let mut incoming: HashMap<NodeId, usize> = self.node_ids().map(|node| (node, 0)).collect();
        for node in self.node_ids() {
            for link in self.links(node) {
                if let Some(count) = incoming.get_mut(&link.target) {
                    *count += 1;
                }
            }
        }

        // A BinaryHeap of Reverse would do the same; a sorted queue is enough here and
        // keeps the "lowest identifier first" rule obvious.
        let mut ready: Vec<NodeId> = incoming
            .iter()
            .filter(|(_, &count)| count == 0)
            .map(|(&node, _)| node)
            .collect();
        ready.sort_unstable();
        let mut ready: VecDeque<NodeId> = ready.into();

        let mut order = Vec::with_capacity(self.node_count());
        while let Some(node) = ready.pop_front() {
            order.push(node);

            let mut freed: Vec<NodeId> = Vec::new();
            for link in self.links(node) {
                if let Some(count) = incoming.get_mut(&link.target) {
                    *count -= 1;
                    if *count == 0 {
                        freed.push(link.target);
                    }
                }
            }
            freed.sort_unstable();
            // Merged in order so the queue stays sorted and the result stays stable.
            for node in freed {
                let position = ready.iter().position(|&queued| queued > node);
                match position {
                    Some(position) => ready.insert(position, node),
                    None => ready.push_back(node),
                }
            }
        }

        if order.len() != self.node_count() {
            let mut unordered: Vec<NodeId> = incoming
                .into_iter()
                .filter(|(_, count)| *count > 0)
                .map(|(node, _)| node)
                .collect();
            unordered.sort_unstable();
            return Err(TopologicalError::Cyclic { unordered });
        }
        Ok(order)
    }

    /// Whether the graph is a directed acyclic graph.
    ///
    /// An undirected graph is never a DAG, whatever its shape.
    fn is_dag(&self) -> bool {
        self.is_directed() && self.topological_order().is_ok()
    }
}

impl<G: GraphView + ?Sized> TopologicalSort for G {}

#[cfg(test)]
#[cfg(feature = "graph")]
mod tests {
    use super::*;
    use crate::graph::Graph;

    #[test]
    fn test_a_chain_orders_from_its_head() {
        let mut graph = Graph::<u32, u32, ()>::new(true);
        let nodes: Vec<_> = (0..4).map(|i| graph.add_node(i)).collect();
        for pair in nodes.windows(2) {
            graph.add_edge(pair[0], pair[1], 1, ()).unwrap();
        }

        assert_eq!(graph.topological_order().unwrap(), nodes);
        assert!(graph.is_dag());
    }

    /// The order must respect every edge, not merely exist.
    #[test]
    fn test_every_edge_points_forward_in_the_order() {
        let mut graph = Graph::<u32, u32, ()>::new(true);
        let nodes: Vec<_> = (0..6).map(|i| graph.add_node(i)).collect();
        for &(from, to) in &[(0, 2), (1, 2), (2, 3), (2, 4), (3, 5), (4, 5)] {
            graph.add_edge(nodes[from], nodes[to], 1, ()).unwrap();
        }

        let order = graph.topological_order().unwrap();
        let position: std::collections::HashMap<_, _> =
            order.iter().enumerate().map(|(i, &n)| (n, i)).collect();
        for node in graph.node_ids() {
            for link in graph.links(node) {
                assert!(
                    position[&node] < position[&link.target],
                    "{:?} should precede {:?}",
                    node,
                    link.target
                );
            }
        }
    }

    #[test]
    fn test_a_cycle_names_the_nodes_it_traps() {
        let mut graph = Graph::<u32, u32, ()>::new(true);
        let nodes: Vec<_> = (0..4).map(|i| graph.add_node(i)).collect();
        graph.add_edge(nodes[0], nodes[1], 1, ()).unwrap();
        // A cycle among the last three.
        graph.add_edge(nodes[1], nodes[2], 1, ()).unwrap();
        graph.add_edge(nodes[2], nodes[3], 1, ()).unwrap();
        graph.add_edge(nodes[3], nodes[1], 1, ()).unwrap();

        match graph.topological_order() {
            Err(TopologicalError::Cyclic { unordered }) => {
                assert_eq!(unordered, vec![nodes[1], nodes[2], nodes[3]]);
            }
            other => panic!("expected a cyclic error, got {:?}", other),
        }
        assert!(!graph.is_dag());
    }

    #[test]
    fn test_an_undirected_graph_has_no_topological_order() {
        let mut graph = Graph::<u32, u32, ()>::new(false);
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        graph.add_edge(a, b, 1, ()).unwrap();

        assert_eq!(graph.topological_order(), Err(TopologicalError::Undirected));
        assert!(!graph.is_dag());
    }

    #[test]
    fn test_the_order_is_reproducible() {
        let mut graph = Graph::<u32, u32, ()>::new(true);
        let nodes: Vec<_> = (0..8).map(|i| graph.add_node(i)).collect();
        for &(from, to) in &[(0, 3), (1, 3), (2, 4), (3, 5), (4, 5), (5, 6)] {
            graph.add_edge(nodes[from], nodes[to], 1, ()).unwrap();
        }

        let first = graph.topological_order().unwrap();
        for _ in 0..5 {
            assert_eq!(graph.topological_order().unwrap(), first);
        }
    }

    #[test]
    fn test_isolated_nodes_are_still_ordered() {
        let mut graph = Graph::<u32, u32, ()>::new(true);
        let nodes: Vec<_> = (0..3).map(|i| graph.add_node(i)).collect();

        assert_eq!(graph.topological_order().unwrap(), nodes);
    }

    #[test]
    fn test_a_self_loop_is_a_cycle() {
        let mut graph = Graph::<u32, u32, ()>::new(true);
        let a = graph.add_node(0);
        graph.add_edge(a, a, 1, ()).unwrap();

        assert!(matches!(
            graph.topological_order(),
            Err(TopologicalError::Cyclic { .. })
        ));
    }
}