fuchsia / third_party / github.com / petgraph / petgraph / 5c8ab669a8618059f20989660e8423e97ac905af / . / crates / core / src / storage / mod.rs

//! Graph storage implementations. | |

//! | |

//! This module contains the various graph storage implementations that are used by the [`Graph`] | |

//! type. | |

//! | |

//! # Overview | |

//! | |

//! The [`GraphStorage`] type is split into multiple sub-traits, while trying to keep the number of | |

//! sub-traits to a minimum. | |

//! | |

//! These include: | |

//! - [`GraphStorage`]: The core trait that all graph storage implementations must implement, maps | |

//! to an undirected graph. | |

//! - [`DirectedGraphStorage`]: A trait for directed graph storage implementations. | |

//! - [`RetainableGraphStorage`]: A trait for retainable graph storage implementations. | |

//! - [`AuxiliaryGraphStorage`]: A trait to access storage for arbitrary additional data. | |

//! - [`SequentialGraphStorage`]: A trait for graph storage implementations that allow the mapping | |

//! of their internal indices to a set of linear indices. | |

//! | |

//! [`GraphStorage`] proposes that [`DirectedGraphStorage`] is simply a specialization of an | |

//! undirected graph, meaning that the supertrait of [`DirectedGraphStorage`] is also | |

//! [`GraphStorage`] and that all implementations of [`DirectedGraphStorage`] must also support | |

//! undirected graph operations. | |

//! | |

//! # Implementation Notes | |

//! | |

//! * [`RetainableGraphStorage`] is subject to removal during the alpha period. | |

//! * [`SequentialGraphStorage`] is subject to removal or rename during the alpha period. | |

//! * [`AuxiliaryGraphStorage`] is subject to removal or rename during the alpha period. | |

//! | |

//! [`Graph`]: crate::graph::Graph | |

mod directed; | |

pub mod auxiliary; | |

mod retain; | |

pub mod reverse; | |

pub mod sequential; | |

use error_stack::{Context, Result}; | |

pub use self::{ | |

auxiliary::AuxiliaryGraphStorage, directed::DirectedGraphStorage, | |

retain::RetainableGraphStorage, sequential::SequentialGraphStorage, | |

}; | |

use crate::{ | |

edge::{DetachedEdge, Edge, EdgeId, EdgeMut}, | |

node::{DetachedNode, Node, NodeId, NodeMut}, | |

}; | |

/// A trait for graph storage implementations. | |

/// | |

/// This trait is the core of the graph storage system, and is used to define the interface that all | |

/// graph storage implementations must implement. | |

/// | |

/// A [`GraphStorage`] is never used alone, but instead is used in conjunction with a [`Graph`], | |

/// which is a thin abstraction layer over the [`GraphStorage`]. | |

/// | |

/// This allows us to have multiple different graph storage implementations, while still having a | |

/// convenient interface with a minimal amount of boilerplate and functions to implement. | |

/// | |

/// You can instantiate a graph storage implementation directly, but it is recommended to use the | |

/// functions [`Graph::new`], [`Graph::new_in`], or [`Graph::with_capacity`] instead. | |

/// | |

/// # Capabilities | |

/// | |

/// > This is a template, which you should use to describe the capabilities of your graph storage | |

/// > implementation. | |

/// | |

/// | Capability | Note | | |

/// |------------------|-------------------| | |

/// | Node Identifiers | Arbitrary/Managed | | |

/// | Edge Identifiers | Arbitrary/Managed | | |

/// | Node Weights | ✓/✗ | | |

/// | Edge Weights | ✓/✗ | | |

/// | Parallel Edges | ✓/✗ | | |

/// | Self Loops | ✓/✗ | | |

/// | |

/// ## Space/Time Complexity | |

/// | |

/// > Optional, but recommended. | |

/// | |

/// | Operation | Time Complexity | Space Complexity | | |

/// |------------------|-----------------|------------------| | |

/// | Node By Id | | | | |

/// | Edge By Id | | | | |

/// | Edge Between | | | | |

/// | Contains Node | | | | |

/// | Contains Edge | | | | |

/// | Insert Node | | | | |

/// | Insert Edge | | | | |

/// | Remove Node | | | | |

/// | Remove Edge | | | | |

/// | Node Count | | | | |

/// | Edge Count | | | | |

/// | Node Iter | | | | |

/// | Edge Iter | | | | |

/// | Node Neighbours | | | | |

/// | Node Connections | | | | |

/// | External Nodes | | | | |

/// | |

/// ### Directed Graphs | |

/// | |

/// > Optional, but recommended. | |

/// | |

/// | Operation | Time Complexity | Space Complexity | | |

/// |-------------------------------|-----------------|------------------| | |

/// | Edge Between | | | | |

/// | Directed Edge Neighbours | | | | |

/// | Undirected Edge Neighbours | | | | |

/// | Directed Edge Connections | | | | |

/// | Undirected Edge Connections | | | | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<(), (), Directed>::new(); | |

/// # assert_eq!(storage.num_nodes(), 0); | |

/// # assert_eq!(storage.num_edges(), 0); | |

/// ``` | |

/// | |

/// [`Graph`]: crate::graph::Graph | |

/// [`Graph::new`]: crate::graph::Graph::new | |

/// [`Graph::new_in`]: crate::graph::Graph::new_in | |

/// [`Graph::with_capacity`]: crate::graph::Graph::with_capacity | |

