dsa64 0.1.3

//! # Directed Acyclic Graph
//!
//! A directed acyclic graph (DAG) generic over the node key type `K`.
//!
//! Forward and reverse adjacency relationships are maintained in parallel
//! `HashMap<K, HashSet<K>>` maps, providing amortised O(1) lookup of nodes,
//! edges, direct dependents, and direct dependencies.
//!
//! # Edge direction
//!
//! An edge `A -> B` means that `B` depends on `A`. Consequently:
//!
//! - `dependents(A)` returns the nodes that directly depend on `A`.
//! - `dependencies(A)` returns the nodes that `A` directly depends on.
//! - `transitive_dependents(A)` returns all nodes that directly or indirectly
//!   depend on `A`.
//! - `transitive_dependencies(A)` returns all nodes that `A` directly or
//!   indirectly depends on.
//!
//! # Cycle prevention
//!
//! `add_edge` preserves the acyclic invariant by checking whether the source
//! node is already reachable from the target before inserting an edge. If it
//! is reachable, adding the edge would create a cycle and `CycleError` is
//! returned. Self-loops are rejected directly.
//!
//! Reachability and transitive queries use breadth-first traversal.
//!
//! # Ordering
//!
//! `topological_order` and `topological_order_from` return nodes in an order
//! in which every node follows all of its dependencies. Ties between nodes
//! that are ready at the same time are broken by key order, so the result is
//! the same on every call for the same graph. This makes the order suitable
//! for replay and for any caller that must produce identical results from
//! identical inputs. The other query methods return sets or iterate the
//! underlying maps, which carry no order.

use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque};
use std::fmt;
use std::hash::Hash;

/// Error returned when adding an edge would introduce a cycle.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CycleError;

impl fmt::Display for CycleError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("edge would create a cycle")
    }
}

impl std::error::Error for CycleError {}

/// A directed acyclic graph with forward and reverse adjacency indexes.
///
/// An edge `A -> B` indicates that `B` depends on `A`. Forward adjacency
/// therefore stores dependents, while reverse adjacency stores dependencies.
///
/// Both adjacency maps contain every node in the graph, including nodes with
/// no incoming or outgoing edges. The maps are updated together to preserve
/// this invariant.
///
/// Direct node and edge lookups are amortised O(1). Adding an edge may require
/// traversing the graph to verify that the new edge would not introduce a
/// cycle. Transitive queries are linear in the portion of the graph traversed.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Dag<K: Hash + Eq + Clone> {
    /// Maps each node to its direct dependents.
    forward: HashMap<K, HashSet<K>>,

    /// Maps each node to its direct dependencies.
    reverse: HashMap<K, HashSet<K>>,

    /// Number of directed edges currently stored in the graph.
    edge_count: usize,
}

impl<K: Hash + Eq + Clone> Dag<K> {
    /// Creates an empty DAG.
    #[inline]
    pub fn new() -> Self {
        Self {
            forward: HashMap::new(),
            reverse: HashMap::new(),
            edge_count: 0,
        }
    }

    /// Returns the number of nodes in the graph.
    #[inline]
    pub fn node_count(&self) -> usize {
        self.forward.len()
    }

    /// Returns the number of directed edges in the graph.
    #[inline]
    pub fn edge_count(&self) -> usize {
        self.edge_count
    }

