petgraph/

csr.rs

//! 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);
    }
}