fuchsia / third_party / github.com / petgraph / petgraph / refs/heads/upstream/next / . / crates / core / src / edge / mod.rs

//! # Edges | |

//! | |

//! This module contains the three edge types used by the graph, an edge is a connection between two | |

//! nodes, that may or may not be directed and has a weight. | |

//! | |

//! The three edge types are: | |

//! * [`Edge`]: An immutable edge, that borrows the graph. | |

//! * [`EdgeMut`]: A mutable edge, that borrows the graph. | |

//! * [`DetachedEdge`]: An edge that is not attached to the graph. | |

//! | |

//! In application code [`DetachedEdge`]s can easily be interchanged with [`Edge`]s and vice-versa, | |

//! as long as all components are [`Clone`]able. | |

//! | |

//! You should prefer to use [`Edge`]s and [`EdgeMut`]s over [`DetachedEdge`]s, as they are more | |

//! efficient, as these are simply (mutable) reference into the underlying graph (storage). | |

//! | |

//! [`EdgeMut`]s are only needed when you want to mutate the weight of an edge, otherwise you should | |

//! use [`Edge`]s. | |

mod compat; | |

mod direction; | |

pub mod marker; | |

use core::fmt::{Debug, Display, Formatter}; | |

pub use self::{direction::Direction, marker::GraphDirectionality}; | |

use crate::{ | |

node::{Node, NodeId}, | |

storage::GraphStorage, | |

DirectedGraphStorage, | |

}; | |

type DetachedStorageEdge<S> = DetachedEdge<<S as GraphStorage>::EdgeWeight>; | |

/// ID of an edge in a graph. | |

/// | |

/// This is guaranteed to be unique within the graph, library authors and library consumers **must** | |

/// treat this as an opaque type akin to [`TypeId`]. | |

/// | |

/// The layout of the type is semver stable, but not part of the public API. | |

/// | |

/// [`GraphStorage`] implementations may uphold additional invariants on the inner value and | |

/// code outside of the [`GraphStorage`] should **never** construct a [`EdgeId`] directly. | |

/// | |

/// Accessing a [`GraphStorage`] implementation with a [`EdgeId`] not returned by an instance itself | |

/// is considered undefined behavior. | |

/// | |

/// [`TypeId`]: core::any::TypeId | |

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] | |

pub struct EdgeId(usize); | |

impl Display for EdgeId { | |

// we could also utilize a VTable here instead, that would allow for custom formatting | |

// but that would be an additional pointer added to the type that must be carried around | |

// that's about ~8 bytes on 64-bit systems | |

fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result { | |

write!(f, "EdgeId({})", self.0) | |

} | |

} | |

// TODO: find a better way to gate these functions | |

impl EdgeId { | |

/// Creates a new [`EdgeId`]. | |

/// | |

/// # Note | |

/// | |

/// Using this outside of the [`GraphStorage`] implementation is considered undefined behavior. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::edge::EdgeId; | |

/// | |

/// let id = EdgeId::new(0); | |

/// ``` | |

// Hidden so that non-GraphStorage implementors are not tempted to use this. | |

#[doc(hidden)] | |

#[must_use] | |

pub const fn new(id: usize) -> Self { | |

Self(id) | |

} | |

/// Returns the inner value of the [`EdgeId`]. | |

/// | |

/// # Note | |

/// | |

/// Using this outside of the [`GraphStorage`] implementation is considered undefined behavior. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::edge::EdgeId; | |

/// | |

/// let id = EdgeId::new(0); | |

/// | |

/// assert_eq!(id.into_inner(), 0); | |

/// ``` | |

// Hidden so that non-GraphStorage implementors are not tempted to use this. | |

#[doc(hidden)] | |

#[must_use] | |

pub const fn into_inner(self) -> usize { | |

self.0 | |

} | |

} | |

/// Active edge in the graph. | |

/// | |

/// Edge that is part of the graph, it borrows the graph and can be used to access the endpoints. | |

/// | |

/// Undirected graph implementations have no notion of a source and target, therefore endpoints can | |

/// only be accessed through [`Self::endpoint_ids`] and [`Self::endpoints`]. | |

/// If the storage implementation is directed (implements [`DirectedGraphStorage`]), one can access | |

/// the source and target through [`Self::source_id`], [`Self::source`], [`Self::target_id`] and | |

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

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let aa = *graph.insert_edge("A → A", &a, &a).id(); | |

/// | |

/// let edge = graph.edge(&aa).unwrap(); | |

/// | |

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