pub trait GraphStorage: SequentialGraphStorage + AuxiliaryGraphStorage + Sized { | |

/// The weight of an edge. | |

/// | |

/// No constraints are enforced on this type (except that it needs to be `Sized`), but | |

/// implementations _may_ choose to enforce additional constraints, or limit the type to a | |

/// specific concrete type. | |

/// For example a graph that is unable to store any edge weights would choose to only support | |

/// `()`. | |

type EdgeWeight; | |

/// The error type used by the graph. | |

/// | |

/// Some operations on a graph may fail, for example during insertion of a node or edge. | |

/// This error (which needs to be an `error-stack` context) will be returned in a [`Report`] if | |

/// any of these operations fail. | |

/// | |

/// # Implementation Notes | |

/// | |

/// Instead of being able to specify a different error type for each operation, we only allow | |

/// for a single error type. | |

/// This is very intentional, as error-stack allows us to layer errors on top of each other, | |

/// meaning that a more specific error may be wrapped in this more general error type. | |

/// | |

/// [`Report`]: error_stack::Report | |

type Error: Context; | |

/// The weight of a node. | |

/// | |

/// No constraints are enforced on this type (except that it needs to be `Sized`), but | |

/// implementations _may_ choose to enforce additional constraints, or limit the type to a | |

/// specific concrete type. | |

/// For example a graph that is unable to store any node weights would choose to only support | |

/// `()`. | |

type NodeWeight; | |

/// Create a new graph storage with the given capacity. | |

/// | |

/// If the capacity is `None`, the implementation is free to choose a default capacity, or may | |

/// not allocate any memory at all. | |

/// | |

/// The semantics are the same as [`Vec::with_capacity`] or [`Vec::new`], where a capacity of | |

/// `None` should correspond to `Vec::new`, and a capacity of `Some(n)` should correspond to | |

/// `Vec::with_capacity(n)`. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::{DiDinoGraph, DinoStorage}; | |

/// | |

/// let storage = DinoStorage::<(), (), Directed>::new(); | |

/// # assert_eq!(storage.num_nodes(), 0); | |

/// # assert_eq!(storage.num_edges(), 0); | |

/// | |

/// // we need to explicitly state the type of the node and edge weights, as we do insert | |

/// // any nodes/edges and therefore cannot infer them. | |

/// let storage = DiDinoGraph::<(), ()>::with_capacity(Some(10), Some(10)); | |

/// # assert_eq!(storage.num_nodes(), 0); | |

/// # assert_eq!(storage.num_edges(), 0); | |

/// ``` | |

fn with_capacity(node_capacity: Option<usize>, edge_capacity: Option<usize>) -> Self; | |

/// Create a new graph storage from the given nodes and edges. | |

/// | |

/// This takes an iterator of nodes and edges, and tries to create a graph from them. | |

/// This is the reverse operation of [`Self::into_parts`], which converts the current graph | |

/// storage into an iterable of nodes and edges. | |

/// | |

/// This process is lossy, neither the node ids or the edge ids are guaranteed to be preserved. | |

/// This function only guarantees that the weights of the nodes and edges are preserved as well | |

/// as the structure of the graph. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// # let id = storage.next_node_id(NoValue::new()); | |

/// let a = *storage.insert_node(id, 1).unwrap().id(); | |

/// | |

/// # let id = storage.next_node_id(NoValue::new()); | |

/// let b = *storage.insert_node(id, 2).unwrap().id(); | |

/// | |

/// # let id = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(id, 3, &a, &b).unwrap(); | |

/// | |

/// assert_eq!(storage.num_nodes(), 2); | |

/// assert_eq!(storage.num_edges(), 1); | |

/// | |

/// let (nodes, edges) = storage.into_parts(); | |

/// | |

/// let storage = DinoStorage::<_, _, Directed>::from_parts(nodes, edges).unwrap(); | |

/// | |

/// assert_eq!(storage.num_nodes(), 2); | |

/// assert_eq!(storage.num_edges(), 1); | |

/// ``` | |

/// | |

/// # 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. | |

/// | |

/// The default implementation uses [`Self::insert_node`] and [`Self::insert_edge`] to insert | |

/// the nodes and edges, which are fallible. | |

/// The default implementation also works in a fail-slow manner, utilizing the `error-stack` | |

/// feature of extending errors with others. This means that even if multiple errors occur, all | |

/// of them will be returned, but has the potential downside of being slower in cases of | |

/// failures. | |

/// | |

/// Implementations may choose to override this default implementation, but should try to also | |

/// be fail-slow. | |

// TODO: additionally should return a mapping! | |

fn from_parts( | |

nodes: impl IntoIterator<Item = DetachedNode<Self::NodeWeight>>, | |

edges: impl IntoIterator<Item = DetachedEdge<Self::EdgeWeight>>, | |

) -> Result<Self, Self::Error> { | |

// TODO: rework this! | |

let nodes = nodes.into_iter(); | |

let edges = edges.into_iter(); | |

let (_, nodes_max) = nodes.size_hint(); | |

let (_, edges_max) = edges.size_hint(); | |

let mut graph = Self::with_capacity(nodes_max, edges_max); | |

// by default we try to fail slow, this way we can get as much data about potential errors | |

// as possible. | |

let mut result: Result<(), Self::Error> = Ok(()); | |

for node in nodes { | |

if let Err(error) = graph.insert_node(node.id, node.weight) { | |

match &mut result { | |

Err(errors) => errors.extend_one(error), | |

result => *result = Err(error), | |

} | |

} | |

} | |

result?; | |

// we need to ensure that all nodes are inserted before we insert edges, otherwise we might | |

// end up with invalid data (or redundant errors). | |

let mut result: Result<(), Self::Error> = Ok(()); | |

for edge in edges { | |

if let Err(error) = graph.insert_edge(edge.id, edge.weight, edge.u, edge.v) { | |

match &mut result { | |

Err(errors) => errors.extend_one(error), | |

result => *result = Err(error), | |

} | |

} | |

} | |

result.map(|()| graph) | |

} | |

/// Convert the current graph storage into an iterable of nodes and edges. | |

/// | |

/// This is the reverse operation of [`Self::from_parts`], which takes an iterable of nodes and | |

/// edges and tries to create a graph from them. | |

/// | |

/// The iterables returned by this function are not guaranteed to be in any particular order, | |

/// but must contain all nodes and edges. | |

/// The ids of said nodes and edges may also be changed during this operation, but the weights | |

/// of the nodes and edges must be the same. | |

/// | |

/// It must always hold true that using the iterables returned by this function to create a new | |

/// graph storage using [`Self::from_parts`] will result in a structurally identical graph and | |

/// that calling [`Self::from_parts`] on the same implementation that invoked | |

/// [`Self::into_parts`] must not error out. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use std::{collections::HashSet, iter::once}; | |

/// | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// # let id = storage.next_node_id(NoValue::new()); | |

/// let a = *storage.insert_node(id, 1).unwrap().id(); | |

/// | |

/// # let id = storage.next_node_id(NoValue::new()); | |

/// let b = *storage.insert_node(id, 2).unwrap().id(); | |

/// | |

/// # let id = storage.next_edge_id(NoValue::new()); | |

/// let ab = *storage.insert_edge(id, 3, &a, &b).unwrap().id(); | |

/// | |

/// assert_eq!(storage.num_nodes(), 2); | |

/// assert_eq!(storage.num_edges(), 1); | |

/// | |

/// let (nodes, edges) = storage.into_parts(); | |

/// | |

/// let node_ids: HashSet<_> = nodes.map(|detached_node| detached_node.id).collect(); | |

/// let edge_ids: HashSet<_> = edges.map(|detached_edge| detached_edge.id).collect(); | |

/// | |

/// assert_eq!(node_ids, [a, b].into_iter().collect()); | |

/// assert_eq!(edge_ids, once(ab).collect()); | |

/// ``` | |

fn into_parts( | |

self, | |

) -> ( | |

impl Iterator<Item = DetachedNode<Self::NodeWeight>>, | |

impl Iterator<Item = DetachedEdge<Self::EdgeWeight>>, | |

); | |

/// Returns the number of nodes in the graph. | |

/// | |

/// This is equivalent to [`Self::nodes`].`count()`. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<(), (), Directed>::new(); | |

/// | |

/// # let id = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(id, ()).unwrap(); | |

/// | |

/// assert_eq!(storage.num_nodes(), 1); | |

/// | |

/// # let id = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(id, ()).unwrap(); | |

/// | |

/// assert_eq!(storage.num_nodes(), 2); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// This is a default implementation, which uses [`Self::nodes`].`count()`, custom | |

/// implementations, should if possible, override this. | |

fn num_nodes(&self) -> usize { | |

self.nodes().count() | |

} | |

/// Returns the number of edges in the graph. | |

/// | |

/// This is equivalent to [`Self::edges`].`count()`. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<(), (), Directed>::new(); | |

/// | |

/// # let id = storage.next_node_id(NoValue::new()); | |

/// # let a = *storage.insert_node(id, ()).unwrap().id(); | |

/// # | |

/// # let id = storage.next_node_id(NoValue::new()); | |

/// # let b = *storage.insert_node(id, ()).unwrap().id(); | |

/// # | |

/// # let id = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(id, (), &a, &b).unwrap(); | |

/// assert_eq!(storage.num_edges(), 1); | |

/// # | |

/// # let id = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(id, (), &a, &b).unwrap(); | |

/// # | |

/// assert_eq!(storage.num_edges(), 2); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// This is a default implementation, which uses [`Self::edges`].`count()`, custom | |

/// implementations, should if possible, override this. | |

fn num_edges(&self) -> usize { | |

self.edges().count() | |

} | |

/// Return the next node identifier for the given attribute. | |

/// | |

/// This is used to generate new node identifiers and should not be called by a user directly | |

/// and is instead used by the [`Graph`] type to generate a new identifier that is then used | |

/// during [`Graph::insert_node`]. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{attributes::NoValue, edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<(), (), Directed>::new(); | |

/// | |

/// // `DinoStorage` uses `ManagedGraphId` for both node and edge identifiers, | |

/// // so we must use `NoValue` here. | |

/// let a = storage.next_node_id(NoValue::new()); | |

/// let b = storage.next_node_id(NoValue::new()); | |

/// | |

/// assert_eq!(a, b); | |

/// | |

/// storage.insert_node(a, ()).unwrap(); | |

/// | |

/// let c = storage.next_node_id(NoValue::new()); | |

/// | |

/// assert_ne!(a, c); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// When implementing this function, it is important to ensure that the returned identifier is | |

/// stable, and unique and must ensure that the returned identifier is not already in use. | |

/// | |

/// Stable meaning that repeated calls to this function (without any other changes to the graph) | |

/// should return the same identifier. | |

/// | |

/// The implementation of this function must also be fast, as it is called every time a new node | |

/// is inserted and must be pure, meaning that it must not have any side-effects. | |

fn next_node_id(&self) -> NodeId; | |

/// Inserts a new node into the graph. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{attributes::NoValue, edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, (), Directed>::new(); | |

/// | |

/// // `DinoStorage` uses `ManagedGraphId` for both node and edge identifiers, | |

/// // so we must use `NoValue` here. | |

/// let id = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(id, 1).unwrap(); | |

/// # | |

/// # assert_eq!(storage.node(&id).unwrap().weight(), &1); | |

/// ``` | |

/// | |

/// # Errors | |

/// | |

/// Returns an error if a node with the given identifier already exists, or if any of the | |

/// constraints (depending on the implementation) are violated. | |

fn insert_node( | |

&mut self, | |

id: NodeId, | |

weight: Self::NodeWeight, | |

) -> Result<NodeMut<Self>, Self::Error>; | |

/// Return the next edge identifier for the given attribute. | |

/// | |

/// This is used to generate new edge identifiers and should not be called by a user directly | |

/// and is instead used by the [`Graph`] type to generate a new identifier that is then used | |

/// during [`Graph::insert_edge`]. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{attributes::NoValue, edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, (), Directed>::new(); | |

/// | |

/// // `DinoStorage` uses `ManagedGraphId` for both node and edge identifiers, | |

/// // so we must use `NoValue` here. | |

/// let id = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(id, 1).unwrap(); | |

/// # | |

/// # assert_eq!(storage.node(&id).unwrap().weight(), &1); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// All the same notes as [`Self::next_node_id`] apply here as well. | |

/// | |

/// [`Graph`]: crate::graph::Graph | |

/// [`Graph::insert_edge`]: crate::graph::Graph::insert_edge | |

fn next_edge_id(&self) -> EdgeId; | |

/// Inserts a new edge into the graph. | |

/// | |

/// If the storage implementation is undirected `u` and `v` are interchangeable, but if the | |

/// storage implementation is directed `u` is the source and `v` is the target. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{attributes::NoValue, edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// # storage.insert_node(a, 1).unwrap(); | |

/// # | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// # storage.insert_node(b, 2).unwrap(); | |

/// | |

/// // `DinoStorage` uses `ManagedGraphId` for both node and edge identifiers, | |

/// // so we must use `NoValue` here. | |

/// let id = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(id, 3, &a, &b).unwrap(); | |

/// # | |

/// # assert_eq!(storage.edge(&id).unwrap().weight(), &3); | |

/// ``` | |

/// | |

/// # Errors | |

/// | |

/// Returns an error if parallel edges are not allowed, or any of the constraints (depending on | |

/// the implementation) are violated. | |

/// These constraints _may_ include that an edge between the source and target already exist, | |

/// but some implementations may choose to allow parallel edges. | |

fn insert_edge( | |

&mut self, | |

id: EdgeId, | |

weight: Self::EdgeWeight, | |

u: NodeId, | |

v: NodeId, | |

) -> Result<EdgeMut<Self>, Self::Error>; | |

/// Removes the node with the given identifier from the graph. | |

/// | |

/// This will return [`None`] if the node does not exist, and will return the detached node if | |

/// it does. | |

/// | |

/// Calling this function will also remove all edges that are connected to the node, but will | |

/// not return those detached edges. | |

/// | |

/// To also return the detached edges that were removed, use a combination of | |

/// [`Self::node_connections`], [`Self::remove_edge`] and [`Self::remove_node`] instead. | |

/// | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{attributes::NoValue, edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// | |

/// let removed = storage.remove_node(&a).unwrap(); | |

/// assert_eq!(removed.id, a); | |

/// assert_eq!(removed.weight, 1); | |

/// # | |

/// # assert_eq!(storage.num_nodes(), 0); | |

/// ``` | |

/// | |

/// ## Return Node with Edges | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 3, &a, &b).unwrap(); | |

/// | |

/// let connections: Vec<_> = storage | |

/// .node_connections(&a) | |

/// .map(|edge| *edge.id()) | |

/// .collect(); | |

/// # | |

/// # assert_eq!(connections, [ab]); | |

/// | |

/// for edge in connections { | |

/// // do something with the detached edge | |

/// storage.remove_edge(&edge).unwrap(); | |

/// } | |

/// | |

/// storage.remove_node(&a).unwrap(); | |

/// ``` | |

fn remove_node(&mut self, id: NodeId) -> Option<DetachedNode<Self::NodeWeight>>; | |

/// Removes the edge with the given identifier from the graph. | |

/// | |

/// This will return [`None`] if the edge does not exist, and will return the detached edge if | |

/// it existed. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 3, &a, &b).unwrap(); | |

/// | |

/// let removed = storage.remove_edge(&ab).unwrap(); | |

/// assert_eq!(removed.id, ab); | |

/// assert_eq!(removed.weight, 3); | |

/// # | |

/// # assert_eq!(storage.num_edges(), 0); | |

/// ``` | |

fn remove_edge(&mut self, id: EdgeId) -> Option<DetachedEdge<Self::EdgeWeight>>; | |

/// Clears the graph, removing all nodes and edges. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 3, &a, &b).unwrap(); | |

/// | |

/// storage.clear(); | |

/// # | |

/// # assert_eq!(storage.num_nodes(), 0); | |

/// # assert_eq!(storage.num_edges(), 0); | |

/// ``` | |

fn clear(&mut self); | |

/// Returns the node with the given identifier. | |

/// | |

/// This will return [`None`] if the node does not exist, and will return the node if it does. | |

/// | |

/// The [`Node`] type returned by this function contains a reference to the current graph, | |

/// meaning you are able to query for e.g. the neighours of the node. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// | |

/// let node = storage.node(&a).unwrap(); | |

/// | |

/// assert_eq!(node.id(), &a); | |

/// assert_eq!(node.weight(), &1); | |

/// | |

/// // This will access the underlying storage, and is equivalent to `storage.neighbours(&a)`. | |

/// assert_eq!(node.neighbours().count(), 0); | |

/// ``` | |

fn node(&self, id: NodeId) -> Option<Node<Self>>; | |

/// Returns the node, with a mutable weight, with the given identifier. | |

/// | |

/// This will return [`None`] if the node does not exist, and will return the node if it does. | |

/// | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// | |

/// let node = storage.node_mut(&a).unwrap(); | |

/// | |

/// assert_eq!(node.id(), &a); | |

/// assert_eq!(node.weight(), &mut 1); | |

/// ``` | |

fn node_mut(&mut self, id: NodeId) -> Option<NodeMut<Self>>; | |

/// Checks if the node with the given identifier exists. | |

/// | |

/// This is equivalent to [`Self::node`].`is_some()`. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// | |

/// assert!(storage.contains_node(&a)); | |

/// assert!(!storage.contains_node(&b)); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation simply checks if [`Self::node`] returns [`Some`], but if | |

/// possible, custom implementations that are able to do this more efficiently should override | |

/// this. | |

fn contains_node(&self, id: NodeId) -> bool { | |

self.node(id).is_some() | |

} | |

/// Returns the edge with the given identifier, if it exists. | |

/// | |

/// This will return [`None`] if the edge does not exist, and will return the edge if it does. | |

/// | |

/// The [`Edge`] type returned by this function contains a reference to the current graph, | |

/// meaning that continued exploration of the graph is possible. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 3, &a, &b).unwrap(); | |

/// | |

/// let edge = storage.edge(&ab).unwrap(); | |

/// assert_eq!(edge.weight(), &3); | |

/// | |

/// assert_eq!(edge.source_id(), &a); | |

/// // This will request the target from underlying storage, | |

/// // meaning if one only wants to retrieve the id it is faster | |

/// // to just use `edge.source_id()`. | |

/// // Because `self.node()` returns an `Option`, so will `edge.source()`. | |

/// assert_eq!(edge.source().id(), &a); | |

/// assert_eq!(edge.source().weight(), &1); | |

/// | |

/// assert_eq!(edge.target_id(), &b); | |

/// // This will request the target from underlying storage, | |

/// // meaning if one only wants to retrieve the id it is faster | |

/// // to just use `edge.target_id()`. | |

/// // Because `self.node()` returns an `Option`, so will `edge.target()`. | |

/// assert_eq!(edge.target().id(), &b); | |

/// assert_eq!(edge.target().weight(), &2); | |

/// ``` | |

fn edge(&self, id: EdgeId) -> Option<Edge<Self>>; | |

/// Returns the edge, with a mutable weight, with the given identifier, if it exists. | |

/// | |

/// This will return [`None`] if the edge does not exist, and will return the edge if it does. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 3, &a, &b).unwrap(); | |

/// | |

/// let mut edge = storage.edge_mut(&ab).unwrap(); | |

/// | |

/// assert_eq!(edge.weight(), &mut 3); | |

/// assert_eq!(edge.source_id(), &a); | |

/// assert_eq!(edge.target_id(), &b); | |

/// | |

/// *edge.weight_mut() = 4; | |

/// | |

/// assert_eq!(storage.edge(&ab).unwrap().weight(), &4); | |

/// ``` | |

fn edge_mut(&mut self, id: EdgeId) -> Option<EdgeMut<Self>>; | |

/// Checks if the edge with the given identifier exists. | |

/// | |

/// This is equivalent to [`Self::edge`].`is_some()`. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 3, &a, &b).unwrap(); | |

/// # let ba = storage.next_edge_id(NoValue::new()); | |

/// | |

/// assert!(storage.contains_edge(&ab)); | |

/// assert!(!storage.contains_edge(&ba)); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation simply checks if [`Self::edge`] returns [`Some`], but if | |

/// possible, custom implementations that are able to do this more efficiently should override | |

/// this. | |

fn contains_edge(&self, id: EdgeId) -> bool { | |

self.edge(id).is_some() | |

} | |

/// Returns an iterator over all edges between the two given nodes. | |

/// | |

/// This will return an iterator over all edges between the two given nodes. The output will | |

/// include all undirected edges between the two nodes, this means that for a directed graph | |

/// both the forward and reverse edges will be included. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 3, &a, &b).unwrap(); | |

/// # let ba = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ba, 4, &b, &a).unwrap(); | |

/// | |

/// assert_eq!( | |

/// storage | |

/// .edges_between(&a, &b) | |

/// .map(|edge| *edge.id()) | |

/// .collect::<Vec<_>>(), | |

/// [ab, ba] | |

/// ); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation simply calls [`Self::node_connections`] on both nodes and then | |

/// chains those, after filtering for the respective end. Most implementations should be able to | |

/// provide a more efficient implementation. | |

fn edges_between(&self, u: NodeId, v: NodeId) -> impl Iterator<Item = Edge<'_, Self>> { | |

// How does this work with a default implementation? | |

let from_source = self.node_connections(u).filter(move |edge| { | |

let (edge_u, edge_v) = edge.endpoint_ids(); | |

let other = if edge_u == u { edge_v } else { edge_u }; | |

other == v | |

}); | |

let from_target = self.node_connections(v).filter(move |edge| { | |

let (edge_u, edge_v) = edge.endpoint_ids(); | |

// we exclude self-loops here as they are already included in `from_source` | |

let other = if edge_u == v { edge_v } else { edge_u }; | |

other == u && edge_u != edge_v | |

}); | |

from_source.chain(from_target) | |

} | |

