xgraph 3.0.0

//! Notifications about changes to a graph.
//!
//! Graph algorithms are expensive to re-run and cheap to maintain. Betweenness costs
//! O(|V| · |E|) from scratch; connectivity after one added edge costs a union-find
//! operation. The difference is knowing *what* changed, which is what this module supplies.
//!
//! An observer is a plain trait, and a graph is generic over it, so the default —
//! observing nothing — compiles to nothing at all. There is no event bus, no dynamic
//! dispatch and no allocation unless a caller asks for one; a library has no business
//! imposing infrastructure on code that does not use it.

use crate::core::view::{EdgeId, NodeId};

/// Something that happened to a graph.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum GraphEvent {
    /// A node was added.
    NodeAdded {
        /// The new node.
        node: NodeId,
    },
    /// A node, and every edge incident to it, was removed.
    ///
    /// The incident edges are reported individually as [`EdgeRemoved`](GraphEvent::EdgeRemoved)
    /// before this arrives, so an observer never has to work out what went with it.
    NodeRemoved {
        /// The node that was removed.
        node: NodeId,
    },
    /// An edge was added.
    EdgeAdded {
        /// The new edge.
        edge: EdgeId,
        /// The node the edge leaves.
        from: NodeId,
        /// The node the edge enters.
        to: NodeId,
    },
    /// An edge was removed.
    EdgeRemoved {
        /// The edge that was removed.
        edge: EdgeId,
        /// The node the edge left.
        from: NodeId,
        /// The node the edge entered.
        to: NodeId,
    },
}

/// Receives notifications as a graph changes.
///
/// # Examples
/// ```rust
/// # #[cfg(feature = "graph")] {
/// use xgraph::core::{GraphEvent, GraphObserver, Observed};
/// use xgraph::graph::Graph;
///
/// #[derive(Default)]
/// struct CountEdits(usize);
///
/// impl GraphObserver for CountEdits {
///     fn on_event(&mut self, _event: GraphEvent) {
///         self.0 += 1;
///     }
/// }
///
/// let mut observed = Observed::new(
///     Graph::<u32, &str, &str>::new(false),
///     CountEdits::default(),
/// );
/// let a = observed.add_node("A");
/// let b = observed.add_node("B");
/// observed.add_edge(a, b, 1, "rail").unwrap();
///
/// assert_eq!(observed.observer().0, 3);
/// # }
/// ```
pub trait GraphObserver {
    /// Called after the change has been applied, so the graph is already consistent.
    fn on_event(&mut self, event: GraphEvent);
}

/// The default observer: it observes nothing.
///
/// A graph parameterised over this has no observation overhead — the call is a no-op the
/// compiler removes entirely.
impl GraphObserver for () {
    fn on_event(&mut self, _event: GraphEvent) {}
}

impl<O: GraphObserver + ?Sized> GraphObserver for Box<O> {
    fn on_event(&mut self, event: GraphEvent) {
        (**self).on_event(event);
    }
}

/// Records every event in order.
///
/// Useful for tests, for auditing, and for feeding a batch of changes to something that
/// wants them all at once.
#[derive(Debug, Clone, Default)]
pub struct EventLog {
    events: Vec<GraphEvent>,
}

impl EventLog {
    /// An empty log.
    pub fn new() -> Self {
        Self::default()
    }

    /// The events recorded so far, oldest first.
    pub fn events(&self) -> &[GraphEvent] {
        &self.events
    }

    /// Empties the log and returns what it held.
    pub fn take(&mut self) -> Vec<GraphEvent> {
        std::mem::take(&mut self.events)
    }
}

impl GraphObserver for EventLog {
    fn on_event(&mut self, event: GraphEvent) {
        self.events.push(event);
    }
}

/// The mutations an [`Observed`] wrapper forwards and reports.
///
/// Implemented by both graph types, so observation is written once and applies to either.
pub trait MutableGraph {
    /// The data a node carries.
    type NodeData;
    /// The data an edge carries.
    type EdgeData;
    /// The type of an edge weight.
    ///
    /// Named `EdgeWeight` rather than `Weight` so that it never collides with
    /// [`GraphView::Weight`](crate::core::GraphView::Weight) on a type that implements both.
    type EdgeWeight;
    /// What a rejected mutation reports.
    type Error;

    /// Adds a node and returns its identifier.
    fn add_node(&mut self, data: Self::NodeData) -> NodeId;

    /// Adds an edge and returns its identifier.
    fn add_edge(
        &mut self,
        from: NodeId,
        to: NodeId,
        weight: Self::EdgeWeight,
        data: Self::EdgeData,
    ) -> Result<EdgeId, Self::Error>;