/// assert_eq!(edge.weight(), &"A → A"); | |

/// ``` | |

#[derive(PartialEq, Eq, PartialOrd, Ord, Hash)] | |

pub struct Edge<'a, S> | |

where | |

S: GraphStorage, | |

{ | |

storage: &'a S, | |

id: EdgeId, | |

u: NodeId, | |

v: NodeId, | |

weight: &'a S::EdgeWeight, | |

} | |

impl<S> Clone for Edge<'_, S> | |

where | |

S: GraphStorage, | |

{ | |

fn clone(&self) -> Self { | |

*self | |

} | |

} | |

impl<S> Copy for Edge<'_, S> where S: GraphStorage {} | |

impl<S> Debug for Edge<'_, S> | |

where | |

S: GraphStorage, | |

S::EdgeWeight: Debug, | |

{ | |

fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result { | |

f.debug_struct("Edge") | |

.field("id", &self.id) | |

.field("u", &self.u) | |

.field("v", &self.v) | |

.field("weight", &self.weight) | |

.finish() | |

} | |

} | |

impl<'a, S> Edge<'a, S> | |

where | |

S: GraphStorage, | |

{ | |

/// Create a new edge. | |

/// | |

/// You should not need to use this directly, instead use [`Graph::edge`]. | |

/// | |

/// This is only for implementors of [`GraphStorage`]. | |

/// | |

/// In an undirected graph `u` and `v` are interchangeable, but in a directed graph (implements | |

/// [`DirectedGraphStorage`]) `u` is the source and `v` is the target. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{ | |

/// edge::{Direction, Edge}, | |

/// node::Node, | |

/// }; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let aa = *graph.insert_edge("A → A", &a, &a).id(); | |

/// | |

/// let edge = graph.edge(&aa).unwrap(); | |

/// let copy = Edge::new( | |

/// graph.storage(), | |

/// edge.id(), | |

/// edge.weight(), | |

/// edge.source_id(), | |

/// edge.target_id(), | |

/// ); | |

/// // ^ exact same as `let copy = *edge;` | |

/// ``` | |

/// | |

/// # Contract | |

/// | |

/// The `id`, `source_id` and `target_id` must be valid in the given `storage`, and | |

/// [`storage.node(source_id)`](GraphStorage::node) and | |

/// [`storage.node(target_id)`](GraphStorage::node) must return `Some(_)`. | |

/// The `weight` must be valid in the given `storage` for the specified `id`. | |

/// | |

/// The contract on `id` is not enforced, to avoid recursive calls to [`GraphStorage::edge`] and | |

/// [`GraphStorage::contains_edge`]. | |

/// The contract on `source_id` and `target_id` is checked in debug builds. | |

/// | |

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

pub fn new( | |

storage: &'a S, | |

id: EdgeId, | |

weight: &'a S::EdgeWeight, | |

u: NodeId, | |

v: NodeId, | |

) -> Self { | |

debug_assert!(storage.contains_node(u)); | |

debug_assert!(storage.contains_node(v)); | |

Self { | |

storage, | |

id, | |

u, | |

v, | |

weight, | |

} | |

} | |

/// The unique id of the edge. | |

/// | |

/// This is guaranteed to be unique within the graph, the type returned depends on the | |

/// implementation of [`GraphStorage`]. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{ | |

/// edge::{Direction, Edge}, | |

/// node::Node, | |

/// }; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let aa = *graph.insert_edge("A → A", &a, &a).id(); | |

/// | |

/// let edge = graph.edge(&aa).unwrap(); | |

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

/// ``` | |

#[must_use] | |

pub const fn id(&self) -> EdgeId { | |

self.id | |

} | |

/// Get the ids of the endpoints of this edge. | |

/// | |

/// While [`Self::source_id`] and [`Self::target_id`] are only available for directed graphs, | |

/// this method is available for both directed and undirected graphs. | |

/// | |

/// The order of the ids is not guaranteed for undirected graphs, but corresponds to `(source, | |

/// target)` for directed graph, this should be considered an implementation detail and one | |

/// **should not** rely on the order. | |

/// | |

/// You should use [`Self::source_id`] and [`Self::target_id`] directly if you need the source | |

/// and target. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

/// let (u, v) = edge.endpoint_ids(); // <- the order is not guaranteed for undirected graphs | |

/// | |

/// assert!((u, v) == (&a, &b) || (u, v) == (&b, &a)); | |

/// ``` | |

#[must_use] | |

pub const fn endpoint_ids(&self) -> (NodeId, NodeId) { | |

(self.u, self.v) | |

} | |

/// Get the endpoints of this edge. | |

/// | |

/// While [`Self::source`] and [`Self::target`] are only available for directed graphs, this | |

/// method is available for both directed and undirected graphs | |

/// | |

/// The order of the endpoints is not guaranteed for undirected graphs, but corresponds to | |

/// `(source, target)` for directed graph, this should be considered an implementation | |

/// detail and one **should not** rely on the order. | |

/// | |

/// You should use [`Self::source`] and [`Self::target`] directly if you need the source and | |

/// target. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

/// let (u, v) = edge.endpoints(); // <- the order is not guaranteed for undirected graphs | |

/// | |

/// assert!((u.id(), v.id()) == (&a, &b) || (u.id(), v.id()) == (&b, &a)); | |

/// ``` | |

/// | |

/// # Panics | |

/// | |

/// Panics if the endpoints are not active in the same storage as this edge. | |

/// | |

/// This error will only occur if the storage has been corrupted or if the contract on | |

/// [`Edge::new`] is violated. | |

#[must_use] | |

pub fn endpoints(&self) -> (Node<'a, S>, Node<'a, S>) { | |

( | |

self.storage.node(self.u).expect( | |

"corrupted storage or violated contract upon creation of this edge; the endpoint \ | |

node must be active in the same storage as this edge", | |

), | |

self.storage.node(self.v).expect( | |

"corrupted storage or violated contract upon creation of this edge; the endpoint \ | |

node must be active in the same storage as this edge", | |

), | |

) | |

} | |

/// Get the weight of this edge. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{ | |

/// edge::{Direction, Edge}, | |

/// node::Node, | |

/// }; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// assert_eq!(edge.weight(), &"A → B"); | |

/// ``` | |

#[must_use] | |

pub const fn weight(&self) -> &'a S::EdgeWeight { | |

self.weight | |

} | |