/// Returns an iterator over all edges between the two given nodes, with mutable weights. | |

/// | |

/// This will return an iterator over all edges between the two given nodes. The output will | |

/// include all undirected edges between the two nodes, this means that for a directed graph | |

/// both the forward and reverse edges will be included. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 3, &a, &b).unwrap(); | |

/// # let ba = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ba, 4, &b, &a).unwrap(); | |

/// | |

/// for mut edge in storage.edges_between_mut(&a, &b) { | |

/// *edge.weight_mut() += 1; | |

/// } | |

/// | |

/// assert_eq!( | |

/// storage | |

/// .edges_between(&a, &b) | |

/// .map(|mut edge| *edge.weight()) | |

/// .collect::<Vec<_>>(), | |

/// [4, 5] | |

/// ); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// Due to the fact that this function returns mutable references to the edges, it is not | |

/// possible to easily provide a default implementation for this function, as a call to | |

/// [`Self::node_connections_mut`] for `source` and `target` would lead to a double mutable | |

/// borrow. | |

// I'd love to provide a default implementation for this, but I just can't get it to work. | |

fn edges_between_mut( | |

&mut self, | |

u: NodeId, | |

v: NodeId, | |

) -> impl Iterator<Item = EdgeMut<'_, Self>>; | |

/// Returns an iterator over all edges that are connected to the given node. | |