    /// Removes a node and every edge incident to it.
    ///
    /// Returns whether the node existed.
    fn remove_node(&mut self, node: NodeId) -> Result<bool, Self::Error>;

    /// Removes one edge.
    fn remove_edge_by_id(&mut self, edge: EdgeId) -> Result<(), Self::Error>;
}

/// A graph paired with something watching it change.
///
/// Wrapping rather than parameterising the graph itself: a caller who does not observe
/// pays nothing and sees no change, and the same wrapper serves both graph types. It
/// implements [`GraphView`](crate::core::GraphView) by delegation, so every algorithm in
/// the crate applies to it directly.
///
/// # Examples
/// ```rust
/// # #[cfg(feature = "graph")] {
/// use xgraph::core::{EventLog, GraphEvent, Observed};
/// use xgraph::graph::Graph;
///
/// let mut observed = Observed::new(Graph::<u32, &str, &str>::new(false), EventLog::new());
/// let a = observed.add_node("A");
/// let b = observed.add_node("B");
/// let edge = observed.add_edge(a, b, 1, "rail").unwrap();
/// observed.remove_edge_by_id(edge).unwrap();
///
/// assert_eq!(
///     observed.observer().events().last(),
///     Some(&GraphEvent::EdgeRemoved { edge, from: a, to: b })
/// );
/// # }
/// ```
#[derive(Debug, Clone, Default)]
pub struct Observed<G, O> {
    graph: G,
    observer: O,
}

impl<G, O> Observed<G, O> {
    /// Pairs a graph with an observer.
    pub fn new(graph: G, observer: O) -> Self {
        Self { graph, observer }
    }

    /// The graph underneath.
    pub fn graph(&self) -> &G {
        &self.graph
    }

    /// The observer.
    pub fn observer(&self) -> &O {
        &self.observer
    }

    /// The observer, mutably.
    pub fn observer_mut(&mut self) -> &mut O {
        &mut self.observer
    }

    /// Splits the pair back into its parts.
    pub fn into_parts(self) -> (G, O) {
        (self.graph, self.observer)
    }

    /// The graph underneath, mutably.
    ///
    /// Changes made through this reference are **not** reported: it is the escape hatch for
    /// operations the wrapper does not model, and using it leaves any observer that
    /// maintains derived state out of date.
    pub fn graph_mut_unobserved(&mut self) -> &mut G {
        &mut self.graph
    }
}

impl<G, O> Observed<G, O>
where
    G: MutableGraph + crate::core::view::GraphView,
    O: GraphObserver,
{
    /// Adds a node and reports it.
    pub fn add_node(&mut self, data: G::NodeData) -> NodeId {
        let node = self.graph.add_node(data);
        self.observer.on_event(GraphEvent::NodeAdded { node });
        node
    }

    /// Adds an edge and reports it.
    ///
    /// Nothing is reported if the graph rejects the edge.
    pub fn add_edge(
        &mut self,
        from: NodeId,
        to: NodeId,
        weight: G::EdgeWeight,
        data: G::EdgeData,
    ) -> Result<EdgeId, G::Error> {
        let edge = self.graph.add_edge(from, to, weight, data)?;
        // Endpoints are read back rather than echoed: an undirected graph normalizes the
        // pair, and an observer maintaining an index needs what was actually stored.
        let (from, to) = self.graph.edge_endpoints(edge).unwrap_or((from, to));
        self.observer
            .on_event(GraphEvent::EdgeAdded { edge, from, to });
        Ok(edge)
    }

    /// Removes an edge and reports it.
    pub fn remove_edge_by_id(&mut self, edge: EdgeId) -> Result<(), G::Error> {
        // Captured before the removal, since afterwards there is nothing to read.
        let endpoints = self.graph.edge_endpoints(edge);
        self.graph.remove_edge_by_id(edge)?;
        if let Some((from, to)) = endpoints {
            self.observer
                .on_event(GraphEvent::EdgeRemoved { edge, from, to });
        }
        Ok(())
    }

    /// Removes a node and reports it, along with each edge that went with it.
    ///
    /// The incident edges are reported first, so an observer never has to work out for
    /// itself what the removal took with it.
    pub fn remove_node(&mut self, node: NodeId) -> Result<bool, G::Error> {
        let incident: Vec<(EdgeId, NodeId, NodeId)> = self
            .graph
            .node_id_vec()
            .into_iter()
            .flat_map(|other| {
                self.graph
                    .links(other)
                    .filter(|link| other == node || link.target == node)
                    .filter_map(|link| {
                        self.graph
                            .edge_endpoints(link.edge)
                            .map(|(from, to)| (link.edge, from, to))
                    })
                    .collect::<Vec<_>>()
            })
            .collect();

        let removed = self.graph.remove_node(node)?;
        if !removed {
            return Ok(false);
        }

        let mut reported = std::collections::HashSet::new();
        for (edge, from, to) in incident {
            if reported.insert(edge) {
                self.observer
                    .on_event(GraphEvent::EdgeRemoved { edge, from, to });
            }
        }
        self.observer.on_event(GraphEvent::NodeRemoved { node });
        Ok(true)
    }
}

