crates/core/src/graph/mod.rs

mod compat;
mod directed;
mod insert;
mod resize;
mod retain;
mod reverse;

use error_stack::Result;

use crate::{
    edge::{DetachedEdge, Edge, EdgeId, EdgeMut},
    node::{DetachedNode, Node, NodeId, NodeMut},
    storage::GraphStorage,
};

/// A graph, which is generic over its storage.
///
/// This is the central point of interaction with `petgraph`, allowing for consistent access to a
/// graph, without worrying about the underlying storage implementations.
///
/// Limitations of the underlying storage implementation apply, meaning that some operations may be
/// more expensive than others, or certain capabilities such as parallel edges may not be available.
///
/// Each graph storage implementation has a section with more information about its capabilities.
///
/// For convenience each graph storage implementation has a type alias for the graph type, which
/// uses the implementation, such as [`DinoGraph`], [`DiDinoGraph`], and [`UnDinoGraph`] in
/// `petgraph-dino`.
///
/// Instead of relying on a single storage implementation, this design encourages (and recommends)
/// the use of `S` as a generic parameter for functions receiving a graph.
///
/// `petgraph` assumes that a directed graph is simply a specialization of an undirected graph where
/// edges have an additional property marking the directionality of the edge. This means that any
/// directed graph also necessarily implements the undirected graph interface, known simply as
/// [`GraphStorage`]. This is similar to other graph libraries such as `networkx` and `igraph`.
///
/// Endpoints of an edge are known as `u` and `v` in `petgraph`, where `u` and `v` are
/// interchangeable in an undirected graph, and `u` is the source and `v` is the target in a
/// directed graph.
///
/// # Storage Implementations
// TODO
///
/// # Example
///
/// ```
/// use petgraph_core::{
///     edge::marker::{Directed, Undirected},
///     Graph, GraphStorage,
/// };
/// use petgraph_dino::{DiDinoGraph, DinoGraph, DinoStorage, UnDinoGraph};
///
/// // we're using explicit generics here to illustrate the difference more clearly, but also
/// // because we do not insert/remove any nodes or edges, which means we cannot infer those types.
///
/// let digraph = Graph::<DinoStorage<u8, u8, Directed>>::new();
/// // ^ same as:
/// let digraph = DinoGraph::<u8, u8, Directed>::new();
/// // ^ same as:
/// let digraph = DiDinoGraph::<u8, u8>::new();
///
/// let ungraph = Graph::<DinoStorage<u8, u8, Undirected>>::new();
/// // ^ same as:
/// let ungraph = DinoGraph::<u8, u8, Undirected>::new();
/// // ^ same as:
/// let ungraph = UnDinoGraph::<u8, u8>::new();
///
/// fn sum_node_weights<S>(graph: &Graph<S>) -> u8
/// where
///     S: GraphStorage<NodeWeight = u8>,
/// {
///     graph.nodes().map(|node| *node.weight()).sum()
/// }
///
/// assert_eq!(sum_node_weights(&digraph), 0);
/// assert_eq!(sum_node_weights(&ungraph), 0);
/// ```
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub struct Graph<S> {
    storage: S,
}

impl<S> Default for Graph<S>
where
    S: GraphStorage,
{
    fn default() -> Self {
        Self::new()
    }
}

