1 //! `MatrixGraph<N, E, Ty, NullN, NullE, Ix>` is a graph datastructure backed by an adjacency matrix.
2 
3 use std::marker::PhantomData;
4 use std::ops::{Index, IndexMut};
5 
6 use std::cmp;
7 use std::mem;
8 
9 use indexmap::IndexSet;
10 
11 use fixedbitset::FixedBitSet;
12 
13 use crate::{Directed, Direction, EdgeType, IntoWeightedEdge, Outgoing, Undirected};
14 
15 use crate::graph::NodeIndex as GraphNodeIndex;
16 
17 use crate::visit::{
18     Data, EdgeCount, GetAdjacencyMatrix, GraphBase, GraphProp, IntoEdgeReferences, IntoEdges,
19     IntoEdgesDirected, IntoNeighbors, IntoNeighborsDirected, IntoNodeIdentifiers,
20     IntoNodeReferences, NodeCount, NodeIndexable, Visitable,
21 };
22 
23 use crate::data::Build;
24 
25 pub use crate::graph::IndexType;
26 
27 // The following types are used to control the max size of the adjacency matrix. Since the maximum
28 // size of the matrix vector's is the square of the maximum number of nodes, the number of nodes
29 // should be reasonably picked.
30 type DefaultIx = u16;
31 
32 /// Node identifier.
33 pub type NodeIndex<Ix = DefaultIx> = GraphNodeIndex<Ix>;
34 
35 mod private {
36     pub trait Sealed {}
37 
38     impl<T> Sealed for super::NotZero<T> {}
39     impl<T> Sealed for Option<T> {}
40 }
41 
42 /// Wrapper trait for an `Option`, allowing user-defined structs to be input as containers when
43 /// defining a null element.
44 ///
45 /// Note: this trait is currently *sealed* and cannot be implemented for types outside this crate.
46 pub trait Nullable: Default + Into<Option<<Self as Nullable>::Wrapped>> + private::Sealed {
47     #[doc(hidden)]
48     type Wrapped;
49 
50     #[doc(hidden)]
new(value: Self::Wrapped) -> Self51     fn new(value: Self::Wrapped) -> Self;
52 
53     #[doc(hidden)]
as_ref(&self) -> Option<&Self::Wrapped>54     fn as_ref(&self) -> Option<&Self::Wrapped>;
55 
56     #[doc(hidden)]
as_mut(&mut self) -> Option<&mut Self::Wrapped>57     fn as_mut(&mut self) -> Option<&mut Self::Wrapped>;
58 
59     #[doc(hidden)]
is_null(&self) -> bool60     fn is_null(&self) -> bool {
61         self.as_ref().is_none()
62     }
63 }
64 
65 impl<T> Nullable for Option<T> {
66     type Wrapped = T;
67 
new(value: T) -> Self68     fn new(value: T) -> Self {
69         Some(value)
70     }
71 
as_ref(&self) -> Option<&Self::Wrapped>72     fn as_ref(&self) -> Option<&Self::Wrapped> {
73         self.as_ref()
74     }
75 
as_mut(&mut self) -> Option<&mut Self::Wrapped>76     fn as_mut(&mut self) -> Option<&mut Self::Wrapped> {
77         self.as_mut()
78     }
79 }
80 
81 /// `NotZero` is used to optimize the memory usage of edge weights `E` in a
82 /// [`MatrixGraph`](struct.MatrixGraph.html), replacing the default `Option<E>` sentinel.
83 ///
84 /// Pre-requisite: edge weight should implement [`Zero`](trait.Zero.html).
85 ///
86 /// Note that if you're already using the standard non-zero types (such as `NonZeroU32`), you don't
87 /// have to use this wrapper and can leave the default `Null` type argument.
88 pub struct NotZero<T>(T);
89 
90 impl<T: Zero> Default for NotZero<T> {
default() -> Self91     fn default() -> Self {
92         NotZero(T::zero())
93     }
94 }
95 
96 impl<T: Zero> Nullable for NotZero<T> {
97     #[doc(hidden)]
98     type Wrapped = T;
99 
100     #[doc(hidden)]
new(value: T) -> Self101     fn new(value: T) -> Self {
102         assert!(!value.is_zero());
103         NotZero(value)
104     }
105 
106     // implemented here for optimization purposes
107     #[doc(hidden)]
is_null(&self) -> bool108     fn is_null(&self) -> bool {
109         self.0.is_zero()
110     }
111 
112     #[doc(hidden)]
as_ref(&self) -> Option<&Self::Wrapped>113     fn as_ref(&self) -> Option<&Self::Wrapped> {
114         if !self.is_null() {
115             Some(&self.0)
116         } else {
117             None
118         }
119     }
120 
121     #[doc(hidden)]
as_mut(&mut self) -> Option<&mut Self::Wrapped>122     fn as_mut(&mut self) -> Option<&mut Self::Wrapped> {
123         if !self.is_null() {
124             Some(&mut self.0)
125         } else {
126             None
127         }
128     }
129 }
130 
131 impl<T: Zero> From<NotZero<T>> for Option<T> {
from(not_zero: NotZero<T>) -> Self132     fn from(not_zero: NotZero<T>) -> Self {
133         if !not_zero.is_null() {
134             Some(not_zero.0)
135         } else {
136             None
137         }
138     }
139 }
140 
141 /// Base trait for types that can be wrapped in a [`NotZero`](struct.NotZero.html).
142 ///
143 /// Implementors must provide a singleton object that will be used to mark empty edges in a
144 /// [`MatrixGraph`](struct.MatrixGraph.html).
145 ///
146 /// Note that this trait is already implemented for the base numeric types.
147 pub trait Zero {
148     /// Return the singleton object which can be used as a sentinel value.
zero() -> Self149     fn zero() -> Self;
150 
151     /// Return true if `self` is equal to the sentinel value.
is_zero(&self) -> bool152     fn is_zero(&self) -> bool;
153 }
154 
155 macro_rules! not_zero_impl {
156     ($t:ty,$z:expr) => {
157         impl Zero for $t {
158             fn zero() -> Self {
159                 $z as $t
160             }
161 
162             #[allow(clippy::float_cmp)]
163             fn is_zero(&self) -> bool {
164                 self == &Self::zero()
165             }
166         }
167     };
168 }
169 
170 macro_rules! not_zero_impls {
171     ($($t:ty),*) => {
172         $(
173             not_zero_impl!($t, 0);
174         )*
175     }
176 }
177 
178 not_zero_impls!(u8, u16, u32, u64, usize);
179 not_zero_impls!(i8, i16, i32, i64, isize);
180 not_zero_impls!(f32, f64);
181 
182 /// Short version of `NodeIndex::new` (with Ix = `DefaultIx`)
183 #[inline]
node_index(ax: usize) -> NodeIndex184 pub fn node_index(ax: usize) -> NodeIndex {
185     NodeIndex::new(ax)
186 }
187 
188 /// `MatrixGraph<N, E, Ty, Null>` is a graph datastructure using an adjacency matrix
189 /// representation.
190 ///
191 /// `MatrixGraph` is parameterized over:
192 ///
193 /// - Associated data `N` for nodes and `E` for edges, called *weights*.
194 ///   The associated data can be of arbitrary type.
195 /// - Edge type `Ty` that determines whether the graph edges are directed or undirected.
196 /// - Nullable type `Null`, which denotes the edges' presence (defaults to `Option<E>`). You may
197 ///   specify [`NotZero<E>`](struct.NotZero.html) if you want to use a sentinel value (such as 0)
198 ///   to mark the absence of an edge.
199 /// - Index type `Ix` that sets the maximum size for the graph (defaults to `DefaultIx`).
200 ///
201 /// The graph uses **O(|V^2|)** space, with fast edge insertion & amortized node insertion, as well
202 /// as efficient graph search and graph algorithms on dense graphs.
203 ///
204 /// This graph is backed by a flattened 2D array. For undirected graphs, only the lower triangular
205 /// matrix is stored. Since the backing array stores edge weights, it is recommended to box large
206 /// edge weights.
207 #[derive(Clone)]
208 pub struct MatrixGraph<N, E, Ty = Directed, Null: Nullable<Wrapped = E> = Option<E>, Ix = DefaultIx>
209 {
210     node_adjacencies: Vec<Null>,
211     node_capacity: usize,
212     nodes: IdStorage<N>,
213     nb_edges: usize,
214     ty: PhantomData<Ty>,
215     ix: PhantomData<Ix>,
216 }
217 
218 /// A `MatrixGraph` with directed edges.
219 pub type DiMatrix<N, E, Null = Option<E>, Ix = DefaultIx> = MatrixGraph<N, E, Directed, Null, Ix>;
220 
221 /// A `MatrixGraph` with undirected edges.
222 pub type UnMatrix<N, E, Null = Option<E>, Ix = DefaultIx> = MatrixGraph<N, E, Undirected, Null, Ix>;
223 
224 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType>
225     MatrixGraph<N, E, Ty, Null, Ix>
226 {
227     /// Create a new `MatrixGraph` with estimated capacity for nodes.
with_capacity(node_capacity: usize) -> Self228     pub fn with_capacity(node_capacity: usize) -> Self {
229         let mut m = Self {
230             node_adjacencies: vec![],
231             node_capacity: 0,
232             nodes: IdStorage::with_capacity(node_capacity),
233             nb_edges: 0,
234             ty: PhantomData,
235             ix: PhantomData,
236         };
237 
238         debug_assert!(node_capacity <= <Ix as IndexType>::max().index());
239         if node_capacity > 0 {
240             m.extend_capacity_for_node(NodeIndex::new(node_capacity - 1), true);
241         }
242 
243         m
244     }
245 
246     #[inline]
to_edge_position(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<usize>247     fn to_edge_position(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<usize> {
248         if cmp::max(a.index(), b.index()) >= self.node_capacity {
249             return None;
250         }
251         Some(self.to_edge_position_unchecked(a, b))
252     }
253 
254     #[inline]
to_edge_position_unchecked(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> usize255     fn to_edge_position_unchecked(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> usize {
256         to_linearized_matrix_position::<Ty>(a.index(), b.index(), self.node_capacity)
257     }
258 
259     /// Remove all nodes and edges.
clear(&mut self)260     pub fn clear(&mut self) {
261         for edge in self.node_adjacencies.iter_mut() {
262             *edge = Default::default();
263         }
264         self.nodes.clear();
265         self.nb_edges = 0;
266     }
267 
268     /// Return the number of nodes (vertices) in the graph.
269     ///
270     /// Computes in **O(1)** time.
271     #[inline]
node_count(&self) -> usize272     pub fn node_count(&self) -> usize {
273         self.nodes.len()
274     }
275 
276     /// Return the number of edges in the graph.
277     ///
278     /// Computes in **O(1)** time.
279     #[inline]
edge_count(&self) -> usize280     pub fn edge_count(&self) -> usize {
281         self.nb_edges
282     }
283 
284     /// Return whether the graph has directed edges or not.
285     #[inline]
is_directed(&self) -> bool286     pub fn is_directed(&self) -> bool {
287         Ty::is_directed()
288     }
289 
290     /// Add a node (also called vertex) with associated data `weight` to the graph.
291     ///
292     /// Computes in **O(1)** time.
293     ///
294     /// Return the index of the new node.
295     ///
296     /// **Panics** if the MatrixGraph is at the maximum number of nodes for its index type.
add_node(&mut self, weight: N) -> NodeIndex<Ix>297     pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix> {
298         NodeIndex::new(self.nodes.add(weight))
299     }
300 
301     /// Remove `a` from the graph.
302     ///
303     /// Computes in **O(V)** time, due to the removal of edges with other nodes.
304     ///
305     /// **Panics** if the node `a` does not exist.
remove_node(&mut self, a: NodeIndex<Ix>) -> N306     pub fn remove_node(&mut self, a: NodeIndex<Ix>) -> N {
307         for id in self.nodes.iter_ids() {
308             let position = self.to_edge_position(a, NodeIndex::new(id));
309             if let Some(pos) = position {
310                 self.node_adjacencies[pos] = Default::default();
311             }
312 
313             if Ty::is_directed() {
314                 let position = self.to_edge_position(NodeIndex::new(id), a);
315                 if let Some(pos) = position {
316                     self.node_adjacencies[pos] = Default::default();
317                 }
318             }
319         }
320 
321         self.nodes.remove(a.index())
322     }
323 
324     #[inline]
extend_capacity_for_node(&mut self, min_node: NodeIndex<Ix>, exact: bool)325     fn extend_capacity_for_node(&mut self, min_node: NodeIndex<Ix>, exact: bool) {
326         self.node_capacity = extend_linearized_matrix::<Ty, _>(
327             &mut self.node_adjacencies,
328             self.node_capacity,
329             min_node.index() + 1,
330             exact,
331         );
332     }
333 
334     #[inline]
extend_capacity_for_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>)335     fn extend_capacity_for_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) {
336         let min_node = cmp::max(a, b);
337         if min_node.index() >= self.node_capacity {
338             self.extend_capacity_for_node(min_node, false);
339         }
340     }
341 
342     /// Update the edge from `a` to `b` to the graph, with its associated data `weight`.
343     ///
344     /// Return the previous data, if any.
345     ///
346     /// Computes in **O(1)** time, best case.
347     /// Computes in **O(|V|^2)** time, worst case (matrix needs to be re-allocated).
348     ///
349     /// **Panics** if any of the nodes don't exist.
update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> Option<E>350     pub fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> Option<E> {
351         self.extend_capacity_for_edge(a, b);
352         let p = self.to_edge_position_unchecked(a, b);
353         let old_weight = mem::replace(&mut self.node_adjacencies[p], Null::new(weight));
354         if old_weight.is_null() {
355             self.nb_edges += 1;
356         }
357         old_weight.into()
358     }
359 
360     /// Add an edge from `a` to `b` to the graph, with its associated
361     /// data `weight`.
362     ///
363     /// Computes in **O(1)** time, best case.
364     /// Computes in **O(|V|^2)** time, worst case (matrix needs to be re-allocated).
365     ///
366     /// **Panics** if any of the nodes don't exist.
367     /// **Panics** if an edge already exists from `a` to `b`.
368     ///
369     /// **Note:** `MatrixGraph` does not allow adding parallel (“duplicate”) edges. If you want to avoid
370     /// this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead.
add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E)371     pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) {
372         let old_edge_id = self.update_edge(a, b, weight);
373         assert!(old_edge_id.is_none());
374     }
375 
376     /// Remove the edge from `a` to `b` to the graph.
377     ///
378     /// **Panics** if any of the nodes don't exist.
379     /// **Panics** if no edge exists between `a` and `b`.
remove_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> E380     pub fn remove_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> E {
381         let p = self
382             .to_edge_position(a, b)
383             .expect("No edge found between the nodes.");
384         let old_weight = mem::take(&mut self.node_adjacencies[p]).into().unwrap();
385         let old_weight: Option<_> = old_weight.into();
386         self.nb_edges -= 1;
387         old_weight.unwrap()
388     }
389 
390     /// Return true if there is an edge between `a` and `b`.
391     ///
392     /// **Panics** if any of the nodes don't exist.
has_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool393     pub fn has_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
394         if let Some(p) = self.to_edge_position(a, b) {
395             return !self.node_adjacencies[p].is_null();
396         }
397         false
398     }
399 
400     /// Access the weight for node `a`.
401     ///
402     /// Also available with indexing syntax: `&graph[a]`.
403     ///
404     /// **Panics** if the node doesn't exist.
node_weight(&self, a: NodeIndex<Ix>) -> &N405     pub fn node_weight(&self, a: NodeIndex<Ix>) -> &N {
406         &self.nodes[a.index()]
407     }
408 
409     /// Access the weight for node `a`, mutably.
410     ///
411     /// Also available with indexing syntax: `&mut graph[a]`.
412     ///
413     /// **Panics** if the node doesn't exist.
node_weight_mut(&mut self, a: NodeIndex<Ix>) -> &mut N414     pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> &mut N {
415         &mut self.nodes[a.index()]
416     }
417 
418     /// Access the weight for edge `e`.
419     ///
420     /// Also available with indexing syntax: `&graph[e]`.
421     ///
422     /// **Panics** if no edge exists between `a` and `b`.
edge_weight(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &E423     pub fn edge_weight(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &E {
424         let p = self
425             .to_edge_position(a, b)
426             .expect("No edge found between the nodes.");
427         self.node_adjacencies[p]
428             .as_ref()
429             .expect("No edge found between the nodes.")
430     }
431 
432     /// Access the weight for edge `e`, mutably.
433     ///
434     /// Also available with indexing syntax: `&mut graph[e]`.
435     ///
436     /// **Panics** if no edge exists between `a` and `b`.
edge_weight_mut(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &mut E437     pub fn edge_weight_mut(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &mut E {
438         let p = self
439             .to_edge_position(a, b)
440             .expect("No edge found between the nodes.");
441         self.node_adjacencies[p]
442             .as_mut()
443             .expect("No edge found between the nodes.")
444     }
445 
446     /// Return an iterator of all nodes with an edge starting from `a`.
447     ///
448     /// - `Directed`: Outgoing edges from `a`.
449     /// - `Undirected`: All edges from or to `a`.
450     ///
451     /// Produces an empty iterator if the node doesn't exist.<br>
452     /// Iterator element type is [`NodeIndex<Ix>`](../graph/struct.NodeIndex.html).
neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<Ty, Null, Ix>453     pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<Ty, Null, Ix> {
454         Neighbors(Edges::on_columns(
455             a.index(),
456             &self.node_adjacencies,
457             self.node_capacity,
458         ))
459     }
460 
461     /// Return an iterator of all edges of `a`.
462     ///
463     /// - `Directed`: Outgoing edges from `a`.
464     /// - `Undirected`: All edges connected to `a`.
465     ///
466     /// Produces an empty iterator if the node doesn't exist.<br>
467     /// Iterator element type is `(NodeIndex<Ix>, NodeIndex<Ix>, &E)`.
edges(&self, a: NodeIndex<Ix>) -> Edges<Ty, Null, Ix>468     pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<Ty, Null, Ix> {
469         Edges::on_columns(a.index(), &self.node_adjacencies, self.node_capacity)
470     }
471 
472     /// Create a new `MatrixGraph` from an iterable of edges.
473     ///
474     /// Node weights `N` are set to default values.
475     /// Edge weights `E` may either be specified in the list,
476     /// or they are filled with default values.
477     ///
478     /// Nodes are inserted automatically to match the edges.
479     ///
480     /// ```
481     /// use petgraph::matrix_graph::MatrixGraph;
482     ///
483     /// let gr = MatrixGraph::<(), i32>::from_edges(&[
484     ///     (0, 1), (0, 2), (0, 3),
485     ///     (1, 2), (1, 3),
486     ///     (2, 3),
487     /// ]);
488     /// ```
from_edges<I>(iterable: I) -> Self where I: IntoIterator, I::Item: IntoWeightedEdge<E>, <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>, N: Default,489     pub fn from_edges<I>(iterable: I) -> Self
490     where
491         I: IntoIterator,
492         I::Item: IntoWeightedEdge<E>,
493         <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
494         N: Default,
495     {
496         let mut g = Self::default();
497         g.extend_with_edges(iterable);
498         g
499     }
500 
501     /// Extend the graph from an iterable of edges.
502     ///
503     /// Node weights `N` are set to default values.
504     /// Edge weights `E` may either be specified in the list,
505     /// or they are filled with default values.
506     ///
507     /// Nodes are inserted automatically to match the edges.
extend_with_edges<I>(&mut self, iterable: I) where I: IntoIterator, I::Item: IntoWeightedEdge<E>, <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>, N: Default,508     pub fn extend_with_edges<I>(&mut self, iterable: I)
509     where
510         I: IntoIterator,
511         I::Item: IntoWeightedEdge<E>,
512         <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
513         N: Default,
514     {
515         for elt in iterable {
516             let (source, target, weight) = elt.into_weighted_edge();
517             let (source, target) = (source.into(), target.into());
518             let nx = cmp::max(source, target);
519             while nx.index() >= self.node_count() {
520                 self.add_node(N::default());
521             }
522             self.add_edge(source, target, weight);
523         }
524     }
525 }
526 
527 impl<N, E, Null: Nullable<Wrapped = E>, Ix: IndexType> MatrixGraph<N, E, Directed, Null, Ix> {
528     /// Return an iterator of all neighbors that have an edge between them and
529     /// `a`, in the specified direction.
530     /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
531     ///
532     /// - `Outgoing`: All edges from `a`.
533     /// - `Incoming`: All edges to `a`.
534     ///
535     /// Produces an empty iterator if the node doesn't exist.<br>
536     /// Iterator element type is [`NodeIndex<Ix>`](../graph/struct.NodeIndex.html).
neighbors_directed( &self, a: NodeIndex<Ix>, d: Direction, ) -> Neighbors<Directed, Null, Ix>537     pub fn neighbors_directed(
538         &self,
539         a: NodeIndex<Ix>,
540         d: Direction,
541     ) -> Neighbors<Directed, Null, Ix> {
542         if d == Outgoing {
543             self.neighbors(a)
544         } else {
545             Neighbors(Edges::on_rows(
546                 a.index(),
547                 &self.node_adjacencies,
548                 self.node_capacity,
549             ))
550         }
551     }
552 
553     /// Return an iterator of all edges of `a`, in the specified direction.
554     ///
555     /// - `Outgoing`: All edges from `a`.
556     /// - `Incoming`: All edges to `a`.
557     ///
558     /// Produces an empty iterator if the node `a` doesn't exist.<br>
559     /// Iterator element type is `(NodeIndex<Ix>, NodeIndex<Ix>, &E)`.
edges_directed(&self, a: NodeIndex<Ix>, d: Direction) -> Edges<Directed, Null, Ix>560     pub fn edges_directed(&self, a: NodeIndex<Ix>, d: Direction) -> Edges<Directed, Null, Ix> {
561         if d == Outgoing {
562             self.edges(a)
563         } else {
564             Edges::on_rows(a.index(), &self.node_adjacencies, self.node_capacity)
565         }
566     }
567 }
568 
569 /// Iterator over the node identifiers of a graph.
570 ///
571 /// Created from a call to [`.node_identifiers()`][1] on a [`MatrixGraph`][2].
572 ///
573 /// [1]: ../visit/trait.IntoNodeIdentifiers.html#tymethod.node_identifiers
574 /// [2]: struct.MatrixGraph.html
575 #[derive(Debug, Clone)]
576 pub struct NodeIdentifiers<'a, Ix> {
577     iter: IdIterator<'a>,
578     ix: PhantomData<Ix>,
579 }
580 
581 impl<'a, Ix: IndexType> NodeIdentifiers<'a, Ix> {
new(iter: IdIterator<'a>) -> Self582     fn new(iter: IdIterator<'a>) -> Self {
583         Self {
584             iter,
585             ix: PhantomData,
586         }
587     }
588 }
589 
590 impl<'a, Ix: IndexType> Iterator for NodeIdentifiers<'a, Ix> {
591     type Item = NodeIndex<Ix>;
592 
next(&mut self) -> Option<Self::Item>593     fn next(&mut self) -> Option<Self::Item> {
594         self.iter.next().map(NodeIndex::new)
595     }
size_hint(&self) -> (usize, Option<usize>)596     fn size_hint(&self) -> (usize, Option<usize>) {
597         self.iter.size_hint()
598     }
599 }
600 
601 /// Iterator over all nodes of a graph.
602 ///
603 /// Created from a call to [`.node_references()`][1] on a [`MatrixGraph`][2].
604 ///
605 /// [1]: ../visit/trait.IntoNodeReferences.html#tymethod.node_references
606 /// [2]: struct.MatrixGraph.html
607 #[derive(Debug, Clone)]
608 pub struct NodeReferences<'a, N: 'a, Ix> {
609     nodes: &'a IdStorage<N>,
610     iter: IdIterator<'a>,
611     ix: PhantomData<Ix>,
612 }
613 
614 impl<'a, N: 'a, Ix> NodeReferences<'a, N, Ix> {
new(nodes: &'a IdStorage<N>) -> Self615     fn new(nodes: &'a IdStorage<N>) -> Self {
616         NodeReferences {
617             nodes,
618             iter: nodes.iter_ids(),
619             ix: PhantomData,
620         }
621     }
622 }
623 
624 impl<'a, N: 'a, Ix: IndexType> Iterator for NodeReferences<'a, N, Ix> {
625     type Item = (NodeIndex<Ix>, &'a N);
626 
next(&mut self) -> Option<Self::Item>627     fn next(&mut self) -> Option<Self::Item> {
628         self.iter
629             .next()
630             .map(|i| (NodeIndex::new(i), &self.nodes[i]))
631     }
size_hint(&self) -> (usize, Option<usize>)632     fn size_hint(&self) -> (usize, Option<usize>) {
633         self.iter.size_hint()
634     }
635 }
636 
637 /// Iterator over all edges of a graph.
638 ///
639 /// Created from a call to [`.edge_references()`][1] on a [`MatrixGraph`][2].
640 ///
641 /// [1]: ../visit/trait.IntoEdgeReferences.html#tymethod.edge_references
642 /// [2]: struct.MatrixGraph.html
643 #[derive(Debug, Clone)]
644 pub struct EdgeReferences<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> {
645     row: usize,
646     column: usize,
647     node_adjacencies: &'a [Null],
648     node_capacity: usize,
649     ty: PhantomData<Ty>,
650     ix: PhantomData<Ix>,
651 }
652 
653 impl<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> EdgeReferences<'a, Ty, Null, Ix> {
new(node_adjacencies: &'a [Null], node_capacity: usize) -> Self654     fn new(node_adjacencies: &'a [Null], node_capacity: usize) -> Self {
655         EdgeReferences {
656             row: 0,
657             column: 0,
658             node_adjacencies,
659             node_capacity,
660             ty: PhantomData,
661             ix: PhantomData,
662         }
663     }
664 }
665 
666 impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator
667     for EdgeReferences<'a, Ty, Null, Ix>
668 {
669     type Item = (NodeIndex<Ix>, NodeIndex<Ix>, &'a Null::Wrapped);
670 
next(&mut self) -> Option<Self::Item>671     fn next(&mut self) -> Option<Self::Item> {
672         loop {
673             let (row, column) = (self.row, self.column);
674             if row >= self.node_capacity {
675                 return None;
676             }
677 
678             // By default, advance the column. Reset and advance the row if the column overflows.
679             //
680             // Note that for undirected graphs, we don't want to yield the same edge twice,
681             // therefore the maximum column length should be the index new after the row index.
682             self.column += 1;
683             let max_column_len = if !Ty::is_directed() {
684                 row + 1
685             } else {
686                 self.node_capacity
687             };
688             if self.column >= max_column_len {
689                 self.column = 0;
690                 self.row += 1;
691             }
692 
693             let p = to_linearized_matrix_position::<Ty>(row, column, self.node_capacity);
694             if let Some(e) = self.node_adjacencies[p].as_ref() {
695                 return Some((NodeIndex::new(row), NodeIndex::new(column), e));
696             }
697         }
698     }
699 }
700 
701 /// Iterator over the neighbors of a node.
702 ///
703 /// Iterator element type is `NodeIndex<Ix>`.
704 ///
705 /// Created with [`.neighbors()`][1], [`.neighbors_directed()`][2].
706 ///
707 /// [1]: struct.MatrixGraph.html#method.neighbors
708 /// [2]: struct.MatrixGraph.html#method.neighbors_directed
709 #[derive(Debug, Clone)]
710 pub struct Neighbors<'a, Ty: EdgeType, Null: 'a + Nullable, Ix>(Edges<'a, Ty, Null, Ix>);
711 
712 impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Neighbors<'a, Ty, Null, Ix> {
713     type Item = NodeIndex<Ix>;
714 
next(&mut self) -> Option<Self::Item>715     fn next(&mut self) -> Option<Self::Item> {
716         self.0.next().map(|(_, b, _)| b)
717     }
size_hint(&self) -> (usize, Option<usize>)718     fn size_hint(&self) -> (usize, Option<usize>) {
719         self.0.size_hint()
720     }
721 }
722 
723 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
724 enum NeighborIterDirection {
725     Rows,
726     Columns,
727 }
728 
729 /// Iterator over the edges of from or to a node
730 ///
731 /// Created with [`.edges()`][1], [`.edges_directed()`][2].
732 ///
733 /// [1]: struct.MatrixGraph.html#method.edges
734 /// [2]: struct.MatrixGraph.html#method.edges_directed
735 #[derive(Debug, Clone)]
736 pub struct Edges<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> {
737     iter_direction: NeighborIterDirection,
738     node_adjacencies: &'a [Null],
739     node_capacity: usize,
740     row: usize,
741     column: usize,
742     ty: PhantomData<Ty>,
743     ix: PhantomData<Ix>,
744 }
745 
746 impl<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> Edges<'a, Ty, Null, Ix> {
on_columns(row: usize, node_adjacencies: &'a [Null], node_capacity: usize) -> Self747     fn on_columns(row: usize, node_adjacencies: &'a [Null], node_capacity: usize) -> Self {
748         Edges {
749             iter_direction: NeighborIterDirection::Columns,
750             node_adjacencies,
751             node_capacity,
752             row,
753             column: 0,
754             ty: PhantomData,
755             ix: PhantomData,
756         }
757     }
758 
on_rows(column: usize, node_adjacencies: &'a [Null], node_capacity: usize) -> Self759     fn on_rows(column: usize, node_adjacencies: &'a [Null], node_capacity: usize) -> Self {
760         Edges {
761             iter_direction: NeighborIterDirection::Rows,
762             node_adjacencies,
763             node_capacity,
764             row: 0,
765             column,
766             ty: PhantomData,
767             ix: PhantomData,
768         }
769     }
770 }
771 
772 impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Edges<'a, Ty, Null, Ix> {
773     type Item = (NodeIndex<Ix>, NodeIndex<Ix>, &'a Null::Wrapped);
774 
next(&mut self) -> Option<Self::Item>775     fn next(&mut self) -> Option<Self::Item> {
776         use self::NeighborIterDirection::*;
777 
778         loop {
779             let (row, column) = (self.row, self.column);
780             if row >= self.node_capacity || column >= self.node_capacity {
781                 return None;
782             }
783 
784             match self.iter_direction {
785                 Rows => self.row += 1,
786                 Columns => self.column += 1,
787             }
788 
789             let p = to_linearized_matrix_position::<Ty>(row, column, self.node_capacity);
790             if let Some(e) = self.node_adjacencies[p].as_ref() {
791                 let (a, b) = match self.iter_direction {
792                     Rows => (column, row),
793                     Columns => (row, column),
794                 };
795 
796                 return Some((NodeIndex::new(a), NodeIndex::new(b), e));
797             }
798         }
799     }
800 }
801 
802 #[inline]
to_linearized_matrix_position<Ty: EdgeType>(row: usize, column: usize, width: usize) -> usize803 fn to_linearized_matrix_position<Ty: EdgeType>(row: usize, column: usize, width: usize) -> usize {
804     if Ty::is_directed() {
805         to_flat_square_matrix_position(row, column, width)
806     } else {
807         to_lower_triangular_matrix_position(row, column)
808     }
809 }
810 
811 #[inline]
extend_linearized_matrix<Ty: EdgeType, T: Default>( node_adjacencies: &mut Vec<T>, old_node_capacity: usize, new_capacity: usize, exact: bool, ) -> usize812 fn extend_linearized_matrix<Ty: EdgeType, T: Default>(
813     node_adjacencies: &mut Vec<T>,
814     old_node_capacity: usize,
815     new_capacity: usize,
816     exact: bool,
817 ) -> usize {
818     if old_node_capacity >= new_capacity {
819         return old_node_capacity;
820     }
821     if Ty::is_directed() {
822         extend_flat_square_matrix(node_adjacencies, old_node_capacity, new_capacity, exact)
823     } else {
824         extend_lower_triangular_matrix(node_adjacencies, new_capacity)
825     }
826 }
827 
828 #[inline]
to_flat_square_matrix_position(row: usize, column: usize, width: usize) -> usize829 fn to_flat_square_matrix_position(row: usize, column: usize, width: usize) -> usize {
830     row * width + column
831 }
832 
833 #[inline]
extend_flat_square_matrix<T: Default>( node_adjacencies: &mut Vec<T>, old_node_capacity: usize, new_node_capacity: usize, exact: bool, ) -> usize834 fn extend_flat_square_matrix<T: Default>(
835     node_adjacencies: &mut Vec<T>,
836     old_node_capacity: usize,
837     new_node_capacity: usize,
838     exact: bool,
839 ) -> usize {
840     // Grow the capacity by exponential steps to avoid repeated allocations.
841     // Disabled for the with_capacity constructor.
842     let new_node_capacity = if exact {
843         new_node_capacity
844     } else {
845         const MIN_CAPACITY: usize = 4;
846         cmp::max(new_node_capacity.next_power_of_two(), MIN_CAPACITY)
847     };
848 
849     // Optimization: when resizing the matrix this way we skip the first few grows to make
850     // small matrices a bit faster to work with.
851 
852     ensure_len(node_adjacencies, new_node_capacity.pow(2));
853     for c in (1..old_node_capacity).rev() {
854         let pos = c * old_node_capacity;
855         let new_pos = c * new_node_capacity;
856         // Move the slices directly if they do not overlap with their new position
857         if pos + old_node_capacity <= new_pos {
858             debug_assert!(pos + old_node_capacity < node_adjacencies.len());
859             debug_assert!(new_pos + old_node_capacity < node_adjacencies.len());
860             let ptr = node_adjacencies.as_mut_ptr();
861             // SAFETY: pos + old_node_capacity <= new_pos, so this won't overlap
862             unsafe {
863                 let old = ptr.add(pos);
864                 let new = ptr.add(new_pos);
865                 core::ptr::swap_nonoverlapping(old, new, old_node_capacity);
866             }
867         } else {
868             for i in (0..old_node_capacity).rev() {
869                 node_adjacencies.as_mut_slice().swap(pos + i, new_pos + i);
870             }
871         }
872     }
873 
874     new_node_capacity
875 }
876 
877 #[inline]
to_lower_triangular_matrix_position(row: usize, column: usize) -> usize878 fn to_lower_triangular_matrix_position(row: usize, column: usize) -> usize {
879     let (row, column) = if row > column {
880         (row, column)
881     } else {
882         (column, row)
883     };
884     (row * (row + 1)) / 2 + column
885 }
886 
887 #[inline]
extend_lower_triangular_matrix<T: Default>( node_adjacencies: &mut Vec<T>, new_capacity: usize, ) -> usize888 fn extend_lower_triangular_matrix<T: Default>(
889     node_adjacencies: &mut Vec<T>,
890     new_capacity: usize,
891 ) -> usize {
892     let max_node = new_capacity - 1;
893     let max_pos = to_lower_triangular_matrix_position(max_node, max_node);
894     ensure_len(node_adjacencies, max_pos + 1);
895     new_capacity
896 }
897 
898 /// Grow a Vec by appending the type's default value until the `size` is reached.
ensure_len<T: Default>(v: &mut Vec<T>, size: usize)899 fn ensure_len<T: Default>(v: &mut Vec<T>, size: usize) {
900     v.resize_with(size, T::default);
901 }
902 
903 #[derive(Debug, Clone)]
904 struct IdStorage<T> {
905     elements: Vec<Option<T>>,
906     upper_bound: usize,
907     removed_ids: IndexSet<usize>,
908 }
909 
910 impl<T> IdStorage<T> {
with_capacity(capacity: usize) -> Self911     fn with_capacity(capacity: usize) -> Self {
912         IdStorage {
913             elements: Vec::with_capacity(capacity),
914             upper_bound: 0,
915             removed_ids: IndexSet::new(),
916         }
917     }
918 
add(&mut self, element: T) -> usize919     fn add(&mut self, element: T) -> usize {
920         let id = if let Some(id) = self.removed_ids.pop() {
921             id
922         } else {
923             let id = self.upper_bound;
924             self.upper_bound += 1;
925 
926             ensure_len(&mut self.elements, id + 1);
927 
928             id
929         };
930 
931         self.elements[id] = Some(element);
932 
933         id
934     }
935 
remove(&mut self, id: usize) -> T936     fn remove(&mut self, id: usize) -> T {
937         let data = self.elements[id].take().unwrap();
938         if self.upper_bound - id == 1 {
939             self.upper_bound -= 1;
940         } else {
941             self.removed_ids.insert(id);
942         }
943         data
944     }
945 
clear(&mut self)946     fn clear(&mut self) {
947         self.upper_bound = 0;
948         self.elements.clear();
949         self.removed_ids.clear();
950     }
951 
952     #[inline]
len(&self) -> usize953     fn len(&self) -> usize {
954         self.upper_bound - self.removed_ids.len()
955     }
956 
iter_ids(&self) -> IdIterator957     fn iter_ids(&self) -> IdIterator {
958         IdIterator {
959             upper_bound: self.upper_bound,
960             removed_ids: &self.removed_ids,
961             current: None,
962         }
963     }
964 }
965 
966 impl<T> Index<usize> for IdStorage<T> {
967     type Output = T;
index(&self, index: usize) -> &T968     fn index(&self, index: usize) -> &T {
969         self.elements[index].as_ref().unwrap()
970     }
971 }
972 
973 impl<T> IndexMut<usize> for IdStorage<T> {
index_mut(&mut self, index: usize) -> &mut T974     fn index_mut(&mut self, index: usize) -> &mut T {
975         self.elements[index].as_mut().unwrap()
976     }
977 }
978 
979 #[derive(Debug, Clone)]
980 struct IdIterator<'a> {
981     upper_bound: usize,
982     removed_ids: &'a IndexSet<usize>,
983     current: Option<usize>,
984 }
985 
986 impl<'a> Iterator for IdIterator<'a> {
987     type Item = usize;
988 
next(&mut self) -> Option<Self::Item>989     fn next(&mut self) -> Option<Self::Item> {
990         // initialize / advance
991         let current = {
992             if self.current.is_none() {
993                 self.current = Some(0);
994                 self.current.as_mut().unwrap()
995             } else {
996                 let current = self.current.as_mut().unwrap();
997                 *current += 1;
998                 current
999             }
1000         };
1001 
1002         // skip removed ids
1003         while self.removed_ids.contains(current) && *current < self.upper_bound {
1004             *current += 1;
1005         }
1006 
1007         if *current < self.upper_bound {
1008             Some(*current)
1009         } else {
1010             None
1011         }
1012     }
1013 }
1014 
1015 /// Create a new empty `MatrixGraph`.
1016 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Default
1017     for MatrixGraph<N, E, Ty, Null, Ix>
1018 {
default() -> Self1019     fn default() -> Self {
1020         Self::with_capacity(0)
1021     }
1022 }
1023 
1024 impl<N, E> MatrixGraph<N, E, Directed> {
1025     /// Create a new `MatrixGraph` with directed edges.
1026     ///
1027     /// This is a convenience method. Use `MatrixGraph::with_capacity` or `MatrixGraph::default` for
1028     /// a constructor that is generic in all the type parameters of `MatrixGraph`.
new() -> Self1029     pub fn new() -> Self {
1030         MatrixGraph::default()
1031     }
1032 }
1033 
1034 impl<N, E> MatrixGraph<N, E, Undirected> {
1035     /// Create a new `MatrixGraph` with undirected edges.
1036     ///
1037     /// This is a convenience method. Use `MatrixGraph::with_capacity` or `MatrixGraph::default` for
1038     /// a constructor that is generic in all the type parameters of `MatrixGraph`.
new_undirected() -> Self1039     pub fn new_undirected() -> Self {
1040         MatrixGraph::default()
1041     }
1042 }
1043 
1044 /// Index the `MatrixGraph` by `NodeIndex` to access node weights.
1045 ///
1046 /// **Panics** if the node doesn't exist.
1047 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Index<NodeIndex<Ix>>
1048     for MatrixGraph<N, E, Ty, Null, Ix>
1049 {
1050     type Output = N;
1051 
index(&self, ax: NodeIndex<Ix>) -> &N1052     fn index(&self, ax: NodeIndex<Ix>) -> &N {
1053         self.node_weight(ax)
1054     }
1055 }
1056 
1057 /// Index the `MatrixGraph` by `NodeIndex` to access node weights.
1058 ///
1059 /// **Panics** if the node doesn't exist.
1060 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IndexMut<NodeIndex<Ix>>
1061     for MatrixGraph<N, E, Ty, Null, Ix>
1062 {
index_mut(&mut self, ax: NodeIndex<Ix>) -> &mut N1063     fn index_mut(&mut self, ax: NodeIndex<Ix>) -> &mut N {
1064         self.node_weight_mut(ax)
1065     }
1066 }
1067 
1068 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeCount
1069     for MatrixGraph<N, E, Ty, Null, Ix>
1070 {
node_count(&self) -> usize1071     fn node_count(&self) -> usize {
1072         MatrixGraph::node_count(self)
1073     }
1074 }
1075 
1076 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> EdgeCount
1077     for MatrixGraph<N, E, Ty, Null, Ix>
1078 {
1079     #[inline]
edge_count(&self) -> usize1080     fn edge_count(&self) -> usize {
1081         self.edge_count()
1082     }
1083 }
1084 
1085 /// Index the `MatrixGraph` by `NodeIndex` pair to access edge weights.
1086 ///
1087 /// Also available with indexing syntax: `&graph[e]`.
1088 ///
1089 /// **Panics** if no edge exists between `a` and `b`.
1090 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType>
1091     Index<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix>
1092 {
1093     type Output = E;
1094 
index(&self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &E1095     fn index(&self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &E {
1096         self.edge_weight(ax, bx)
1097     }
1098 }
1099 
1100 /// Index the `MatrixGraph` by `NodeIndex` pair to access edge weights.
1101 ///
1102 /// Also available with indexing syntax: `&mut graph[e]`.
1103 ///
1104 /// **Panics** if no edge exists between `a` and `b`.
1105 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType>
1106     IndexMut<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix>
1107 {
index_mut(&mut self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &mut E1108     fn index_mut(&mut self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &mut E {
1109         self.edge_weight_mut(ax, bx)
1110     }
1111 }
1112 
1113 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GetAdjacencyMatrix
1114     for MatrixGraph<N, E, Ty, Null, Ix>
1115 {
1116     type AdjMatrix = ();
1117 
adjacency_matrix(&self) -> Self::AdjMatrix1118     fn adjacency_matrix(&self) -> Self::AdjMatrix {}
1119 
is_adjacent(&self, _: &Self::AdjMatrix, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool1120     fn is_adjacent(&self, _: &Self::AdjMatrix, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
1121         MatrixGraph::has_edge(self, a, b)
1122     }
1123 }
1124 
1125 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Visitable
1126     for MatrixGraph<N, E, Ty, Null, Ix>
1127 {
1128     type Map = FixedBitSet;
1129 
visit_map(&self) -> FixedBitSet1130     fn visit_map(&self) -> FixedBitSet {
1131         FixedBitSet::with_capacity(self.node_bound())
1132     }
1133 
reset_map(&self, map: &mut Self::Map)1134     fn reset_map(&self, map: &mut Self::Map) {
1135         map.clear();
1136         map.grow(self.node_bound());
1137     }
1138 }
1139 
1140 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphBase
1141     for MatrixGraph<N, E, Ty, Null, Ix>
1142 {
1143     type NodeId = NodeIndex<Ix>;
1144     type EdgeId = (NodeIndex<Ix>, NodeIndex<Ix>);
1145 }
1146 
1147 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphProp
1148     for MatrixGraph<N, E, Ty, Null, Ix>
1149 {
1150     type EdgeType = Ty;
1151 }
1152 
1153 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Data
1154     for MatrixGraph<N, E, Ty, Null, Ix>
1155 {
1156     type NodeWeight = N;
1157     type EdgeWeight = E;
1158 }
1159 
1160 impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeIdentifiers
1161     for &'a MatrixGraph<N, E, Ty, Null, Ix>
1162 {
1163     type NodeIdentifiers = NodeIdentifiers<'a, Ix>;
1164 
node_identifiers(self) -> Self::NodeIdentifiers1165     fn node_identifiers(self) -> Self::NodeIdentifiers {
1166         NodeIdentifiers::new(self.nodes.iter_ids())
1167     }
1168 }
1169 
1170 impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNeighbors
1171     for &'a MatrixGraph<N, E, Ty, Null, Ix>
1172 {
1173     type Neighbors = Neighbors<'a, Ty, Null, Ix>;
1174 
neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors1175     fn neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors {
1176         MatrixGraph::neighbors(self, a)
1177     }
1178 }
1179 
1180 impl<'a, N, E: 'a, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNeighborsDirected
1181     for &'a MatrixGraph<N, E, Directed, Null, Ix>
1182 {
1183     type NeighborsDirected = Neighbors<'a, Directed, Null, Ix>;
1184 
neighbors_directed(self, a: NodeIndex<Ix>, d: Direction) -> Self::NeighborsDirected1185     fn neighbors_directed(self, a: NodeIndex<Ix>, d: Direction) -> Self::NeighborsDirected {
1186         MatrixGraph::neighbors_directed(self, a, d)
1187     }
1188 }
1189 
1190 impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeReferences
1191     for &'a MatrixGraph<N, E, Ty, Null, Ix>
1192 {
1193     type NodeRef = (NodeIndex<Ix>, &'a N);
1194     type NodeReferences = NodeReferences<'a, N, Ix>;
node_references(self) -> Self::NodeReferences1195     fn node_references(self) -> Self::NodeReferences {
1196         NodeReferences::new(&self.nodes)
1197     }
1198 }
1199 
1200 impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdgeReferences
1201     for &'a MatrixGraph<N, E, Ty, Null, Ix>
1202 {
1203     type EdgeRef = (NodeIndex<Ix>, NodeIndex<Ix>, &'a E);
1204     type EdgeReferences = EdgeReferences<'a, Ty, Null, Ix>;
edge_references(self) -> Self::EdgeReferences1205     fn edge_references(self) -> Self::EdgeReferences {
1206         EdgeReferences::new(&self.node_adjacencies, self.node_capacity)
1207     }
1208 }
1209 
1210 impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdges
1211     for &'a MatrixGraph<N, E, Ty, Null, Ix>
1212 {
1213     type Edges = Edges<'a, Ty, Null, Ix>;
edges(self, a: Self::NodeId) -> Self::Edges1214     fn edges(self, a: Self::NodeId) -> Self::Edges {
1215         MatrixGraph::edges(self, a)
1216     }
1217 }
1218 
1219 impl<'a, N, E, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdgesDirected
1220     for &'a MatrixGraph<N, E, Directed, Null, Ix>
1221 {
1222     type EdgesDirected = Edges<'a, Directed, Null, Ix>;
1223 
edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected1224     fn edges_directed(self, a: Self::NodeId, dir: Direction) -> Self::EdgesDirected {
1225         MatrixGraph::edges_directed(self, a, dir)
1226     }
1227 }
1228 
1229 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeIndexable
1230     for MatrixGraph<N, E, Ty, Null, Ix>
1231 {
node_bound(&self) -> usize1232     fn node_bound(&self) -> usize {
1233         self.nodes.upper_bound
1234     }
1235 
to_index(&self, ix: NodeIndex<Ix>) -> usize1236     fn to_index(&self, ix: NodeIndex<Ix>) -> usize {
1237         ix.index()
1238     }
1239 
from_index(&self, ix: usize) -> Self::NodeId1240     fn from_index(&self, ix: usize) -> Self::NodeId {
1241         NodeIndex::new(ix)
1242     }
1243 }
1244 
1245 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Build
1246     for MatrixGraph<N, E, Ty, Null, Ix>
1247 {
add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId1248     fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
1249         self.add_node(weight)
1250     }
1251 
add_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight, ) -> Option<Self::EdgeId>1252     fn add_edge(
1253         &mut self,
1254         a: Self::NodeId,
1255         b: Self::NodeId,
1256         weight: Self::EdgeWeight,
1257     ) -> Option<Self::EdgeId> {
1258         if !self.has_edge(a, b) {
1259             MatrixGraph::update_edge(self, a, b, weight);
1260             Some((a, b))
1261         } else {
1262             None
1263         }
1264     }
1265 
update_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight, ) -> Self::EdgeId1266     fn update_edge(
1267         &mut self,
1268         a: Self::NodeId,
1269         b: Self::NodeId,
1270         weight: Self::EdgeWeight,
1271     ) -> Self::EdgeId {
1272         MatrixGraph::update_edge(self, a, b, weight);
1273         (a, b)
1274     }
1275 }
1276 
1277 #[cfg(test)]
1278 mod tests {
1279     use super::*;
1280     use crate::{Incoming, Outgoing};
1281 
1282     #[test]
test_new()1283     fn test_new() {
1284         let g = MatrixGraph::<i32, i32>::new();
1285         assert_eq!(g.node_count(), 0);
1286         assert_eq!(g.edge_count(), 0);
1287     }
1288 
1289     #[test]
test_default()1290     fn test_default() {
1291         let g = MatrixGraph::<i32, i32>::default();
1292         assert_eq!(g.node_count(), 0);
1293         assert_eq!(g.edge_count(), 0);
1294     }
1295 
1296     #[test]
test_with_capacity()1297     fn test_with_capacity() {
1298         let g = MatrixGraph::<i32, i32>::with_capacity(10);
1299         assert_eq!(g.node_count(), 0);
1300         assert_eq!(g.edge_count(), 0);
1301     }
1302 
1303     #[test]
test_node_indexing()1304     fn test_node_indexing() {
1305         let mut g: MatrixGraph<char, ()> = MatrixGraph::new();
1306         let a = g.add_node('a');
1307         let b = g.add_node('b');
1308         assert_eq!(g.node_count(), 2);
1309         assert_eq!(g.edge_count(), 0);
1310         assert_eq!(g[a], 'a');
1311         assert_eq!(g[b], 'b');
1312     }
1313 
1314     #[test]
test_remove_node()1315     fn test_remove_node() {
1316         let mut g: MatrixGraph<char, ()> = MatrixGraph::new();
1317         let a = g.add_node('a');
1318 
1319         g.remove_node(a);
1320 
1321         assert_eq!(g.node_count(), 0);
1322         assert_eq!(g.edge_count(), 0);
1323     }
1324 
1325     #[test]
test_add_edge()1326     fn test_add_edge() {
1327         let mut g = MatrixGraph::new();
1328         let a = g.add_node('a');
1329         let b = g.add_node('b');
1330         let c = g.add_node('c');
1331         g.add_edge(a, b, ());
1332         g.add_edge(b, c, ());
1333         assert_eq!(g.node_count(), 3);
1334         assert_eq!(g.edge_count(), 2);
1335     }
1336 
1337     #[test]
1338     /// Adds an edge that triggers a second extension of the matrix.
1339     /// From #425
test_add_edge_with_extension()1340     fn test_add_edge_with_extension() {
1341         let mut g = DiMatrix::<u8, ()>::new();
1342         let _n0 = g.add_node(0);
1343         let n1 = g.add_node(1);
1344         let n2 = g.add_node(2);
1345         let n3 = g.add_node(3);
1346         let n4 = g.add_node(4);
1347         let _n5 = g.add_node(5);
1348         g.add_edge(n2, n1, ());
1349         g.add_edge(n2, n3, ());
1350         g.add_edge(n2, n4, ());
1351         assert_eq!(g.node_count(), 6);
1352         assert_eq!(g.edge_count(), 3);
1353         assert!(g.has_edge(n2, n1));
1354         assert!(g.has_edge(n2, n3));
1355         assert!(g.has_edge(n2, n4));
1356     }
1357 
1358     #[test]
test_matrix_resize()1359     fn test_matrix_resize() {
1360         let mut g = DiMatrix::<u8, ()>::with_capacity(3);
1361         let n0 = g.add_node(0);
1362         let n1 = g.add_node(1);
1363         let n2 = g.add_node(2);
1364         let n3 = g.add_node(3);
1365         g.add_edge(n1, n0, ());
1366         g.add_edge(n1, n1, ());
1367         // Triggers a resize from capacity 3 to 4
1368         g.add_edge(n2, n3, ());
1369         assert_eq!(g.node_count(), 4);
1370         assert_eq!(g.edge_count(), 3);
1371         assert!(g.has_edge(n1, n0));
1372         assert!(g.has_edge(n1, n1));
1373         assert!(g.has_edge(n2, n3));
1374     }
1375 
1376     #[test]
test_add_edge_with_weights()1377     fn test_add_edge_with_weights() {
1378         let mut g = MatrixGraph::new();
1379         let a = g.add_node('a');
1380         let b = g.add_node('b');
1381         let c = g.add_node('c');
1382         g.add_edge(a, b, true);
1383         g.add_edge(b, c, false);
1384         assert_eq!(*g.edge_weight(a, b), true);
1385         assert_eq!(*g.edge_weight(b, c), false);
1386     }
1387 
1388     #[test]
test_add_edge_with_weights_undirected()1389     fn test_add_edge_with_weights_undirected() {
1390         let mut g = MatrixGraph::new_undirected();
1391         let a = g.add_node('a');
1392         let b = g.add_node('b');
1393         let c = g.add_node('c');
1394         let d = g.add_node('d');
1395         g.add_edge(a, b, "ab");
1396         g.add_edge(a, a, "aa");
1397         g.add_edge(b, c, "bc");
1398         g.add_edge(d, d, "dd");
1399         assert_eq!(*g.edge_weight(a, b), "ab");
1400         assert_eq!(*g.edge_weight(b, c), "bc");
1401     }
1402 
1403     /// Shorthand for `.collect::<Vec<_>>()`
1404     trait IntoVec<T> {
into_vec(self) -> Vec<T>1405         fn into_vec(self) -> Vec<T>;
1406     }
1407 
1408     impl<It, T> IntoVec<T> for It
1409     where
1410         It: Iterator<Item = T>,
1411     {
into_vec(self) -> Vec<T>1412         fn into_vec(self) -> Vec<T> {
1413             self.collect()
1414         }
1415     }
1416 
1417     #[test]
test_clear()1418     fn test_clear() {
1419         let mut g = MatrixGraph::new();
1420         let a = g.add_node('a');
1421         let b = g.add_node('b');
1422         let c = g.add_node('c');
1423         assert_eq!(g.node_count(), 3);
1424 
1425         g.add_edge(a, b, ());
1426         g.add_edge(b, c, ());
1427         g.add_edge(c, a, ());
1428         assert_eq!(g.edge_count(), 3);
1429 
1430         g.clear();
1431 
1432         assert_eq!(g.node_count(), 0);
1433         assert_eq!(g.edge_count(), 0);
1434 
1435         let a = g.add_node('a');
1436         let b = g.add_node('b');
1437         let c = g.add_node('c');
1438         assert_eq!(g.node_count(), 3);
1439         assert_eq!(g.edge_count(), 0);
1440 
1441         assert_eq!(g.neighbors_directed(a, Incoming).into_vec(), vec![]);
1442         assert_eq!(g.neighbors_directed(b, Incoming).into_vec(), vec![]);
1443         assert_eq!(g.neighbors_directed(c, Incoming).into_vec(), vec![]);
1444 
1445         assert_eq!(g.neighbors_directed(a, Outgoing).into_vec(), vec![]);
1446         assert_eq!(g.neighbors_directed(b, Outgoing).into_vec(), vec![]);
1447         assert_eq!(g.neighbors_directed(c, Outgoing).into_vec(), vec![]);
1448     }
1449 
1450     #[test]
test_clear_undirected()1451     fn test_clear_undirected() {
1452         let mut g = MatrixGraph::new_undirected();
1453         let a = g.add_node('a');
1454         let b = g.add_node('b');
1455         let c = g.add_node('c');
1456         assert_eq!(g.node_count(), 3);
1457 
1458         g.add_edge(a, b, ());
1459         g.add_edge(b, c, ());
1460         g.add_edge(c, a, ());
1461         assert_eq!(g.edge_count(), 3);
1462 
1463         g.clear();
1464 
1465         assert_eq!(g.node_count(), 0);
1466         assert_eq!(g.edge_count(), 0);
1467 
1468         let a = g.add_node('a');
1469         let b = g.add_node('b');
1470         let c = g.add_node('c');
1471         assert_eq!(g.node_count(), 3);
1472         assert_eq!(g.edge_count(), 0);
1473 
1474         assert_eq!(g.neighbors(a).into_vec(), vec![]);
1475         assert_eq!(g.neighbors(b).into_vec(), vec![]);
1476         assert_eq!(g.neighbors(c).into_vec(), vec![]);
1477     }
1478 
1479     /// Helper trait for always sorting before testing.
1480     trait IntoSortedVec<T> {
into_sorted_vec(self) -> Vec<T>1481         fn into_sorted_vec(self) -> Vec<T>;
1482     }
1483 
1484     impl<It, T> IntoSortedVec<T> for It
1485     where
1486         It: Iterator<Item = T>,
1487         T: Ord,
1488     {
into_sorted_vec(self) -> Vec<T>1489         fn into_sorted_vec(self) -> Vec<T> {
1490             let mut v: Vec<T> = self.collect();
1491             v.sort();
1492             v
1493         }
1494     }
1495 
1496     /// Helper macro for always sorting before testing.
1497     macro_rules! sorted_vec {
1498         ($($x:expr),*) => {
1499             {
1500                 let mut v = vec![$($x,)*];
1501                 v.sort();
1502                 v
1503             }
1504         }
1505     }
1506 
1507     #[test]
test_neighbors()1508     fn test_neighbors() {
1509         let mut g = MatrixGraph::new();
1510         let a = g.add_node('a');
1511         let b = g.add_node('b');
1512         let c = g.add_node('c');
1513         g.add_edge(a, b, ());
1514         g.add_edge(a, c, ());
1515 
1516         let a_neighbors = g.neighbors(a).into_sorted_vec();
1517         assert_eq!(a_neighbors, sorted_vec![b, c]);
1518 
1519         let b_neighbors = g.neighbors(b).into_sorted_vec();
1520         assert_eq!(b_neighbors, vec![]);
1521 
1522         let c_neighbors = g.neighbors(c).into_sorted_vec();
1523         assert_eq!(c_neighbors, vec![]);
1524     }
1525 
1526     #[test]
test_neighbors_undirected()1527     fn test_neighbors_undirected() {
1528         let mut g = MatrixGraph::new_undirected();
1529         let a = g.add_node('a');
1530         let b = g.add_node('b');
1531         let c = g.add_node('c');
1532         g.add_edge(a, b, ());
1533         g.add_edge(a, c, ());
1534 
1535         let a_neighbors = g.neighbors(a).into_sorted_vec();
1536         assert_eq!(a_neighbors, sorted_vec![b, c]);
1537 
1538         let b_neighbors = g.neighbors(b).into_sorted_vec();
1539         assert_eq!(b_neighbors, sorted_vec![a]);
1540 
1541         let c_neighbors = g.neighbors(c).into_sorted_vec();
1542         assert_eq!(c_neighbors, sorted_vec![a]);
1543     }
1544 
1545     #[test]
test_remove_node_and_edges()1546     fn test_remove_node_and_edges() {
1547         let mut g = MatrixGraph::new();
1548         let a = g.add_node('a');
1549         let b = g.add_node('b');
1550         let c = g.add_node('c');
1551         g.add_edge(a, b, ());
1552         g.add_edge(b, c, ());
1553         g.add_edge(c, a, ());
1554 
1555         // removing b should break the `a -> b` and `b -> c` edges
1556         g.remove_node(b);
1557 
1558         assert_eq!(g.node_count(), 2);
1559 
1560         let a_neighbors = g.neighbors(a).into_sorted_vec();
1561         assert_eq!(a_neighbors, vec![]);
1562 
1563         let c_neighbors = g.neighbors(c).into_sorted_vec();
1564         assert_eq!(c_neighbors, vec![a]);
1565     }
1566 
1567     #[test]
test_remove_node_and_edges_undirected()1568     fn test_remove_node_and_edges_undirected() {
1569         let mut g = UnMatrix::new_undirected();
1570         let a = g.add_node('a');
1571         let b = g.add_node('b');
1572         let c = g.add_node('c');
1573         g.add_edge(a, b, ());
1574         g.add_edge(b, c, ());
1575         g.add_edge(c, a, ());
1576 
1577         // removing a should break the `a - b` and `a - c` edges
1578         g.remove_node(a);
1579 
1580         assert_eq!(g.node_count(), 2);
1581 
1582         let b_neighbors = g.neighbors(b).into_sorted_vec();
1583         assert_eq!(b_neighbors, vec![c]);
1584 
1585         let c_neighbors = g.neighbors(c).into_sorted_vec();
1586         assert_eq!(c_neighbors, vec![b]);
1587     }
1588 
1589     #[test]
test_node_identifiers()1590     fn test_node_identifiers() {
1591         let mut g = MatrixGraph::new();
1592         let a = g.add_node('a');
1593         let b = g.add_node('b');
1594         let c = g.add_node('c');
1595         let d = g.add_node('c');
1596         g.add_edge(a, b, ());
1597         g.add_edge(a, c, ());
1598 
1599         let node_ids = g.node_identifiers().into_sorted_vec();
1600         assert_eq!(node_ids, sorted_vec![a, b, c, d]);
1601     }
1602 
1603     #[test]
test_edges_directed()1604     fn test_edges_directed() {
1605         let g: MatrixGraph<char, bool> = MatrixGraph::from_edges(&[
1606             (0, 5),
1607             (0, 2),
1608             (0, 3),
1609             (0, 1),
1610             (1, 3),
1611             (2, 3),
1612             (2, 4),
1613             (4, 0),
1614             (6, 6),
1615         ]);
1616 
1617         assert_eq!(g.edges_directed(node_index(0), Outgoing).count(), 4);
1618         assert_eq!(g.edges_directed(node_index(1), Outgoing).count(), 1);
1619         assert_eq!(g.edges_directed(node_index(2), Outgoing).count(), 2);
1620         assert_eq!(g.edges_directed(node_index(3), Outgoing).count(), 0);
1621         assert_eq!(g.edges_directed(node_index(4), Outgoing).count(), 1);
1622         assert_eq!(g.edges_directed(node_index(5), Outgoing).count(), 0);
1623         assert_eq!(g.edges_directed(node_index(6), Outgoing).count(), 1);
1624 
1625         assert_eq!(g.edges_directed(node_index(0), Incoming).count(), 1);
1626         assert_eq!(g.edges_directed(node_index(1), Incoming).count(), 1);
1627         assert_eq!(g.edges_directed(node_index(2), Incoming).count(), 1);
1628         assert_eq!(g.edges_directed(node_index(3), Incoming).count(), 3);
1629         assert_eq!(g.edges_directed(node_index(4), Incoming).count(), 1);
1630         assert_eq!(g.edges_directed(node_index(5), Incoming).count(), 1);
1631         assert_eq!(g.edges_directed(node_index(6), Incoming).count(), 1);
1632     }
1633 
1634     #[test]
test_edges_undirected()1635     fn test_edges_undirected() {
1636         let g: UnMatrix<char, bool> = UnMatrix::from_edges(&[
1637             (0, 5),
1638             (0, 2),
1639             (0, 3),
1640             (0, 1),
1641             (1, 3),
1642             (2, 3),
1643             (2, 4),
1644             (4, 0),
1645             (6, 6),
1646         ]);
1647 
1648         assert_eq!(g.edges(node_index(0)).count(), 5);
1649         assert_eq!(g.edges(node_index(1)).count(), 2);
1650         assert_eq!(g.edges(node_index(2)).count(), 3);
1651         assert_eq!(g.edges(node_index(3)).count(), 3);
1652         assert_eq!(g.edges(node_index(4)).count(), 2);
1653         assert_eq!(g.edges(node_index(5)).count(), 1);
1654         assert_eq!(g.edges(node_index(6)).count(), 1);
1655     }
1656 
1657     #[test]
test_edges_of_absent_node_is_empty_iterator()1658     fn test_edges_of_absent_node_is_empty_iterator() {
1659         let g: MatrixGraph<char, bool> = MatrixGraph::new();
1660         assert_eq!(g.edges(node_index(0)).count(), 0);
1661     }
1662 
1663     #[test]
test_neighbors_of_absent_node_is_empty_iterator()1664     fn test_neighbors_of_absent_node_is_empty_iterator() {
1665         let g: MatrixGraph<char, bool> = MatrixGraph::new();
1666         assert_eq!(g.neighbors(node_index(0)).count(), 0);
1667     }
1668 
1669     #[test]
test_edge_references()1670     fn test_edge_references() {
1671         let g: MatrixGraph<char, bool> = MatrixGraph::from_edges(&[
1672             (0, 5),
1673             (0, 2),
1674             (0, 3),
1675             (0, 1),
1676             (1, 3),
1677             (2, 3),
1678             (2, 4),
1679             (4, 0),
1680             (6, 6),
1681         ]);
1682 
1683         assert_eq!(g.edge_references().count(), 9);
1684     }
1685 
1686     #[test]
test_edge_references_undirected()1687     fn test_edge_references_undirected() {
1688         let g: UnMatrix<char, bool> = UnMatrix::from_edges(&[
1689             (0, 5),
1690             (0, 2),
1691             (0, 3),
1692             (0, 1),
1693             (1, 3),
1694             (2, 3),
1695             (2, 4),
1696             (4, 0),
1697             (6, 6),
1698         ]);
1699 
1700         assert_eq!(g.edge_references().count(), 9);
1701     }
1702 
1703     #[test]
test_id_storage()1704     fn test_id_storage() {
1705         use super::IdStorage;
1706 
1707         let mut storage: IdStorage<char> = IdStorage::with_capacity(0);
1708         let a = storage.add('a');
1709         let b = storage.add('b');
1710         let c = storage.add('c');
1711 
1712         assert!(a < b && b < c);
1713 
1714         // list IDs
1715         assert_eq!(storage.iter_ids().into_vec(), vec![a, b, c]);
1716 
1717         storage.remove(b);
1718 
1719         // re-use of IDs
1720         let bb = storage.add('B');
1721         assert_eq!(b, bb);
1722 
1723         // list IDs
1724         assert_eq!(storage.iter_ids().into_vec(), vec![a, b, c]);
1725     }
1726 
1727     #[test]
test_not_zero()1728     fn test_not_zero() {
1729         let mut g: MatrixGraph<(), i32, Directed, NotZero<i32>> = MatrixGraph::default();
1730 
1731         let a = g.add_node(());
1732         let b = g.add_node(());
1733 
1734         assert!(!g.has_edge(a, b));
1735         assert_eq!(g.edge_count(), 0);
1736 
1737         g.add_edge(a, b, 12);
1738 
1739         assert!(g.has_edge(a, b));
1740         assert_eq!(g.edge_count(), 1);
1741         assert_eq!(g.edge_weight(a, b), &12);
1742 
1743         g.remove_edge(a, b);
1744 
1745         assert!(!g.has_edge(a, b));
1746         assert_eq!(g.edge_count(), 0);
1747     }
1748 
1749     #[test]
1750     #[should_panic]
test_not_zero_asserted()1751     fn test_not_zero_asserted() {
1752         let mut g: MatrixGraph<(), i32, Directed, NotZero<i32>> = MatrixGraph::default();
1753 
1754         let a = g.add_node(());
1755         let b = g.add_node(());
1756 
1757         g.add_edge(a, b, 0); // this should trigger an assertion
1758     }
1759 
1760     #[test]
test_not_zero_float()1761     fn test_not_zero_float() {
1762         let mut g: MatrixGraph<(), f32, Directed, NotZero<f32>> = MatrixGraph::default();
1763 
1764         let a = g.add_node(());
1765         let b = g.add_node(());
1766 
1767         assert!(!g.has_edge(a, b));
1768         assert_eq!(g.edge_count(), 0);
1769 
1770         g.add_edge(a, b, 12.);
1771 
1772         assert!(g.has_edge(a, b));
1773         assert_eq!(g.edge_count(), 1);
1774         assert_eq!(g.edge_weight(a, b), &12.);
1775 
1776         g.remove_edge(a, b);
1777 
1778         assert!(!g.has_edge(a, b));
1779         assert_eq!(g.edge_count(), 0);
1780     }
1781     #[test]
1782     // From https://github.com/petgraph/petgraph/issues/523
test_tarjan_scc_with_removed_node()1783     fn test_tarjan_scc_with_removed_node() {
1784         let mut g: MatrixGraph<(), ()> = MatrixGraph::new();
1785 
1786         g.add_node(());
1787         let b = g.add_node(());
1788         g.add_node(());
1789 
1790         g.remove_node(b);
1791 
1792         assert_eq!(
1793             crate::algo::tarjan_scc(&g),
1794             [[node_index(0)], [node_index(2)]]
1795         );
1796     }
1797 
1798     #[test]
1799     // From https://github.com/petgraph/petgraph/issues/523
test_kosaraju_scc_with_removed_node()1800     fn test_kosaraju_scc_with_removed_node() {
1801         let mut g: MatrixGraph<(), ()> = MatrixGraph::new();
1802 
1803         g.add_node(());
1804         let b = g.add_node(());
1805         g.add_node(());
1806 
1807         g.remove_node(b);
1808 
1809         assert_eq!(
1810             crate::algo::kosaraju_scc(&g),
1811             [[node_index(2)], [node_index(0)]]
1812         );
1813     }
1814 }
1815