impl<G, O> crate::core::view::GraphView for Observed<G, O>
where
    G: crate::core::view::GraphView,
{
    type Weight = G::Weight;
    type NodeIds<'a>
        = G::NodeIds<'a>
    where
        Self: 'a;
    type Links<'a>
        = G::Links<'a>
    where
        Self: 'a;

    fn is_directed(&self) -> bool {
        self.graph.is_directed()
    }
    fn node_count(&self) -> usize {
        self.graph.node_count()
    }
    fn edge_count(&self) -> usize {
        self.graph.edge_count()
    }
    fn contains_node(&self, node: NodeId) -> bool {
        self.graph.contains_node(node)
    }
    fn node_ids(&self) -> Self::NodeIds<'_> {
        self.graph.node_ids()
    }
    fn links(&self, node: NodeId) -> Self::Links<'_> {
        self.graph.links(node)
    }
    fn edge_endpoints(&self, edge: EdgeId) -> Option<(NodeId, NodeId)> {
        self.graph.edge_endpoints(edge)
    }
}

/// Tracks which nodes are connected to which, without re-running a traversal.
///
/// Answers "are these two nodes in the same component?" in effectively constant time and
/// keeps the answer current as edges arrive. This is the case that motivates the whole
/// mechanism: recomputing connected components after every edge is O(|V| + |E|) each time,
/// and maintaining them incrementally is a union-find operation.
///
/// Only edge additions can be absorbed incrementally — a removal can split a component,
/// which union-find cannot undo. A removal therefore marks the tracker stale, and
/// [`is_current`](IncrementalComponents::is_current) says so rather than letting a caller
/// trust a wrong answer.
///
/// # Examples
/// ```rust
/// # #[cfg(feature = "graph")] {
/// use xgraph::core::{IncrementalComponents, Observed};
/// use xgraph::graph::Graph;
///
/// let mut observed = Observed::new(
///     Graph::<u32, &str, &str>::new(false),
///     IncrementalComponents::new(),
/// );
/// let a = observed.add_node("A");
/// let b = observed.add_node("B");
/// let c = observed.add_node("C");
/// observed.add_edge(a, b, 1, "rail").unwrap();
///
/// assert!(observed.observer_mut().connected(a, b));
/// assert!(!observed.observer_mut().connected(a, c));
/// assert!(observed.observer().is_current());
/// # }
/// ```
#[derive(Debug, Default)]
pub struct IncrementalComponents {
    sets: crate::core::algo::spanning_tree::DisjointSets,
    stale: bool,
}

impl IncrementalComponents {
    /// A tracker for an empty graph.
    pub fn new() -> Self {
        Self::default()
    }

    /// Whether two nodes are in the same component.
    ///
    /// Meaningful only while [`is_current`](IncrementalComponents::is_current) holds.
    pub fn connected(&mut self, left: NodeId, right: NodeId) -> bool {
        self.sets.connected(left, right)
    }

    /// Whether the tracker still reflects the graph.
    ///
    /// Becomes false once anything is removed, because a removal can split a component and
    /// the union-find structure cannot express that.
    pub fn is_current(&self) -> bool {
        !self.stale
    }

    /// Rebuilds the tracker from scratch, making it current again.
    pub fn rebuild<G: crate::core::view::GraphView + ?Sized>(&mut self, graph: &G) {
        self.sets = crate::core::algo::spanning_tree::DisjointSets::new();
        for node in graph.node_ids() {
            self.sets.insert(node);
        }
        for node in graph.node_id_vec() {
            for link in graph.links(node) {
                self.sets.union(node, link.target);
            }
        }
        self.stale = false;
    }
}

