petgraph/
csr.rs

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

petgraph/
csr.rs