impl<S> Graph<S>
where
    S: GraphStorage,
{
    /// Create a new graph on-top of the given storage.
    ///
    /// # Example
    ///
    /// ```
    /// use petgraph_core::{
    ///     edge::marker::{Directed, Undirected},
    ///     Graph, GraphStorage,
    /// };
    /// use petgraph_dino::DinoStorage;
    ///
    /// let storage = DinoStorage::<u8, u8, Directed>::with_capacity(None, None);
    /// let graph = Graph::new_in(storage);
    /// // ^ this is the same as `Graph::new()`
    /// # assert_eq!(graph.num_nodes(), 0);
    /// # assert_eq!(graph.num_edges(), 0);
    /// ```
    #[must_use]
    pub const fn new_in(storage: S) -> Self {
        Self { storage }
    }

    /// Creates a new graph with the default capacity.
    ///
    /// The default capacity is `None` for both nodes and edges.
    ///
    /// # Example
    ///
    /// ```
    /// use petgraph_core::{edge::marker::Undirected, Graph};
    /// use petgraph_dino::DinoStorage;
    ///
    /// let graph = Graph::<DinoStorage<u8, u8, Undirected>>::new();
    /// # assert_eq!(graph.num_nodes(), 0);
    /// # assert_eq!(graph.num_edges(), 0);
    /// ```
    #[must_use]
    pub fn new() -> Self {
        Self::new_in(S::with_capacity(None, None))
    }

    /// Creates a new graph with the given capacity.
    ///
    /// Helpful in cases where the number of nodes and edges is known in advance, and one wants to
    /// avoid reallocations.
    /// Be aware that some storage implementations may not support this and may not be able to
    /// provide the requested capacity in advance.
    ///
    /// # Example
    ///
    /// ```
    /// use petgraph_core::{edge::marker::Undirected, Graph};
    /// use petgraph_dino::DinoStorage;
    ///
    /// let graph = Graph::<DinoStorage<u8, u8, Undirected>>::with_capacity(Some(16), Some(16));
    /// # assert_eq!(graph.num_nodes(), 0);
    /// # assert_eq!(graph.num_edges(), 0);
    /// ```
    #[must_use]
    pub fn with_capacity(node_capacity: Option<usize>, edge_capacity: Option<usize>) -> Self {
        Self::new_in(S::with_capacity(node_capacity, edge_capacity))
    }

    /// Returns a reference to the underlying storage.
    ///
    /// # Example
    ///
    /// ```
    /// use petgraph_core::{
    ///     edge::marker::{Directed, Undirected},
    ///     Graph, GraphStorage,
    /// };
    /// use petgraph_dino::DinoStorage;
    ///
    /// let storage = DinoStorage::<u8, u8, Directed>::with_capacity(None, None);
    /// let graph = Graph::new_in(storage);
    ///
    /// assert_eq!(graph.storage().num_nodes(), 0);
    /// assert_eq!(graph.storage().num_edges(), 0);
    /// ```
    pub const fn storage(&self) -> &S {
        &self.storage
    }

    /// Returns the underlying storage.
    ///
    /// # Example
    ///
    /// ```
    /// use petgraph_core::{
    ///     edge::marker::{Directed, Undirected},
    ///     Graph, GraphStorage,
    /// };
    /// use petgraph_dino::DinoStorage;
    ///
    /// let storage = DinoStorage::<u8, u8, Directed>::with_capacity(None, None);
    /// let graph = Graph::new_in(storage);
    ///
    /// let storage = graph.into_storage();
    /// assert_eq!(storage.num_nodes(), 0);
    /// assert_eq!(storage.num_edges(), 0);
    /// ```
    pub fn into_storage(self) -> S {
        self.storage
    }

    /// Create a new graph from the given nodes and edges.
    ///
    /// Takes two iterators, one for nodes and one for edges, and returns a new graph with the given
    /// nodes and edges, if the iterator is well-formed.
    /// This is the reverse operation to [`Self::into_parts`], which converts a graph into its
    /// parts.
    ///
    /// The resulting graph may change the order of the nodes and edges and reassign their IDs.
    /// The only properties that stay consistent are the weights and the structural equivalence of
    /// the graph.
    /// For more information see [`GraphStorage::from_parts`].
    ///
    /// # Example
    ///
    /// ```
    /// use std::collections::HashSet;
    ///
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut other = DiDinoGraph::new();
    /// let a = *other.insert_node(0).id();
    /// let b = *other.insert_node(1).id();
    /// let c = *other.insert_node(2).id();
    ///
    /// other.insert_edge(u8::MAX, &a, &b);
    /// other.insert_edge(u8::MAX - 1, &b, &c);
    ///
    /// let other = other.into_parts();
    ///
    /// let graph = DiDinoGraph::from_parts(other.0, other.1).unwrap();
    /// assert_eq!(graph.num_nodes(), 3);
    /// assert_eq!(graph.num_edges(), 2);
    ///
    /// assert_eq!(
    ///     graph
    ///         .nodes()
    ///         .map(|node| *node.weight())
    ///         .collect::<HashSet<_>>(),
    ///     [0, 1, 2].into_iter().collect::<HashSet<_>>(),
    /// );
    ///
    /// let a = *graph.nodes().find(|node| *node.weight() == 0).unwrap().id();
    /// let b = *graph.nodes().find(|node| *node.weight() == 1).unwrap().id();
    /// let c = *graph.nodes().find(|node| *node.weight() == 2).unwrap().id();
    ///
    /// assert_eq!(
    ///     graph
    ///         .edges()
    ///         .map(|edge| (*edge.weight(), edge.endpoint_ids()))
    ///         .collect::<HashSet<_>>(),
    ///     [(u8::MAX, (&a, &b)), (u8::MAX - 1, (&b, &c))]
    ///         .into_iter()
    ///         .collect::<HashSet<_>>(),
    /// );
    /// ```
    ///
    /// # Errors
    ///
    /// If any of the nodes or edges are invalid, or any of the constraint checks of the underlying
    /// implementation fail, an error is returned.
    pub fn from_parts(
        nodes: impl IntoIterator<Item = DetachedNode<S::NodeWeight>>,
        edges: impl IntoIterator<Item = DetachedEdge<S::EdgeWeight>>,
    ) -> Result<Self, S::Error> {
        Ok(Self {
            storage: S::from_parts(nodes, edges)?,
        })
    }

    /// Converts the graph into its parts.
    ///
    /// This is the reverse operation to [`Self::from_parts`], which creates a graph from its parts.
    ///
    /// The iterables returned by this function are not guaranteed to be in any particular order,
    /// but must contain all nodes and edges.
    ///
    /// For more information see [`GraphStorage::into_parts`].
    ///
    /// # Example
    ///
    /// ```
    /// use std::collections::HashSet;
    ///
    /// use petgraph_core::{DetachedEdge, DetachedNode};
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let bc = *graph.insert_edge(u8::MAX - 1, &b, &c).id();
    ///
    /// let (nodes, edges) = graph.into_parts();
    /// let (nodes, edges) = (
    ///     nodes
    ///         .into_iter()
    ///         .map(|node| node.weight)
    ///         .collect::<HashSet<_>>(),
    ///     edges
    ///         .into_iter()
    ///         .map(|edge| edge.weight)
    ///         .collect::<HashSet<_>>(),
    /// );
    ///
    /// assert_eq!(nodes.len(), 3);
    /// assert_eq!(edges.len(), 2);
    ///
    /// assert_eq!(nodes, [0, 1, 2].into_iter().collect::<HashSet<_>>());
    /// assert_eq!(
    ///     edges,
    ///     [u8::MAX, u8::MAX - 1].into_iter().collect::<HashSet<_>>()
    /// );
    /// ```
    pub fn into_parts(
        self,
    ) -> (
        impl IntoIterator<Item = DetachedNode<S::NodeWeight>>,
        impl IntoIterator<Item = DetachedEdge<S::EdgeWeight>>,
    ) {
        self.storage.into_parts()
    }

    /// Converts the graph into a graph with a different storage implementation.
    ///
    /// Internally this simply calls [`GraphStorage::into_parts`] on `S` and then calls
    /// [`Graph::from_parts`] on `T`.
    ///
    /// # Errors
    ///
    /// If any of the nodes or edges are invalid, or any of the constraint checks of the new storage
    /// implementation fail, an error is returned.
    ///
    /// An example would be switching between a storage implementation that supports parallel edges
    /// to one that does not.
    // TODO: example
    pub fn convert<T>(self) -> Result<Graph<T>, T::Error>
    where
        T: GraphStorage<NodeWeight = S::NodeWeight, EdgeWeight = S::EdgeWeight>,
    {
        let (nodes, edges) = self.storage.into_parts();

        Graph::from_parts(nodes, edges)
    }

    /// Returns the number of nodes in the graph.
    ///
    /// This is generally faster than iterating over all nodes and counting them via
    /// `self.nodes().count()`.
    ///
    /// # Example
    ///
    /// ```
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let bc = *graph.insert_edge(u8::MAX - 1, &b, &c).id();
    ///
    /// assert_eq!(graph.num_nodes(), 3);
    /// ```
    pub fn num_nodes(&self) -> usize {
        self.storage.num_nodes()
    }

    /// Returns the number of edges in the graph.
    ///
    /// This is generally faster than iterating over all edges and counting them via
    /// `self.edges().count()`.
    ///
    /// # Example
    ///
    /// ```
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let bc = *graph.insert_edge(u8::MAX - 1, &b, &c).id();
    ///
    /// assert_eq!(graph.num_edges(), 2);
    /// ```
    pub fn num_edges(&self) -> usize {
        self.storage.num_edges()
    }

    /// Returns `true` if the graph has no nodes or edges.
    ///
    /// # Example
    ///
    /// ```
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// // we need to explicitly state the type of the edge weights, as we do insert any edges and
    /// // therefore cannot infer them.
    /// let mut graph = DiDinoGraph::<_, u8>::new();
    /// assert!(graph.is_empty());
    ///
    /// let a = *graph.insert_node(0).id();
    /// assert!(!graph.is_empty());
    ///
    /// graph.remove_node(&a);
    /// assert!(graph.is_empty());
    /// ```
    pub fn is_empty(&self) -> bool {
        self.num_nodes() == 0 && self.num_edges() == 0
    }

    /// Clears the graph, removing all nodes and edges.
    ///
    /// # Example
    ///
    /// ```
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let bc = *graph.insert_edge(u8::MAX - 1, &b, &c).id();
    ///
    /// assert!(!graph.is_empty());
    ///
    /// graph.clear();
    ///
    /// assert!(graph.is_empty());
    /// ```
    pub fn clear(&mut self) {
        self.storage.clear();
    }

    /// Returns the node with the given identifier, if it exists.
    ///
    /// The returned [`Node`] has a reference to the current graph, meaning that you're able to
    /// query for neighbours and [`Edge`]s on the returned value directly.
    ///
    /// # Example
    ///
    /// ```
    /// # use petgraph_core::attributes::NoValue;
    /// # use petgraph_core::{GraphStorage, Node};
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// // we need to explicitly state the type of the edge weights, as we do insert
    /// // any edges and therefore cannot infer them.
    /// let mut graph = DiDinoGraph::<_, u8>::new();
    /// let a = *graph.insert_node(0).id();
    /// # let b = graph.storage().next_node_id(NoValue::new());
    ///
    /// assert_eq!(
    ///     graph.node(&a).map(|node| (*node.id(), *node.weight())),
    ///     Some((a, 0))
    /// );
    /// assert_eq!(
    ///     graph.node(&b).map(|node| (*node.id(), *node.weight())),
    ///     None
    /// );
    /// ```
    pub fn node(&self, id: NodeId) -> Option<Node<S>> {
        self.storage.node(id)
    }

    /// Returns the node, with a mutable weight, with the given identifier, if it exists.
    ///
    /// # Example
    ///
    /// ```
    /// # use petgraph_core::attributes::NoValue;
    /// # use petgraph_core::{GraphStorage, Node};
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// // we need to explicitly state the type of the edge weights, as we do insert
    /// // any edges and therefore cannot infer them.
    /// let mut graph = DiDinoGraph::<_, u8>::new();
    /// let a = *graph.insert_node(0).id();
    /// # let b = graph.storage().next_node_id(NoValue::new());
    ///
    /// if let Some(mut node) = graph.node_mut(&a) {
    ///     *node.weight_mut() = 1;
    /// }
    ///
    /// assert_eq!(
    ///     graph.node(&a).map(|node| (*node.id(), *node.weight())),
    ///     Some((a, 1))
    /// );
    ///
    /// assert!(graph.node_mut(&b).is_none());
    /// ```
    pub fn node_mut(&mut self, id: NodeId) -> Option<NodeMut<S>> {
        self.storage.node_mut(id)
    }

    /// Returns `true` if the graph contains a node with the given identifier.
    ///
    /// This is generally faster than calling `self.node(id).is_some()`.
    ///
    /// # Example
    ///
    /// ```
    /// # use petgraph_core::attributes::NoValue;
    /// # use petgraph_core::{GraphStorage, Node};
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// // we need to explicitly state the type of the edge weights, as we do insert
    /// // any edges and therefore cannot infer them.
    /// let mut graph = DiDinoGraph::<_, u8>::new();
    /// let a = *graph.insert_node(0).id();
    /// # let b = graph.storage().next_node_id(NoValue::new());
    ///
    /// assert!(graph.contains_node(&a));
    /// assert!(!graph.contains_node(&b));
    /// ```
    pub fn contains_node(&self, id: NodeId) -> bool {
        self.storage.contains_node(id)
    }

    /// Removes the node with the given identifier, if it exists.
    ///
    /// This will return the detached representation of the node, which can be used to reinsert the
    /// node into a new graph _or_ used to access any of the properties independently of the graph.
    ///
    /// # Example
    ///
    /// ```
    /// # use petgraph_core::attributes::NoValue;
    /// # use petgraph_core::{DetachedNode, GraphStorage, Node};
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// // we need to explicitly state the type of the edge weights, as we do insert
    /// // any edges and therefore cannot infer them.
    /// let mut graph = DiDinoGraph::<_, u8>::new();
    /// let a = *graph.insert_node(0).id();
    /// # let b = graph.storage().next_node_id(NoValue::new());
    ///
    /// assert_eq!(
    ///     graph.remove_node(&a),
    ///     Some(DetachedNode { id: a, weight: 0 })
    /// );
    /// assert_eq!(graph.remove_node(&a), None);
    /// assert_eq!(graph.remove_node(&b), None);
    /// ```
    pub fn remove_node(&mut self, id: NodeId) -> Option<DetachedNode<S::NodeWeight>> {
        self.storage.remove_node(id)
    }

    /// Returns the edge with the given identifier, if it exists.
    ///
    /// The returned [`Edge`] has a reference to the current graph, meaning that you're able to
    /// query the [`Node`] endpoints directly on the edge.
    ///
    /// # Example
    ///
    /// ```
    /// # use petgraph_core::attributes::NoValue;
    /// # use petgraph_core::{DetachedNode, GraphStorage, Node};
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// # let bc = graph.storage().next_edge_id(NoValue::new());
    ///
    /// assert_eq!(
    ///     graph
    ///         .edge(&ab)
    ///         .map(|edge| (*edge.id(), *edge.weight(), edge.endpoint_ids())),
    ///     Some((ab, u8::MAX, (&a, &b)))
    /// );
    /// assert!(graph.edge(&bc).is_none());
    /// ```
    pub fn edge(&self, id: EdgeId) -> Option<Edge<S>> {
        self.storage.edge(id)
    }

    /// Returns the edge, with a mutable weight, with the given identifier, if it exists.
    ///
    /// # Example
    ///
    /// ```
    /// # use petgraph_core::attributes::NoValue;
    /// # use petgraph_core::{DetachedNode, GraphStorage, Node};
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// # let bc = graph.storage().next_edge_id(NoValue::new());
    ///
    /// if let Some(mut edge) = graph.edge_mut(&ab) {
    ///     *edge.weight_mut() = u8::MAX - 1;
    /// }
    ///
    /// assert_eq!(
    ///     graph
    ///         .edge(&ab)
    ///         .map(|edge| (*edge.id(), *edge.weight(), edge.endpoint_ids())),
    ///     Some((ab, u8::MAX - 1, (&a, &b)))
    /// );
    /// assert!(graph.edge_mut(&bc).is_none());
    /// ```
    pub fn edge_mut(&mut self, id: EdgeId) -> Option<EdgeMut<S>> {
        self.storage.edge_mut(id)
    }

    /// Returns `true` if the graph contains an edge with the given identifier.
    ///
    /// This is generally faster than calling `self.edge(id).is_some()`.
    ///
    /// # Example
    ///
    /// ```
    /// # use petgraph_core::attributes::NoValue;
    /// # use petgraph_core::{DetachedNode, GraphStorage, Node};
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// # let bc = graph.storage().next_edge_id(NoValue::new());
    ///
    /// assert!(graph.contains_edge(&ab));
    /// assert!(!graph.contains_edge(&bc));
    /// ```
    pub fn contains_edge(&self, id: EdgeId) -> bool {
        self.storage.contains_edge(id)
    }

    /// Removes the edge with the given identifier, if it exists.
    ///
    /// This will return the detached representation of the edge, which can be used to reinsert the
    /// edge into a new graph _or_ used to access any of the properties independently of the graph.
    ///
    /// # Example
    ///
    /// ```
    /// # use petgraph_core::attributes::NoValue;
    /// # use petgraph_core::{DetachedEdge, DetachedNode, GraphStorage, Node};
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// # let bc = graph.storage().next_edge_id(NoValue::new());
    ///
    /// assert_eq!(
    ///     graph.remove_edge(&ab),
    ///     Some(DetachedEdge {
    ///         id: ab,
    ///         weight: u8::MAX,
    ///         u: a,
    ///         v: b,
    ///     })
    /// );
    /// assert_eq!(graph.remove_edge(&ab), None);
    /// assert_eq!(graph.remove_edge(&bc), None);
    /// ```
    pub fn remove_edge(&mut self, id: EdgeId) -> Option<DetachedEdge<S::EdgeWeight>> {
        self.storage.remove_edge(id)
    }

    /// Returns the neighbours of the node with the given identifier.
    ///
    /// This is an alias for [`Self::neighbours`], as there's a spelling difference between the
    /// American and British English.
    #[inline]
    pub fn neighbors(&self, id: NodeId) -> impl Iterator<Item = Node<'_, S>> {
        self.neighbours(id)
    }

    /// Returns the neighbours of the node with the given identifier.
    ///
    /// Returns an iterator over all nodes that are connected to the given node.
    /// In the case of a directed graph all edges (both incoming and outgoing) are taken into
    /// account.
    ///
    /// If the graph allows self-loops, and a self-loop exists, then the node will be returned
    /// as its own neighbour.
    ///
    /// The results won't be in any particular order.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let bc = *graph.insert_edge(u8::MAX - 1, &b, &c).id();
    /// let ca = *graph.insert_edge(u8::MAX - 2, &c, &a).id();
    /// let aa = *graph.insert_edge(u8::MAX - 3, &a, &a).id();
    ///
    /// assert_eq!(
    ///     graph
    ///         .neighbours(&a)
    ///         .map(|node| *node.id())
    ///         .collect::<HashSet<_>>(),
    ///     [a, b, c].into_iter().collect::<HashSet<_>>()
    /// );
    /// assert_eq!(
    ///     graph
    ///         .neighbours(&b)
    ///         .map(|node| *node.id())
    ///         .collect::<HashSet<_>>(),
    ///     [a, c].into_iter().collect::<HashSet<_>>()
    /// );
    /// ```
    pub fn neighbours(&self, id: NodeId) -> impl Iterator<Item = Node<'_, S>> {
        self.storage.node_neighbours(id)
    }

    /// Returns the neighbours of the node with the given identifier, with mutable weights.
    ///
    /// This is an alias for [`Self::neighbours_mut`], as there's a spelling difference between
    /// American and British English.
    #[inline]
    pub fn neighbors_mut(&mut self, id: NodeId) -> impl Iterator<Item = NodeMut<'_, S>> {
        self.neighbours_mut(id)
    }

    /// Returns the neighbours of the node with the given identifier, with mutable weights.
    ///
    /// Returns an iterator over all nodes that are connected to the given node.
    /// In the case of a directed graph all edges (both incoming and outgoing) are taken into
    /// account.
    ///
    /// If the graph allows self-loops, and a self-loop exists, then the node will be returned as
    /// well.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    /// let d = *graph.insert_node(3).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let bc = *graph.insert_edge(u8::MAX - 1, &b, &c).id();
    /// let ca = *graph.insert_edge(u8::MAX - 2, &c, &a).id();
    /// let aa = *graph.insert_edge(u8::MAX - 3, &a, &a).id();
    ///
    /// for mut node in graph.neighbours_mut(&a) {
    ///     *node.weight_mut() += 16;
    /// }
    ///
    /// assert_eq!(
    ///     graph
    ///         .neighbours(&a)
    ///         .map(|node| (*node.id(), *node.weight()))
    ///         .collect::<HashSet<_>>(),
    ///     [(a, 16), (b, 17), (c, 18)]
    ///         .into_iter()
    ///         .collect::<HashSet<_>>()
    /// );
    /// assert_eq!(
    ///     graph.node(&d).map(|node| (*node.id(), *node.weight())),
    ///     Some((d, 3))
    /// );
    /// ```
    pub fn neighbours_mut(&mut self, id: NodeId) -> impl Iterator<Item = NodeMut<'_, S>> {
        self.storage.node_neighbours_mut(id)
    }

    /// Returns the edges that are connected to the node with the given identifier.
    ///
    /// Returns an iterator over all edges that are connected to the given node.
    /// In the case of a directed graph this will return an iterator over all incoming and outgoing
    /// edges.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    /// let d = *graph.insert_node(3).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let bc = *graph.insert_edge(u8::MAX - 1, &b, &c).id();
    /// let ca = *graph.insert_edge(u8::MAX - 2, &c, &a).id();
    /// let aa = *graph.insert_edge(u8::MAX - 3, &a, &a).id();
    ///
    /// assert_eq!(
    ///     graph
    ///         .connections(&a)
    ///         .map(|edge| *edge.id())
    ///         .collect::<HashSet<_>>(),
    ///     [ab, ca, aa].into_iter().collect::<HashSet<_>>()
    /// );
    /// ```
    pub fn connections(&self, id: NodeId) -> impl Iterator<Item = Edge<'_, S>> {
        self.storage.node_connections(id)
    }

    /// Returns the edges that are connected to the node with the given identifier, with mutable
    /// weights.
    ///
    /// Returns an iterator over all edges that are connected to the given node.
    /// In the case of a directed graph this will return an iterator over all incoming and outgoing
    /// edges.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    /// let d = *graph.insert_node(3).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let bc = *graph.insert_edge(u8::MAX - 1, &b, &c).id();
    /// let ca = *graph.insert_edge(u8::MAX - 2, &c, &a).id();
    /// let aa = *graph.insert_edge(u8::MAX - 3, &a, &a).id();
    ///
    /// for mut edge in graph.connections_mut(&a) {
    ///     *edge.weight_mut() -= 16;
    /// }
    ///
    /// assert_eq!(
    ///     graph
    ///         .connections(&a)
    ///         .map(|edge| (*edge.id(), *edge.weight()))
    ///         .collect::<HashSet<_>>(),
    ///     [(ab, u8::MAX - 16), (ca, u8::MAX - 18), (aa, u8::MAX - 19)]
    ///         .into_iter()
    ///         .collect::<HashSet<_>>()
    /// );
    /// assert_eq!(
    ///     graph.edge(&bc).map(|edge| (*edge.id(), *edge.weight())),
    ///     Some((bc, u8::MAX - 1))
    /// );
    /// ```
    pub fn connections_mut(&mut self, id: NodeId) -> impl Iterator<Item = EdgeMut<'_, S>> {
        self.storage.node_connections_mut(id)
    }

    /// Returns the degree of the node with the given identifier.
    ///
    /// This is the number of edges that are connected to the given node, sometimes referred to as
    /// valency.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    /// let d = *graph.insert_node(3).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let bc = *graph.insert_edge(u8::MAX - 1, &b, &c).id();
    /// let ca = *graph.insert_edge(u8::MAX - 2, &c, &a).id();
    /// let aa = *graph.insert_edge(u8::MAX - 3, &a, &a).id();
    ///
    /// assert_eq!(graph.degree(&a), 3);
    /// assert_eq!(graph.degree(&b), 2);
    /// assert_eq!(graph.degree(&c), 2);
    /// assert_eq!(graph.degree(&d), 0);
    /// ```
    pub fn degree(&self, id: NodeId) -> usize {
        self.storage.node_degree(id)
    }

    // TODO: `map`, `filter`, `filter_map`, `find`, `reverse`, `any`, `all`, etc.

    /// Returns all edges that are between the given
    ///
    /// Returns an iterator over all edges that are between the given nodes.
    /// In the case of a directed graph this will return an iterator over both `u → v` and `v → u`.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id();
    /// let bc = *graph.insert_edge(u8::MAX - 2, &b, &c).id();
    ///
    /// assert_eq!(
    ///     graph
    ///         .edges_between(&a, &b)
    ///         .map(|edge| *edge.id())
    ///         .collect::<HashSet<_>>(),
    ///     [ab, ba].into_iter().collect::<HashSet<_>>()
    /// );
    /// ```
    pub fn edges_between(&self, u: NodeId, v: NodeId) -> impl Iterator<Item = Edge<'_, S>> {
        self.storage.edges_between(u, v)
    }

    /// Returns all edges that are between the given nodes, with mutable weights.
    ///
    /// Returns an iterator over all edges that are between the given nodes.
    /// In the case of a directed graph this will return an iterator over both `u → v` and `v → u`.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id();
    /// let bc = *graph.insert_edge(u8::MAX - 2, &b, &c).id();
    ///
    /// for mut edge in graph.edges_between_mut(&a, &b) {
    ///     *edge.weight_mut() -= 16;
    /// }
    ///
    /// assert_eq!(
    ///     graph
    ///         .edges()
    ///         .map(|edge| (*edge.id(), *edge.weight()))
    ///         .collect::<HashSet<_>>(),
    ///     [(ab, u8::MAX - 16), (ba, u8::MAX - 17), (bc, u8::MAX - 2),]
    ///         .into_iter()
    ///         .collect::<HashSet<_>>()
    /// );
    /// ```
    pub fn edges_between_mut(
        &mut self,
        u: NodeId,
        v: NodeId,
    ) -> impl Iterator<Item = EdgeMut<'_, S>> {
        self.storage.edges_between_mut(u, v)
    }

    /// Returns all nodes that have no edges connected to them.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id();
    ///
    /// assert_eq!(
    ///     graph
    ///         .isolated_nodes()
    ///         .map(|node| *node.id())
    ///         .collect::<HashSet<_>>(),
    ///     [c].into_iter().collect::<HashSet<_>>()
    /// );
    /// ```
    pub fn isolated_nodes(&self) -> impl Iterator<Item = Node<S>> {
        self.storage.isolated_nodes()
    }

    /// Returns all nodes that have no edges connected to them, with mutable weights.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id();
    ///
    /// for mut node in graph.isolated_nodes_mut() {
    ///     *node.weight_mut() += 16;
    /// }
    ///
    /// assert_eq!(
    ///     graph
    ///         .nodes()
    ///         .map(|node| (*node.id(), *node.weight()))
    ///         .collect::<HashSet<_>>(),
    ///     [(a, 0), (b, 1), (c, 18)]
    ///         .into_iter()
    ///         .collect::<HashSet<_>>()
    /// );
    /// ```
    pub fn isolated_nodes_mut(&mut self) -> impl Iterator<Item = NodeMut<S>> {
        self.storage.isolated_nodes_mut()
    }

    /// Returns an iterator over all nodes in the graph.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id();
    ///
    /// assert_eq!(
    ///     graph
    ///         .nodes()
    ///         .map(|node| (*node.id(), *node.weight()))
    ///         .collect::<HashSet<_>>(),
    ///     [(a, 0), (b, 1), (c, 2)].into_iter().collect::<HashSet<_>>()
    /// );
    /// ```
    pub fn nodes(&self) -> impl Iterator<Item = Node<S>> {
        self.storage.nodes()
    }

    /// Returns an iterator over all nodes in the graph, with mutable weights.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id();
    ///
    /// for mut node in graph.nodes_mut() {
    ///     *node.weight_mut() += 16;
    /// }
    ///
    /// assert_eq!(
    ///     graph
    ///         .nodes()
    ///         .map(|node| (*node.id(), *node.weight()))
    ///         .collect::<HashSet<_>>(),
    ///     [(a, 16), (b, 17), (c, 18)]
    ///         .into_iter()
    ///         .collect::<HashSet<_>>()
    /// );
    /// ```
    pub fn nodes_mut(&mut self) -> impl Iterator<Item = NodeMut<S>> {
        self.storage.nodes_mut()
    }

    /// Returns an iterator over all edges in the graph.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id();
    ///
    /// assert_eq!(
    ///     graph
    ///         .edges()
    ///         .map(|edge| (*edge.id(), *edge.weight()))
    ///         .collect::<HashSet<_>>(),
    ///     [(ab, u8::MAX), (ba, u8::MAX - 1)]
    ///         .into_iter()
    ///         .collect::<HashSet<_>>()
    /// );
    /// ```
    pub fn edges(&self) -> impl Iterator<Item = Edge<S>> {
        self.storage.edges()
    }

    /// Returns an iterator over all edges in the graph, with mutable weights.
    ///
    /// # Example
    ///
    /// ```
    /// # use std::collections::HashSet;
    /// use petgraph_dino::DiDinoGraph;
    ///
    /// let mut graph = DiDinoGraph::new();
    /// let a = *graph.insert_node(0).id();
    /// let b = *graph.insert_node(1).id();
    /// let c = *graph.insert_node(2).id();
    ///
    /// let ab = *graph.insert_edge(u8::MAX, &a, &b).id();
    /// let ba = *graph.insert_edge(u8::MAX - 1, &b, &a).id();
    ///
    /// for mut edge in graph.edges_mut() {
    ///     *edge.weight_mut() -= 16;
    /// }
    ///
    /// assert_eq!(
    ///     graph
    ///         .edges()
    ///         .map(|edge| (*edge.id(), *edge.weight()))
    ///         .collect::<HashSet<_>>(),
    ///     [(ab, u8::MAX - 16), (ba, u8::MAX - 17)]
    ///         .into_iter()
    ///         .collect::<HashSet<_>>()
    /// );
    /// ```
    pub fn edges_mut(&mut self) -> impl Iterator<Item = EdgeMut<S>> {
        self.storage.edges_mut()
    }
}