impl GraphObserver for IncrementalComponents {
    fn on_event(&mut self, event: GraphEvent) {
        match event {
            GraphEvent::NodeAdded { node } => self.sets.insert(node),
            GraphEvent::EdgeAdded { from, to, .. } => {
                self.sets.union(from, to);
            }
            // A removal can split a component; union-find cannot express that, so the
            // honest response is to admit the answer is no longer trustworthy.
            GraphEvent::NodeRemoved { .. } | GraphEvent::EdgeRemoved { .. } => self.stale = true,
        }
    }
}

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

    fn observed() -> Observed<Graph<u32, u32, &'static str>, EventLog> {
        Observed::new(Graph::<u32, u32, &str>::new(false), EventLog::new())
    }

    #[test]
    fn test_every_mutation_is_reported() {
        let mut graph = observed();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let edge = graph.add_edge(a, b, 1, "rail").unwrap();
        graph.remove_edge_by_id(edge).unwrap();

        assert_eq!(
            graph.observer().events(),
            &[
                GraphEvent::NodeAdded { node: a },
                GraphEvent::NodeAdded { node: b },
                GraphEvent::EdgeAdded {
                    edge,
                    from: a,
                    to: b
                },
                GraphEvent::EdgeRemoved {
                    edge,
                    from: a,
                    to: b
                },
            ]
        );
    }

    /// Removing a node takes its edges with it, and an observer maintaining an index needs
    /// to be told about each of them rather than deduce it.
    #[test]
    fn test_removing_a_node_reports_its_edges_first() {
        let mut graph = observed();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let ab = graph.add_edge(a, b, 1, "x").unwrap();
        let bc = graph.add_edge(b, c, 1, "y").unwrap();
        graph.observer_mut().take();

        graph.remove_node(b).unwrap();

        let events = graph.observer().events();
        let removed_edges: Vec<_> = events
            .iter()
            .filter_map(|event| match event {
                GraphEvent::EdgeRemoved { edge, .. } => Some(*edge),
                _ => None,
            })
            .collect();
        assert_eq!(removed_edges.len(), 2);
        assert!(removed_edges.contains(&ab) && removed_edges.contains(&bc));
        assert_eq!(events.last(), Some(&GraphEvent::NodeRemoved { node: b }));
    }

    #[test]
    fn test_a_rejected_mutation_reports_nothing() {
        let mut graph = observed();
        let a = graph.add_node(0);
        graph.observer_mut().take();

        assert!(graph.add_edge(a, NodeId::from_index(999), 1, "x").is_err());
        assert!(graph.observer().events().is_empty());
    }

    /// The wrapper is a view, so every algorithm applies to it directly.
    #[test]
    fn test_algorithms_run_over_the_wrapper() {
        let mut graph = observed();
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        graph.add_edge(a, b, 1, "rail").unwrap();

        assert_eq!(graph.node_count(), 2);
        assert!(graph.is_connected().unwrap());
    }

    /// The case that justifies the mechanism: connectivity kept current for the cost of a
    /// union-find operation instead of a fresh O(|V| + |E|) sweep per edit.
    #[test]
    fn test_components_are_maintained_incrementally() {
        let mut graph = Observed::new(
            Graph::<u32, u32, &str>::new(false),
            IncrementalComponents::new(),
        );
        let nodes: Vec<_> = (0..6).map(|i| graph.add_node(i)).collect();
        graph.add_edge(nodes[0], nodes[1], 1, "x").unwrap();
        graph.add_edge(nodes[1], nodes[2], 1, "x").unwrap();
        graph.add_edge(nodes[3], nodes[4], 1, "x").unwrap();

        assert!(graph.observer().is_current());
        assert!(graph.observer_mut().connected(nodes[0], nodes[2]));
        assert!(!graph.observer_mut().connected(nodes[0], nodes[3]));
        assert!(!graph.observer_mut().connected(nodes[0], nodes[5]));

        // Checked against the algorithm it stands in for.
        let components = graph.weakly_connected_components().unwrap();
        for component in &components {
            for &node in component {
                assert!(graph.observer_mut().connected(component[0], node));
            }
        }
    }

    /// A removal can split a component, which union-find cannot undo. Saying so beats
    /// answering confidently and wrongly.
    #[test]
    fn test_a_removal_marks_the_tracker_stale() {
        let mut graph = Observed::new(
            Graph::<u32, u32, &str>::new(false),
            IncrementalComponents::new(),
        );
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let edge = graph.add_edge(a, b, 1, "x").unwrap();
        assert!(graph.observer().is_current());

        graph.remove_edge_by_id(edge).unwrap();
        assert!(!graph.observer().is_current());

        // A rebuild restores it.
        let (graph_inner, mut observer) = graph.into_parts();
        observer.rebuild(&graph_inner);
        assert!(observer.is_current());
        assert!(!observer.connected(a, b));
    }

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

        // Nothing to assert about the observer itself; the point is that it compiles and
        // costs nothing.
        assert_eq!(graph.node_count(), 2);
    }
}