    /// Returns `true` if the graph contains no nodes.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.forward.is_empty()
    }

    /// Returns `true` if the graph contains `key`.
    #[inline]
    pub fn contains_node(&self, key: &K) -> bool {
        self.forward.contains_key(key)
    }

    /// Returns `true` if the graph contains the directed edge `from -> to`.
    #[inline]
    pub fn contains_edge(&self, from: &K, to: &K) -> bool {
        self.forward.get(from).is_some_and(|s| s.contains(to))
    }

    /// Iterates over every node in the graph, in no particular order.
    #[inline]
    pub fn nodes(&self) -> impl Iterator<Item = &K> {
        self.forward.keys()
    }

    /// Iterates over every directed edge as a `(from, to)` pair, in no
    /// particular order.
    pub fn edges(&self) -> impl Iterator<Item = (&K, &K)> {
        self.forward
            .iter()
            .flat_map(|(from, tos)| tos.iter().map(move |to| (from, to)))
    }

    /// Returns the nodes with no dependencies, in no particular order.
    ///
    /// These are the entry points of the graph. An isolated node is both a
    /// source and a sink.
    pub fn sources(&self) -> Vec<&K> {
        self.reverse
            .iter()
            .filter(|(_, deps)| deps.is_empty())
            .map(|(k, _)| k)
            .collect()
    }

    /// Returns the nodes with no dependents, in no particular order.
    ///
    /// These are the terminal points of the graph. An isolated node is both a
    /// source and a sink.
    pub fn sinks(&self) -> Vec<&K> {
        self.forward
            .iter()
            .filter(|(_, deps)| deps.is_empty())
            .map(|(k, _)| k)
            .collect()
    }

    /// Inserts a node into the graph.
    ///
    /// Returns `true` if the node was inserted, or `false` if it was already
    /// present.
    #[inline]
    pub fn insert_node(&mut self, key: K) -> bool {
        if self.forward.contains_key(&key) {
            return false;
        }

        self.forward.insert(key.clone(), HashSet::new());
        self.reverse.insert(key, HashSet::new());
        true
    }

    /// Adds the directed edge `from -> to`.
    ///
    /// An edge `from -> to` indicates that `to` depends on `from`. Missing
    /// endpoint nodes are inserted automatically.
    ///
    /// Returns `Ok(true)` if the edge was inserted or `Ok(false)` if the edge
    /// already exists.
    ///
    /// # Errors
    ///
    /// Returns [`CycleError`] if the edge would introduce a cycle. Self-loops
    /// are considered cycles and are rejected.
    pub fn add_edge(&mut self, from: K, to: K) -> Result<bool, CycleError> {
        if from == to {
            return Err(CycleError);
        }

        if self.contains_edge(&from, &to) {
            return Ok(false);
        }

        // Adding `from -> to` creates a cycle exactly when `from` is already
        // reachable from `to`.
        if self.is_reachable(&to, &from) {
            return Err(CycleError);
        }

        self.insert_node(from.clone());
        self.insert_node(to.clone());

        self.forward.get_mut(&from).unwrap().insert(to.clone());
        self.reverse.get_mut(&to).unwrap().insert(from);
        self.edge_count += 1;

        Ok(true)
    }

    /// Removes a node and every edge incident to it.
    ///
    /// Returns `true` if the node existed, or `false` if it was not present.
    pub fn remove_node(&mut self, key: &K) -> bool {
        let Some(dependents) = self.forward.remove(key) else {
            return false;
        };

        // Remove each outgoing edge `key -> dependent` from the corresponding
        // reverse adjacency set.
        self.edge_count -= dependents.len();
        for dep in &dependents {
            if let Some(rev) = self.reverse.get_mut(dep) {
                rev.remove(key);
            }
        }

        // Remove each incoming edge `dependency -> key` from the corresponding
        // forward adjacency set.
        if let Some(dependencies) = self.reverse.remove(key) {
            self.edge_count -= dependencies.len();
            for dep in &dependencies {
                if let Some(fwd) = self.forward.get_mut(dep) {
                    fwd.remove(key);
                }
            }
        }

        true
    }

    /// Removes the directed edge `from -> to`.
    ///
    /// Returns `true` if the edge existed, or `false` otherwise. Nodes are
    /// retained even if removing the edge leaves them isolated.
    #[inline]
    pub fn remove_edge(&mut self, from: &K, to: &K) -> bool {
        let removed = self
            .forward
            .get_mut(from)
            .is_some_and(|s| s.remove(to));

        if removed {
            self.reverse.get_mut(to).unwrap().remove(from);
            self.edge_count -= 1;
        }

        removed
    }

    /// Returns the direct dependents of `key`.
    ///
    /// These are the nodes `D` for which an edge `key -> D` exists. Returns
    /// `None` if `key` is not present in the graph.
    #[inline]
    pub fn dependents(&self, key: &K) -> Option<&HashSet<K>> {
        self.forward.get(key)
    }

    /// Returns the direct dependencies of `key`.
    ///
    /// These are the nodes `D` for which an edge `D -> key` exists. Returns
    /// `None` if `key` is not present in the graph.
    #[inline]
    pub fn dependencies(&self, key: &K) -> Option<&HashSet<K>> {
        self.reverse.get(key)
    }

    /// Returns all direct and indirect dependents of `key`.
    ///
    /// The starting node is not included. An empty set is returned if `key`
    /// does not exist or has no dependents.
    pub fn transitive_dependents(&self, key: &K) -> HashSet<K> {
        self.walk(&self.forward, key)
    }

    /// Returns all direct and indirect dependencies of `key`.
    ///
    /// The starting node is not included. An empty set is returned if `key`
    /// does not exist or has no dependencies.
    pub fn transitive_dependencies(&self, key: &K) -> HashSet<K> {
        self.walk(&self.reverse, key)
    }

    /// Returns every node in an order where each node follows all of its
    /// dependencies.
    ///
    /// Nodes that become ready at the same time are emitted in ascending key
    /// order, so the result is identical on every call for the same graph.
    /// An empty graph returns an empty vector.
    pub fn topological_order(&self) -> Vec<K>
    where
        K: Ord,
    {
        let in_degree: HashMap<&K, usize> = self
            .reverse
            .iter()
            .map(|(k, deps)| (k, deps.len()))
            .collect();
        self.kahn(in_degree, None)
    }

    /// Returns `starts` and every node that directly or indirectly depends on
    /// any of them, in an order where each node follows all of its
    /// dependencies within that set.
    ///
    /// This is the set to recompute when the nodes in `starts` change. A
    /// dependency outside the set is treated as already satisfied. Nodes in
    /// `starts` that are not in the graph are ignored, and a `starts` that
    /// names no graph node returns an empty vector. Ties are broken by
    /// ascending key order, as for [`Dag::topological_order`].
    pub fn topological_order_from(&self, starts: &[K]) -> Vec<K>
    where
        K: Ord,
    {
        let mut affected: HashSet<&K> = HashSet::new();
        for start in starts {
            if let Some((key, _)) = self.forward.get_key_value(start) {
                affected.insert(key);
                for dep in self.transitive_dependents(start) {
                    let (key, _) = self.forward.get_key_value(&dep).unwrap();
                    affected.insert(key);
                }
            }
        }

        // In-degree counts only the edges that stay inside the affected set.
        let in_degree: HashMap<&K, usize> = affected
            .iter()
            .map(|&k| {
                let inside = self.reverse[k]
                    .iter()
                    .filter(|dep| affected.contains(dep))
                    .count();
                (k, inside)
            })
            .collect();
        self.kahn(in_degree, Some(&affected))
    }

    /// Kahn's algorithm over the forward index with a min-heap on the ready
    /// set, so ties resolve in ascending key order.
    ///
    /// `in_degree` holds every node to order, with its count of incoming
    /// edges from within the same set. `within` restricts the walk to that
    /// set when it is a subgraph, and `None` means the whole graph.
    fn kahn(&self, mut in_degree: HashMap<&K, usize>, within: Option<&HashSet<&K>>) -> Vec<K>
    where
        K: Ord,
    {
        let mut ready: BinaryHeap<Reverse<&K>> = in_degree
            .iter()
            .filter(|(_, degree)| **degree == 0)
            .map(|(&k, _)| Reverse(k))
            .collect();
        let mut order = Vec::with_capacity(in_degree.len());

        while let Some(Reverse(current)) = ready.pop() {
            order.push(current.clone());
            for dependent in &self.forward[current] {
                if within.is_some_and(|set| !set.contains(dependent)) {
                    continue;
                }
                let degree = in_degree.get_mut(dependent).unwrap();
                *degree -= 1;
                if *degree == 0 {
                    ready.push(Reverse(dependent));
                }
            }
        }

        order
    }

    /// Traverses an adjacency map breadth-first and returns all nodes reachable
    /// from `start`.
    ///
    /// `start` itself is not included in the returned set.
    fn walk(&self, adj: &HashMap<K, HashSet<K>>, start: &K) -> HashSet<K> {
        let mut result = HashSet::new();
        let mut queue = VecDeque::new();

        if let Some(neighbours) = adj.get(start) {
            for n in neighbours {
                if result.insert(n.clone()) {
                    queue.push_back(n);
                }
            }
        }

        while let Some(current) = queue.pop_front() {
            if let Some(neighbours) = adj.get(current) {
                for n in neighbours {
                    if result.insert(n.clone()) {
                        queue.push_back(n);
                    }
                }
            }
        }

        result
    }

    /// Returns `true` if `target` is reachable from `start` by following
    /// forward edges, meaning `target` directly or indirectly depends on
    /// `start`.
    ///
    /// A node does not reach itself. Either key being absent from the graph
    /// returns `false`. The traversal stores references to node keys rather
    /// than cloning them.
    pub fn is_reachable(&self, start: &K, target: &K) -> bool {
        let Some(neighbours) = self.forward.get(start) else {
            return false;
        };

        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();

        for n in neighbours {
            if n == target {
                return true;
            }

            if visited.insert(n) {
                queue.push_back(n);
            }
        }

        while let Some(current) = queue.pop_front() {
            if let Some(next) = self.forward.get(current) {
                for n in next {
                    if n == target {
                        return true;
                    }

                    if visited.insert(n) {
                        queue.push_back(n);
                    }
                }
            }
        }

        false
    }
}