/// Change the underlying storage of this edge. | |

/// | |

/// Should only be used when layering multiple [`GraphStorage`] implementations on top of each | |

/// other. | |

/// | |

/// # Note | |

/// | |

/// This should not lead to any undefined behaviour, but might have unintended consequences if | |

/// the storage does not recognize the inner id as valid. | |

/// You should only use this if you know what you are doing. | |

#[must_use] | |

pub const fn change_storage_unchecked<T>(self, storage: &'a T) -> Edge<'a, T> | |

where | |

T: GraphStorage<EdgeWeight = S::EdgeWeight>, | |

{ | |

Edge { | |

storage, | |

id: self.id, | |

u: self.u, | |

v: self.v, | |

weight: self.weight, | |

} | |

} | |

} | |

impl<'a, S> Edge<'a, S> | |

where | |

S: DirectedGraphStorage, | |

{ | |

/// Get the source node id of this edge. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{ | |

/// edge::{Direction, Edge}, | |

/// node::Node, | |

/// }; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

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

/// ``` | |

#[must_use] | |

pub const fn source_id(&self) -> NodeId { | |

self.u | |

} | |

/// Get the source node of this edge. | |

/// | |

/// This is a shortcut for [`self.storage.node(self.source_id())`](GraphStorage::node). | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{ | |

/// edge::{Direction, Edge}, | |

/// node::Node, | |

/// }; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

/// let source = edge.source(); | |

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

/// ``` | |

/// | |

/// | |

/// # Panics | |

/// | |

/// Panics if the source node is not active in the same storage as this edge. | |

/// | |

/// This error will only occur if the storage has been corrupted or if the contract on | |

/// [`Edge::new`] is violated. | |

#[must_use] | |

pub fn source(&self) -> Node<'a, S> { | |

self.storage.node(self.u).expect( | |

"corrupted storage or violated contract upon creation of this edge; the source node \ | |

must be active in the same storage as this edge", | |

) | |

} | |

#[must_use] | |

/// Get the target node id of this edge. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{ | |

/// edge::{Direction, Edge}, | |

/// node::Node, | |

/// }; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

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

/// ``` | |

pub const fn target_id(&self) -> NodeId { | |

self.v | |

} | |

/// Get the target node of this edge. | |

/// | |

/// This is a shortcut for [`self.storage.node(self.target_id())`](GraphStorage::node). | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{ | |

/// edge::{Direction, Edge}, | |

/// node::Node, | |

/// }; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

/// let target = edge.target(); | |

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

/// ``` | |

/// | |

/// | |

/// # Panics | |

/// | |

/// Panics if the target node is not active in the same storage as this edge. | |

/// | |

