summaryrefslogtreecommitdiff
path: root/vendor/petgraph-0.6.5/src/csr.rs
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/petgraph-0.6.5/src/csr.rs')
-rw-r--r--vendor/petgraph-0.6.5/src/csr.rs1148
1 files changed, 0 insertions, 1148 deletions
diff --git a/vendor/petgraph-0.6.5/src/csr.rs b/vendor/petgraph-0.6.5/src/csr.rs
deleted file mode 100644
index f9f7446c..00000000
--- a/vendor/petgraph-0.6.5/src/csr.rs
+++ /dev/null
@@ -1,1148 +0,0 @@
-//! Compressed Sparse Row (CSR) is a sparse adjacency matrix graph.
-
-use std::cmp::{max, Ordering};
-use std::iter::{Enumerate, Zip};
-use std::marker::PhantomData;
-use std::ops::{Index, IndexMut, Range};
-use std::slice::Windows;
-
-use crate::visit::{
- Data, EdgeCount, EdgeRef, GetAdjacencyMatrix, GraphBase, GraphProp, IntoEdgeReferences,
- IntoEdges, IntoNeighbors, IntoNodeIdentifiers, IntoNodeReferences, NodeCompactIndexable,
- NodeCount, NodeIndexable, Visitable,
-};
-
-use crate::util::zip;
-
-#[doc(no_inline)]
-pub use crate::graph::{DefaultIx, IndexType};
-
-use crate::{Directed, EdgeType, IntoWeightedEdge};
-
-/// Csr node index type, a plain integer.
-pub type NodeIndex<Ix = DefaultIx> = Ix;
-/// Csr edge index type, a plain integer.
-pub type EdgeIndex = usize;
-
-const BINARY_SEARCH_CUTOFF: usize = 32;
-
-/// Compressed Sparse Row ([`CSR`]) is a sparse adjacency matrix graph.
-///
-/// `CSR` is parameterized over:
-///
-/// - Associated data `N` for nodes and `E` for edges, called *weights*.
-/// The associated data can be of arbitrary type.
-/// - Edge type `Ty` that determines whether the graph edges are directed or undirected.
-/// - Index type `Ix`, which determines the maximum size of the graph.
-///
-///
-/// Using **O(|E| + |V|)** space.
-///
-/// Self loops are allowed, no parallel edges.
-///
-/// Fast iteration of the outgoing edges of a vertex.
-///
-/// [`CSR`]: https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format)
-#[derive(Debug)]
-pub struct Csr<N = (), E = (), Ty = Directed, Ix = DefaultIx> {
- /// Column of next edge
- column: Vec<NodeIndex<Ix>>,
- /// weight of each edge; lock step with column
- edges: Vec<E>,
- /// Index of start of row Always node_count + 1 long.
- /// Last element is always equal to column.len()
- row: Vec<usize>,
- node_weights: Vec<N>,
- edge_count: usize,
- ty: PhantomData<Ty>,
-}
-
-impl<N, E, Ty, Ix> Default for Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn default() -> Self {
- Self::new()
- }
-}
-
-impl<N: Clone, E: Clone, Ty, Ix: Clone> Clone for Csr<N, E, Ty, Ix> {
- fn clone(&self) -> Self {
- Csr {
- column: self.column.clone(),
- edges: self.edges.clone(),
- row: self.row.clone(),
- node_weights: self.node_weights.clone(),
- edge_count: self.edge_count,
- ty: self.ty,
- }
- }
-}
-
-impl<N, E, Ty, Ix> Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- /// Create an empty `Csr`.
- pub fn new() -> Self {
- Csr {
- column: vec![],
- edges: vec![],
- row: vec![0; 1],
- node_weights: vec![],
- edge_count: 0,
- ty: PhantomData,
- }
- }
-
- /// Create a new `Csr` with `n` nodes. `N` must implement [`Default`] for the weight of each node.
- ///
- /// [`Default`]: https://doc.rust-lang.org/nightly/core/default/trait.Default.html
- ///
- /// # Example
- /// ```rust
- /// use petgraph::csr::Csr;
- /// use petgraph::prelude::*;
- ///
- /// let graph = Csr::<u8,()>::with_nodes(5);
- /// assert_eq!(graph.node_count(),5);
- /// assert_eq!(graph.edge_count(),0);
- ///
- /// assert_eq!(graph[0],0);
- /// assert_eq!(graph[4],0);
- /// ```
- pub fn with_nodes(n: usize) -> Self
- where
- N: Default,
- {
- Csr {
- column: Vec::new(),
- edges: Vec::new(),
- row: vec![0; n + 1],
- node_weights: (0..n).map(|_| N::default()).collect(),
- edge_count: 0,
- ty: PhantomData,
- }
- }
-}
-
-/// Csr creation error: edges were not in sorted order.
-#[derive(Clone, Debug)]
-pub struct EdgesNotSorted {
- first_error: (usize, usize),
-}
-
-impl<N, E, Ix> Csr<N, E, Directed, Ix>
-where
- Ix: IndexType,
-{
- /// Create a new `Csr` from a sorted sequence of edges
- ///
- /// Edges **must** be sorted and unique, where the sort order is the default
- /// order for the pair *(u, v)* in Rust (*u* has priority).
- ///
- /// Computes in **O(|E| + |V|)** time.
- /// # Example
- /// ```rust
- /// use petgraph::csr::Csr;
- /// use petgraph::prelude::*;
- ///
- /// let graph = Csr::<(),()>::from_sorted_edges(&[
- /// (0, 1), (0, 2),
- /// (1, 0), (1, 2), (1, 3),
- /// (2, 0),
- /// (3, 1),
- /// ]);
- /// ```
- pub fn from_sorted_edges<Edge>(edges: &[Edge]) -> Result<Self, EdgesNotSorted>
- where
- Edge: Clone + IntoWeightedEdge<E, NodeId = NodeIndex<Ix>>,
- N: Default,
- {
- let max_node_id = match edges
- .iter()
- .map(|edge| {
- let (x, y, _) = edge.clone().into_weighted_edge();
- max(x.index(), y.index())
- })
- .max()
- {
- None => return Ok(Self::with_nodes(0)),
- Some(x) => x,
- };
- let mut self_ = Self::with_nodes(max_node_id + 1);
- let mut iter = edges.iter().cloned().peekable();
- {
- let mut rows = self_.row.iter_mut();
-
- let mut rstart = 0;
- let mut last_target;
- 'outer: for (node, r) in (&mut rows).enumerate() {
- *r = rstart;
- last_target = None;
- 'inner: loop {
- if let Some(edge) = iter.peek() {
- let (n, m, weight) = edge.clone().into_weighted_edge();
- // check that the edges are in increasing sequence
- if node > n.index() {
- return Err(EdgesNotSorted {
- first_error: (n.index(), m.index()),
- });
- }
- /*
- debug_assert!(node <= n.index(),
- concat!("edges are not sorted, ",
- "failed assertion source {:?} <= {:?} ",
- "for edge {:?}"),
- node, n, (n, m));
- */
- if n.index() != node {
- break 'inner;
- }
- // check that the edges are in increasing sequence
- /*
- debug_assert!(last_target.map_or(true, |x| m > x),
- "edges are not sorted, failed assertion {:?} < {:?}",
- last_target, m);
- */
- if !last_target.map_or(true, |x| m > x) {
- return Err(EdgesNotSorted {
- first_error: (n.index(), m.index()),
- });
- }
- last_target = Some(m);
- self_.column.push(m);
- self_.edges.push(weight);
- rstart += 1;
- } else {
- break 'outer;
- }
- iter.next();
- }
- }
- for r in rows {
- *r = rstart;
- }
- }
-
- Ok(self_)
- }
-}
-
-impl<N, E, Ty, Ix> Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- pub fn node_count(&self) -> usize {
- self.row.len() - 1
- }
-
- pub fn edge_count(&self) -> usize {
- if self.is_directed() {
- self.column.len()
- } else {
- self.edge_count
- }
- }
-
- pub fn is_directed(&self) -> bool {
- Ty::is_directed()
- }
-
- /// Remove all edges
- pub fn clear_edges(&mut self) {
- self.column.clear();
- self.edges.clear();
- for r in &mut self.row {
- *r = 0;
- }
- if !self.is_directed() {
- self.edge_count = 0;
- }
- }
-
- /// Adds a new node with the given weight, returning the corresponding node index.
- pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix> {
- let i = self.row.len() - 1;
- self.row.insert(i, self.column.len());
- self.node_weights.insert(i, weight);
- Ix::new(i)
- }
-
- /// Return `true` if the edge was added
- ///
- /// If you add all edges in row-major order, the time complexity
- /// is **O(|V|·|E|)** for the whole operation.
- ///
- /// **Panics** if `a` or `b` are out of bounds.
- pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> bool
- where
- E: Clone,
- {
- let ret = self.add_edge_(a, b, weight.clone());
- if ret && !self.is_directed() {
- self.edge_count += 1;
- }
- if ret && !self.is_directed() && a != b {
- let _ret2 = self.add_edge_(b, a, weight);
- debug_assert_eq!(ret, _ret2);
- }
- ret
- }
-
- // Return false if the edge already exists
- fn add_edge_(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> bool {
- assert!(a.index() < self.node_count() && b.index() < self.node_count());
- // a x b is at (a, b) in the matrix
-
- // find current range of edges from a
- let pos = match self.find_edge_pos(a, b) {
- Ok(_) => return false, /* already exists */
- Err(i) => i,
- };
- self.column.insert(pos, b);
- self.edges.insert(pos, weight);
- // update row vector
- for r in &mut self.row[a.index() + 1..] {
- *r += 1;
- }
- true
- }
-
- fn find_edge_pos(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Result<usize, usize> {
- let (index, neighbors) = self.neighbors_of(a);
- if neighbors.len() < BINARY_SEARCH_CUTOFF {
- for (i, elt) in neighbors.iter().enumerate() {
- match elt.cmp(&b) {
- Ordering::Equal => return Ok(i + index),
- Ordering::Greater => return Err(i + index),
- Ordering::Less => {}
- }
- }
- Err(neighbors.len() + index)
- } else {
- match neighbors.binary_search(&b) {
- Ok(i) => Ok(i + index),
- Err(i) => Err(i + index),
- }
- }
- }
-
- /// Computes in **O(log |V|)** time.
- ///
- /// **Panics** if the node `a` does not exist.
- pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
- self.find_edge_pos(a, b).is_ok()
- }
-
- fn neighbors_range(&self, a: NodeIndex<Ix>) -> Range<usize> {
- let index = self.row[a.index()];
- let end = self
- .row
- .get(a.index() + 1)
- .cloned()
- .unwrap_or(self.column.len());
- index..end
- }
-
- fn neighbors_of(&self, a: NodeIndex<Ix>) -> (usize, &[Ix]) {
- let r = self.neighbors_range(a);
- (r.start, &self.column[r])
- }
-
- /// Computes in **O(1)** time.
- ///
- /// **Panics** if the node `a` does not exist.
- pub fn out_degree(&self, a: NodeIndex<Ix>) -> usize {
- let r = self.neighbors_range(a);
- r.end - r.start
- }
-
- /// Computes in **O(1)** time.
- ///
- /// **Panics** if the node `a` does not exist.
- pub fn neighbors_slice(&self, a: NodeIndex<Ix>) -> &[NodeIndex<Ix>] {
- self.neighbors_of(a).1
- }
-
- /// Computes in **O(1)** time.
- ///
- /// **Panics** if the node `a` does not exist.
- pub fn edges_slice(&self, a: NodeIndex<Ix>) -> &[E] {
- &self.edges[self.neighbors_range(a)]
- }
-
- /// Return an iterator of all edges of `a`.
- ///
- /// - `Directed`: Outgoing edges from `a`.
- /// - `Undirected`: All edges connected to `a`.
- ///
- /// **Panics** if the node `a` does not exist.<br>
- /// Iterator element type is `EdgeReference<E, Ty, Ix>`.
- pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<E, Ty, Ix> {
- let r = self.neighbors_range(a);
- Edges {
- index: r.start,
- source: a,
- iter: zip(&self.column[r.clone()], &self.edges[r]),
- ty: self.ty,
- }
- }
-}
-
-#[derive(Clone, Debug)]
-pub struct Edges<'a, E: 'a, Ty = Directed, Ix: 'a = DefaultIx> {
- index: usize,
- source: NodeIndex<Ix>,
- iter: Zip<SliceIter<'a, NodeIndex<Ix>>, SliceIter<'a, E>>,
- ty: PhantomData<Ty>,
-}
-
-#[derive(Debug)]
-pub struct EdgeReference<'a, E: 'a, Ty, Ix: 'a = DefaultIx> {
- index: EdgeIndex,
- source: NodeIndex<Ix>,
- target: NodeIndex<Ix>,
- weight: &'a E,
- ty: PhantomData<Ty>,
-}
-
-impl<'a, E, Ty, Ix: Copy> Clone for EdgeReference<'a, E, Ty, Ix> {
- fn clone(&self) -> Self {
- *self
- }
-}
-
-impl<'a, E, Ty, Ix: Copy> Copy for EdgeReference<'a, E, Ty, Ix> {}
-
-impl<'a, Ty, E, Ix> EdgeReference<'a, E, Ty, Ix>
-where
- Ty: EdgeType,
-{
- /// Access the edge’s weight.
- ///
- /// **NOTE** that this method offers a longer lifetime
- /// than the trait (unfortunately they don't match yet).
- pub fn weight(&self) -> &'a E {
- self.weight
- }
-}
-
-impl<'a, E, Ty, Ix> EdgeRef for EdgeReference<'a, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type NodeId = NodeIndex<Ix>;
- type EdgeId = EdgeIndex;
- type Weight = E;
-
- fn source(&self) -> Self::NodeId {
- self.source
- }
- fn target(&self) -> Self::NodeId {
- self.target
- }
- fn weight(&self) -> &E {
- self.weight
- }
- fn id(&self) -> Self::EdgeId {
- self.index
- }
-}
-
-impl<'a, E, Ty, Ix> Iterator for Edges<'a, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type Item = EdgeReference<'a, E, Ty, Ix>;
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(move |(&j, w)| {
- let index = self.index;
- self.index += 1;
- EdgeReference {
- index,
- source: self.source,
- target: j,
- weight: w,
- ty: PhantomData,
- }
- })
- }
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-}
-
-impl<N, E, Ty, Ix> Data for Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type NodeWeight = N;
- type EdgeWeight = E;
-}
-
-impl<'a, N, E, Ty, Ix> IntoEdgeReferences for &'a Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type EdgeRef = EdgeReference<'a, E, Ty, Ix>;
- type EdgeReferences = EdgeReferences<'a, E, Ty, Ix>;
- fn edge_references(self) -> Self::EdgeReferences {
- EdgeReferences {
- index: 0,
- source_index: Ix::new(0),
- edge_ranges: self.row.windows(2).enumerate(),
- column: &self.column,
- edges: &self.edges,
- iter: zip(&[], &[]),
- ty: self.ty,
- }
- }
-}
-
-#[derive(Debug, Clone)]
-pub struct EdgeReferences<'a, E: 'a, Ty, Ix: 'a> {
- source_index: NodeIndex<Ix>,
- index: usize,
- edge_ranges: Enumerate<Windows<'a, usize>>,
- column: &'a [NodeIndex<Ix>],
- edges: &'a [E],
- iter: Zip<SliceIter<'a, NodeIndex<Ix>>, SliceIter<'a, E>>,
- ty: PhantomData<Ty>,
-}
-
-impl<'a, E, Ty, Ix> Iterator for EdgeReferences<'a, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type Item = EdgeReference<'a, E, Ty, Ix>;
- fn next(&mut self) -> Option<Self::Item> {
- loop {
- if let Some((&j, w)) = self.iter.next() {
- let index = self.index;
- self.index += 1;
- return Some(EdgeReference {
- index,
- source: self.source_index,
- target: j,
- weight: w,
- ty: PhantomData,
- });
- }
- if let Some((i, w)) = self.edge_ranges.next() {
- let a = w[0];
- let b = w[1];
- self.iter = zip(&self.column[a..b], &self.edges[a..b]);
- self.source_index = Ix::new(i);
- } else {
- return None;
- }
- }
- }
-}
-
-impl<'a, N, E, Ty, Ix> IntoEdges for &'a Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type Edges = Edges<'a, E, Ty, Ix>;
- fn edges(self, a: Self::NodeId) -> Self::Edges {
- self.edges(a)
- }
-}
-
-impl<N, E, Ty, Ix> GraphBase for Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type NodeId = NodeIndex<Ix>;
- type EdgeId = EdgeIndex; // index into edges vector
-}
-
-use fixedbitset::FixedBitSet;
-
-impl<N, E, Ty, Ix> Visitable for Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type Map = FixedBitSet;
- fn visit_map(&self) -> FixedBitSet {
- FixedBitSet::with_capacity(self.node_count())
- }
- fn reset_map(&self, map: &mut Self::Map) {
- map.clear();
- map.grow(self.node_count());
- }
-}
-
-use std::slice::Iter as SliceIter;
-
-#[derive(Clone, Debug)]
-pub struct Neighbors<'a, Ix: 'a = DefaultIx> {
- iter: SliceIter<'a, NodeIndex<Ix>>,
-}
-
-impl<'a, Ix> Iterator for Neighbors<'a, Ix>
-where
- Ix: IndexType,
-{
- type Item = NodeIndex<Ix>;
-
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().cloned()
- }
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-}
-
-impl<'a, N, E, Ty, Ix> IntoNeighbors for &'a Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type Neighbors = Neighbors<'a, Ix>;
-
- /// Return an iterator of all neighbors of `a`.
- ///
- /// - `Directed`: Targets of outgoing edges from `a`.
- /// - `Undirected`: Opposing endpoints of all edges connected to `a`.
- ///
- /// **Panics** if the node `a` does not exist.<br>
- /// Iterator element type is `NodeIndex<Ix>`.
- fn neighbors(self, a: Self::NodeId) -> Self::Neighbors {
- Neighbors {
- iter: self.neighbors_slice(a).iter(),
- }
- }
-}
-
-impl<N, E, Ty, Ix> NodeIndexable for Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn node_bound(&self) -> usize {
- self.node_count()
- }
- fn to_index(&self, a: Self::NodeId) -> usize {
- a.index()
- }
- fn from_index(&self, ix: usize) -> Self::NodeId {
- Ix::new(ix)
- }
-}
-
-impl<N, E, Ty, Ix> NodeCompactIndexable for Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
-}
-
-impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type Output = N;
-
- fn index(&self, ix: NodeIndex<Ix>) -> &N {
- &self.node_weights[ix.index()]
- }
-}
-
-impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn index_mut(&mut self, ix: NodeIndex<Ix>) -> &mut N {
- &mut self.node_weights[ix.index()]
- }
-}
-
-#[derive(Debug, Clone)]
-pub struct NodeIdentifiers<Ix = DefaultIx> {
- r: Range<usize>,
- ty: PhantomData<Ix>,
-}
-
-impl<Ix> Iterator for NodeIdentifiers<Ix>
-where
- Ix: IndexType,
-{
- type Item = NodeIndex<Ix>;
-
- fn next(&mut self) -> Option<Self::Item> {
- self.r.next().map(Ix::new)
- }
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.r.size_hint()
- }
-}
-
-impl<'a, N, E, Ty, Ix> IntoNodeIdentifiers for &'a Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type NodeIdentifiers = NodeIdentifiers<Ix>;
- fn node_identifiers(self) -> Self::NodeIdentifiers {
- NodeIdentifiers {
- r: 0..self.node_count(),
- ty: PhantomData,
- }
- }
-}
-
-impl<N, E, Ty, Ix> NodeCount for Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- fn node_count(&self) -> usize {
- (*self).node_count()
- }
-}
-
-impl<N, E, Ty, Ix> EdgeCount for Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- #[inline]
- fn edge_count(&self) -> usize {
- self.edge_count()
- }
-}
-
-impl<N, E, Ty, Ix> GraphProp for Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type EdgeType = Ty;
-}
-
-impl<'a, N, E, Ty, Ix> IntoNodeReferences for &'a Csr<N, E, Ty, Ix>
-where
- Ty: EdgeType,
- Ix: IndexType,
-{
- type NodeRef = (NodeIndex<Ix>, &'a N);
- type NodeReferences = NodeReferences<'a, N, Ix>;
- fn node_references(self) -> Self::NodeReferences {
- NodeReferences {
- iter: self.node_weights.iter().enumerate(),
- ty: PhantomData,
- }
- }
-}
-
-/// Iterator over all nodes of a graph.
-#[derive(Debug, Clone)]
-pub struct NodeReferences<'a, N: 'a, Ix: IndexType = DefaultIx> {
- iter: Enumerate<SliceIter<'a, N>>,
- ty: PhantomData<Ix>,
-}
-
-impl<'a, N, Ix> Iterator for NodeReferences<'a, N, Ix>
-where
- Ix: IndexType,
-{
- type Item = (NodeIndex<Ix>, &'a N);
-
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(|(i, weight)| (Ix::new(i), weight))
- }
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
-}
-
-impl<'a, N, Ix> DoubleEndedIterator for NodeReferences<'a, N, Ix>
-where
- Ix: IndexType,
-{
- fn next_back(&mut self) -> Option<Self::Item> {
- self.iter
- .next_back()
- .map(|(i, weight)| (Ix::new(i), weight))
- }
-}
-
-impl<'a, N, Ix> ExactSizeIterator for NodeReferences<'a, N, Ix> where Ix: IndexType {}
-
-/// The adjacency matrix for **Csr** is a bitmap that's computed by
-/// `.adjacency_matrix()`.
-impl<'a, N, E, Ty, Ix> GetAdjacencyMatrix for &'a Csr<N, E, Ty, Ix>
-where
- Ix: IndexType,
- Ty: EdgeType,
-{
- type AdjMatrix = FixedBitSet;
-
- fn adjacency_matrix(&self) -> FixedBitSet {
- let n = self.node_count();
- let mut matrix = FixedBitSet::with_capacity(n * n);
- for edge in self.edge_references() {
- let i = edge.source().index() * n + edge.target().index();
- matrix.put(i);
-
- let j = edge.source().index() + n * edge.target().index();
- matrix.put(j);
- }
- matrix
- }
-
- fn is_adjacent(&self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
- let n = self.edge_count();
- let index = n * a.index() + b.index();
- matrix.contains(index)
- }
-}
-
-/*
- *
-Example
-
-[ a 0 b
- c d e
- 0 0 f ]
-
-Values: [a, b, c, d, e, f]
-Column: [0, 2, 0, 1, 2, 2]
-Row : [0, 2, 5] <- value index of row start
-
- * */
-
-#[cfg(test)]
-mod tests {
- use super::Csr;
- use crate::algo::bellman_ford;
- use crate::algo::find_negative_cycle;
- use crate::algo::tarjan_scc;
- use crate::visit::Dfs;
- use crate::visit::VisitMap;
- use crate::Undirected;
-
- #[test]
- fn csr1() {
- let mut m: Csr = Csr::with_nodes(3);
- m.add_edge(0, 0, ());
- m.add_edge(1, 2, ());
- m.add_edge(2, 2, ());
- m.add_edge(0, 2, ());
- m.add_edge(1, 0, ());
- m.add_edge(1, 1, ());
- println!("{:?}", m);
- assert_eq!(&m.column, &[0, 2, 0, 1, 2, 2]);
- assert_eq!(&m.row, &[0, 2, 5, 6]);
-
- let added = m.add_edge(1, 2, ());
- assert!(!added);
- assert_eq!(&m.column, &[0, 2, 0, 1, 2, 2]);
- assert_eq!(&m.row, &[0, 2, 5, 6]);
-
- assert_eq!(m.neighbors_slice(1), &[0, 1, 2]);
- assert_eq!(m.node_count(), 3);
- assert_eq!(m.edge_count(), 6);
- }
-
- #[test]
- fn csr_undirected() {
- /*
- [ 1 . 1
- . . 1
- 1 1 1 ]
- */
-
- let mut m: Csr<(), (), Undirected> = Csr::with_nodes(3);
- m.add_edge(0, 0, ());
- m.add_edge(0, 2, ());
- m.add_edge(1, 2, ());
- m.add_edge(2, 2, ());
- println!("{:?}", m);
- assert_eq!(&m.column, &[0, 2, 2, 0, 1, 2]);
- assert_eq!(&m.row, &[0, 2, 3, 6]);
- assert_eq!(m.node_count(), 3);
- assert_eq!(m.edge_count(), 4);
- }
-
- #[should_panic]
- #[test]
- fn csr_from_error_1() {
- // not sorted in source
- let m: Csr = Csr::from_sorted_edges(&[(0, 1), (1, 0), (0, 2)]).unwrap();
- println!("{:?}", m);
- }
-
- #[should_panic]
- #[test]
- fn csr_from_error_2() {
- // not sorted in target
- let m: Csr = Csr::from_sorted_edges(&[(0, 1), (1, 0), (1, 2), (1, 1)]).unwrap();
- println!("{:?}", m);
- }
-
- #[test]
- fn csr_from() {
- let m: Csr =
- Csr::from_sorted_edges(&[(0, 1), (0, 2), (1, 0), (1, 1), (2, 2), (2, 4)]).unwrap();
- println!("{:?}", m);
- assert_eq!(m.neighbors_slice(0), &[1, 2]);
- assert_eq!(m.neighbors_slice(1), &[0, 1]);
- assert_eq!(m.neighbors_slice(2), &[2, 4]);
- assert_eq!(m.node_count(), 5);
- assert_eq!(m.edge_count(), 6);
- }
-
- #[test]
- fn csr_dfs() {
- let mut m: Csr = Csr::from_sorted_edges(&[
- (0, 1),
- (0, 2),
- (1, 0),
- (1, 1),
- (1, 3),
- (2, 2),
- // disconnected subgraph
- (4, 4),
- (4, 5),
- ])
- .unwrap();
- println!("{:?}", m);
- let mut dfs = Dfs::new(&m, 0);
- while let Some(_) = dfs.next(&m) {}
- for i in 0..m.node_count() - 2 {
- assert!(dfs.discovered.is_visited(&i), "visited {}", i)
- }
- assert!(!dfs.discovered[4]);
- assert!(!dfs.discovered[5]);
-
- m.add_edge(1, 4, ());
- println!("{:?}", m);
-
- dfs.reset(&m);
- dfs.move_to(0);
- while let Some(_) = dfs.next(&m) {}
-
- for i in 0..m.node_count() {
- assert!(dfs.discovered[i], "visited {}", i)
- }
- }
-
- #[test]
- fn csr_tarjan() {
- let m: Csr = Csr::from_sorted_edges(&[
- (0, 1),
- (0, 2),
- (1, 0),
- (1, 1),
- (1, 3),
- (2, 2),
- (2, 4),
- (4, 4),
- (4, 5),
- (5, 2),
- ])
- .unwrap();
- println!("{:?}", m);
- println!("{:?}", tarjan_scc(&m));
- }
-
- #[test]
- fn test_bellman_ford() {
- let m: Csr<(), _> = Csr::from_sorted_edges(&[
- (0, 1, 0.5),
- (0, 2, 2.),
- (1, 0, 1.),
- (1, 1, 1.),
- (1, 2, 1.),
- (1, 3, 1.),
- (2, 3, 3.),
- (4, 5, 1.),
- (5, 7, 2.),
- (6, 7, 1.),
- (7, 8, 3.),
- ])
- .unwrap();
- println!("{:?}", m);
- let result = bellman_ford(&m, 0).unwrap();
- println!("{:?}", result);
- let answer = [0., 0.5, 1.5, 1.5];
- assert_eq!(&answer, &result.distances[..4]);
- assert!(result.distances[4..].iter().all(|&x| f64::is_infinite(x)));
- }
-
- #[test]
- fn test_bellman_ford_neg_cycle() {
- let m: Csr<(), _> = Csr::from_sorted_edges(&[
- (0, 1, 0.5),
- (0, 2, 2.),
- (1, 0, 1.),
- (1, 1, -1.),
- (1, 2, 1.),
- (1, 3, 1.),
- (2, 3, 3.),
- ])
- .unwrap();
- let result = bellman_ford(&m, 0);
- assert!(result.is_err());
- }
-
- #[test]
- fn test_find_neg_cycle1() {
- let m: Csr<(), _> = Csr::from_sorted_edges(&[
- (0, 1, 0.5),
- (0, 2, 2.),
- (1, 0, 1.),
- (1, 1, -1.),
- (1, 2, 1.),
- (1, 3, 1.),
- (2, 3, 3.),
- ])
- .unwrap();
- let result = find_negative_cycle(&m, 0);
- assert_eq!(result, Some([1].to_vec()));
- }
-
- #[test]
- fn test_find_neg_cycle2() {
- let m: Csr<(), _> = Csr::from_sorted_edges(&[
- (0, 1, 0.5),
- (0, 2, 2.),
- (1, 0, 1.),
- (1, 2, 1.),
- (1, 3, 1.),
- (2, 3, 3.),
- ])
- .unwrap();
- let result = find_negative_cycle(&m, 0);
- assert_eq!(result, None);
- }
-
- #[test]
- fn test_find_neg_cycle3() {
- let m: Csr<(), _> = Csr::from_sorted_edges(&[
- (0, 1, 1.),
- (0, 2, 1.),
- (0, 3, 1.),
- (1, 3, 1.),
- (2, 1, 1.),
- (3, 2, -3.),
- ])
- .unwrap();
- let result = find_negative_cycle(&m, 0);
- assert_eq!(result, Some([1, 3, 2].to_vec()));
- }
-
- #[test]
- fn test_find_neg_cycle4() {
- let m: Csr<(), _> = Csr::from_sorted_edges(&[(0, 0, -1.)]).unwrap();
- let result = find_negative_cycle(&m, 0);
- assert_eq!(result, Some([0].to_vec()));
- }
-
- #[test]
- fn test_edge_references() {
- use crate::visit::EdgeRef;
- use crate::visit::IntoEdgeReferences;
- let m: Csr<(), _> = Csr::from_sorted_edges(&[
- (0, 1, 0.5),
- (0, 2, 2.),
- (1, 0, 1.),
- (1, 1, 1.),
- (1, 2, 1.),
- (1, 3, 1.),
- (2, 3, 3.),
- (4, 5, 1.),
- (5, 7, 2.),
- (6, 7, 1.),
- (7, 8, 3.),
- ])
- .unwrap();
- let mut copy = Vec::new();
- for e in m.edge_references() {
- copy.push((e.source(), e.target(), *e.weight()));
- println!("{:?}", e);
- }
- let m2: Csr<(), _> = Csr::from_sorted_edges(&copy).unwrap();
- assert_eq!(&m.row, &m2.row);
- assert_eq!(&m.column, &m2.column);
- assert_eq!(&m.edges, &m2.edges);
- }
-
- #[test]
- fn test_add_node() {
- let mut g: Csr = Csr::new();
- let a = g.add_node(());
- let b = g.add_node(());
- let c = g.add_node(());
-
- assert!(g.add_edge(a, b, ()));
- assert!(g.add_edge(b, c, ()));
- assert!(g.add_edge(c, a, ()));
-
- println!("{:?}", g);
-
- assert_eq!(g.node_count(), 3);
-
- assert_eq!(g.neighbors_slice(a), &[b]);
- assert_eq!(g.neighbors_slice(b), &[c]);
- assert_eq!(g.neighbors_slice(c), &[a]);
-
- assert_eq!(g.edge_count(), 3);
- }
-
- #[test]
- fn test_add_node_with_existing_edges() {
- let mut g: Csr = Csr::new();
- let a = g.add_node(());
- let b = g.add_node(());
-
- assert!(g.add_edge(a, b, ()));
-
- let c = g.add_node(());
-
- println!("{:?}", g);
-
- assert_eq!(g.node_count(), 3);
-
- assert_eq!(g.neighbors_slice(a), &[b]);
- assert_eq!(g.neighbors_slice(b), &[]);
- assert_eq!(g.neighbors_slice(c), &[]);
-
- assert_eq!(g.edge_count(), 1);
- }
-
- #[test]
- fn test_node_references() {
- use crate::visit::IntoNodeReferences;
- let mut g: Csr<u32> = Csr::new();
- g.add_node(42);
- g.add_node(3);
- g.add_node(44);
-
- let mut refs = g.node_references();
- assert_eq!(refs.next(), Some((0, &42)));
- assert_eq!(refs.next(), Some((1, &3)));
- assert_eq!(refs.next(), Some((2, &44)));
- assert_eq!(refs.next(), None);
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-02 02:58:35 +0000