/// | |

/// This will return an iterator over all edges that are connected to the given node. | |

/// This includes all edges, meaning that for a directed graph both the incoming and outgoing | |

/// edges will be included. | |

/// | |

/// There may be multiple edges between two nodes, if the implementation allows for parallel | |

/// edges. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # let c = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(c, 3).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 4, &a, &b).unwrap(); | |

/// # let ca = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ca, 5, &c, &a).unwrap(); | |

/// | |

/// assert_eq!( | |

/// storage | |

/// .node_connections(&a) | |

/// .map(|mut edge| *edge.id()) | |

/// .collect::<Vec<_>>(), | |

/// [ab, ca] | |

/// ); | |

/// ``` | |

fn node_connections(&self, id: NodeId) -> impl Iterator<Item = Edge<'_, Self>>; | |

/// Returns an iterator over all edges that are connected to the given node, with mutable | |

/// weights. | |

/// | |

/// This will return an iterator over all edges that are connected to the given node. | |

/// This includes all edges, meaning that for a directed graph both the incoming and outgoing | |

/// edges will be included. | |

/// | |

/// There may be multiple edges between two nodes, if the implementation allows for parallel | |

/// edges. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # let c = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(c, 3).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 4, &a, &b).unwrap(); | |

/// # let ca = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ca, 5, &c, &a).unwrap(); | |

