blob: 50a9ce2909751423313e4045221be3aff5429d86 [file] [log] [blame]
 //! 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, GraphProp, IntoEdgeReferences, NodeCount}; use crate::visit::{EdgeRef, GraphBase, IntoEdges, IntoNeighbors, NodeIndexable}; use crate::visit::{IntoNodeIdentifiers, NodeCompactIndexable, 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; /// 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 { /// Column of next edge column: Vec>, /// weight of each edge; lock step with column edges: Vec, /// Index of start of row Always node_count + 1 long. /// Last element is always equal to column.len() row: Vec, node_weights: Vec, edge_count: usize, ty: PhantomData, } impl Default for Csr where Ty: EdgeType, Ix: IndexType, { fn default() -> Self { Self::new() } } impl Clone for Csr { 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 Csr 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 /// [`Csr`]: #struct.Csr.html /// /// # Example /// ```rust /// use petgraph::csr::Csr; /// use petgraph::prelude::*; /// /// let graph = Csr::::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 Csr 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(edges: &[Edge]) -> Result where Edge: Clone + IntoWeightedEdge>, 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 node = 0; let mut rstart = 0; let mut last_target; 'outer: for r in &mut rows { *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(); } node += 1; } for r in rows { *r = rstart; } } Ok(self_) } } impl Csr 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 { 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, b: NodeIndex, 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, b: NodeIndex, 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, b: NodeIndex) -> Result { 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, b: NodeIndex) -> bool { self.find_edge_pos(a, b).is_ok() } fn neighbors_range(&self, a: NodeIndex) -> Range { let index = self.row[a.index()]; let end = self .row .get(a.index() + 1) .cloned() .unwrap_or_else(|| self.column.len()); index..end } fn neighbors_of(&self, a: NodeIndex) -> (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) -> 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) -> &[NodeIndex] { 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) -> &[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.
/// Iterator element type is `EdgeReference`. pub fn edges(&self, a: NodeIndex) -> Edges { 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, iter: Zip>, SliceIter<'a, E>>, ty: PhantomData, } #[derive(Debug)] pub struct EdgeReference<'a, E: 'a, Ty, Ix: 'a = DefaultIx> { index: EdgeIndex, source: NodeIndex, target: NodeIndex, weight: &'a E, ty: PhantomData, } 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; 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.iter.next().map(move |(&j, w)| { let index = self.index; self.index += 1; EdgeReference { index, source: self.source, target: j, weight: w, ty: PhantomData, } }) } } impl Data for Csr where Ty: EdgeType, Ix: IndexType, { type NodeWeight = N; type EdgeWeight = E; } impl<'a, N, E, Ty, Ix> IntoEdgeReferences for &'a Csr 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, } } } pub struct EdgeReferences<'a, E: 'a, Ty, Ix: 'a> { source_index: NodeIndex, index: usize, edge_ranges: Enumerate>, column: &'a [NodeIndex], edges: &'a [E], iter: Zip>, SliceIter<'a, E>>, ty: PhantomData, } 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 { 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 where Ty: EdgeType, Ix: IndexType, { type Edges = Edges<'a, E, Ty, Ix>; fn edges(self, a: Self::NodeId) -> Self::Edges { self.edges(a) } } impl GraphBase for Csr where Ty: EdgeType, Ix: IndexType, { type NodeId = NodeIndex; type EdgeId = EdgeIndex; // index into edges vector } use fixedbitset::FixedBitSet; impl Visitable for Csr 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>, } impl<'a, Ix> Iterator for Neighbors<'a, Ix> where Ix: IndexType, { type Item = NodeIndex; fn next(&mut self) -> Option { self.iter.next().cloned() } fn size_hint(&self) -> (usize, Option) { self.iter.size_hint() } } impl<'a, N, E, Ty, Ix> IntoNeighbors for &'a Csr 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.