summaryrefslogtreecommitdiff
path: root/vendor/petgraph-0.6.5/src/data.rs
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/petgraph-0.6.5/src/data.rs')
-rw-r--r--vendor/petgraph-0.6.5/src/data.rs481
1 files changed, 0 insertions, 481 deletions
diff --git a/vendor/petgraph-0.6.5/src/data.rs b/vendor/petgraph-0.6.5/src/data.rs
deleted file mode 100644
index 8b7db64b..00000000
--- a/vendor/petgraph-0.6.5/src/data.rs
+++ /dev/null
@@ -1,481 +0,0 @@
-//! Graph traits for associated data and graph construction.
-
-use crate::graph::IndexType;
-#[cfg(feature = "graphmap")]
-use crate::graphmap::{GraphMap, NodeTrait};
-#[cfg(feature = "stable_graph")]
-use crate::stable_graph::StableGraph;
-use crate::visit::{Data, NodeCount, NodeIndexable, Reversed};
-use crate::EdgeType;
-use crate::Graph;
-
-trait_template! {
- /// Access node and edge weights (associated data).
-#[allow(clippy::needless_arbitrary_self_type)]
-pub trait DataMap : Data {
- @section self
- fn node_weight(self: &Self, id: Self::NodeId) -> Option<&Self::NodeWeight>;
- fn edge_weight(self: &Self, id: Self::EdgeId) -> Option<&Self::EdgeWeight>;
-}
-}
-
-macro_rules! access0 {
- ($e:expr) => {
- $e.0
- };
-}
-
-DataMap! {delegate_impl []}
-DataMap! {delegate_impl [['a, G], G, &'a mut G, deref_twice]}
-DataMap! {delegate_impl [[G], G, Reversed<G>, access0]}
-
-trait_template! {
- /// Access node and edge weights mutably.
-#[allow(clippy::needless_arbitrary_self_type)]
-pub trait DataMapMut : DataMap {
- @section self
- fn node_weight_mut(self: &mut Self, id: Self::NodeId) -> Option<&mut Self::NodeWeight>;
- fn edge_weight_mut(self: &mut Self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight>;
-}
-}
-
-DataMapMut! {delegate_impl [['a, G], G, &'a mut G, deref_twice]}
-DataMapMut! {delegate_impl [[G], G, Reversed<G>, access0]}
-
-/// A graph that can be extended with further nodes and edges
-pub trait Build: Data + NodeCount {
- fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId;
- /// Add a new edge. If parallel edges (duplicate) are not allowed and
- /// the edge already exists, return `None`.
- fn add_edge(
- &mut self,
- a: Self::NodeId,
- b: Self::NodeId,
- weight: Self::EdgeWeight,
- ) -> Option<Self::EdgeId> {
- Some(self.update_edge(a, b, weight))
- }
- /// Add or update the edge from `a` to `b`. Return the id of the affected
- /// edge.
- fn update_edge(
- &mut self,
- a: Self::NodeId,
- b: Self::NodeId,
- weight: Self::EdgeWeight,
- ) -> Self::EdgeId;
-}
-
-/// A graph that can be created
-pub trait Create: Build + Default {
- fn with_capacity(nodes: usize, edges: usize) -> Self;
-}
-
-impl<N, E, Ty, Ix> Data for Graph<N, E, Ty, Ix>
-where
- Ix: IndexType,
-{
- type NodeWeight = N;
- type EdgeWeight = E;
-}
-
-impl<N, E, Ty, Ix> DataMap for Graph<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight> {
- self.node_weight(id)
- }
- fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight> {
- self.edge_weight(id)
- }
-}
-
-impl<N, E, Ty, Ix> DataMapMut for Graph<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn node_weight_mut(&mut self, id: Self::NodeId) -> Option<&mut Self::NodeWeight> {
- self.node_weight_mut(id)
- }
- fn edge_weight_mut(&mut self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight> {
- self.edge_weight_mut(id)
- }
-}
-
-#[cfg(feature = "stable_graph")]
-impl<N, E, Ty, Ix> DataMap for StableGraph<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn node_weight(&self, id: Self::NodeId) -> Option<&Self::NodeWeight> {
- self.node_weight(id)
- }
- fn edge_weight(&self, id: Self::EdgeId) -> Option<&Self::EdgeWeight> {
- self.edge_weight(id)
- }
-}
-
-#[cfg(feature = "stable_graph")]
-impl<N, E, Ty, Ix> DataMapMut for StableGraph<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn node_weight_mut(&mut self, id: Self::NodeId) -> Option<&mut Self::NodeWeight> {
- self.node_weight_mut(id)
- }
- fn edge_weight_mut(&mut self, id: Self::EdgeId) -> Option<&mut Self::EdgeWeight> {
- self.edge_weight_mut(id)
- }
-}
-
-impl<N, E, Ty, Ix> Build for Graph<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
- self.add_node(weight)
- }
- fn add_edge(
- &mut self,
- a: Self::NodeId,
- b: Self::NodeId,
- weight: Self::EdgeWeight,
- ) -> Option<Self::EdgeId> {
- Some(self.add_edge(a, b, weight))
- }
- fn update_edge(
- &mut self,
- a: Self::NodeId,
- b: Self::NodeId,
- weight: Self::EdgeWeight,
- ) -> Self::EdgeId {
- self.update_edge(a, b, weight)
- }
-}
-
-#[cfg(feature = "stable_graph")]
-impl<N, E, Ty, Ix> Build for StableGraph<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
- self.add_node(weight)
- }
- fn add_edge(
- &mut self,
- a: Self::NodeId,
- b: Self::NodeId,
- weight: Self::EdgeWeight,
- ) -> Option<Self::EdgeId> {
- Some(self.add_edge(a, b, weight))
- }
- fn update_edge(
- &mut self,
- a: Self::NodeId,
- b: Self::NodeId,
- weight: Self::EdgeWeight,
- ) -> Self::EdgeId {
- self.update_edge(a, b, weight)
- }
-}
-
-#[cfg(feature = "graphmap")]
-impl<N, E, Ty> Build for GraphMap<N, E, Ty>
-where
- Ty: EdgeType,
- N: NodeTrait,
-{
- fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
- self.add_node(weight)
- }
- fn add_edge(
- &mut self,
- a: Self::NodeId,
- b: Self::NodeId,
- weight: Self::EdgeWeight,
- ) -> Option<Self::EdgeId> {
- if self.contains_edge(a, b) {
- None
- } else {
- let r = self.add_edge(a, b, weight);
- debug_assert!(r.is_none());
- Some((a, b))
- }
- }
- fn update_edge(
- &mut self,
- a: Self::NodeId,
- b: Self::NodeId,
- weight: Self::EdgeWeight,
- ) -> Self::EdgeId {
- self.add_edge(a, b, weight);
- (a, b)
- }
-}
-
-impl<N, E, Ty, Ix> Create for Graph<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn with_capacity(nodes: usize, edges: usize) -> Self {
- Self::with_capacity(nodes, edges)
- }
-}
-
-#[cfg(feature = "stable_graph")]
-impl<N, E, Ty, Ix> Create for StableGraph<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn with_capacity(nodes: usize, edges: usize) -> Self {
- Self::with_capacity(nodes, edges)
- }
-}
-
-#[cfg(feature = "graphmap")]
-impl<N, E, Ty> Create for GraphMap<N, E, Ty>
-where
- Ty: EdgeType,
- N: NodeTrait,
-{
- fn with_capacity(nodes: usize, edges: usize) -> Self {
- Self::with_capacity(nodes, edges)
- }
-}
-
-/// A graph element.
-///
-/// A sequence of Elements, for example an iterator, is laid out as follows:
-/// Nodes are implicitly given the index of their appearance in the sequence.
-/// The edges’ source and target fields refer to these indices.
-#[derive(Clone, Debug, PartialEq, Eq)]
-pub enum Element<N, E> {
- /// A graph node.
- Node { weight: N },
- /// A graph edge.
- Edge {
- source: usize,
- target: usize,
- weight: E,
- },
-}
-
-/// Create a graph from an iterator of elements.
-pub trait FromElements: Create {
- fn from_elements<I>(iterable: I) -> Self
- where
- Self: Sized,
- I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
- {
- let mut gr = Self::with_capacity(0, 0);
- // usize -> NodeId map
- let mut map = Vec::new();
- for element in iterable {
- match element {
- Element::Node { weight } => {
- map.push(gr.add_node(weight));
- }
- Element::Edge {
- source,
- target,
- weight,
- } => {
- gr.add_edge(map[source], map[target], weight);
- }
- }
- }
- gr
- }
-}
-
-fn from_elements_indexable<G, I>(iterable: I) -> G
-where
- G: Create + NodeIndexable,
- I: IntoIterator<Item = Element<G::NodeWeight, G::EdgeWeight>>,
-{
- let mut gr = G::with_capacity(0, 0);
- let map = |gr: &G, i| gr.from_index(i);
- for element in iterable {
- match element {
- Element::Node { weight } => {
- gr.add_node(weight);
- }
- Element::Edge {
- source,
- target,
- weight,
- } => {
- let from = map(&gr, source);
- let to = map(&gr, target);
- gr.add_edge(from, to, weight);
- }
- }
- }
- gr
-}
-
-impl<N, E, Ty, Ix> FromElements for Graph<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn from_elements<I>(iterable: I) -> Self
- where
- Self: Sized,
- I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
- {
- from_elements_indexable(iterable)
- }
-}
-
-#[cfg(feature = "stable_graph")]
-impl<N, E, Ty, Ix> FromElements for StableGraph<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn from_elements<I>(iterable: I) -> Self
- where
- Self: Sized,
- I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
- {
- from_elements_indexable(iterable)
- }
-}
-
-#[cfg(feature = "graphmap")]
-impl<N, E, Ty> FromElements for GraphMap<N, E, Ty>
-where
- Ty: EdgeType,
- N: NodeTrait,
-{
- fn from_elements<I>(iterable: I) -> Self
- where
- Self: Sized,
- I: IntoIterator<Item = Element<Self::NodeWeight, Self::EdgeWeight>>,
- {
- from_elements_indexable(iterable)
- }
-}
-
-/// Iterator adaptors for iterators of `Element`.
-pub trait ElementIterator<N, E>: Iterator<Item = Element<N, E>> {
- /// Create an iterator adaptor that filters graph elements.
- ///
- /// The function `f` is called with each element and if its return value
- /// is `true` the element is accepted and if `false` it is removed.
- /// `f` is called with mutable references to the node and edge weights,
- /// so that they can be mutated (but the edge endpoints can not).
- ///
- /// This filter adapts the edge source and target indices in the
- /// stream so that they are correct after the removals.
- fn filter_elements<F>(self, f: F) -> FilterElements<Self, F>
- where
- Self: Sized,
- F: FnMut(Element<&mut N, &mut E>) -> bool,
- {
- FilterElements {
- iter: self,
- node_index: 0,
- map: Vec::new(),
- f,
- }
- }
-}
-
-impl<N, E, I: ?Sized> ElementIterator<N, E> for I where I: Iterator<Item = Element<N, E>> {}
-
-/// An iterator that filters graph elements.
-///
-/// See [`.filter_elements()`][1] for more information.
-///
-/// [1]: trait.ElementIterator.html#method.filter_elements
-#[derive(Debug, Clone)]
-pub struct FilterElements<I, F> {
- iter: I,
- node_index: usize,
- map: Vec<usize>,
- f: F,
-}
-
-impl<I, F, N, E> Iterator for FilterElements<I, F>
-where
- I: Iterator<Item = Element<N, E>>,
- F: FnMut(Element<&mut N, &mut E>) -> bool,
-{
- type Item = Element<N, E>;
-
- fn next(&mut self) -> Option<Self::Item> {
- loop {
- let mut elt = match self.iter.next() {
- None => return None,
- Some(elt) => elt,
- };
- let keep = (self.f)(match elt {
- Element::Node { ref mut weight } => Element::Node { weight },
- Element::Edge {
- source,
- target,
- ref mut weight,
- } => Element::Edge {
- source,
- target,
- weight,
- },
- });
- let is_node = if let Element::Node { .. } = elt {
- true
- } else {
- false
- };
- if !keep && is_node {
- self.map.push(self.node_index);
- }
- if is_node {
- self.node_index += 1;
- }
- if !keep {
- continue;
- }
-
- // map edge parts
- match elt {
- Element::Edge {
- ref mut source,
- ref mut target,
- ..
- } => {
- // Find the node indices in the map of removed ones.
- // If a node was removed, the edge is as well.
- // Otherwise the counts are adjusted by the number of nodes
- // removed.
- // Example: map: [1, 3, 4, 6]
- // binary search for 2, result is Err(1). One node has been
- // removed before 2.
- match self.map.binary_search(source) {
- Ok(_) => continue,
- Err(i) => *source -= i,
- }
- match self.map.binary_search(target) {
- Ok(_) => continue,
- Err(i) => *target -= i,
- }
- }
- Element::Node { .. } => {}
- }
- return Some(elt);
- }
- }
- fn size_hint(&self) -> (usize, Option<usize>) {
- let (_, upper) = self.iter.size_hint();
- (0, upper)
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-02 02:50:08 +0000