grapes 0.3.0

//! Persistent [Graph] & related items
//!
//! A [Graph] (a [well-known data structure](https://en.wikipedia.org/wiki/Directed_graph)!) consists of a set of nodes and a set of edges.
//!
//! - Every node is associated with some `NodeData` (also known as node weight) and has a [NodeId]
//! - Every edge connects one node to another. It has `EdgeData` (edge weight) and an [EdgeId]
//!
//! You get to choose what data you want to store in the `NodeData` and `EdgeData`!
//!
//! Note:
//! - The graph is directed. This means that an edge going from node `a` to node `b` is not the same as `b` to `a`
//! - There may be multiple edges for the same `from` and `to` nodes.
//! - There may be loops: edges which have the same `from` and `to` node.

mod edge_iter;
mod edge_mut;
mod edge_ref;
mod node_iter;
mod node_mut;
mod node_ref;

pub use edge_iter::*;
pub use edge_mut::*;
pub use edge_ref::*;
pub use node_iter::*;
pub use node_mut::*;
pub use node_ref::*;

use crate::arena::{Arena, EntryId};

/// A directed graph
///
/// See [module docs](crate::graph) for more information
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Graph<NodeData: Clone, EdgeData: Clone> {
    /// Collection of nodes in this graph
    pub(crate) nodes: Arena<Node<NodeData>>,
    /// Collection of edges in this graph
    ///
    /// Note: each edge is part of 2 double-linked lists, 1 for outgoing edges and 1 for incoming edges.
    /// See [Edge] for more details
    pub(crate) edges: Arena<Edge<EdgeData>>,
}

/// Node identifier
///
/// You can use it to refer to nodes in a [Graph] without needing to keep a reference to them
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct NodeId(pub(crate) EntryId);

/// Internal structure for representing a node (vertex) in a graph
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(crate) struct Node<NodeData: Clone> {
    /// Data (weight) associated with this node
    pub(crate) data: NodeData,
    /// Edges from this node: head of double-linked list in `edges`
    ///
    /// Must point to a valid edge
    first_edge_from: Option<EdgeId>,
    /// Edges to this node: head of double-linked list in `edges`
    ///
    /// Must point to a valid edge
    first_edge_to: Option<EdgeId>,
}

/// Edge identifier
///
/// You can use it to refer to edges in a [Graph] without needing to keep a reference to them
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct EdgeId(pub(crate) EntryId);

/// Internal structure for representing an edge (arc) in a graph
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub(crate) struct Edge<EdgeData: Clone> {
    /// Data (weight) associated with this edge
    data: EdgeData,
    /// Node where this edge starts. Must be valid.
    from: NodeId,
    /// Node which this edge points to. Must be valid.
    to: NodeId,

    /// Next edge with same `from` node
    ///
    /// Together with `previous_with_from`, forms a double-linked list in `Graph::edges`
    next_with_from: Option<EdgeId>,
    /// Previous edge with same `from` node
    previous_with_from: Option<EdgeId>,

    /// Next edge with same `to` node
    ///
    /// Together with `previous_with_to`, forms a double-linked list in `Graph::edges`
    next_with_to: Option<EdgeId>,
    /// Previous edge with same `to` node
    previous_with_to: Option<EdgeId>,
}

/// Error: the specified node was not found in the graph
#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct NoSuchNode(pub NodeId);

impl<NodeData: Clone, EdgeData: Clone> Default for Graph<NodeData, EdgeData> {
    fn default() -> Self {
        Self::new()
    }
}

impl<NodeData: Clone, EdgeData: Clone> Graph<NodeData, EdgeData> {
    /// Construct a new, empty, [Graph]
    #[must_use]
    pub fn new() -> Self {
        Self {
            nodes: Arena::new(),
            edges: Arena::new(),
        }
    }

    /// Insert a node with the specified data (weight)
    pub fn insert_node(&mut self, data: NodeData) -> NodeMut<NodeData, EdgeData> {
        let id = self.nodes.insert(Node {
            data,
            first_edge_from: None,
            first_edge_to: None,
        });

        NodeMut::new(self, NodeId(id))
    }

    /// Get a node by its identifier
    ///
    /// Returns [None] if there is no such node
    #[must_use]
    pub fn get_node(&self, id: NodeId) -> Option<NodeRef<NodeData, EdgeData>> {
        let _ = self.nodes.get(id.0)?;
        Some(NodeRef::new(self, id))
    }