/// | |

/// for mut edge in storage.node_connections_mut(&a) { | |

/// *edge.weight_mut() += 1; | |

/// } | |

/// | |

/// assert_eq!( | |

/// storage | |

/// .node_connections(&a) | |

/// .map(|mut edge| *edge.weight()) | |

/// .collect::<Vec<_>>(), | |

/// [5, 6] | |

/// ); | |

/// ``` | |

fn node_connections_mut(&mut self, id: NodeId) -> impl Iterator<Item = EdgeMut<'_, Self>>; | |

/// Returns the number of edges that are connected to the given node. | |

/// | |

/// This is also commonly known as the degree or valency of the node. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # let c = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(c, 3).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 4, &a, &b).unwrap(); | |

/// # let ca = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ca, 5, &c, &a).unwrap(); | |

/// | |

/// assert_eq!(storage.node_degree(&a), 2); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation simply calls [`Self::node_connections`] and counts the number of | |

/// edges. | |

/// This is unlikely to be the most efficient implementation, so custom implementations should | |

/// override this. | |

fn node_degree(&self, id: NodeId) -> usize { | |

self.node_connections(id).count() | |

} | |

/// Returns an iterator over all nodes that are connected to the given node. | |

/// | |

/// This will return an iterator over all nodes that are connected to the given node. | |

