petgraph/
csr.rs

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

petgraph/
csr.rs