    /// Get a mutable reference to a node by its identifier
    ///
    /// Returns [None] if there is no such node
    #[must_use]
    pub fn get_node_mut(&mut self, id: NodeId) -> Option<NodeMut<NodeData, EdgeData>> {
        let _ = self.nodes.get(id.0)?;
        Some(NodeMut::new(self, id))
    }

    /// Iterate over all nodes in the graph
    ///
    /// Order is unspecified
    pub fn iter_nodes(&self) -> GraphNodes<NodeData, EdgeData> {
        GraphNodes::new(self)
    }

    /// Insert a new edge connecting the specified nodes, with the specified edge data (weight)
    ///
    /// Notes:
    /// - The graph is directed. Inserting an edge from *x* to *y* is not the same as *y* to *x*
    /// - There may be multiple edges from any node to another
    pub fn insert_edge(
        &mut self,
        from: NodeId,
        to: NodeId,
        data: EdgeData,
    ) -> Result<EdgeMut<NodeData, EdgeData>, NoSuchNode> {
        let from_node = self.nodes.get(from.0).ok_or(NoSuchNode(from))?;
        let to_node = self.nodes.get(to.0).ok_or(NoSuchNode(to))?;

        let edge = Edge {
            data,
            from,
            to,
            next_with_from: from_node.first_edge_from,
            previous_with_from: None,
            next_with_to: to_node.first_edge_to,
            previous_with_to: None,
        };
        let new_id = self.edges.insert(edge);
        let new_id = EdgeId(new_id);

        if let Some(previous_first_from) = from_node.first_edge_from {
            let second_from = self
                .edges
                .get_mut(previous_first_from.0)
                .expect("corrupt `from` list: head points to invalid node");
            second_from.previous_with_from = Some(new_id);
        }

        if let Some(previous_first_to) = to_node.first_edge_to {
            let second_to = self
                .edges
                .get_mut(previous_first_to.0)
                .expect("corrupt `to` list: head points to invalid node");
            second_to.previous_with_to = Some(new_id);
        }

        let from_node = self.nodes.get_mut(from.0).expect("unreachable");
        from_node.first_edge_from = Some(new_id);

        let to_node = self.nodes.get_mut(to.0).expect("unreachable");
        to_node.first_edge_to = Some(new_id);

        Ok(EdgeMut::new(self, new_id))
    }

    /// Get an edge by identifier
    ///
    /// If there is no such edge, returns [None]
    #[must_use]
    pub fn get_edge(&self, id: EdgeId) -> Option<EdgeRef<NodeData, EdgeData>> {
        let _ = self.edges.get(id.0)?;
        Some(EdgeRef::new(self, id))
    }

    /// Get a mutable reference to an edge by identifier
    ///
    /// If there is no such edge, returns [None]
    #[must_use]
    pub fn get_edge_mut(&mut self, id: EdgeId) -> Option<EdgeMut<NodeData, EdgeData>> {
        let _ = self.edges.get(id.0)?;
        Some(EdgeMut::new(self, id))
    }

    /// Iterate over all edges in the Graph
    ///
    /// Order is unspecified
    pub fn iter_edges(&self) -> GraphEdges<NodeData, EdgeData> {
        GraphEdges::new(self)
    }
}

/// Private helpers
impl<NodeData: Clone, EdgeData: Clone> Graph<NodeData, EdgeData> {
    /// Detach an edge from the `to` linked list
    fn detach_edge_from_to_list(&mut self, target: &Edge<EdgeData>) {
        match target.previous_with_to {
            None => {
                // first in list; update head
                self.nodes[target.to.0].first_edge_to = target.next_with_to;
            }
            Some(id) => {
                // not first in list; update previous
                self.edges[id.0].next_with_to = target.next_with_to;
            }
        }
        if let Some(id) = target.next_with_to {
            // not last in list -> update next
            self.edges[id.0].previous_with_to = target.previous_with_to;
        }
    }

    /// Detach an edge from the `from` linked list
    fn detach_edge_from_from_list(&mut self, target: &Edge<EdgeData>) {
        match target.previous_with_from {
            None => {
                // first in list; update head
                self.nodes[target.from.0].first_edge_from = target.next_with_from;
            }
            Some(id) => {
                // not first in list; update previous
                self.edges[id.0].next_with_from = target.next_with_from;
            }
        }
        if let Some(id) = target.next_with_from {
            // not last in list -> update next
            self.edges[id.0].previous_with_from = target.previous_with_from;
        }
    }