/// This includes all nodes, meaning that for a directed graph both the incoming and outgoing | |

/// edges are taken into account. | |

/// | |

/// If the graph allows for parallel edges, the same node **SHOULD NOT** be returned multiple | |

/// times, if an implementation allows for self-loops, the given node may also be returned. | |

/// | |

/// The results won't be in any particular order, any order should be considered an | |

/// implementation detail of the storage implementation. | |

/// | |

/// > **Note**: For more information of **SHOULD NOT** visit [RFC 2119](https://www.ietf.org/rfc/rfc2119.txt). | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # let c = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(c, 3).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 4, &a, &b).unwrap(); | |

/// # let ca = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ca, 5, &c, &a).unwrap(); | |

/// | |

/// assert_eq!( | |

/// storage | |

/// .node_neighbours(&a) | |

/// .map(|node| *node.id()) | |

/// .collect::<Vec<_>>(), | |

/// [b, c] | |

/// ); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// Implementations should try to provide a more efficient implementation than the default one, | |

/// and must uphold the contract that the returned iterator does not contain duplicates. | |

/// | |

/// Due to it's allocation free nature, the default implementation currently returns an iterator | |

/// that may contain duplicates and is based on [`Self::node_connections`]. | |

/// | |

/// Changing the requirement from **SHOULD NOT** to **MUST NOT** may occur in the future, and is | |

/// to be considered a breaking change. | |

fn node_neighbours(&self, id: NodeId) -> impl Iterator<Item = Node<'_, Self>> { | |

self.node_connections(id) | |

.filter_map(move |edge: Edge<Self>| { | |

let (u, v) = edge.endpoint_ids(); | |

// doing it this way allows us to also get ourselves as a neighbour if we have a | |

// self-loop | |

if u == id { self.node(v) } else { self.node(u) } | |

}) | |

} | |

/// Returns an iterator over all nodes that are connected to the given node, with mutable | |

/// weights. | |

/// | |

/// This will return an iterator over all nodes that are connected to the given node. | |

/// This includes all nodes, meaning that for a directed graph both the incoming and outgoing | |

/// edges are taken into account. | |

/// | |

/// If the graph allows for parallel edges, the same node **MUST NOT** be returned multiple | |

/// times. | |

/// | |

/// > **Note**: For more information of **MUST NOT** visit [RFC 2119](https://www.ietf.org/rfc/rfc2119.txt). | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # let c = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(c, 3).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 4, &a, &b).unwrap(); | |

/// # let ca = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ca, 5, &c, &a).unwrap(); | |

/// | |

/// for mut node in storage.node_neighbours_mut(&a) { | |

/// *node.weight_mut() += 1; | |

/// } | |

/// | |

/// assert_eq!( | |

/// storage | |

/// .node_neighbours(&a) | |

