petgraph/
csr.rs

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

petgraph/
csr.rs