    /// Remove all edges leaving a specified target node
    pub(crate) fn remove_all_edges_connecting(
        &mut self,
        target_index: NodeId,
        target: &Node<NodeData>,
    ) {
        // remove edges from target node
        // except loops; they will be removed later
        {
            let mut next_edge_from = target.first_edge_from;
            while let Some(id) = next_edge_from {
                let edge = self.edges.get(id.0).expect("corrupt `from` edge list");
                next_edge_from = edge.next_with_from;
                if edge.to == target_index {
                    // don't remove loops yet, they'll be removed when removing `to` edges.
                    continue;
                }

                let removed_edge = self.edges.remove(id.0).unwrap();

                self.detach_edge_from_to_list(&removed_edge);
                // don't bother detaching from `from` list, since we're clearing the whole list anyway
                // self.detach_edge_from_from_list(&removed_edge);
            }
        }

        // remove all edges to target node
        // including loops
        let mut next_edge_to = target.first_edge_to;

        while let Some(id) = next_edge_to {
            let removed_edge = self.edges.remove(id.0).expect("corrupt `from` edge list");

            // don't detach loops from the `from` list, since it's the target node's `from` list, and we already cleared that list
            // (except for the loops, which we're clearing now)
            if removed_edge.from != target_index {
                self.detach_edge_from_from_list(&removed_edge);
                // don't bother detaching from `to` list, since we're clearing the whole list anyway
                // self.detach_edge_from_to_list(&removed_edge);
            }

            next_edge_to = removed_edge.next_with_to;
        }
    }
}

