summaryrefslogtreecommitdiff
path: root/vendor/petgraph-0.6.5/src/graphmap.rs
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/petgraph-0.6.5/src/graphmap.rs')
-rw-r--r--vendor/petgraph-0.6.5/src/graphmap.rs1504
1 files changed, 0 insertions, 1504 deletions
diff --git a/vendor/petgraph-0.6.5/src/graphmap.rs b/vendor/petgraph-0.6.5/src/graphmap.rs
deleted file mode 100644
index 9e1bdd36..00000000
--- a/vendor/petgraph-0.6.5/src/graphmap.rs
+++ /dev/null
@@ -1,1504 +0,0 @@
-//! `GraphMap<N, E, Ty>` is a graph datastructure where node values are mapping
-//! keys.
-
-use indexmap::map::Keys;
-use indexmap::map::{Iter as IndexMapIter, IterMut as IndexMapIterMut};
-use indexmap::IndexMap;
-use std::cmp::Ordering;
-use std::collections::hash_map::RandomState;
-use std::collections::HashSet;
-use std::fmt;
-use std::hash::{self, BuildHasher, Hash};
-use std::iter::Copied;
-use std::iter::FromIterator;
-use std::marker::PhantomData;
-use std::mem;
-use std::ops::{Deref, Index, IndexMut};
-use std::slice::Iter;
-
-use crate::{Directed, Direction, EdgeType, Incoming, Outgoing, Undirected};
-
-use crate::graph::node_index;
-use crate::graph::Graph;
-use crate::visit;
-use crate::IntoWeightedEdge;
-
-#[cfg(feature = "rayon")]
-use indexmap::map::rayon::{ParIter, ParIterMut, ParKeys};
-#[cfg(feature = "rayon")]
-use rayon::prelude::*;
-
-/// A `GraphMap` with undirected edges.
-///
-/// For example, an edge between *1* and *2* is equivalent to an edge between
-/// *2* and *1*.
-pub type UnGraphMap<N, E> = GraphMap<N, E, Undirected>;
-/// A `GraphMap` with directed edges.
-///
-/// For example, an edge from *1* to *2* is distinct from an edge from *2* to
-/// *1*.
-pub type DiGraphMap<N, E> = GraphMap<N, E, Directed>;
-
-/// `GraphMap<N, E, Ty>` is a graph datastructure using an associative array
-/// of its node weights `N`.
-///
-/// It uses an combined adjacency list and sparse adjacency matrix
-/// representation, using **O(|V| + |E|)** space, and allows testing for edge
-/// existence in constant time.
-///
-/// `GraphMap` is parameterized over:
-///
-/// - Associated data `N` for nodes and `E` for edges, called *weights*.
-/// - The node weight `N` must implement `Copy` and will be used as node
-/// identifier, duplicated into several places in the data structure.
-/// It must be suitable as a hash table key (implementing `Eq + Hash`).
-/// The node type must also implement `Ord` so that the implementation can
-/// order the pair (`a`, `b`) for an edge connecting any two nodes `a` and `b`.
-/// - `E` can be of arbitrary type.
-/// - Edge type `Ty` that determines whether the graph edges are directed or
-/// undirected.
-///
-/// You can use the type aliases `UnGraphMap` and `DiGraphMap` for convenience.
-///
-/// `GraphMap` does not allow parallel edges, but self loops are allowed.
-///
-/// Depends on crate feature `graphmap` (default).
-#[derive(Clone)]
-pub struct GraphMap<N, E, Ty, S = RandomState>
-where
- S: BuildHasher,
-{
- nodes: IndexMap<N, Vec<(N, CompactDirection)>, S>,
- edges: IndexMap<(N, N), E, S>,
- ty: PhantomData<Ty>,
-}
-
-impl<N: Eq + Hash + fmt::Debug, E: fmt::Debug, Ty: EdgeType, S: BuildHasher> fmt::Debug
- for GraphMap<N, E, Ty, S>
-{
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- self.nodes.fmt(f)
- }
-}
-
-/// A trait group for `GraphMap`'s node identifier.
-pub trait NodeTrait: Copy + Ord + Hash {}
-impl<N> NodeTrait for N where N: Copy + Ord + Hash {}
-
-// non-repr(usize) version of Direction
-#[derive(Copy, Clone, Debug, PartialEq)]
-enum CompactDirection {
- Outgoing,
- Incoming,
-}
-
-impl CompactDirection {
- /// Return the opposite `CompactDirection`.
- #[inline]
- pub fn opposite(self) -> CompactDirection {
- match self {
- CompactDirection::Outgoing => CompactDirection::Incoming,
- CompactDirection::Incoming => CompactDirection::Outgoing,
- }
- }
-}
-
-impl From<Direction> for CompactDirection {
- fn from(d: Direction) -> Self {
- match d {
- Outgoing => CompactDirection::Outgoing,
- Incoming => CompactDirection::Incoming,
- }
- }
-}
-
-impl From<CompactDirection> for Direction {
- fn from(d: CompactDirection) -> Self {
- match d {
- CompactDirection::Outgoing => Outgoing,
- CompactDirection::Incoming => Incoming,
- }
- }
-}
-
-impl PartialEq<Direction> for CompactDirection {
- fn eq(&self, rhs: &Direction) -> bool {
- (*self as usize) == (*rhs as usize)
- }
-}
-
-#[cfg(feature = "serde-1")]
-impl<N, E, Ty, S> serde::Serialize for GraphMap<N, E, Ty, S>
-where
- Ty: EdgeType,
- N: NodeTrait + serde::Serialize,
- E: serde::Serialize,
- S: BuildHasher,
- Self: Clone,
-{
- /// Serializes the given `GraphMap` into the same format as the standard
- /// `Graph`. Needs feature `serde-1`.
- ///
- /// Note: the graph has to be `Clone` for this to work.
- fn serialize<Ser>(&self, serializer: Ser) -> Result<Ser::Ok, Ser::Error>
- where
- Ser: serde::Serializer,
- {
- let cloned_graph: GraphMap<N, E, Ty, S> = GraphMap::clone(self);
- let equivalent_graph: Graph<N, E, Ty, u32> = cloned_graph.into_graph();
- equivalent_graph.serialize(serializer)
- }
-}
-
-#[cfg(feature = "serde-1")]
-impl<'de, N, E, Ty, S> serde::Deserialize<'de> for GraphMap<N, E, Ty, S>
-where
- Ty: EdgeType,
- N: NodeTrait + serde::Deserialize<'de>,
- E: Clone + serde::Deserialize<'de>,
- S: BuildHasher + Default,
-{
- /// Deserializes into a new `GraphMap` from the same format as the standard
- /// `Graph`. Needs feature `serde-1`.
- ///
- /// **Warning**: When deseralizing a graph that was not originally a `GraphMap`,
- /// the restrictions from [`from_graph`](#method.from_graph) apply.
- ///
- /// Note: The edge weights have to be `Clone` for this to work.
- fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
- where
- D: serde::Deserializer<'de>,
- {
- let equivalent_graph: Graph<N, E, Ty, u32> = Graph::deserialize(deserializer)?;
- Ok(GraphMap::from_graph(equivalent_graph))
- }
-}
-
-impl<N, E, Ty, S> GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- /// Create a new `GraphMap`
- pub fn new() -> Self
- where
- S: Default,
- {
- Self::default()
- }
-
- /// Create a new `GraphMap` with estimated capacity.
- pub fn with_capacity(nodes: usize, edges: usize) -> Self
- where
- S: Default,
- {
- Self {
- nodes: IndexMap::with_capacity_and_hasher(nodes, S::default()),
- edges: IndexMap::with_capacity_and_hasher(edges, S::default()),
- ty: PhantomData,
- }
- }
-
- /// Create a new `GraphMap` with estimated capacity, and specified hasher.
- pub fn with_capacity_and_hasher(nodes: usize, edges: usize, hasher: S) -> Self
- where
- S: Clone,
- {
- Self {
- nodes: IndexMap::with_capacity_and_hasher(nodes, hasher.clone()),
- edges: IndexMap::with_capacity_and_hasher(edges, hasher),
- ty: PhantomData,
- }
- }
-
- /// Return the current node and edge capacity of the graph.
- pub fn capacity(&self) -> (usize, usize) {
- (self.nodes.capacity(), self.edges.capacity())
- }
-
- /// Use their natural order to map the node pair (a, b) to a canonical edge id.
- #[inline]
- fn edge_key(a: N, b: N) -> (N, N) {
- if Ty::is_directed() || a <= b {
- (a, b)
- } else {
- (b, a)
- }
- }
-
- /// Whether the graph has directed edges.
- pub fn is_directed(&self) -> bool {
- Ty::is_directed()
- }
-
- /// Create a new `GraphMap` from an iterable of edges.
- ///
- /// Node values are taken directly from the list.
- /// Edge weights `E` may either be specified in the list,
- /// or they are filled with default values.
- ///
- /// Nodes are inserted automatically to match the edges.
- ///
- /// ```
- /// use petgraph::graphmap::UnGraphMap;
- ///
- /// // Create a new undirected GraphMap.
- /// // Use a type hint to have `()` be the edge weight type.
- /// let gr = UnGraphMap::<_, ()>::from_edges(&[
- /// (0, 1), (0, 2), (0, 3),
- /// (1, 2), (1, 3),
- /// (2, 3),
- /// ]);
- /// ```
- pub fn from_edges<I>(iterable: I) -> Self
- where
- I: IntoIterator,
- I::Item: IntoWeightedEdge<E, NodeId = N>,
- S: Default,
- {
- Self::from_iter(iterable)
- }
-
- /// Return the number of nodes in the graph.
- pub fn node_count(&self) -> usize {
- self.nodes.len()
- }
-
- /// Return the number of edges in the graph.
- pub fn edge_count(&self) -> usize {
- self.edges.len()
- }
-
- /// Remove all nodes and edges
- pub fn clear(&mut self) {
- self.nodes.clear();
- self.edges.clear();
- }
-
- /// Add node `n` to the graph.
- pub fn add_node(&mut self, n: N) -> N {
- self.nodes.entry(n).or_default();
- n
- }
-
- /// Return `true` if node `n` was removed.
- ///
- /// Computes in **O(V)** time, due to the removal of edges with other nodes.
- pub fn remove_node(&mut self, n: N) -> bool {
- let links = match self.nodes.swap_remove(&n) {
- None => return false,
- Some(sus) => sus,
- };
- for (succ, dir) in links {
- let edge = if dir == CompactDirection::Outgoing {
- Self::edge_key(n, succ)
- } else {
- Self::edge_key(succ, n)
- };
- // remove all successor links
- self.remove_single_edge(&succ, &n, dir.opposite());
- // Remove all edge values
- self.edges.swap_remove(&edge);
- }
- true
- }
-
- /// Return `true` if the node is contained in the graph.
- pub fn contains_node(&self, n: N) -> bool {
- self.nodes.contains_key(&n)
- }
-
- /// Add an edge connecting `a` and `b` to the graph, with associated
- /// data `weight`. For a directed graph, the edge is directed from `a`
- /// to `b`.
- ///
- /// Inserts nodes `a` and/or `b` if they aren't already part of the graph.
- ///
- /// Return `None` if the edge did not previously exist, otherwise,
- /// the associated data is updated and the old value is returned
- /// as `Some(old_weight)`.
- ///
- /// ```
- /// // Create a GraphMap with directed edges, and add one edge to it
- /// use petgraph::graphmap::DiGraphMap;
- ///
- /// let mut g = DiGraphMap::new();
- /// g.add_edge("x", "y", -1);
- /// assert_eq!(g.node_count(), 2);
- /// assert_eq!(g.edge_count(), 1);
- /// assert!(g.contains_edge("x", "y"));
- /// assert!(!g.contains_edge("y", "x"));
- /// ```
- pub fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E> {
- if let old @ Some(_) = self.edges.insert(Self::edge_key(a, b), weight) {
- old
- } else {
- // insert in the adjacency list if it's a new edge
- self.nodes
- .entry(a)
- .or_insert_with(|| Vec::with_capacity(1))
- .push((b, CompactDirection::Outgoing));
- if a != b {
- // self loops don't have the Incoming entry
- self.nodes
- .entry(b)
- .or_insert_with(|| Vec::with_capacity(1))
- .push((a, CompactDirection::Incoming));
- }
- None
- }
- }
-
- /// Remove edge relation from a to b
- ///
- /// Return `true` if it did exist.
- fn remove_single_edge(&mut self, a: &N, b: &N, dir: CompactDirection) -> bool {
- match self.nodes.get_mut(a) {
- None => false,
- Some(sus) => {
- if Ty::is_directed() {
- match sus.iter().position(|elt| elt == &(*b, dir)) {
- Some(index) => {
- sus.swap_remove(index);
- true
- }
- None => false,
- }
- } else {
- match sus.iter().position(|elt| &elt.0 == b) {
- Some(index) => {
- sus.swap_remove(index);
- true
- }
- None => false,
- }
- }
- }
- }
- }
-
- /// Remove edge from `a` to `b` from the graph and return the edge weight.
- ///
- /// Return `None` if the edge didn't exist.
- ///
- /// ```
- /// // Create a GraphMap with undirected edges, and add and remove an edge.
- /// use petgraph::graphmap::UnGraphMap;
- ///
- /// let mut g = UnGraphMap::new();
- /// g.add_edge("x", "y", -1);
- ///
- /// let edge_data = g.remove_edge("y", "x");
- /// assert_eq!(edge_data, Some(-1));
- /// assert_eq!(g.edge_count(), 0);
- /// ```
- pub fn remove_edge(&mut self, a: N, b: N) -> Option<E> {
- let exist1 = self.remove_single_edge(&a, &b, CompactDirection::Outgoing);
- let exist2 = if a != b {
- self.remove_single_edge(&b, &a, CompactDirection::Incoming)
- } else {
- exist1
- };
- let weight = self.edges.swap_remove(&Self::edge_key(a, b));
- debug_assert!(exist1 == exist2 && exist1 == weight.is_some());
- weight
- }
-
- /// Return `true` if the edge connecting `a` with `b` is contained in the graph.
- pub fn contains_edge(&self, a: N, b: N) -> bool {
- self.edges.contains_key(&Self::edge_key(a, b))
- }
-
- /// Return an iterator over the nodes of the graph.
- ///
- /// Iterator element type is `N`.
- pub fn nodes(&self) -> Nodes<'_, N> {
- Nodes {
- iter: self.nodes.keys().copied(),
- }
- }
-
- /// Return a parallel iterator over the nodes of the graph.
- ///
- /// Iterator element type is `N`.
- #[cfg(feature = "rayon")]
- pub fn par_nodes(&self) -> ParNodes<'_, N>
- where
- N: Send + Sync,
- {
- ParNodes {
- iter: self.nodes.par_keys(),
- }
- }
-
- /// Return an iterator of all nodes with an edge starting from `a`.
- ///
- /// - `Directed`: Outgoing edges from `a`.
- /// - `Undirected`: All edges from or to `a`.
- ///
- /// Produces an empty iterator if the node doesn't exist.<br>
- /// Iterator element type is `N`.
- pub fn neighbors(&self, a: N) -> Neighbors<N, Ty> {
- Neighbors {
- iter: match self.nodes.get(&a) {
- Some(neigh) => neigh.iter(),
- None => [].iter(),
- },
- ty: self.ty,
- }
- }
-
- /// Return an iterator of all neighbors that have an edge between them and
- /// `a`, in the specified direction.
- /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
- ///
- /// - `Directed`, `Outgoing`: All edges from `a`.
- /// - `Directed`, `Incoming`: All edges to `a`.
- /// - `Undirected`: All edges from or to `a`.
- ///
- /// Produces an empty iterator if the node doesn't exist.<br>
- /// Iterator element type is `N`.
- pub fn neighbors_directed(&self, a: N, dir: Direction) -> NeighborsDirected<N, Ty> {
- NeighborsDirected {
- iter: match self.nodes.get(&a) {
- Some(neigh) => neigh.iter(),
- None => [].iter(),
- },
- start_node: a,
- dir,
- ty: self.ty,
- }
- }
-
- /// Return an iterator of target nodes with an edge starting from `a`,
- /// paired with their respective edge weights.
- ///
- /// - `Directed`: Outgoing edges from `a`.
- /// - `Undirected`: All edges from or to `a`.
- ///
- /// Produces an empty iterator if the node doesn't exist.<br>
- /// Iterator element type is `(N, N, &E)`.
- pub fn edges(&self, a: N) -> Edges<N, E, Ty, S> {
- Edges {
- from: a,
- iter: self.neighbors(a),
- edges: &self.edges,
- }
- }
-
- /// Return an iterator of target nodes with an edge starting from `a`,
- /// paired with their respective edge weights.
- ///
- /// - `Directed`, `Outgoing`: All edges from `a`.
- /// - `Directed`, `Incoming`: All edges to `a`.
- /// - `Undirected`, `Outgoing`: All edges connected to `a`, with `a` being the source of each
- /// edge.
- /// - `Undirected`, `Incoming`: All edges connected to `a`, with `a` being the target of each
- /// edge.
- ///
- /// Produces an empty iterator if the node doesn't exist.<br>
- /// Iterator element type is `(N, N, &E)`.
- pub fn edges_directed(&self, a: N, dir: Direction) -> EdgesDirected<N, E, Ty, S> {
- EdgesDirected {
- from: a,
- iter: self.neighbors_directed(a, dir),
- dir,
- edges: &self.edges,
- }
- }
-
- /// Return a reference to the edge weight connecting `a` with `b`, or
- /// `None` if the edge does not exist in the graph.
- pub fn edge_weight(&self, a: N, b: N) -> Option<&E> {
- self.edges.get(&Self::edge_key(a, b))
- }
-
- /// Return a mutable reference to the edge weight connecting `a` with `b`, or
- /// `None` if the edge does not exist in the graph.
- pub fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E> {
- self.edges.get_mut(&Self::edge_key(a, b))
- }
-
- /// Return an iterator over all edges of the graph with their weight in arbitrary order.
- ///
- /// Iterator element type is `(N, N, &E)`
- pub fn all_edges(&self) -> AllEdges<N, E, Ty> {
- AllEdges {
- inner: self.edges.iter(),
- ty: self.ty,
- }
- }
-
- /// Return an iterator over all edges of the graph in arbitrary order, with a mutable reference
- /// to their weight.
- ///
- /// Iterator element type is `(N, N, &mut E)`
- pub fn all_edges_mut(&mut self) -> AllEdgesMut<N, E, Ty> {
- AllEdgesMut {
- inner: self.edges.iter_mut(),
- ty: self.ty,
- }
- }
-
- /// Return a parallel iterator over all edges of the graph with their weight in arbitrary
- /// order.
- ///
- /// Iterator element type is `(N, N, &E)`
- #[cfg(feature = "rayon")]
- pub fn par_all_edges(&self) -> ParAllEdges<N, E, Ty>
- where
- N: Send + Sync,
- E: Sync,
- {
- ParAllEdges {
- inner: self.edges.par_iter(),
- ty: PhantomData,
- }
- }
-
- /// Return a parallel iterator over all edges of the graph in arbitrary order, with a mutable
- /// reference to their weight.
- ///
- /// Iterator element type is `(N, N, &mut E)`
- #[cfg(feature = "rayon")]
- pub fn par_all_edges_mut(&mut self) -> ParAllEdgesMut<N, E, Ty>
- where
- N: Send + Sync,
- E: Send,
- {
- ParAllEdgesMut {
- inner: self.edges.par_iter_mut(),
- ty: PhantomData,
- }
- }
-
- /// Return a `Graph` that corresponds to this `GraphMap`.
- ///
- /// 1. Note that node and edge indices in the `Graph` have nothing in common
- /// with the `GraphMap`s node weights `N`. The node weights `N` are used as
- /// node weights in the resulting `Graph`, too.
- /// 2. Note that the index type is user-chosen.
- ///
- /// Computes in **O(|V| + |E|)** time (average).
- ///
- /// **Panics** if the number of nodes or edges does not fit with
- /// the resulting graph's index type.
- pub fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix>
- where
- Ix: crate::graph::IndexType,
- {
- // assuming two successive iterations of the same hashmap produce the same order
- let mut gr = Graph::with_capacity(self.node_count(), self.edge_count());
- for (&node, _) in &self.nodes {
- gr.add_node(node);
- }
- for ((a, b), edge_weight) in self.edges {
- let ai = self.nodes.get_index_of(&a).unwrap();
- let bi = self.nodes.get_index_of(&b).unwrap();
- gr.add_edge(node_index(ai), node_index(bi), edge_weight);
- }
- gr
- }
-
- /// Creates a `GraphMap` that corresponds to the given `Graph`.
- ///
- /// **Warning**: Nodes with the same weight are merged and only the last parallel edge
- /// is kept. Node and edge indices of the `Graph` are lost. Only use this function
- /// if the node weights are distinct and there are no parallel edges.
- ///
- /// Computes in **O(|V| + |E|)** time (average).
- pub fn from_graph<Ix>(graph: Graph<N, E, Ty, Ix>) -> Self
- where
- Ix: crate::graph::IndexType,
- E: Clone,
- S: Default,
- {
- let mut new_graph: GraphMap<N, E, Ty, S> =
- GraphMap::with_capacity(graph.node_count(), graph.edge_count());
-
- for node in graph.raw_nodes() {
- new_graph.add_node(node.weight);
- }
-
- for edge in graph.edge_indices() {
- let (a, b) = graph.edge_endpoints(edge).unwrap();
- new_graph.add_edge(
- *graph.node_weight(a).unwrap(),
- *graph.node_weight(b).unwrap(),
- graph.edge_weight(edge).unwrap().clone(),
- );
- }
-
- new_graph
- }
-}
-
-/// Create a new `GraphMap` from an iterable of edges.
-impl<N, E, Ty, Item, S> FromIterator<Item> for GraphMap<N, E, Ty, S>
-where
- Item: IntoWeightedEdge<E, NodeId = N>,
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher + Default,
-{
- fn from_iter<I>(iterable: I) -> Self
- where
- I: IntoIterator<Item = Item>,
- {
- let iter = iterable.into_iter();
- let (low, _) = iter.size_hint();
- let mut g = Self::with_capacity(0, low);
- g.extend(iter);
- g
- }
-}
-
-/// Extend the graph from an iterable of edges.
-///
-/// Nodes are inserted automatically to match the edges.
-impl<N, E, Ty, Item, S> Extend<Item> for GraphMap<N, E, Ty, S>
-where
- Item: IntoWeightedEdge<E, NodeId = N>,
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- fn extend<I>(&mut self, iterable: I)
- where
- I: IntoIterator<Item = Item>,
- {
- let iter = iterable.into_iter();
- let (low, _) = iter.size_hint();
- self.edges.reserve(low);
-
- for elt in iter {
- let (source, target, weight) = elt.into_weighted_edge();
- self.add_edge(source, target, weight);
- }
- }
-}
-
-iterator_wrap! {
- impl (Iterator DoubleEndedIterator ExactSizeIterator) for
- #[derive(Debug, Clone)]
- struct Nodes <'a, N> where { N: 'a + NodeTrait }
- item: N,
- iter: Copied<Keys<'a, N, Vec<(N, CompactDirection)>>>,
-}
-
-#[derive(Debug, Clone)]
-pub struct Neighbors<'a, N, Ty = Undirected>
-where
- N: 'a,
- Ty: EdgeType,
-{
- iter: Iter<'a, (N, CompactDirection)>,
- ty: PhantomData<Ty>,
-}
-
-impl<'a, N, Ty> Iterator for Neighbors<'a, N, Ty>
-where
- N: NodeTrait,
- Ty: EdgeType,
-{
- type Item = N;
- fn next(&mut self) -> Option<N> {
- if Ty::is_directed() {
- (&mut self.iter)
- .filter_map(|&(n, dir)| if dir == Outgoing { Some(n) } else { None })
- .next()
- } else {
- self.iter.next().map(|&(n, _)| n)
- }
- }
- fn size_hint(&self) -> (usize, Option<usize>) {
- let (lower, upper) = self.iter.size_hint();
- if Ty::is_directed() {
- (0, upper)
- } else {
- (lower, upper)
- }
- }
-}
-
-#[derive(Debug, Clone)]
-pub struct NeighborsDirected<'a, N, Ty>
-where
- N: 'a,
- Ty: EdgeType,
-{
- iter: Iter<'a, (N, CompactDirection)>,
- start_node: N,
- dir: Direction,
- ty: PhantomData<Ty>,
-}
-
-impl<'a, N, Ty> Iterator for NeighborsDirected<'a, N, Ty>
-where
- N: NodeTrait,
- Ty: EdgeType,
-{
- type Item = N;
- fn next(&mut self) -> Option<N> {
- if Ty::is_directed() {
- let self_dir = self.dir;
- let start_node = self.start_node;
- (&mut self.iter)
- .filter_map(move |&(n, dir)| {
- if dir == self_dir || n == start_node {
- Some(n)
- } else {
- None
- }
- })
- .next()
- } else {
- self.iter.next().map(|&(n, _)| n)
- }
- }
- fn size_hint(&self) -> (usize, Option<usize>) {
- let (lower, upper) = self.iter.size_hint();
- if Ty::is_directed() {
- (0, upper)
- } else {
- (lower, upper)
- }
- }
-}
-
-#[derive(Debug, Clone)]
-pub struct Edges<'a, N, E: 'a, Ty, S = RandomState>
-where
- N: 'a + NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- from: N,
- edges: &'a IndexMap<(N, N), E, S>,
- iter: Neighbors<'a, N, Ty>,
-}
-
-impl<'a, N, E, Ty, S> Iterator for Edges<'a, N, E, Ty, S>
-where
- N: 'a + NodeTrait,
- E: 'a,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type Item = (N, N, &'a E);
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(|b| {
- let a = self.from;
- match self.edges.get(&GraphMap::<N, E, Ty>::edge_key(a, b)) {
- None => unreachable!(),
- Some(edge) => (a, b, edge),
- }
- })
- }
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-}
-
-#[derive(Debug, Clone)]
-pub struct EdgesDirected<'a, N, E: 'a, Ty, S = RandomState>
-where
- N: 'a + NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- from: N,
- dir: Direction,
- edges: &'a IndexMap<(N, N), E, S>,
- iter: NeighborsDirected<'a, N, Ty>,
-}
-
-impl<'a, N, E, Ty, S> Iterator for EdgesDirected<'a, N, E, Ty, S>
-where
- N: 'a + NodeTrait,
- E: 'a,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type Item = (N, N, &'a E);
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(|mut b| {
- let mut a = self.from;
- if self.dir == Direction::Incoming {
- mem::swap(&mut a, &mut b);
- }
- match self.edges.get(&GraphMap::<N, E, Ty>::edge_key(a, b)) {
- None => unreachable!(),
- Some(edge) => (a, b, edge),
- }
- })
- }
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-}
-
-#[derive(Debug, Clone)]
-pub struct AllEdges<'a, N, E: 'a, Ty>
-where
- N: 'a + NodeTrait,
-{
- inner: IndexMapIter<'a, (N, N), E>,
- ty: PhantomData<Ty>,
-}
-
-impl<'a, N, E, Ty> Iterator for AllEdges<'a, N, E, Ty>
-where
- N: 'a + NodeTrait,
- E: 'a,
- Ty: EdgeType,
-{
- type Item = (N, N, &'a E);
- fn next(&mut self) -> Option<Self::Item> {
- self.inner.next().map(|(&(a, b), v)| (a, b, v))
- }
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.inner.size_hint()
- }
-
- fn count(self) -> usize {
- self.inner.count()
- }
-
- fn nth(&mut self, n: usize) -> Option<Self::Item> {
- self.inner
- .nth(n)
- .map(|(&(n1, n2), weight)| (n1, n2, weight))
- }
-
- fn last(self) -> Option<Self::Item> {
- self.inner
- .last()
- .map(|(&(n1, n2), weight)| (n1, n2, weight))
- }
-}
-
-impl<'a, N, E, Ty> DoubleEndedIterator for AllEdges<'a, N, E, Ty>
-where
- N: 'a + NodeTrait,
- E: 'a,
- Ty: EdgeType,
-{
- fn next_back(&mut self) -> Option<Self::Item> {
- self.inner
- .next_back()
- .map(|(&(n1, n2), weight)| (n1, n2, weight))
- }
-}
-
-pub struct AllEdgesMut<'a, N, E: 'a, Ty>
-where
- N: 'a + NodeTrait,
-{
- inner: IndexMapIterMut<'a, (N, N), E>, // TODO: change to something that implements Debug + Clone?
- ty: PhantomData<Ty>,
-}
-
-impl<'a, N, E, Ty> Iterator for AllEdgesMut<'a, N, E, Ty>
-where
- N: 'a + NodeTrait,
- E: 'a,
- Ty: EdgeType,
-{
- type Item = (N, N, &'a mut E);
- fn next(&mut self) -> Option<Self::Item> {
- self.inner
- .next()
- .map(|(&(n1, n2), weight)| (n1, n2, weight))
- }
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.inner.size_hint()
- }
-
- fn count(self) -> usize {
- self.inner.count()
- }
-
- fn nth(&mut self, n: usize) -> Option<Self::Item> {
- self.inner
- .nth(n)
- .map(|(&(n1, n2), weight)| (n1, n2, weight))
- }
-
- fn last(self) -> Option<Self::Item> {
- self.inner
- .last()
- .map(|(&(n1, n2), weight)| (n1, n2, weight))
- }
-}
-
-impl<'a, N, E, Ty> DoubleEndedIterator for AllEdgesMut<'a, N, E, Ty>
-where
- N: 'a + NodeTrait,
- E: 'a,
- Ty: EdgeType,
-{
- fn next_back(&mut self) -> Option<Self::Item> {
- self.inner
- .next_back()
- .map(|(&(n1, n2), weight)| (n1, n2, weight))
- }
-}
-
-/// Index `GraphMap` by node pairs to access edge weights.
-impl<N, E, Ty, S> Index<(N, N)> for GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type Output = E;
- fn index(&self, index: (N, N)) -> &E {
- let index = Self::edge_key(index.0, index.1);
- self.edge_weight(index.0, index.1)
- .expect("GraphMap::index: no such edge")
- }
-}
-
-/// Index `GraphMap` by node pairs to access edge weights.
-impl<N, E, Ty, S> IndexMut<(N, N)> for GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- fn index_mut(&mut self, index: (N, N)) -> &mut E {
- let index = Self::edge_key(index.0, index.1);
- self.edge_weight_mut(index.0, index.1)
- .expect("GraphMap::index: no such edge")
- }
-}
-
-/// Create a new empty `GraphMap`.
-impl<N, E, Ty, S> Default for GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher + Default,
-{
- fn default() -> Self {
- GraphMap::with_capacity(0, 0)
- }
-}
-
-/// A reference that is hashed and compared by its pointer value.
-///
-/// `Ptr` is used for certain configurations of `GraphMap`,
-/// in particular in the combination where the node type for
-/// `GraphMap` is something of type for example `Ptr(&Cell<T>)`,
-/// with the `Cell<T>` being `TypedArena` allocated.
-pub struct Ptr<'b, T: 'b>(pub &'b T);
-
-impl<'b, T> Copy for Ptr<'b, T> {}
-impl<'b, T> Clone for Ptr<'b, T> {
- fn clone(&self) -> Self {
- *self
- }
-}
-
-fn ptr_eq<T>(a: *const T, b: *const T) -> bool {
- a == b
-}
-
-impl<'b, T> PartialEq for Ptr<'b, T> {
- /// Ptr compares by pointer equality, i.e if they point to the same value
- fn eq(&self, other: &Ptr<'b, T>) -> bool {
- ptr_eq(self.0, other.0)
- }
-}
-
-impl<'b, T> PartialOrd for Ptr<'b, T> {
- fn partial_cmp(&self, other: &Ptr<'b, T>) -> Option<Ordering> {
- Some(self.cmp(other))
- }
-}
-
-impl<'b, T> Ord for Ptr<'b, T> {
- /// Ptr is ordered by pointer value, i.e. an arbitrary but stable and total order.
- fn cmp(&self, other: &Ptr<'b, T>) -> Ordering {
- let a: *const T = self.0;
- let b: *const T = other.0;
- a.cmp(&b)
- }
-}
-
-impl<'b, T> Deref for Ptr<'b, T> {
- type Target = T;
- fn deref(&self) -> &T {
- self.0
- }
-}
-
-impl<'b, T> Eq for Ptr<'b, T> {}
-
-impl<'b, T> Hash for Ptr<'b, T> {
- fn hash<H: hash::Hasher>(&self, st: &mut H) {
- let ptr = (self.0) as *const T;
- ptr.hash(st)
- }
-}
-
-impl<'b, T: fmt::Debug> fmt::Debug for Ptr<'b, T> {
- fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
- self.0.fmt(f)
- }
-}
-
-#[derive(Debug, Clone)]
-pub struct NodeIdentifiers<'a, N, E: 'a, Ty>
-where
- N: 'a + NodeTrait,
-{
- iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
- ty: PhantomData<Ty>,
- edge_ty: PhantomData<E>,
-}
-
-impl<'a, N, E, Ty> Iterator for NodeIdentifiers<'a, N, E, Ty>
-where
- N: 'a + NodeTrait,
- E: 'a,
- Ty: EdgeType,
-{
- type Item = N;
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(|(&n, _)| n)
- }
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-}
-
-#[derive(Debug, Clone)]
-pub struct NodeReferences<'a, N, E: 'a, Ty>
-where
- N: 'a + NodeTrait,
-{
- iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
- ty: PhantomData<Ty>,
- edge_ty: PhantomData<E>,
-}
-
-impl<'a, N, E, Ty> Iterator for NodeReferences<'a, N, E, Ty>
-where
- N: 'a + NodeTrait,
- E: 'a,
- Ty: EdgeType,
-{
- type Item = (N, &'a N);
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(|(n, _)| (*n, n))
- }
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-}
-
-impl<N, E, Ty, S> visit::GraphBase for GraphMap<N, E, Ty, S>
-where
- N: Copy + PartialEq,
- S: BuildHasher,
-{
- type NodeId = N;
- type EdgeId = (N, N);
-}
-
-impl<N, E, Ty, S> visit::Data for GraphMap<N, E, Ty, S>
-where
- N: Copy + PartialEq,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type NodeWeight = N;
- type EdgeWeight = E;
-}
-
-impl<N, E, Ty, S> visit::Visitable for GraphMap<N, E, Ty, S>
-where
- N: Copy + Ord + Hash,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type Map = HashSet<N>;
- fn visit_map(&self) -> HashSet<N> {
- HashSet::with_capacity(self.node_count())
- }
- fn reset_map(&self, map: &mut Self::Map) {
- map.clear();
- }
-}
-
-impl<N, E, Ty, S> visit::GraphProp for GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type EdgeType = Ty;
-}
-
-impl<'a, N, E, Ty, S> visit::IntoNodeReferences for &'a GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type NodeRef = (N, &'a N);
- type NodeReferences = NodeReferences<'a, N, E, Ty>;
- fn node_references(self) -> Self::NodeReferences {
- NodeReferences {
- iter: self.nodes.iter(),
- ty: self.ty,
- edge_ty: PhantomData,
- }
- }
-}
-
-impl<'a, N, E: 'a, Ty, S> visit::IntoNodeIdentifiers for &'a GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type NodeIdentifiers = NodeIdentifiers<'a, N, E, Ty>;
-
- fn node_identifiers(self) -> Self::NodeIdentifiers {
- NodeIdentifiers {
- iter: self.nodes.iter(),
- ty: self.ty,
- edge_ty: PhantomData,
- }
- }
-}
-
-impl<N, E, Ty, S> visit::NodeCount for GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- fn node_count(&self) -> usize {
- (*self).node_count()
- }
-}
-
-impl<N, E, Ty, S> visit::NodeIndexable for GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- fn node_bound(&self) -> usize {
- self.node_count()
- }
- fn to_index(&self, ix: Self::NodeId) -> usize {
- self.nodes.get_index_of(&ix).unwrap()
- }
- fn from_index(&self, ix: usize) -> Self::NodeId {
- assert!(
- ix < self.nodes.len(),
- "The requested index {} is out-of-bounds.",
- ix
- );
- let (&key, _) = self.nodes.get_index(ix).unwrap();
- key
- }
-}
-
-impl<N, E, Ty, S> visit::NodeCompactIndexable for GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
-}
-
-impl<'a, N: 'a, E, Ty, S> visit::IntoNeighbors for &'a GraphMap<N, E, Ty, S>
-where
- N: Copy + Ord + Hash,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type Neighbors = Neighbors<'a, N, Ty>;
- fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
- self.neighbors(n)
- }
-}
-
-impl<'a, N: 'a, E, Ty, S> visit::IntoNeighborsDirected for &'a GraphMap<N, E, Ty, S>
-where
- N: Copy + Ord + Hash,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type NeighborsDirected = NeighborsDirected<'a, N, Ty>;
- fn neighbors_directed(self, n: N, dir: Direction) -> Self::NeighborsDirected {
- self.neighbors_directed(n, dir)
- }
-}
-
-impl<N, E, Ty, S> visit::EdgeIndexable for GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- fn edge_bound(&self) -> usize {
- self.edge_count()
- }
-
- fn to_index(&self, ix: Self::EdgeId) -> usize {
- self.edges.get_index_of(&ix).unwrap()
- }
-
- fn from_index(&self, ix: usize) -> Self::EdgeId {
- assert!(
- ix < self.edges.len(),
- "The requested index {} is out-of-bounds.",
- ix
- );
- let (&key, _) = self.edges.get_index(ix).unwrap();
- key
- }
-}
-
-impl<'a, N: 'a, E: 'a, Ty, S> visit::IntoEdges for &'a GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type Edges = Edges<'a, N, E, Ty, S>;
- fn edges(self, a: Self::NodeId) -> Self::Edges {
- self.edges(a)
- }
-}
-
-impl<'a, N: 'a, E: 'a, Ty, S> visit::IntoEdgesDirected for &'a GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type EdgesDirected = EdgesDirected<'a, N, E, Ty, S>;
- fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected {
- self.edges_directed(a, dir)
- }
-}
-
-impl<'a, N: 'a, E: 'a, Ty, S> visit::IntoEdgeReferences for &'a GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type EdgeRef = (N, N, &'a E);
- type EdgeReferences = AllEdges<'a, N, E, Ty>;
- fn edge_references(self) -> Self::EdgeReferences {
- self.all_edges()
- }
-}
-
-impl<N, E, Ty, S> visit::EdgeCount for GraphMap<N, E, Ty, S>
-where
- N: NodeTrait,
- Ty: EdgeType,
- S: BuildHasher,
-{
- #[inline]
- fn edge_count(&self) -> usize {
- self.edge_count()
- }
-}
-
-/// The `GraphMap` keeps an adjacency matrix internally.
-impl<N, E, Ty, S> visit::GetAdjacencyMatrix for GraphMap<N, E, Ty, S>
-where
- N: Copy + Ord + Hash,
- Ty: EdgeType,
- S: BuildHasher,
-{
- type AdjMatrix = ();
- #[inline]
- fn adjacency_matrix(&self) {}
- #[inline]
- fn is_adjacent(&self, _: &(), a: N, b: N) -> bool {
- self.contains_edge(a, b)
- }
-}
-
-/// A [ParallelIterator] over this graph's nodes.
-#[cfg(feature = "rayon")]
-pub struct ParNodes<'a, N>
-where
- N: NodeTrait + Send + Sync,
-{
- iter: ParKeys<'a, N, Vec<(N, CompactDirection)>>,
-}
-
-#[cfg(feature = "rayon")]
-impl<'a, N> ParallelIterator for ParNodes<'a, N>
-where
- N: NodeTrait + Send + Sync,
-{
- type Item = N;
-
- fn drive_unindexed<C>(self, consumer: C) -> C::Result
- where
- C: rayon::iter::plumbing::UnindexedConsumer<Self::Item>,
- {
- self.iter.copied().drive_unindexed(consumer)
- }
-
- fn opt_len(&self) -> Option<usize> {
- self.iter.opt_len()
- }
-}
-
-#[cfg(feature = "rayon")]
-impl<'a, N> IndexedParallelIterator for ParNodes<'a, N>
-where
- N: NodeTrait + Send + Sync,
-{
- fn drive<C>(self, consumer: C) -> C::Result
- where
- C: rayon::iter::plumbing::Consumer<Self::Item>,
- {
- self.iter.copied().drive(consumer)
- }
-
- fn len(&self) -> usize {
- self.iter.len()
- }
-
- fn with_producer<CB>(self, callback: CB) -> CB::Output
- where
- CB: rayon::iter::plumbing::ProducerCallback<Self::Item>,
- {
- self.iter.copied().with_producer(callback)
- }
-}
-
-/// A [ParallelIterator] over this graph's edges.
-#[cfg(feature = "rayon")]
-pub struct ParAllEdges<'a, N, E, Ty>
-where
- N: NodeTrait + Send + Sync,
- E: Sync,
-{
- inner: ParIter<'a, (N, N), E>,
- ty: PhantomData<fn(Ty)>,
-}
-
-#[cfg(feature = "rayon")]
-impl<'a, N, E, Ty> ParallelIterator for ParAllEdges<'a, N, E, Ty>
-where
- N: NodeTrait + Send + Sync,
- E: Sync,
-{
- type Item = (N, N, &'a E);
-
- fn drive_unindexed<C>(self, c: C) -> C::Result
- where
- C: rayon::iter::plumbing::UnindexedConsumer<Self::Item>,
- {
- self.inner.map(|(&(a, b), v)| (a, b, v)).drive_unindexed(c)
- }
-
- fn opt_len(&self) -> Option<usize> {
- self.inner.opt_len()
- }
-}
-
-#[cfg(feature = "rayon")]
-impl<'a, N, E, Ty> IndexedParallelIterator for ParAllEdges<'a, N, E, Ty>
-where
- N: NodeTrait + Send + Sync,
- E: Sync,
-{
- fn drive<C>(self, consumer: C) -> C::Result
- where
- C: rayon::iter::plumbing::Consumer<Self::Item>,
- {
- self.inner.map(|(&(a, b), v)| (a, b, v)).drive(consumer)
- }
-
- fn len(&self) -> usize {
- self.inner.len()
- }
-
- fn with_producer<CB>(self, callback: CB) -> CB::Output
- where
- CB: rayon::iter::plumbing::ProducerCallback<Self::Item>,
- {
- self.inner
- .map(|(&(a, b), v)| (a, b, v))
- .with_producer(callback)
- }
-}
-
-/// A [ParallelIterator] over this graph's edges by mutable reference.
-#[cfg(feature = "rayon")]
-pub struct ParAllEdgesMut<'a, N, E: 'a, Ty>
-where
- N: NodeTrait + Send + Sync,
- E: Send,
-{
- inner: ParIterMut<'a, (N, N), E>,
- ty: PhantomData<fn(Ty)>,
-}
-
-#[cfg(feature = "rayon")]
-impl<'a, N, E, Ty> ParallelIterator for ParAllEdgesMut<'a, N, E, Ty>
-where
- N: NodeTrait + Send + Sync,
- E: Send,
-{
- type Item = (N, N, &'a mut E);
-
- fn drive_unindexed<C>(self, c: C) -> C::Result
- where
- C: rayon::iter::plumbing::UnindexedConsumer<Self::Item>,
- {
- self.inner.map(|(&(a, b), v)| (a, b, v)).drive_unindexed(c)
- }
-
- fn opt_len(&self) -> Option<usize> {
- self.inner.opt_len()
- }
-}
-
-#[cfg(feature = "rayon")]
-impl<'a, N, E, Ty> IndexedParallelIterator for ParAllEdgesMut<'a, N, E, Ty>
-where
- N: NodeTrait + Send + Sync,
- E: Send,
-{
- fn drive<C>(self, consumer: C) -> C::Result
- where
- C: rayon::iter::plumbing::Consumer<Self::Item>,
- {
- self.inner.map(|(&(a, b), v)| (a, b, v)).drive(consumer)
- }
-
- fn len(&self) -> usize {
- self.inner.len()
- }
-
- fn with_producer<CB>(self, callback: CB) -> CB::Output
- where
- CB: rayon::iter::plumbing::ProducerCallback<Self::Item>,
- {
- self.inner
- .map(|(&(a, b), v)| (a, b, v))
- .with_producer(callback)
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-02 02:51:44 +0000