blob: ae3a8d45020e36145835ce3573445d468ad9c790 [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, 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_else(|| 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);
}
}