/// .map(|node| *node.weight()) | |

/// .collect::<Vec<_>>(), | |

/// [3, 4] | |

/// ); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// No default implementation is provided, as a mutable iterator based on | |

/// [`Self::node_connections_mut`] could potentially lead to a double mutable borrow. | |

fn node_neighbours_mut(&mut self, id: NodeId) -> impl Iterator<Item = NodeMut<'_, Self>>; | |

/// Returns an iterator over all nodes that do not have any edges connected to them. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # let c = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(c, 3).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 4, &a, &b).unwrap(); | |

/// | |

/// let isolated_nodes: Vec<_> = storage.isolated_nodes().map(|node| *node.id()).collect(); | |

/// | |

/// assert_eq!(isolated_nodes, [c]); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation is based on [`Self::nodes`], and filters out all nodes that have | |

/// no edges via [`Self::node_neighbours`]. | |

/// This is quite inefficient, and implementations should try to provide a more efficient | |

/// implementation if possible. | |

fn isolated_nodes(&self) -> impl Iterator<Item = Node<Self>> { | |

self.nodes().filter(|node| self.node_degree(node.id()) == 0) | |

} | |

/// Returns an iterator over all nodes that do not have any edges connected to them, with | |

/// mutable weights. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # let c = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(c, 3).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 4, &a, &b).unwrap(); | |

/// | |

/// for mut external in storage.isolated_nodes_mut() { | |

/// *external.weight_mut() += 1; | |

/// } | |

/// | |

/// assert_eq!(storage.node(&c).unwrap().weight(), &4); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// No default implementation is provided, as a mutable iterator based on [`Self::nodes_mut`] | |

/// and [`Self::node_neighbours`] would lead to a mutable borrow of the storage implementation | |

/// followed by a shared borrow, which is not allowed. | |

fn isolated_nodes_mut(&mut self) -> impl Iterator<Item = NodeMut<Self>>; | |

/// Returns an iterator over all nodes in the graph. | |

/// | |

/// This **MUST** return all nodes in the graph, and **MUST NOT** return the same node multiple | |

/// times. | |

/// | |

/// > **Note**: For more information of **MUST** and **MUST NOT** visit [RFC 2119](https://www.ietf.org/rfc/rfc2119.txt). | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # let c = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(c, 3).unwrap(); | |

/// | |

/// assert_eq!( | |

/// storage.nodes().map(|node| *node.id()).collect::<Vec<_>>(), | |

/// [a, b, c] | |

/// ); | |

/// ``` | |

fn nodes(&self) -> impl Iterator<Item = Node<Self>>; | |

/// Returns an iterator over all nodes in the graph, with mutable weights. | |

/// | |

/// This **MUST** return all nodes in the graph, and **MUST NOT** return the same node multiple | |

/// times. | |

/// | |

/// > **Note**: For more information of **MUST** and **MUST NOT** visit [RFC 2119](https://www.ietf.org/rfc/rfc2119.txt). | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # let c = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(c, 3).unwrap(); | |

/// | |

/// for mut node in storage.nodes_mut() { | |

/// *node.weight_mut() += 1; | |

/// } | |

/// | |

/// assert_eq!( | |

/// storage | |

/// .nodes() | |

/// .map(|node| *node.weight()) | |

/// .collect::<Vec<_>>(), | |

/// [2, 3, 4] | |

/// ); | |

/// ``` | |

fn nodes_mut(&mut self) -> impl Iterator<Item = NodeMut<Self>>; | |

/// Returns an iterator over all edges in the graph. | |

/// | |

/// This **MUST** return all edges in the graph, and **MUST NOT** return the same edge multiple | |

/// times. | |

/// | |

/// > **Note**: For more information of **MUST** and **MUST NOT** visit [RFC 2119](https://www.ietf.org/rfc/rfc2119.txt). | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # let c = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(c, 3).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 4, &a, &b).unwrap(); | |

/// # let ca = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ca, 5, &c, &a).unwrap(); | |

/// | |

/// assert_eq!( | |

/// storage.edges().map(|edge| *edge.id()).collect::<Vec<_>>(), | |

/// [ab, ca] | |

/// ); | |

/// ``` | |

fn edges(&self) -> impl Iterator<Item = Edge<Self>>; | |

/// Returns an iterator over all edges in the graph, with mutable weights. | |

/// | |

/// This **MUST** return all edges in the graph, and **MUST NOT** return the same edge multiple | |

/// times. | |

/// | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// # | |

/// # let a = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(a, 1).unwrap(); | |

/// # let b = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(b, 2).unwrap(); | |

/// # let c = storage.next_node_id(NoValue::new()); | |

/// storage.insert_node(c, 3).unwrap(); | |

/// | |

/// # let ab = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ab, 4, &a, &b).unwrap(); | |

/// # let ca = storage.next_edge_id(NoValue::new()); | |

/// storage.insert_edge(ca, 5, &c, &a).unwrap(); | |

/// | |

/// for mut edge in storage.edges_mut() { | |

/// *edge.weight_mut() += 1; | |

/// } | |

/// | |

/// assert_eq!( | |

/// storage | |

/// .edges() | |

/// .map(|edge| *edge.weight()) | |

/// .collect::<Vec<_>>(), | |

/// [5, 6] | |

/// ); | |

/// ``` | |

fn edges_mut(&mut self) -> impl Iterator<Item = EdgeMut<Self>>; | |

/// Reserves capacity for at least `additional_nodes` nodes and `additional_edges` edges. | |

/// | |

/// This will reserve capacity for at least `additional_nodes` nodes and `additional_edges`, but | |

/// may reserve more. | |

/// This function **MUST NOT** change the number of nodes or edges in the graph. | |

