petgraph/
csr.rs

1//! Compressed Sparse Row (CSR) is a sparse adjacency matrix graph.
2
3#[cfg(feature = "std")]
4use std::{
5    cmp::{max, Ordering},
6    iter::{Enumerate, Zip},
7    marker::PhantomData,
8    ops::{Index, IndexMut, Range},
9    slice::Iter as SliceIter,
10    slice::Windows,
11};
12
13#[cfg(not(feature = "std"))]
14use core::{
15    cmp::{max, Ordering},
16    iter::{Enumerate, Zip},
17    marker::PhantomData,
18    ops::{Index, IndexMut, Range},
19    slice::Iter as SliceIter,
20    slice::Windows,
21};
22
23#[cfg(not(feature = "std"))]
24use alloc::vec::Vec;
25
26use crate::visit::{Data, GraphProp, IntoEdgeReferences, NodeCount};
27use crate::visit::{EdgeRef, GraphBase, IntoEdges, IntoNeighbors, NodeIndexable};
28use crate::visit::{IntoNodeIdentifiers, NodeCompactIndexable, Visitable};
29
30use crate::util::zip;
31
32#[doc(no_inline)]
33pub use crate::graph::{DefaultIx, IndexType};
34
35use crate::{Directed, EdgeType, IntoWeightedEdge};
36
37/// Csr node index type, a plain integer.
38pub type NodeIndex<Ix = DefaultIx> = Ix;
39/// Csr edge index type, a plain integer.
40pub type EdgeIndex = usize;
41
42const BINARY_SEARCH_CUTOFF: usize = 32;
43
44/// Compressed Sparse Row ([`CSR`]) is a sparse adjacency matrix graph.
45///
46/// `CSR` is parameterized over:
47///
48/// - Associated data `N` for nodes and `E` for edges, called *weights*.
49///   The associated data can be of arbitrary type.
50/// - Edge type `Ty` that determines whether the graph edges are directed or undirected.
51/// - Index type `Ix`, which determines the maximum size of the graph.
52///
53///
54/// Using **O(|E| + |V|)** space.
55///
56/// Self loops are allowed, no parallel edges.
57///
58/// Fast iteration of the outgoing edges of a vertex.
59///
60/// [`CSR`]: https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_(CSR,_CRS_or_Yale_format)
61#[derive(Debug)]
62pub struct Csr<N = (), E = (), Ty = Directed, Ix = DefaultIx> {
63    /// Column of next edge
64    column: Vec<NodeIndex<Ix>>,
65    /// weight of each edge; lock step with column
66    edges: Vec<E>,
67    /// Index of start of row Always node_count + 1 long.
68    /// Last element is always equal to column.len()
69    row: Vec<usize>,
70    node_weights: Vec<N>,
71    edge_count: usize,
72    ty: PhantomData<Ty>,
73}
74
75impl<N, E, Ty, Ix> Default for Csr<N, E, Ty, Ix>
76where
77    Ty: EdgeType,
78    Ix: IndexType,
79{
80    fn default() -> Self {
81        Self::new()
82    }
83}
84
85impl<N: Clone, E: Clone, Ty, Ix: Clone> Clone for Csr<N, E, Ty, Ix> {
86    fn clone(&self) -> Self {
87        Csr {
88            column: self.column.clone(),
89            edges: self.edges.clone(),
90            row: self.row.clone(),
91            node_weights: self.node_weights.clone(),
92            edge_count: self.edge_count,
93            ty: self.ty,
94        }
95    }
96}
97
98impl<N, E, Ty, Ix> Csr<N, E, Ty, Ix>
99where
100    Ty: EdgeType,
101    Ix: IndexType,
102{
103    /// Create an empty `Csr`.
104    pub fn new() -> Self {
105        Csr {
106            column: vec![],
107            edges: vec![],
108            row: vec![0; 1],
109            node_weights: vec![],
110            edge_count: 0,
111            ty: PhantomData,
112        }
113    }
114
115    /// Create a new [`Csr`] with `n` nodes. `N` must implement [`Default`] for the weight of each node.
116    ///
117    /// [`Default`]: https://doc.rust-lang.org/nightly/core/default/trait.Default.html
118    /// [`Csr`]: #struct.Csr.html
119    ///
120    /// # Example
121    /// ```rust
122    /// use petgraph::csr::Csr;
123    /// use petgraph::prelude::*;
124    ///
125    /// let graph = Csr::<u8,()>::with_nodes(5);
126    /// assert_eq!(graph.node_count(),5);
127    /// assert_eq!(graph.edge_count(),0);
128    ///
129    /// assert_eq!(graph[0],0);
130    /// assert_eq!(graph[4],0);
131    /// ```
132    pub fn with_nodes(n: usize) -> Self
133    where
134        N: Default,
135    {
136        Csr {
137            column: Vec::new(),
138            edges: Vec::new(),
139            row: vec![0; n + 1],
140            node_weights: (0..n).map(|_| N::default()).collect(),
141            edge_count: 0,
142            ty: PhantomData,
143        }
144    }
145}
146
147/// Csr creation error: edges were not in sorted order.
148#[derive(Clone, Debug)]
149pub struct EdgesNotSorted {
150    first_error: (usize, usize),
151}
152
153impl<N, E, Ix> Csr<N, E, Directed, Ix>
154where
155    Ix: IndexType,
156{
157    /// Create a new `Csr` from a sorted sequence of edges
158    ///
159    /// Edges **must** be sorted and unique, where the sort order is the default
160    /// order for the pair *(u, v)* in Rust (*u* has priority).
161    ///
162    /// Computes in **O(|E| + |V|)** time.
163    /// # Example
164    /// ```rust
165    /// use petgraph::csr::Csr;
166    /// use petgraph::prelude::*;
167    ///
168    /// let graph = Csr::<(),()>::from_sorted_edges(&[
169    ///                     (0, 1), (0, 2),
170    ///                     (1, 0), (1, 2), (1, 3),
171    ///                     (2, 0),
172    ///                     (3, 1),
173    /// ]);
174    /// ```
175    pub fn from_sorted_edges<Edge>(edges: &[Edge]) -> Result<Self, EdgesNotSorted>
176    where
177        Edge: Clone + IntoWeightedEdge<E, NodeId = NodeIndex<Ix>>,
178        N: Default,
179    {
180        let max_node_id = match edges
181            .iter()
182            .map(|edge| {
183                let (x, y, _) = edge.clone().into_weighted_edge();
184                max(x.index(), y.index())
185            })
186            .max()
187        {
188            None => return Ok(Self::with_nodes(0)),
189            Some(x) => x,
190        };
191        let mut self_ = Self::with_nodes(max_node_id + 1);
192        let mut iter = edges.iter().cloned().peekable();
193        {
194            let mut rows = self_.row.iter_mut();
195
196            let mut node = 0;
197            let mut rstart = 0;
198            let mut last_target;
199            'outer: for r in &mut rows {
200                *r = rstart;
201                last_target = None;
202                'inner: loop {
203                    if let Some(edge) = iter.peek() {
204                        let (n, m, weight) = edge.clone().into_weighted_edge();
205                        // check that the edges are in increasing sequence
206                        if node > n.index() {
207                            return Err(EdgesNotSorted {
208                                first_error: (n.index(), m.index()),
209                            });
210                        }
211                        /*
212                        debug_assert!(node <= n.index(),
213                                      concat!("edges are not sorted, ",
214                                              "failed assertion source {:?} <= {:?} ",
215                                              "for edge {:?}"),
216                                      node, n, (n, m));
217                                      */
218                        if n.index() != node {
219                            break 'inner;
220                        }
221                        // check that the edges are in increasing sequence
222                        /*
223                        debug_assert!(last_target.map_or(true, |x| m > x),
224                                      "edges are not sorted, failed assertion {:?} < {:?}",
225                                      last_target, m);
226                                      */
227                        if !last_target.map_or(true, |x| m > x) {
228                            return Err(EdgesNotSorted {
229                                first_error: (n.index(), m.index()),
230                            });
231                        }
232                        last_target = Some(m);
233                        self_.column.push(m);
234                        self_.edges.push(weight);
235                        rstart += 1;
236                    } else {
237                        break 'outer;
238                    }
239                    iter.next();
240                }
241                node += 1;
242            }
243            for r in rows {
244                *r = rstart;
245            }
246        }
247
248        Ok(self_)
249    }
250}
251
252impl<N, E, Ty, Ix> Csr<N, E, Ty, Ix>
253where
254    Ty: EdgeType,
255    Ix: IndexType,
256{
257    pub fn node_count(&self) -> usize {
258        self.row.len() - 1
259    }
260
261    pub fn edge_count(&self) -> usize {
262        if self.is_directed() {
263            self.column.len()
264        } else {
265            self.edge_count
266        }
267    }
268
269    pub fn is_directed(&self) -> bool {
270        Ty::is_directed()
271    }
272
273    /// Remove all edges
274    pub fn clear_edges(&mut self) {
275        self.column.clear();
276        self.edges.clear();
277        for r in &mut self.row {
278            *r = 0;
279        }
280        if !self.is_directed() {
281            self.edge_count = 0;
282        }
283    }
284
285    /// Adds a new node with the given weight, returning the corresponding node index.
286    pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix> {
287        let i = self.row.len() - 1;
288        self.row.insert(i, self.column.len());
289        self.node_weights.insert(i, weight);
290        Ix::new(i)
291    }
292
293    /// Return `true` if the edge was added
294    ///
295    /// If you add all edges in row-major order, the time complexity
296    /// is **O(|V|·|E|)** for the whole operation.
297    ///
298    /// **Panics** if `a` or `b` are out of bounds.
299    pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> bool
300    where
301        E: Clone,
302    {
303        let ret = self.add_edge_(a, b, weight.clone());
304        if ret && !self.is_directed() {
305            self.edge_count += 1;
306        }
307        if ret && !self.is_directed() && a != b {
308            let _ret2 = self.add_edge_(b, a, weight);
309            debug_assert_eq!(ret, _ret2);
310        }
311        ret
312    }
313
314    // Return false if the edge already exists
315    fn add_edge_(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> bool {
316        assert!(a.index() < self.node_count() && b.index() < self.node_count());
317        // a x b is at (a, b) in the matrix
318
319        // find current range of edges from a
320        let pos = match self.find_edge_pos(a, b) {
321            Ok(_) => return false, /* already exists */
322            Err(i) => i,
323        };
324        self.column.insert(pos, b);
325        self.edges.insert(pos, weight);
326        // update row vector
327        for r in &mut self.row[a.index() + 1..] {
328            *r += 1;
329        }
330        true
331    }
332
333    fn find_edge_pos(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Result<usize, usize> {
334        let (index, neighbors) = self.neighbors_of(a);
335        if neighbors.len() < BINARY_SEARCH_CUTOFF {
336            for (i, elt) in neighbors.iter().enumerate() {
337                match elt.cmp(&b) {
338                    Ordering::Equal => return Ok(i + index),
339                    Ordering::Greater => return Err(i + index),
340                    Ordering::Less => {}
341                }
342            }
343            Err(neighbors.len() + index)
344        } else {
345            match neighbors.binary_search(&b) {
346                Ok(i) => Ok(i + index),
347                Err(i) => Err(i + index),
348            }
349        }
350    }
351
352    /// Computes in **O(log |V|)** time.
353    ///
354    /// **Panics** if the node `a` does not exist.
355    pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
356        self.find_edge_pos(a, b).is_ok()
357    }
358
359    fn neighbors_range(&self, a: NodeIndex<Ix>) -> Range<usize> {
360        let index = self.row[a.index()];
361        let end = self
362            .row
363            .get(a.index() + 1)
364            .cloned()
365            .unwrap_or_else(|| self.column.len());
366        index..end
367    }
368
369    fn neighbors_of(&self, a: NodeIndex<Ix>) -> (usize, &[Ix]) {
370        let r = self.neighbors_range(a);
371        (r.start, &self.column[r])
372    }
373
374    /// Computes in **O(1)** time.
375    ///
376    /// **Panics** if the node `a` does not exist.
377    pub fn out_degree(&self, a: NodeIndex<Ix>) -> usize {
378        let r = self.neighbors_range(a);
379        r.end - r.start
380    }
381
382    /// Computes in **O(1)** time.
383    ///
384    /// **Panics** if the node `a` does not exist.
385    pub fn neighbors_slice(&self, a: NodeIndex<Ix>) -> &[NodeIndex<Ix>] {
386        self.neighbors_of(a).1
387    }
388
389    /// Computes in **O(1)** time.
390    ///
391    /// **Panics** if the node `a` does not exist.
392    pub fn edges_slice(&self, a: NodeIndex<Ix>) -> &[E] {
393        &self.edges[self.neighbors_range(a)]
394    }
395
396    /// Return an iterator of all edges of `a`.
397    ///
398    /// - `Directed`: Outgoing edges from `a`.
399    /// - `Undirected`: All edges connected to `a`.
400    ///
401    /// **Panics** if the node `a` does not exist.<br>
402    /// Iterator element type is `EdgeReference<E, Ty, Ix>`.
403    pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<E, Ty, Ix> {
404        let r = self.neighbors_range(a);
405        Edges {
406            index: r.start,
407            source: a,
408            iter: zip(&self.column[r.clone()], &self.edges[r]),
409            ty: self.ty,
410        }
411    }
412}
413
414#[derive(Clone, Debug)]
415pub struct Edges<'a, E: 'a, Ty = Directed, Ix: 'a = DefaultIx> {
416    index: usize,
417    source: NodeIndex<Ix>,
418    iter: Zip<SliceIter<'a, NodeIndex<Ix>>, SliceIter<'a, E>>,
419    ty: PhantomData<Ty>,
420}
421
422#[derive(Debug)]
423pub struct EdgeReference<'a, E: 'a, Ty, Ix: 'a = DefaultIx> {
424    index: EdgeIndex,
425    source: NodeIndex<Ix>,
426    target: NodeIndex<Ix>,
427    weight: &'a E,
428    ty: PhantomData<Ty>,
429}
430
431impl<'a, E, Ty, Ix: Copy> Clone for EdgeReference<'a, E, Ty, Ix> {
432    fn clone(&self) -> Self {
433        *self
434    }
435}
436
437impl<'a, E, Ty, Ix: Copy> Copy for EdgeReference<'a, E, Ty, Ix> {}
438
439impl<'a, Ty, E, Ix> EdgeReference<'a, E, Ty, Ix>
440where
441    Ty: EdgeType,
442{
443    /// Access the edge’s weight.
444    ///
445    /// **NOTE** that this method offers a longer lifetime
446    /// than the trait (unfortunately they don't match yet).
447    pub fn weight(&self) -> &'a E {
448        self.weight
449    }
450}
451
452impl<'a, E, Ty, Ix> EdgeRef for EdgeReference<'a, E, Ty, Ix>
453where
454    Ty: EdgeType,
455    Ix: IndexType,
456{
457    type NodeId = NodeIndex<Ix>;
458    type EdgeId = EdgeIndex;
459    type Weight = E;
460
461    fn source(&self) -> Self::NodeId {
462        self.source
463    }
464    fn target(&self) -> Self::NodeId {
465        self.target
466    }
467    fn weight(&self) -> &E {
468        self.weight
469    }
470    fn id(&self) -> Self::EdgeId {
471        self.index
472    }
473}
474
475impl<'a, E, Ty, Ix> Iterator for Edges<'a, E, Ty, Ix>
476where
477    Ty: EdgeType,
478    Ix: IndexType,
479{
480    type Item = EdgeReference<'a, E, Ty, Ix>;
481    fn next(&mut self) -> Option<Self::Item> {
482        self.iter.next().map(move |(&j, w)| {
483            let index = self.index;
484            self.index += 1;
485            EdgeReference {
486                index,
487                source: self.source,
488                target: j,
489                weight: w,
490                ty: PhantomData,
491            }
492        })
493    }
494}
495
496impl<N, E, Ty, Ix> Data for Csr<N, E, Ty, Ix>
497where
498    Ty: EdgeType,
499    Ix: IndexType,
500{
501    type NodeWeight = N;
502    type EdgeWeight = E;
503}
504
505impl<'a, N, E, Ty, Ix> IntoEdgeReferences for &'a Csr<N, E, Ty, Ix>
506where
507    Ty: EdgeType,
508    Ix: IndexType,
509{
510    type EdgeRef = EdgeReference<'a, E, Ty, Ix>;
511    type EdgeReferences = EdgeReferences<'a, E, Ty, Ix>;
512    fn edge_references(self) -> Self::EdgeReferences {
513        EdgeReferences {
514            index: 0,
515            source_index: Ix::new(0),
516            edge_ranges: self.row.windows(2).enumerate(),
517            column: &self.column,
518            edges: &self.edges,
519            iter: zip(&[], &[]),
520            ty: self.ty,
521        }
522    }
523}
524
525pub struct EdgeReferences<'a, E: 'a, Ty, Ix: 'a> {
526    source_index: NodeIndex<Ix>,
527    index: usize,
528    edge_ranges: Enumerate<Windows<'a, usize>>,
529    column: &'a [NodeIndex<Ix>],
530    edges: &'a [E],
531    iter: Zip<SliceIter<'a, NodeIndex<Ix>>, SliceIter<'a, E>>,
532    ty: PhantomData<Ty>,
533}
534
535impl<'a, E, Ty, Ix> Iterator for EdgeReferences<'a, E, Ty, Ix>
536where
537    Ty: EdgeType,
538    Ix: IndexType,
539{
540    type Item = EdgeReference<'a, E, Ty, Ix>;
541    fn next(&mut self) -> Option<Self::Item> {
542        loop {
543            if let Some((&j, w)) = self.iter.next() {
544                let index = self.index;
545                self.index += 1;
546                return Some(EdgeReference {
547                    index,
548                    source: self.source_index,
549                    target: j,
550                    weight: w,
551                    ty: PhantomData,
552                });
553            }
554            if let Some((i, w)) = self.edge_ranges.next() {
555                let a = w[0];
556                let b = w[1];
557                self.iter = zip(&self.column[a..b], &self.edges[a..b]);
558                self.source_index = Ix::new(i);
559            } else {
560                return None;
561            }
562        }
563    }
564}
565
566impl<'a, N, E, Ty, Ix> IntoEdges for &'a Csr<N, E, Ty, Ix>
567where
568    Ty: EdgeType,
569    Ix: IndexType,
570{
571    type Edges = Edges<'a, E, Ty, Ix>;
572    fn edges(self, a: Self::NodeId) -> Self::Edges {
573        self.edges(a)
574    }
575}
576
577impl<N, E, Ty, Ix> GraphBase for Csr<N, E, Ty, Ix>
578where
579    Ty: EdgeType,
580    Ix: IndexType,
581{
582    type NodeId = NodeIndex<Ix>;
583    type EdgeId = EdgeIndex; // index into edges vector
584}
585
586use fixedbitset::FixedBitSet;
587
588impl<N, E, Ty, Ix> Visitable for Csr<N, E, Ty, Ix>
589where
590    Ty: EdgeType,
591    Ix: IndexType,
592{
593    type Map = FixedBitSet;
594    fn visit_map(&self) -> FixedBitSet {
595        FixedBitSet::with_capacity(self.node_count())
596    }
597    fn reset_map(&self, map: &mut Self::Map) {
598        map.clear();
599        map.grow(self.node_count());
600    }
601}
602
603#[derive(Clone, Debug)]
604pub struct Neighbors<'a, Ix: 'a = DefaultIx> {
605    iter: SliceIter<'a, NodeIndex<Ix>>,
606}
607
608impl<'a, Ix> Iterator for Neighbors<'a, Ix>
609where
610    Ix: IndexType,
611{
612    type Item = NodeIndex<Ix>;
613
614    fn next(&mut self) -> Option<Self::Item> {
615        self.iter.next().cloned()
616    }
617
618    fn size_hint(&self) -> (usize, Option<usize>) {
619        self.iter.size_hint()
620    }
621}
622
623impl<'a, N, E, Ty, Ix> IntoNeighbors for &'a Csr<N, E, Ty, Ix>
624where
625    Ty: EdgeType,
626    Ix: IndexType,
627{
628    type Neighbors = Neighbors<'a, Ix>;
629
630    /// Return an iterator of all neighbors of `a`.
631    ///
632    /// - `Directed`: Targets of outgoing edges from `a`.
633    /// - `Undirected`: Opposing endpoints of all edges connected to `a`.
634    ///
635    /// **Panics** if the node `a` does not exist.<br>
636    /// Iterator element type is `NodeIndex<Ix>`.
637    fn neighbors(self, a: Self::NodeId) -> Self::Neighbors {
638        Neighbors {
639            iter: self.neighbors_slice(a).iter(),
640        }
641    }
642}
643
644impl<N, E, Ty, Ix> NodeIndexable for Csr<N, E, Ty, Ix>
645where
646    Ty: EdgeType,
647    Ix: IndexType,
648{
649    fn node_bound(&self) -> usize {
650        self.node_count()
651    }
652    fn to_index(&self, a: Self::NodeId) -> usize {
653        a.index()
654    }
655    fn from_index(&self, ix: usize) -> Self::NodeId {
656        Ix::new(ix)
657    }
658}
659
660impl<N, E, Ty, Ix> NodeCompactIndexable for Csr<N, E, Ty, Ix>
661where
662    Ty: EdgeType,
663    Ix: IndexType,
664{
665}
666
667impl<N, E, Ty, Ix> Index<NodeIndex<Ix>> for Csr<N, E, Ty, Ix>
668where
669    Ty: EdgeType,
670    Ix: IndexType,
671{
672    type Output = N;
673
674    fn index(&self, ix: NodeIndex<Ix>) -> &N {
675        &self.node_weights[ix.index()]
676    }
677}
678
679impl<N, E, Ty, Ix> IndexMut<NodeIndex<Ix>> for Csr<N, E, Ty, Ix>
680where
681    Ty: EdgeType,
682    Ix: IndexType,
683{
684    fn index_mut(&mut self, ix: NodeIndex<Ix>) -> &mut N {
685        &mut self.node_weights[ix.index()]
686    }
687}
688
689pub struct NodeIdentifiers<Ix = DefaultIx> {
690    r: Range<usize>,
691    ty: PhantomData<Ix>,
692}
693
694impl<Ix> Iterator for NodeIdentifiers<Ix>
695where
696    Ix: IndexType,
697{
698    type Item = NodeIndex<Ix>;
699
700    fn next(&mut self) -> Option<Self::Item> {
701        self.r.next().map(Ix::new)
702    }
703
704    fn size_hint(&self) -> (usize, Option<usize>) {
705        self.r.size_hint()
706    }
707}
708
709impl<'a, N, E, Ty, Ix> IntoNodeIdentifiers for &'a Csr<N, E, Ty, Ix>
710where
711    Ty: EdgeType,
712    Ix: IndexType,
713{
714    type NodeIdentifiers = NodeIdentifiers<Ix>;
715    fn node_identifiers(self) -> Self::NodeIdentifiers {
716        NodeIdentifiers {
717            r: 0..self.node_count(),
718            ty: PhantomData,
719        }
720    }
721}
722
723impl<N, E, Ty, Ix> NodeCount for Csr<N, E, Ty, Ix>
724where
725    Ty: EdgeType,
726    Ix: IndexType,
727{
728    fn node_count(&self) -> usize {
729        (*self).node_count()
730    }
731}
732
733impl<N, E, Ty, Ix> GraphProp for Csr<N, E, Ty, Ix>
734where
735    Ty: EdgeType,
736    Ix: IndexType,
737{
738    type EdgeType = Ty;
739}
740
741/*
742 *
743Example
744
745[ a 0 b
746  c d e
747  0 0 f ]
748
749Values: [a, b, c, d, e, f]
750Column: [0, 2, 0, 1, 2, 2]
751Row   : [0, 2, 5]   <- value index of row start
752
753 * */
754#[allow(unused_variables)]
755#[cfg(test)]
756mod tests {
757    use super::Csr;
758    use crate::algo::bellman_ford;
759    use crate::algo::tarjan_scc;
760    #[cfg(not(feature = "std"))]
761    use alloc::vec::Vec;
762    use crate::visit::Dfs;
763    use crate::visit::VisitMap;
764    use crate::Undirected;
765
766    #[test]
767    fn csr1() {
768        let mut m: Csr = Csr::with_nodes(3);
769        m.add_edge(0, 0, ());
770        m.add_edge(1, 2, ());
771        m.add_edge(2, 2, ());
772        m.add_edge(0, 2, ());
773        m.add_edge(1, 0, ());
774        m.add_edge(1, 1, ());
775        #[cfg(feature = "std")]
776        println!("{:?}", m);
777        assert_eq!(&m.column, &[0, 2, 0, 1, 2, 2]);
778        assert_eq!(&m.row, &[0, 2, 5, 6]);
779
780        let added = m.add_edge(1, 2, ());
781        assert!(!added);
782        assert_eq!(&m.column, &[0, 2, 0, 1, 2, 2]);
783        assert_eq!(&m.row, &[0, 2, 5, 6]);
784
785        assert_eq!(m.neighbors_slice(1), &[0, 1, 2]);
786        assert_eq!(m.node_count(), 3);
787        assert_eq!(m.edge_count(), 6);
788    }
789
790    #[test]
791    fn csr_undirected() {
792        /*
793           [ 1 . 1
794             . . 1
795             1 1 1 ]
796        */
797
798        let mut m: Csr<(), (), Undirected> = Csr::with_nodes(3);
799        m.add_edge(0, 0, ());
800        m.add_edge(0, 2, ());
801        m.add_edge(1, 2, ());
802        m.add_edge(2, 2, ());
803        #[cfg(feature = "std")]
804        println!("{:?}", m);
805        assert_eq!(&m.column, &[0, 2, 2, 0, 1, 2]);
806        assert_eq!(&m.row, &[0, 2, 3, 6]);
807        assert_eq!(m.node_count(), 3);
808        assert_eq!(m.edge_count(), 4);
809    }
810
811    #[should_panic]
812    #[test]
813    fn csr_from_error_1() {
814        // not sorted in source
815        let m: Csr = Csr::from_sorted_edges(&[(0, 1), (1, 0), (0, 2)]).unwrap();
816        #[cfg(feature = "std")]
817        println!("{:?}", m);
818    }
819
820    #[should_panic]
821    #[test]
822    fn csr_from_error_2() {
823        // not sorted in target
824        let m: Csr = Csr::from_sorted_edges(&[(0, 1), (1, 0), (1, 2), (1, 1)]).unwrap();
825        #[cfg(feature = "std")]
826        println!("{:?}", m);
827    }
828
829    #[test]
830    fn csr_from() {
831        let m: Csr =
832            Csr::from_sorted_edges(&[(0, 1), (0, 2), (1, 0), (1, 1), (2, 2), (2, 4)]).unwrap();
833        #[cfg(feature = "std")]
834        println!("{:?}", m);
835        assert_eq!(m.neighbors_slice(0), &[1, 2]);
836        assert_eq!(m.neighbors_slice(1), &[0, 1]);
837        assert_eq!(m.neighbors_slice(2), &[2, 4]);
838        assert_eq!(m.node_count(), 5);
839        assert_eq!(m.edge_count(), 6);
840    }
841
842    #[test]
843    fn csr_dfs() {
844        let mut m: Csr = Csr::from_sorted_edges(&[
845            (0, 1),
846            (0, 2),
847            (1, 0),
848            (1, 1),
849            (1, 3),
850            (2, 2),
851            // disconnected subgraph
852            (4, 4),
853            (4, 5),
854        ])
855        .unwrap();
856        #[cfg(feature = "std")]
857        println!("{:?}", m);
858        let mut dfs = Dfs::new(&m, 0);
859        while let Some(_) = dfs.next(&m) {}
860        for i in 0..m.node_count() - 2 {
861            assert!(dfs.discovered.is_visited(&i), "visited {}", i)
862        }
863        assert!(!dfs.discovered[4]);
864        assert!(!dfs.discovered[5]);
865
866        m.add_edge(1, 4, ());
867        #[cfg(feature = "std")]
868        println!("{:?}", m);
869
870        dfs.reset(&m);
871        dfs.move_to(0);
872        while let Some(_) = dfs.next(&m) {}
873
874        for i in 0..m.node_count() {
875            assert!(dfs.discovered[i], "visited {}", i)
876        }
877    }
878
879    #[test]
880    fn csr_tarjan() {
881        let m: Csr = Csr::from_sorted_edges(&[
882            (0, 1),
883            (0, 2),
884            (1, 0),
885            (1, 1),
886            (1, 3),
887            (2, 2),
888            (2, 4),
889            (4, 4),
890            (4, 5),
891            (5, 2),
892        ])
893        .unwrap();
894        #[cfg(feature = "std")]
895        println!("{:?}", m);
896        let tarjan = tarjan_scc(&m);
897        #[cfg(feature = "std")]
898        println!("{:?}", tarjan);
899    }
900
901    #[test]
902    fn test_bellman_ford() {
903        let m: Csr<(), _> = Csr::from_sorted_edges(&[
904            (0, 1, 0.5),
905            (0, 2, 2.),
906            (1, 0, 1.),
907            (1, 1, 1.),
908            (1, 2, 1.),
909            (1, 3, 1.),
910            (2, 3, 3.),
911            (4, 5, 1.),
912            (5, 7, 2.),
913            (6, 7, 1.),
914            (7, 8, 3.),
915        ])
916        .unwrap();
917        #[cfg(feature = "std")]
918        println!("{:?}", m);
919        let result = bellman_ford(&m, 0).unwrap();
920        #[cfg(feature = "std")]
921        println!("{:?}", result);
922        let answer = [0., 0.5, 1.5, 1.5];
923        assert_eq!(&answer, &result.0[..4]);
924        assert!(answer[4..].iter().all(|&x| f64::is_infinite(x)));
925    }
926
927    #[test]
928    fn test_bellman_ford_neg_cycle() {
929        let m: Csr<(), _> = Csr::from_sorted_edges(&[
930            (0, 1, 0.5),
931            (0, 2, 2.),
932            (1, 0, 1.),
933            (1, 1, -1.),
934            (1, 2, 1.),
935            (1, 3, 1.),
936            (2, 3, 3.),
937        ])
938        .unwrap();
939        let result = bellman_ford(&m, 0);
940        assert!(result.is_err());
941    }
942
943    #[test]
944    fn test_edge_references() {
945        use crate::visit::EdgeRef;
946        use crate::visit::IntoEdgeReferences;
947        let m: Csr<(), _> = Csr::from_sorted_edges(&[
948            (0, 1, 0.5),
949            (0, 2, 2.),
950            (1, 0, 1.),
951            (1, 1, 1.),
952            (1, 2, 1.),
953            (1, 3, 1.),
954            (2, 3, 3.),
955            (4, 5, 1.),
956            (5, 7, 2.),
957            (6, 7, 1.),
958            (7, 8, 3.),
959        ])
960        .unwrap();
961        let mut copy = Vec::new();
962        for e in m.edge_references() {
963            copy.push((e.source(), e.target(), *e.weight()));
964            #[cfg(feature = "std")]
965            println!("{:?}", e);
966        }
967        let m2: Csr<(), _> = Csr::from_sorted_edges(&copy).unwrap();
968        assert_eq!(&m.row, &m2.row);
969        assert_eq!(&m.column, &m2.column);
970        assert_eq!(&m.edges, &m2.edges);
971    }
972
973    #[test]
974    fn test_add_node() {
975        let mut g: Csr = Csr::new();
976        let a = g.add_node(());
977        let b = g.add_node(());
978        let c = g.add_node(());
979
980        assert!(g.add_edge(a, b, ()));
981        assert!(g.add_edge(b, c, ()));
982        assert!(g.add_edge(c, a, ()));
983
984        #[cfg(feature = "std")]
985        println!("{:?}", g);
986
987        assert_eq!(g.node_count(), 3);
988
989        assert_eq!(g.neighbors_slice(a), &[b]);
990        assert_eq!(g.neighbors_slice(b), &[c]);
991        assert_eq!(g.neighbors_slice(c), &[a]);
992
993        assert_eq!(g.edge_count(), 3);
994    }
995
996    #[test]
997    fn test_add_node_with_existing_edges() {
998        let mut g: Csr = Csr::new();
999        let a = g.add_node(());
1000        let b = g.add_node(());
1001
1002        assert!(g.add_edge(a, b, ()));
1003
1004        let c = g.add_node(());
1005
1006        #[cfg(feature = "std")]
1007        println!("{:?}", g);
1008
1009        assert_eq!(g.node_count(), 3);
1010
1011        assert_eq!(g.neighbors_slice(a), &[b]);
1012        assert_eq!(g.neighbors_slice(b), &[]);
1013        assert_eq!(g.neighbors_slice(c), &[]);
1014
1015        assert_eq!(g.edge_count(), 1);
1016    }
1017}
petgraph/csr.rs

petgraph/
csr.rs