/// This error will only occur if the storage has been corrupted or if the contract on | |

/// [`Edge::new`] is violated. | |

#[must_use] | |

pub fn target(&self) -> Node<'a, S> { | |

self.storage.node(self.v).expect( | |

"corrupted storage or violated contract upon creation of this edge; the target node \ | |

must be active in the same storage as this edge", | |

) | |

} | |

} | |

impl<S> Edge<'_, S> | |

where | |

S: GraphStorage, | |

S::EdgeWeight: Clone, | |

{ | |

/// Detach this edge from the graph. | |

/// | |

/// > **Note:** This will _not_ remove the node from the graph, it will only detach the this | |

/// > instance of the node removing the lifetime dependency on the graph. | |

/// | |

/// This will return a [`DetachedEdge`], which can be reattached to the graph using | |

/// [`Graph::from_parts`]. | |

/// | |

/// This is especially useful in use-cases where you want direct (mutable access) to both the | |

/// weight and id or do not want to bother with the graph's lifetime. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::{ | |

/// edge::{Direction, Edge}, | |

/// node::Node, | |

/// }; | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

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

/// assert_eq!(edge.weight, "A → B"); | |

/// ``` | |

/// | |

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

#[must_use] | |

pub fn detach(self) -> DetachedStorageEdge<S> { | |

DetachedEdge::new(self.id, self.weight.clone(), self.u, self.v) | |

} | |

} | |

/// Active (mutable) edge in the graph. | |

/// | |

/// Edge that is part of the graph, it borrows the graph and can be used to mutably access the | |

/// weight of an edge. The source and node are not available mutably, as changing those might | |

/// violate some internal constraints of the [`GraphStorage`] they are part of. | |

/// | |

/// To prevent multiple borrows of the same edge, while still allowing for multiple borrows into the | |

/// same storage, this type does not carry a reference to the storage itself. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let mut ab = graph.insert_edge("A → B", &a, &b); | |

/// | |

/// assert_eq!(ab.weight(), &"A → B"); | |

/// assert_eq!(ab.weight_mut(), &mut "A → B"); | |

/// ``` | |

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] | |

pub struct EdgeMut<'a, S> | |

where | |

S: GraphStorage, | |

{ | |

id: EdgeId, | |

weight: &'a mut S::EdgeWeight, | |

u: NodeId, | |

v: NodeId, | |

} | |

impl<'a, S> EdgeMut<'a, S> | |

where | |

S: GraphStorage, | |

{ | |

/// Create a new edge. | |

/// | |

/// You should not need to use this directly, instead use [`Graph::edge_mut`] or | |

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

/// | |

/// This is only for implementors of [`GraphStorage`]. | |

/// | |

/// In an undirected graph `u` and `v` are interchangeable, but in a directed graph (implements | |

/// [`DirectedGraphStorage`]) `u` is the source and `v` is the target. | |

/// | |

/// # Contract | |

/// | |

/// The `id`, `source_id` and `target_id` must be valid in the given `storage`, and the `weight` | |

/// must be valid in the given `storage` for the specified `id`. | |

/// | |

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

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

pub fn new(id: EdgeId, weight: &'a mut S::EdgeWeight, u: NodeId, v: NodeId) -> Self { | |

Self { id, weight, u, v } | |

} | |

/// The unique id of the edge. | |

/// | |

/// This is guaranteed to be unique within the graph, the type returned depends on the | |

/// implementation of [`GraphStorage`]. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

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

/// ``` | |

#[must_use] | |

pub const fn id(&self) -> EdgeId { | |

self.id | |

} | |

/// The ids of the endpoints of the edge. | |

/// | |

/// While [`Self::source_id`] and [`Self::target_id`] are only available for directed graphs, | |

/// this method is available for both directed and undirected graphs. | |

/// | |

/// The order of the ids is not guaranteed for undirected graphs, but corresponds to `(source, | |

/// target)` for directed graph, this should be considered an implementation detail and one | |

/// **should not** rely on the order. | |

/// | |

/// You should use [`Self::source_id`] and [`Self::target_id`] directly if you need the source | |

/// and target. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// | |

/// let ab = graph.insert_edge("A → B", &a, &b); | |

/// | |

/// let (u, v) = ab.endpoint_ids(); // <- the order is not guaranteed for undirected graphs | |

/// | |

/// assert!((u, v) == (&a, &b) || (u, v) == (&b, &a)); | |

/// ``` | |

#[must_use] | |

pub const fn endpoint_ids(&self) -> (NodeId, NodeId) { | |

(self.u, self.v) | |

} | |

/// The weight of the edge. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

/// assert_eq!(edge.weight(), &"A → B"); | |

/// ``` | |

#[must_use] | |

pub fn weight(&self) -> &S::EdgeWeight { | |

self.weight | |

} | |

/// The (mutable) weight of the edge. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

/// assert_eq!(edge.weight_mut(), &mut "A → B"); | |

/// ``` | |

pub fn weight_mut(&mut self) -> &mut S::EdgeWeight { | |

self.weight | |

} | |

/// Change the underlying storage of this edge. | |

/// | |

/// Should only be used when layering multiple [`GraphStorage`] implementations on top of each | |

/// other. | |

/// | |

/// # Note | |

/// | |

/// This should not lead to any undefined behaviour, but might have unintended consequences if | |

/// the storage does not recognize the inner id as valid. | |

/// You should only use this if you know what you are doing. | |

#[must_use] | |

pub fn change_storage_unchecked<T>(self) -> EdgeMut<'a, T> | |

where | |

T: GraphStorage<EdgeWeight = S::EdgeWeight>, | |

{ | |

EdgeMut { | |

id: self.id, | |

weight: self.weight, | |

u: self.u, | |

v: self.v, | |

} | |

} | |

} | |