/// A storage implementation **MAY** decide to not reserve any additional capacity. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// storage.reserve(16, 16); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation calls [`Self::reserve_nodes`] and [`Self::reserve_edges`]. | |

fn reserve(&mut self, additional_nodes: usize, additional_edges: usize) { | |

self.reserve_nodes(additional_nodes); | |

self.reserve_edges(additional_edges); | |

} | |

/// Reserves capacity for at least `additional_nodes` nodes. | |

/// | |

/// This will reserve capacity for at least `additional_nodes` nodes, but may reserve more. | |

/// This function **MUST NOT** change the number of nodes in the graph. | |

/// A storage implementation **MAY** decide to not reserve any additional capacity. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// storage.reserve_nodes(16); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation does not reserve any additional capacity, and is simply empty. | |

/// Implementations that wish to support resizing should override this. | |

#[allow(unused_variables)] | |

fn reserve_nodes(&mut self, additional: usize) {} | |

/// Reserves capacity for at least `additional_edges` edges. | |

/// | |

/// This will reserve capacity for at least `additional_edges` edges, but may reserve more. | |

/// This function **MUST NOT** change the number of edges in the graph. | |

/// A storage implementation **MAY** decide to not reserve any additional capacity. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// storage.reserve_edges(16); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation does not reserve any additional capacity, and is simply empty. | |

/// Implementations that wish to support resizing should override this. | |

#[allow(unused_variables)] | |

fn reserve_edges(&mut self, additional: usize) {} | |

/// Reserves the minimum capacity for exactly `additional_nodes` nodes and `additional_edges` | |

/// | |

/// This will reserve the minimum capacity for exactly `additional_nodes` nodes and | |

/// `additional_edges` edges. | |

/// | |

/// This function **MUST NOT** change the number of nodes or edges in the graph. | |

/// A storage implementation **MAY** decide to not reserve any additional capacity. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// storage.reserve_exact(16, 16); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation calls [`Self::reserve_exact_nodes`] and | |

/// [`Self::reserve_exact_edges`]. | |

fn reserve_exact(&mut self, additional_nodes: usize, additional_edges: usize) { | |

self.reserve_exact_nodes(additional_nodes); | |

self.reserve_exact_edges(additional_edges); | |

} | |

/// Reserves the minimum capacity for exactly `additional_nodes` nodes. | |

/// | |

/// This will reserve the minimum capacity for exactly `additional_nodes` nodes. | |

/// | |

/// This function **MUST NOT** change the number of nodes in the graph. | |

/// A storage implementation **MAY** decide to not reserve any additional capacity. | |

/// | |

/// The implementation may try to not deliberately over-allocate, but this is not required, | |

/// should frequent insertions be expected prefer [`Self::reserve_nodes`]. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// storage.reserve_exact_nodes(16); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation forwards to [`Self::reserve_nodes`]. | |

fn reserve_exact_nodes(&mut self, additional: usize) { | |

self.reserve_nodes(additional); | |

} | |

/// Reserves the minimum capacity for exactly `additional_edges` edges. | |

/// | |

/// This will reserve the minimum capacity for exactly `additional_edges` edges. | |

/// | |

/// This function **MUST NOT** change the number of edges in the graph. | |

/// A storage implementation **MAY** decide to not reserve any additional capacity. | |

/// | |

/// The implementation may try to not deliberately over-allocate, but this is not required, | |

/// should frequent insertions be expected prefer [`Self::reserve_edges`]. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// storage.reserve_exact_edges(16); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation forwards to [`Self::reserve_edges`]. | |

fn reserve_exact_edges(&mut self, additional: usize) { | |

self.reserve_edges(additional); | |

} | |

/// Shrinks the capacity of the storage as much as possible. | |

/// | |

/// This will shrink the capacity of the storage as much as possible. | |

/// | |

/// This function **MUST NOT** change the number of nodes or edges in the graph. | |

/// A storage implementation **MAY** decide to not shrink the capacity at all. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// storage.reserve(16, 16); | |

/// storage.shrink_to_fit(); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation calls [`Self::shrink_to_fit_nodes`] and | |

/// [`Self::shrink_to_fit_edges`]. | |

fn shrink_to_fit(&mut self) { | |

self.shrink_to_fit_nodes(); | |

self.shrink_to_fit_edges(); | |

} | |

/// Shrinks the capacity of the node storage as much as possible. | |

/// | |

/// This will shrink the capacity of the node storage as much as possible. | |

/// | |

/// This function **MUST NOT** change the number of nodes in the graph. | |

/// A storage implementation **MAY** decide to not shrink the capacity at all. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// storage.reserve_nodes(16); | |

/// storage.shrink_to_fit_nodes(); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation does not shrink the capacity at all and is effectively a no-op. | |

/// Implementations that wish to support resizing should override this. | |

fn shrink_to_fit_nodes(&mut self) {} | |

/// Shrinks the capacity of the edge storage as much as possible. | |

/// | |

/// This will shrink the capacity of the edge storage as much as possible. | |

/// | |

/// This function **MUST NOT** change the number of edges in the graph. | |

/// A storage implementation **MAY** decide to not shrink the capacity at all. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// # use petgraph_core::attributes::NoValue; | |

/// use petgraph_core::{edge::marker::Directed, storage::GraphStorage}; | |

/// use petgraph_dino::DinoStorage; | |

/// | |

/// let mut storage = DinoStorage::<u8, u8, Directed>::new(); | |

/// | |

/// storage.reserve_edges(16); | |

/// storage.shrink_to_fit_edges(); | |

/// ``` | |

/// | |

/// # Implementation Notes | |

/// | |

/// The default implementation does not shrink the capacity at all and is effectively a no-op. | |

/// Implementations that wish to support resizing should override this. | |

fn shrink_to_fit_edges(&mut self) {} | |

} |