impl<K: Hash + Eq + Clone> Default for Dag<K> {
    fn default() -> Self {
        Self::new()
    }
}

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

    #[test]
    fn empty_graph() {
        let dag = Dag::<u32>::new();
        assert!(dag.is_empty());
        assert_eq!(dag.node_count(), 0);
        assert_eq!(dag.edge_count(), 0);
        assert!(!dag.contains_node(&1));
        assert!(!dag.contains_edge(&1, &2));
    }

    #[test]
    fn insert_node() {
        let mut dag = Dag::new();
        assert!(dag.insert_node(1));
        assert!(!dag.insert_node(1));
        assert_eq!(dag.node_count(), 1);
        assert!(dag.contains_node(&1));
        assert!(!dag.contains_node(&2));
    }

    #[test]
    fn add_edge() {
        let mut dag = Dag::new();
        assert_eq!(dag.add_edge(1, 2), Ok(true));
        assert_eq!(dag.add_edge(1, 2), Ok(false));
        assert_eq!(dag.node_count(), 2);
        assert_eq!(dag.edge_count(), 1);
        assert!(dag.contains_edge(&1, &2));
        assert!(!dag.contains_edge(&2, &1));
    }

    #[test]
    fn add_edge_auto_inserts_nodes() {
        let mut dag = Dag::new();
        dag.add_edge(10, 20).unwrap();
        assert!(dag.contains_node(&10));
        assert!(dag.contains_node(&20));
    }

    #[test]
    fn self_loop_rejected() {
        let mut dag = Dag::new();
        assert_eq!(dag.add_edge(1, 1), Err(CycleError));
        assert_eq!(dag.edge_count(), 0);
    }

    #[test]
    fn direct_cycle_rejected() {
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        assert_eq!(dag.add_edge(2, 1), Err(CycleError));
        assert_eq!(dag.edge_count(), 1);
    }

    #[test]
    fn transitive_cycle_rejected() {
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(2, 3).unwrap();
        dag.add_edge(3, 4).unwrap();
        assert_eq!(dag.add_edge(4, 1), Err(CycleError));
        assert_eq!(dag.add_edge(4, 2), Err(CycleError));
        assert_eq!(dag.edge_count(), 3);
    }

    #[test]
    fn diamond_is_valid() {
        //   1
        //  / \
        // 2   3
        //  \ /
        //   4
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(1, 3).unwrap();
        dag.add_edge(2, 4).unwrap();
        dag.add_edge(3, 4).unwrap();
        assert_eq!(dag.node_count(), 4);
        assert_eq!(dag.edge_count(), 4);

        // Closing the diamond into a cycle is rejected.
        assert_eq!(dag.add_edge(4, 1), Err(CycleError));
    }

    #[test]
    fn remove_node() {
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(2, 3).unwrap();
        dag.add_edge(1, 3).unwrap();

        assert!(dag.remove_node(&2));
        assert!(!dag.contains_node(&2));
        assert_eq!(dag.node_count(), 2);
        assert_eq!(dag.edge_count(), 1);
        assert!(dag.contains_edge(&1, &3));
        assert!(!dag.contains_edge(&1, &2));
        assert!(!dag.contains_edge(&2, &3));
    }

    #[test]
    fn remove_node_nonexistent() {
        let mut dag = Dag::<u32>::new();
        assert!(!dag.remove_node(&99));
    }

    #[test]
    fn remove_edge() {
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(2, 3).unwrap();

        assert!(dag.remove_edge(&1, &2));
        assert!(!dag.contains_edge(&1, &2));
        assert_eq!(dag.edge_count(), 1);
        assert!(dag.contains_node(&1));
        assert!(dag.contains_node(&2));
    }

    #[test]
    fn remove_edge_nonexistent() {
        let mut dag = Dag::<u32>::new();
        assert!(!dag.remove_edge(&1, &2));
    }

    #[test]
    fn remove_edge_enables_previously_cyclic_edge() {
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(2, 3).unwrap();

        // 3 -> 1 would create a cycle through 1 -> 2 -> 3 -> 1.
        assert_eq!(dag.add_edge(3, 1), Err(CycleError));

        // Removing 1 -> 2 breaks the path, so 3 -> 1 is now valid.
        dag.remove_edge(&1, &2);
        assert_eq!(dag.add_edge(3, 1), Ok(true));
    }

    #[test]
    fn direct_dependents() {
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(1, 3).unwrap();

        let deps = dag.dependents(&1).unwrap();
        assert_eq!(deps.len(), 2);
        assert!(deps.contains(&2));
        assert!(deps.contains(&3));
    }

    #[test]
    fn direct_dependencies() {
        let mut dag = Dag::new();
        dag.add_edge(1, 3).unwrap();
        dag.add_edge(2, 3).unwrap();

        let deps = dag.dependencies(&3).unwrap();
        assert_eq!(deps.len(), 2);
        assert!(deps.contains(&1));
        assert!(deps.contains(&2));
    }

    #[test]
    fn dependents_of_unknown_node() {
        let dag = Dag::<u32>::new();
        assert!(dag.dependents(&1).is_none());
    }

    #[test]
    fn dependencies_of_unknown_node() {
        let dag = Dag::<u32>::new();
        assert!(dag.dependencies(&1).is_none());
    }

    #[test]
    fn dependents_of_leaf_node() {
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        let deps = dag.dependents(&2).unwrap();
        assert!(deps.is_empty());
    }

    #[test]
    fn transitive_dependents_chain() {
        // 1 -> 2 -> 3 -> 4
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(2, 3).unwrap();
        dag.add_edge(3, 4).unwrap();

        let td = dag.transitive_dependents(&1);
        assert_eq!(td, HashSet::from([2, 3, 4]));
    }

    #[test]
    fn transitive_dependencies_chain() {
        // 1 -> 2 -> 3 -> 4
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(2, 3).unwrap();
        dag.add_edge(3, 4).unwrap();

        let td = dag.transitive_dependencies(&4);
        assert_eq!(td, HashSet::from([1, 2, 3]));
    }

    #[test]
    fn transitive_dependents_diamond() {
        //   1
        //  / \
        // 2   3
        //  \ /
        //   4
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(1, 3).unwrap();
        dag.add_edge(2, 4).unwrap();
        dag.add_edge(3, 4).unwrap();

        let td = dag.transitive_dependents(&1);
        assert_eq!(td, HashSet::from([2, 3, 4]));

        let td2 = dag.transitive_dependents(&2);
        assert_eq!(td2, HashSet::from([4]));
    }

    #[test]
    fn transitive_dependencies_diamond() {
        //   1
        //  / \
        // 2   3
        //  \ /
        //   4
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(1, 3).unwrap();
        dag.add_edge(2, 4).unwrap();
        dag.add_edge(3, 4).unwrap();

        let td = dag.transitive_dependencies(&4);
        assert_eq!(td, HashSet::from([1, 2, 3]));

        let td2 = dag.transitive_dependencies(&2);
        assert_eq!(td2, HashSet::from([1]));
    }

    #[test]
    fn transitive_queries_on_empty_graph() {
        let dag = Dag::<u32>::new();
        assert!(dag.transitive_dependents(&1).is_empty());
        assert!(dag.transitive_dependencies(&1).is_empty());
    }

    #[test]
    fn transitive_queries_on_isolated_node() {
        let mut dag = Dag::new();
        dag.insert_node(1);
        assert!(dag.transitive_dependents(&1).is_empty());
        assert!(dag.transitive_dependencies(&1).is_empty());
    }

    #[test]
    fn string_keys() {
        let mut dag = Dag::new();
        dag.add_edge("a".to_string(), "b".to_string()).unwrap();
        dag.add_edge("b".to_string(), "c".to_string()).unwrap();

        assert!(dag.contains_edge(&"a".to_string(), &"b".to_string()));
        let td = dag.transitive_dependents(&"a".to_string());
        assert_eq!(td.len(), 2);
        assert!(td.contains("b"));
        assert!(td.contains("c"));
    }

    #[test]
    fn wide_fan_out() {
        let mut dag = Dag::new();
        for i in 1..=100 {
            dag.add_edge(0u32, i).unwrap();
        }
        assert_eq!(dag.node_count(), 101);
        assert_eq!(dag.edge_count(), 100);

        let deps = dag.dependents(&0).unwrap();
        assert_eq!(deps.len(), 100);

        let td = dag.transitive_dependents(&0);
        assert_eq!(td.len(), 100);
    }

    #[test]
    fn wide_fan_in() {
        let mut dag = Dag::new();
        for i in 1..=100 {
            dag.add_edge(i, 0u32).unwrap();
        }

        let deps = dag.dependencies(&0).unwrap();
        assert_eq!(deps.len(), 100);

        let td = dag.transitive_dependencies(&0);
        assert_eq!(td.len(), 100);
    }

    #[test]
    fn default_is_empty() {
        let dag: Dag<u32> = Dag::default();
        assert!(dag.is_empty());
    }

    #[test]
    fn cycle_error_display() {
        assert_eq!(CycleError.to_string(), "edge would create a cycle");
    }

    #[test]
    fn nodes_and_edges() {
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(1, 3).unwrap();
        dag.insert_node(4);

        let mut nodes: Vec<u32> = dag.nodes().copied().collect();
        nodes.sort();
        assert_eq!(nodes, vec![1, 2, 3, 4]);

        let mut edges: Vec<(u32, u32)> = dag.edges().map(|(a, b)| (*a, *b)).collect();
        edges.sort();
        assert_eq!(edges, vec![(1, 2), (1, 3)]);
    }

    #[test]
    fn sources_and_sinks() {
        //   1
        //  / \
        // 2   3
        //  \ /
        //   4      5 (isolated)
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(1, 3).unwrap();
        dag.add_edge(2, 4).unwrap();
        dag.add_edge(3, 4).unwrap();
        dag.insert_node(5);

        let mut sources: Vec<u32> = dag.sources().into_iter().copied().collect();
        sources.sort();
        assert_eq!(sources, vec![1, 5]);

        let mut sinks: Vec<u32> = dag.sinks().into_iter().copied().collect();
        sinks.sort();
        assert_eq!(sinks, vec![4, 5]);
    }

    #[test]
    fn sources_and_sinks_of_empty_graph() {
        let dag = Dag::<u32>::new();
        assert!(dag.sources().is_empty());
        assert!(dag.sinks().is_empty());
    }

    #[test]
    fn reachability() {
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(2, 3).unwrap();

        assert!(dag.is_reachable(&1, &3));
        assert!(dag.is_reachable(&1, &2));
        assert!(!dag.is_reachable(&3, &1));
        assert!(!dag.is_reachable(&1, &1));
        assert!(!dag.is_reachable(&1, &99));
        assert!(!dag.is_reachable(&99, &1));
    }

    #[test]
    fn topological_order_chain() {
        let mut dag = Dag::new();
        dag.add_edge(3, 2).unwrap();
        dag.add_edge(2, 1).unwrap();
        assert_eq!(dag.topological_order(), vec![3, 2, 1]);
    }

    #[test]
    fn topological_order_diamond_breaks_ties_by_key() {
        //   1
        //  / \
        // 3   2
        //  \ /
        //   4
        let mut dag = Dag::new();
        dag.add_edge(1, 3).unwrap();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(3, 4).unwrap();
        dag.add_edge(2, 4).unwrap();
        assert_eq!(dag.topological_order(), vec![1, 2, 3, 4]);
    }

    #[test]
    fn topological_order_is_stable_across_calls() {
        let mut dag = Dag::new();
        for i in (1..=200u32).rev() {
            dag.add_edge(0, i).unwrap();
        }
        let expected: Vec<u32> = (0..=200).collect();
        assert_eq!(dag.topological_order(), expected);
        assert_eq!(dag.topological_order(), expected);
    }

    #[test]
    fn topological_order_places_isolated_nodes_by_key() {
        let mut dag = Dag::new();
        dag.add_edge(2, 3).unwrap();
        dag.insert_node(1);
        assert_eq!(dag.topological_order(), vec![1, 2, 3]);
    }

    #[test]
    fn topological_order_of_empty_graph() {
        assert!(Dag::<u32>::new().topological_order().is_empty());
    }

    #[test]
    fn topological_order_from_includes_start_and_dependents_only() {
        //   1
        //  / \
        // 2   3
        //  \ /
        //   4 -> 5
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        dag.add_edge(1, 3).unwrap();
        dag.add_edge(2, 4).unwrap();
        dag.add_edge(3, 4).unwrap();
        dag.add_edge(4, 5).unwrap();

        assert_eq!(dag.topological_order_from(&[2]), vec![2, 4, 5]);
        assert_eq!(dag.topological_order_from(&[2, 3]), vec![2, 3, 4, 5]);
        assert_eq!(dag.topological_order_from(&[1]), vec![1, 2, 3, 4, 5]);
        assert_eq!(dag.topological_order_from(&[5]), vec![5]);
    }

    #[test]
    fn topological_order_from_treats_outside_dependencies_as_satisfied() {
        // 1 -> 3 and 2 -> 3. Starting from 2 alone, 3 must still be emitted
        // even though its other dependency, 1, is outside the set.
        let mut dag = Dag::new();
        dag.add_edge(1, 3).unwrap();
        dag.add_edge(2, 3).unwrap();
        assert_eq!(dag.topological_order_from(&[2]), vec![2, 3]);
    }

    #[test]
    fn topological_order_from_unknown_start() {
        let mut dag = Dag::new();
        dag.add_edge(1, 2).unwrap();
        assert!(dag.topological_order_from(&[99]).is_empty());
        assert_eq!(dag.topological_order_from(&[99, 1]), vec![1, 2]);
    }

    #[test]
    fn equality() {
        let mut a = Dag::new();
        a.add_edge(1, 2).unwrap();
        a.add_edge(2, 3).unwrap();

        let mut b = Dag::new();
        b.add_edge(2, 3).unwrap();
        b.add_edge(1, 2).unwrap();

        assert_eq!(a, b);
    }
}