#[cfg(test)]
type SimpleGraph = Graph<i32, i32>;

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

    use std::hash::Hash;
    use velcro::hash_set;

    impl<NodeData: Clone + Hash + Eq, EdgeData: Clone + Hash + Eq> Graph<NodeData, EdgeData> {
        pub(crate) fn to_description(
            &self,
        ) -> (HashSet<NodeData>, HashSet<(NodeData, NodeData, EdgeData)>) {
            let nodes = self.iter_nodes().map(|node| node.data().clone()).collect();

            let edges = self
                .iter_edges()
                .map(|edge| {
                    (
                        edge.get_from_node().data().clone(),
                        edge.get_to_node().data().clone(),
                        edge.data().clone(),
                    )
                })
                .collect();

            (nodes, edges)
        }

        /// Ensure that the graph is in a valid state: invariants are upheld
        ///
        /// - Linked lists are valid
        /// - Underlying arenas are valid
        ///
        /// Panics if invalid
        pub(crate) fn validate(&self) {
            self.edges.validate();
            self.nodes.validate();

            for (id, node) in self.nodes.iter_items() {
                if let Some(first) = node.first_edge_from {
                    assert_eq!(self.edges[first.0].from, NodeId(id))
                }
                if let Some(first) = node.first_edge_to {
                    assert_eq!(self.edges[first.0].to, NodeId(id))
                }
            }

            for (id, edge) in self.edges.iter_items() {
                if let Some(previous_from) = edge.previous_with_from {
                    assert_eq!(self.edges[previous_from.0].next_with_from, Some(EdgeId(id)));
                } else {
                    assert_eq!(self.nodes[edge.from.0].first_edge_from, Some(EdgeId(id)))
                }
                if let Some(next_from) = edge.next_with_from {
                    assert_eq!(self.edges[next_from.0].previous_with_from, Some(EdgeId(id)))
                }

                if let Some(previous_to) = edge.previous_with_to {
                    assert_eq!(self.edges[previous_to.0].next_with_to, Some(EdgeId(id)));
                } else {
                    assert_eq!(self.nodes[edge.to.0].first_edge_to, Some(EdgeId(id)))
                }
                if let Some(next_to) = edge.next_with_to {
                    assert_eq!(self.edges[next_to.0].previous_with_to, Some(EdgeId(id)))
                }
            }
        }
    }

    #[test]
    fn new() {
        let graph = SimpleGraph::new();

        assert_eq!(graph.to_description(), (hash_set!(), hash_set!()));
        graph.validate();
    }

    #[test]
    fn insert_node() {
        let mut graph = SimpleGraph::new();

        graph.insert_node(42);

        assert_eq!(graph.to_description(), (hash_set!(42), hash_set!()));
        graph.validate();
    }

    #[test]
    fn node_accessors() {
        let mut graph = SimpleGraph::new();

        let node = graph.insert_node(42);
        assert_eq!(node.data(), &42);

        let node_id = node.id();
        let node = graph.get_node(node_id).unwrap();
        assert_eq!(node.data(), &42);
        graph.validate();
    }

    #[test]
    fn node_data_mut() {
        let mut graph = SimpleGraph::new();

        let mut node = graph.insert_node(42);
        *node.data_mut() += 1;

        assert_eq!(graph.to_description(), (hash_set!(43), hash_set!()));
        graph.validate();
    }

    #[test]
    fn node_remove() {
        let mut graph = SimpleGraph::new();

        graph.insert_node(100);
        let node = graph.insert_node(42);
        node.remove();

        assert_eq!(graph.to_description(), (hash_set!(100), hash_set!()));
        graph.validate();
    }

    #[test]
    fn iter_nodes() {
        let mut graph = SimpleGraph::new();

        graph.insert_node(42);
        graph.insert_node(43);
        graph.insert_node(44);

        assert_eq!(
            graph
                .iter_nodes()
                .map(|node| *node.data())
                .collect::<HashSet<_>>(),
            hash_set!(42, 43, 44)
        );
        graph.validate();
    }

    #[test]
    fn insert_edge() {
        let mut graph = SimpleGraph::new();

        let a = graph.insert_node(1).id();
        let b = graph.insert_node(2).id();

        graph.insert_edge(a, b, 3).unwrap();

        assert_eq!(
            graph.to_description(),
            (hash_set!(1, 2), hash_set!((1, 2, 3)))
        );
        graph.validate();
    }

    #[test]
    fn edge_loop() {
        let mut graph = SimpleGraph::new();

        let a = graph.insert_node(1).id();
        let edge_id = graph.insert_edge(a, a, 3).unwrap().id();

        assert_eq!(graph.to_description(), (hash_set!(1), hash_set!((1, 1, 3))));

        graph.get_edge_mut(edge_id).unwrap().remove();

        assert_eq!(graph.to_description(), (hash_set!(1), hash_set!()));
        graph.validate();
    }

    #[test]
    fn parallel_edge() {
        let mut graph = SimpleGraph::new();

        let a = graph.insert_node(1).id();
        let b = graph.insert_node(2).id();
        graph.insert_edge(a, b, 3).unwrap();
        let edge_id = graph.insert_edge(a, b, 4).unwrap().id();

        assert_eq!(
            graph.to_description(),
            (hash_set!(1, 2), hash_set!((1, 2, 3), (1, 2, 4)))
        );

        graph.get_edge_mut(edge_id).unwrap().remove();

        assert_eq!(
            graph.to_description(),
            (hash_set!(1, 2), hash_set!((1, 2, 3)))
        );
        graph.validate();
    }

    #[test]
    fn edge_accessors() {
        let mut graph = SimpleGraph::new();

        let a = graph.insert_node(1).id();
        let b = graph.insert_node(2).id();

        let edge = graph.insert_edge(a, b, 3).unwrap();

        assert_eq!(edge.get_from_node().id(), a);
        assert_eq!(edge.get_to_node().id(), b);
        assert_eq!(edge.data(), &3);

        let edge_id = edge.id();
        let edge_ref = graph.get_edge(edge_id).unwrap();

        assert_eq!(edge_ref.get_from_node().id(), a);
        assert_eq!(edge_ref.get_to_node().id(), b);
        assert_eq!(edge_ref.data(), &3);

        graph.validate();
    }

    #[test]
    fn removing_node_removes_edges() {
        let mut graph = SimpleGraph::new();

        let a = graph.insert_node(1).id();
        graph.validate();

        let b = graph.insert_node(2).id();
        graph.validate();
        let c = graph.insert_node(3).id();
        graph.validate();

        graph.insert_edge(a, a, 11).unwrap();
        graph.validate();
        graph.insert_edge(a, b, 12).unwrap();
        graph.validate();

        graph.insert_edge(b, b, 22).unwrap();
        graph.validate();
        graph.insert_edge(b, c, 23).unwrap();
        graph.validate();

        graph.insert_edge(c, c, 33).unwrap();
        graph.validate();
        graph.insert_edge(c, a, 31).unwrap();
        graph.validate();

        assert_eq!(
            graph.to_description(),
            (
                hash_set!(1, 2, 3),
                hash_set!(
                    (1, 1, 11),
                    (1, 2, 12),
                    (2, 2, 22),
                    (2, 3, 23),
                    (3, 3, 33),
                    (3, 1, 31)
                )
            )
        );

        graph.get_node_mut(a).unwrap().remove();
        graph.validate();

        assert_eq!(
            graph.to_description(),
            (
                hash_set!(2, 3),
                hash_set!((2, 2, 22), (2, 3, 23), (3, 3, 33),)
            )
        );
        graph.validate();
    }
}