impl<'a, S> EdgeMut<'a, S> | |

where | |

S: DirectedGraphStorage, | |

{ | |

/// The source node id of the edge. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

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

/// ``` | |

#[must_use] | |

pub const fn source_id(&self) -> NodeId { | |

self.u | |

} | |

/// The target node id of the edge. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

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

/// ``` | |

#[must_use] | |

pub const fn target_id(&self) -> NodeId { | |

self.v | |

} | |

} | |

impl<S> EdgeMut<'_, S> | |

where | |

S: GraphStorage, | |

S::EdgeWeight: Clone, | |

{ | |

/// Detaches the edge from the graph. | |

/// | |

/// > **Note:** This will _not_ remove the node from the graph, it will only detach the this | |

/// > instance of the node removing the lifetime dependency on the graph. | |

/// | |

/// | |

/// This will return an [`DetachedEdge`], which can be reattached to the graph using | |

/// [`Graph::from_parts`]. | |

/// | |

/// This is especially useful in use-cases where you want direct (mutable access) to both the | |

/// weight and id or do not want to bother with the graph's lifetime. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

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

/// assert_eq!(edge.weight, "A → B"); | |

/// ``` | |

/// | |

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

#[must_use] | |

pub fn detach(self) -> DetachedStorageEdge<S> { | |

DetachedEdge::new(self.id, self.weight.clone(), self.u, self.v) | |

} | |

} | |

/// Detached edge from a graph. | |

/// | |

/// This edge is no longer considered to be, but can be reattached to the graph using | |

/// [`Graph::from_parts`]. | |

/// | |

/// Especially useful in cases of decomposition ([`Graph::into_parts`]) or if one does not want to | |

/// deal with the graph's lifetime or needs a node to outlive the graph. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_dino::DiDinoGraph; | |

/// | |

/// let mut graph = DiDinoGraph::new(); | |

/// | |

/// let a = *graph.insert_node("A").id(); | |

/// let b = *graph.insert_node("B").id(); | |

/// let ab = *graph.insert_edge("A → B", &a, &b).id(); | |

/// | |

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

/// | |

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

/// assert_eq!(edge.weight, "A → B"); | |

/// ``` | |

/// | |

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

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

#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] | |

pub struct DetachedEdge<W> { | |

/// The unique id of the edge. | |

pub id: EdgeId, | |

/// The `u` endpoint of the `(u, v)` pair of endpoints. | |

pub u: NodeId, | |

/// The `v` endpoint of the `(u, v)` pair of endpoints. | |

pub v: NodeId, | |

/// The weight of the edge. | |

pub weight: W, | |

} | |

impl<W> DetachedEdge<W> { | |

/// Create a new detached edge. | |

/// | |

/// In an undirected graph `u` and `v` are interchangeable, but in a directed graph (implements | |

/// [`DirectedGraphStorage`]) `u` is the source and `v` is the target. | |

/// | |

/// # Example | |

/// | |

/// ``` | |

/// use petgraph_core::edge::DetachedEdge; | |

/// | |

/// let edge = DetachedEdge::new(0, "A → B", 1, 2); | |

/// ``` | |

pub const fn new(id: EdgeId, weight: W, u: NodeId, v: NodeId) -> Self { | |

Self { id, u, v, weight } | |

} | |

} |