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, GetAdjacencyMatrix, GraphBase, GraphProp, IntoEdgeReferences, IntoEdges, IntoNeighbors,
19 IntoNeighborsDirected, IntoNodeIdentifiers, IntoNodeReferences, NodeCompactIndexable,
20 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 type Wrapped = T;
98
new(value: T) -> Self99 fn new(value: T) -> Self {
100 assert!(!value.is_zero());
101 NotZero(value)
102 }
103
104 // implemented here for optimization purposes
is_null(&self) -> bool105 fn is_null(&self) -> bool {
106 self.0.is_zero()
107 }
108
as_ref(&self) -> Option<&Self::Wrapped>109 fn as_ref(&self) -> Option<&Self::Wrapped> {
110 if !self.is_null() {
111 Some(&self.0)
112 } else {
113 None
114 }
115 }
116
as_mut(&mut self) -> Option<&mut Self::Wrapped>117 fn as_mut(&mut self) -> Option<&mut Self::Wrapped> {
118 if !self.is_null() {
119 Some(&mut self.0)
120 } else {
121 None
122 }
123 }
124 }
125
126 impl<T: Zero> Into<Option<T>> for NotZero<T> {
into(self) -> Option<T>127 fn into(self) -> Option<T> {
128 if !self.is_null() {
129 Some(self.0)
130 } else {
131 None
132 }
133 }
134 }
135
136 /// Base trait for types that can be wrapped in a [`NotZero`](struct.NotZero.html).
137 ///
138 /// Implementors must provide a singleton object that will be used to mark empty edges in a
139 /// [`MatrixGraph`](struct.MatrixGraph.html).
140 ///
141 /// Note that this trait is already implemented for the base numeric types.
142 pub trait Zero {
143 /// Return the singleton object which can be used as a sentinel value.
zero() -> Self144 fn zero() -> Self;
145
146 /// Return true if `self` is equal to the sentinel value.
is_zero(&self) -> bool147 fn is_zero(&self) -> bool;
148 }
149
150 macro_rules! not_zero_impl {
151 ($t:ty,$z:expr) => {
152 impl Zero for $t {
153 fn zero() -> Self {
154 $z as $t
155 }
156
157 fn is_zero(&self) -> bool {
158 self == &Self::zero()
159 }
160 }
161 };
162 }
163
164 macro_rules! not_zero_impls {
165 ($($t:ty),*) => {
166 $(
167 not_zero_impl!($t, 0);
168 )*
169 }
170 }
171
172 not_zero_impls!(u8, u16, u32, u64, usize);
173 not_zero_impls!(i8, i16, i32, i64, isize);
174 not_zero_impls!(f32, f64);
175
176 /// Short version of `NodeIndex::new` (with Ix = `DefaultIx`)
177 #[inline]
node_index(ax: usize) -> NodeIndex178 pub fn node_index(ax: usize) -> NodeIndex {
179 NodeIndex::new(ax)
180 }
181
182 /// `MatrixGraph<N, E, Ty, Null>` is a graph datastructure using an adjacency matrix
183 /// representation.
184 ///
185 /// `MatrixGraph` is parameterized over:
186 ///
187 /// - Associated data `N` for nodes and `E` for edges, called *weights*.
188 /// The associated data can be of arbitrary type.
189 /// - Edge type `Ty` that determines whether the graph edges are directed or undirected.
190 /// - Nullable type `Null`, which denotes the edges' presence (defaults to `Option<E>`). You may
191 /// specify [`NotZero<E>`](struct.NotZero.html) if you want to use a sentinel value (such as 0)
192 /// to mark the absence of an edge.
193 /// - Index type `Ix` that sets the maximum size for the graph (defaults to `DefaultIx`).
194 ///
195 /// The graph uses **O(|V^2|)** space, with fast edge insertion & amortized node insertion, as well
196 /// as efficient graph search and graph algorithms on dense graphs.
197 ///
198 /// This graph is backed by a flattened 2D array. For undirected graphs, only the lower triangular
199 /// matrix is stored. Since the backing array stores edge weights, it is recommended to box large
200 /// edge weights.
201 #[derive(Clone)]
202 pub struct MatrixGraph<N, E, Ty = Directed, Null: Nullable<Wrapped = E> = Option<E>, Ix = DefaultIx>
203 {
204 node_adjacencies: Vec<Null>,
205 node_capacity: usize,
206 nodes: IdStorage<N>,
207 nb_edges: usize,
208 ty: PhantomData<Ty>,
209 ix: PhantomData<Ix>,
210 }
211
212 /// A `MatrixGraph` with directed edges.
213 pub type DiMatrix<N, E, Null = Option<E>, Ix = DefaultIx> = MatrixGraph<N, E, Directed, Null, Ix>;
214
215 /// A `MatrixGraph` with undirected edges.
216 pub type UnMatrix<N, E, Null = Option<E>, Ix = DefaultIx> = MatrixGraph<N, E, Undirected, Null, Ix>;
217
218 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType>
219 MatrixGraph<N, E, Ty, Null, Ix>
220 {
221 /// Create a new `MatrixGraph` with estimated capacity for nodes.
with_capacity(node_capacity: usize) -> Self222 pub fn with_capacity(node_capacity: usize) -> Self {
223 let mut m = Self {
224 node_adjacencies: vec![],
225 node_capacity: 0,
226 nodes: IdStorage::with_capacity(node_capacity),
227 nb_edges: 0,
228 ty: PhantomData,
229 ix: PhantomData,
230 };
231
232 debug_assert!(node_capacity <= <Ix as IndexType>::max().index());
233 m.extend_capacity_for_node(NodeIndex::new(node_capacity));
234
235 m
236 }
237
238 #[inline]
to_edge_position(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> usize239 fn to_edge_position(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> usize {
240 to_linearized_matrix_position::<Ty>(a.index(), b.index(), self.node_capacity)
241 }
242
243 /// Remove all nodes and edges.
clear(&mut self)244 pub fn clear(&mut self) {
245 for edge in self.node_adjacencies.iter_mut() {
246 *edge = Default::default();
247 }
248 self.nodes.clear();
249 self.nb_edges = 0;
250 }
251
252 /// Return the number of nodes (vertices) in the graph.
253 ///
254 /// Computes in **O(1)** time.
255 #[inline]
node_count(&self) -> usize256 pub fn node_count(&self) -> usize {
257 self.nodes.len()
258 }
259
260 /// Return the number of edges in the graph.
261 ///
262 /// Computes in **O(1)** time.
263 #[inline]
edge_count(&self) -> usize264 pub fn edge_count(&self) -> usize {
265 self.nb_edges
266 }
267
268 /// Return whether the graph has directed edges or not.
269 #[inline]
is_directed(&self) -> bool270 pub fn is_directed(&self) -> bool {
271 Ty::is_directed()
272 }
273
274 /// Add a node (also called vertex) with associated data `weight` to the graph.
275 ///
276 /// Computes in **O(1)** time.
277 ///
278 /// Return the index of the new node.
279 ///
280 /// **Panics** if the MatrixGraph is at the maximum number of nodes for its index type.
add_node(&mut self, weight: N) -> NodeIndex<Ix>281 pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix> {
282 NodeIndex::new(self.nodes.add(weight))
283 }
284
285 /// Remove `a` from the graph.
286 ///
287 /// Computes in **O(V)** time, due to the removal of edges with other nodes.
288 ///
289 /// **Panics** if the node `a` does not exist.
remove_node(&mut self, a: NodeIndex<Ix>) -> N290 pub fn remove_node(&mut self, a: NodeIndex<Ix>) -> N {
291 for id in self.nodes.iter_ids() {
292 let position = self.to_edge_position(a, NodeIndex::new(id));
293 self.node_adjacencies[position] = Default::default();
294
295 if Ty::is_directed() {
296 let position = self.to_edge_position(NodeIndex::new(id), a);
297 self.node_adjacencies[position] = Default::default();
298 }
299 }
300
301 self.nodes.remove(a.index())
302 }
303
304 #[inline]
extend_capacity_for_node(&mut self, min_node: NodeIndex<Ix>)305 fn extend_capacity_for_node(&mut self, min_node: NodeIndex<Ix>) {
306 self.node_capacity = extend_linearized_matrix::<Ty, _>(
307 &mut self.node_adjacencies,
308 self.node_capacity,
309 min_node.index(),
310 );
311 }
312
313 #[inline]
extend_capacity_for_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>)314 fn extend_capacity_for_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) {
315 let min_node = cmp::max(a, b);
316 if min_node.index() >= self.node_capacity {
317 self.extend_capacity_for_node(min_node);
318 }
319 }
320
321 /// Update the edge from `a` to `b` to the graph, with its associated data `weight`.
322 ///
323 /// Return the previous data, if any.
324 ///
325 /// Computes in **O(1)** time, best case.
326 /// Computes in **O(|V|^2)** time, worst case (matrix needs to be re-allocated).
327 ///
328 /// **Panics** if any of the nodes don't exist.
update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> Option<E>329 pub fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> Option<E> {
330 self.extend_capacity_for_edge(a, b);
331
332 let p = self.to_edge_position(a, b);
333 let old_weight = mem::replace(&mut self.node_adjacencies[p], Null::new(weight));
334 if old_weight.is_null() {
335 self.nb_edges += 1;
336 }
337 old_weight.into()
338 }
339
340 /// Add an edge from `a` to `b` to the graph, with its associated
341 /// data `weight`.
342 ///
343 /// Return the index of the new edge.
344 ///
345 /// Computes in **O(1)** time, best case.
346 /// Computes in **O(|V|^2)** time, worst case (matrix needs to be re-allocated).
347 ///
348 /// **Panics** if any of the nodes don't exist.
349 /// **Panics** if an edge already exists from `a` to `b`.
350 ///
351 /// **Note:** `MatrixGraph` does not allow adding parallel (“duplicate”) edges. If you want to avoid
352 /// this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead.
add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E)353 pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) {
354 let old_edge_id = self.update_edge(a, b, weight);
355 assert!(old_edge_id.is_none());
356 }
357
358 /// Remove the edge from `a` to `b` to the graph.
359 ///
360 /// **Panics** if any of the nodes don't exist.
361 /// **Panics** if no edge exists between `a` and `b`.
remove_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> E362 pub fn remove_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> E {
363 let p = self.to_edge_position(a, b);
364 let old_weight = mem::replace(&mut self.node_adjacencies[p], Default::default())
365 .into()
366 .unwrap();
367 let old_weight: Option<_> = old_weight.into();
368 self.nb_edges -= 1;
369 old_weight.unwrap()
370 }
371
372 /// Return true if there is an edge between `a` and `b`.
373 ///
374 /// **Panics** if any of the nodes don't exist.
has_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool375 pub fn has_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
376 let p = self.to_edge_position(a, b);
377 !self.node_adjacencies[p].is_null()
378 }
379
380 /// Access the weight for node `a`.
381 ///
382 /// Also available with indexing syntax: `&graph[a]`.
383 ///
384 /// **Panics** if the node doesn't exist.
node_weight(&self, a: NodeIndex<Ix>) -> &N385 pub fn node_weight(&self, a: NodeIndex<Ix>) -> &N {
386 &self.nodes[a.index()]
387 }
388
389 /// Access the weight for node `a`, mutably.
390 ///
391 /// Also available with indexing syntax: `&mut graph[a]`.
392 ///
393 /// **Panics** if the node doesn't exist.
node_weight_mut(&mut self, a: NodeIndex<Ix>) -> &mut N394 pub fn node_weight_mut(&mut self, a: NodeIndex<Ix>) -> &mut N {
395 &mut self.nodes[a.index()]
396 }
397
398 /// Access the weight for edge `e`.
399 ///
400 /// Also available with indexing syntax: `&graph[e]`.
401 ///
402 /// **Panics** if no edge exists between `a` and `b`.
edge_weight(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &E403 pub fn edge_weight(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &E {
404 let p = self.to_edge_position(a, b);
405 self.node_adjacencies[p].as_ref().unwrap()
406 }
407
408 /// Access the weight for edge `e`, mutably.
409 ///
410 /// Also available with indexing syntax: `&mut graph[e]`.
411 ///
412 /// **Panics** if no edge exists between `a` and `b`.
edge_weight_mut(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &mut E413 pub fn edge_weight_mut(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> &mut E {
414 let p = self.to_edge_position(a, b);
415 self.node_adjacencies[p].as_mut().unwrap()
416 }
417
418 /// Return an iterator of all nodes with an edge starting from `a`.
419 ///
420 /// - `Directed`: Outgoing edges from `a`.
421 /// - `Undirected`: All edges from or to `a`.
422 ///
423 /// Produces an empty iterator if the node doesn't exist.<br>
424 /// Iterator element type is [`NodeIndex<Ix>`](../graph/struct.NodeIndex.html).
neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<Ty, Null, Ix>425 pub fn neighbors(&self, a: NodeIndex<Ix>) -> Neighbors<Ty, Null, Ix> {
426 Neighbors(Edges::on_columns(
427 a.index(),
428 &self.node_adjacencies,
429 self.node_capacity,
430 ))
431 }
432
433 /// Return an iterator of all edges of `a`.
434 ///
435 /// - `Directed`: Outgoing edges from `a`.
436 /// - `Undirected`: All edges connected to `a`.
437 ///
438 /// Produces an empty iterator if the node doesn't exist.<br>
439 /// Iterator element type is [`Edges<E, Ix>`](../graph/struct.Edges.html).
edges(&self, a: NodeIndex<Ix>) -> Edges<Ty, Null, Ix>440 pub fn edges(&self, a: NodeIndex<Ix>) -> Edges<Ty, Null, Ix> {
441 Edges::on_columns(a.index(), &self.node_adjacencies, self.node_capacity)
442 }
443
444 /// Create a new `MatrixGraph` from an iterable of edges.
445 ///
446 /// Node weights `N` are set to default values.
447 /// Edge weights `E` may either be specified in the list,
448 /// or they are filled with default values.
449 ///
450 /// Nodes are inserted automatically to match the edges.
451 ///
452 /// ```
453 /// use petgraph::matrix_graph::MatrixGraph;
454 ///
455 /// let gr = MatrixGraph::<(), i32>::from_edges(&[
456 /// (0, 1), (0, 2), (0, 3),
457 /// (1, 2), (1, 3),
458 /// (2, 3),
459 /// ]);
460 /// ```
from_edges<I>(iterable: I) -> Self where I: IntoIterator, I::Item: IntoWeightedEdge<E>, <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>, N: Default,461 pub fn from_edges<I>(iterable: I) -> Self
462 where
463 I: IntoIterator,
464 I::Item: IntoWeightedEdge<E>,
465 <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
466 N: Default,
467 {
468 let mut g = Self::default();
469 g.extend_with_edges(iterable);
470 g
471 }
472
473 /// Extend the graph from an iterable of edges.
474 ///
475 /// Node weights `N` are set to default values.
476 /// Edge weights `E` may either be specified in the list,
477 /// or they are filled with default values.
478 ///
479 /// 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,480 pub fn extend_with_edges<I>(&mut self, iterable: I)
481 where
482 I: IntoIterator,
483 I::Item: IntoWeightedEdge<E>,
484 <I::Item as IntoWeightedEdge<E>>::NodeId: Into<NodeIndex<Ix>>,
485 N: Default,
486 {
487 for elt in iterable {
488 let (source, target, weight) = elt.into_weighted_edge();
489 let (source, target) = (source.into(), target.into());
490 let nx = cmp::max(source, target);
491 while nx.index() >= self.node_count() {
492 self.add_node(N::default());
493 }
494 self.add_edge(source, target, weight);
495 }
496 }
497 }
498
499 impl<N, E, Null: Nullable<Wrapped = E>, Ix: IndexType> MatrixGraph<N, E, Directed, Null, Ix> {
500 /// Return an iterator of all neighbors that have an edge between them and
501 /// `a`, in the specified direction.
502 /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*.
503 ///
504 /// - `Outgoing`: All edges from `a`.
505 /// - `Incoming`: All edges to `a`.
506 ///
507 /// Produces an empty iterator if the node doesn't exist.<br>
508 /// Iterator element type is [`NodeIndex<Ix>`](../graph/struct.NodeIndex.html).
neighbors_directed( &self, a: NodeIndex<Ix>, d: Direction, ) -> Neighbors<Directed, Null, Ix>509 pub fn neighbors_directed(
510 &self,
511 a: NodeIndex<Ix>,
512 d: Direction,
513 ) -> Neighbors<Directed, Null, Ix> {
514 if d == Outgoing {
515 self.neighbors(a)
516 } else {
517 Neighbors(Edges::on_rows(
518 a.index(),
519 &self.node_adjacencies,
520 self.node_capacity,
521 ))
522 }
523 }
524
525 /// Return an iterator of all edges of `a`, in the specified direction.
526 ///
527 /// - `Outgoing`: All edges from `a`.
528 /// - `Incoming`: All edges to `a`.
529 ///
530 /// Produces an empty iterator if the node `a` doesn't exist.<br>
531 /// Iterator element type is [`EdgeReference<E, Ix>`](../graph/struct.EdgeReference.html).
edges_directed(&self, a: NodeIndex<Ix>, d: Direction) -> Edges<Directed, Null, Ix>532 pub fn edges_directed(&self, a: NodeIndex<Ix>, d: Direction) -> Edges<Directed, Null, Ix> {
533 if d == Outgoing {
534 self.edges(a)
535 } else {
536 Edges::on_rows(a.index(), &self.node_adjacencies, self.node_capacity)
537 }
538 }
539 }
540
541 /// Iterator over the node identifiers of a graph.
542 ///
543 /// Created from a call to [`.node_identifiers()`][1] on a [`MatrixGraph`][2].
544 ///
545 /// [1]: ../visit/trait.IntoNodeIdentifiers.html#tymethod.node_identifiers
546 /// [2]: struct.MatrixGraph.html
547 pub struct NodeIdentifiers<'a, Ix> {
548 iter: IdIterator<'a>,
549 ix: PhantomData<Ix>,
550 }
551
552 impl<'a, Ix: IndexType> NodeIdentifiers<'a, Ix> {
new(iter: IdIterator<'a>) -> Self553 fn new(iter: IdIterator<'a>) -> Self {
554 Self {
555 iter,
556 ix: PhantomData,
557 }
558 }
559 }
560
561 impl<'a, Ix: IndexType> Iterator for NodeIdentifiers<'a, Ix> {
562 type Item = NodeIndex<Ix>;
563
next(&mut self) -> Option<Self::Item>564 fn next(&mut self) -> Option<Self::Item> {
565 self.iter.next().map(NodeIndex::new)
566 }
567 }
568
569 /// Iterator over all nodes of a graph.
570 ///
571 /// Created from a call to [`.node_references()`][1] on a [`MatrixGraph`][2].
572 ///
573 /// [1]: ../visit/trait.IntoNodeReferences.html#tymethod.node_references
574 /// [2]: struct.MatrixGraph.html
575 pub struct NodeReferences<'a, N: 'a, Ix> {
576 nodes: &'a IdStorage<N>,
577 iter: IdIterator<'a>,
578 ix: PhantomData<Ix>,
579 }
580
581 impl<'a, N: 'a, Ix> NodeReferences<'a, N, Ix> {
new(nodes: &'a IdStorage<N>) -> Self582 fn new(nodes: &'a IdStorage<N>) -> Self {
583 NodeReferences {
584 nodes,
585 iter: nodes.iter_ids(),
586 ix: PhantomData,
587 }
588 }
589 }
590
591 impl<'a, N: 'a, Ix: IndexType> Iterator for NodeReferences<'a, N, Ix> {
592 type Item = (NodeIndex<Ix>, &'a N);
593
next(&mut self) -> Option<Self::Item>594 fn next(&mut self) -> Option<Self::Item> {
595 self.iter
596 .next()
597 .map(|i| (NodeIndex::new(i), &self.nodes[i]))
598 }
599 }
600
601 /// Iterator over all edges of a graph.
602 ///
603 /// Created from a call to [`.edge_references()`][1] on a [`MatrixGraph`][2].
604 ///
605 /// [1]: ../visit/trait.IntoEdgeReferences.html#tymethod.edge_references
606 /// [2]: struct.MatrixGraph.html
607 pub struct EdgeReferences<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> {
608 row: usize,
609 column: usize,
610 node_adjacencies: &'a [Null],
611 node_capacity: usize,
612 ty: PhantomData<Ty>,
613 ix: PhantomData<Ix>,
614 }
615
616 impl<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> EdgeReferences<'a, Ty, Null, Ix> {
new(node_adjacencies: &'a [Null], node_capacity: usize) -> Self617 fn new(node_adjacencies: &'a [Null], node_capacity: usize) -> Self {
618 EdgeReferences {
619 row: 0,
620 column: 0,
621 node_adjacencies,
622 node_capacity,
623 ty: PhantomData,
624 ix: PhantomData,
625 }
626 }
627 }
628
629 impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator
630 for EdgeReferences<'a, Ty, Null, Ix>
631 {
632 type Item = (NodeIndex<Ix>, NodeIndex<Ix>, &'a Null::Wrapped);
633
next(&mut self) -> Option<Self::Item>634 fn next(&mut self) -> Option<Self::Item> {
635 loop {
636 let (row, column) = (self.row, self.column);
637 if row >= self.node_capacity {
638 return None;
639 }
640
641 // By default, advance the column. Reset and advance the row if the column overflows.
642 //
643 // Note that for undirected graphs, we don't want to yield the same edge twice,
644 // therefore the maximum column length should be the index new after the row index.
645 self.column += 1;
646 let max_column_len = if !Ty::is_directed() {
647 row + 1
648 } else {
649 self.node_capacity
650 };
651 if self.column >= max_column_len {
652 self.column = 0;
653 self.row += 1;
654 }
655
656 let p = to_linearized_matrix_position::<Ty>(row, column, self.node_capacity);
657 if let Some(e) = self.node_adjacencies[p].as_ref() {
658 return Some((NodeIndex::new(row), NodeIndex::new(column), e));
659 }
660 }
661 }
662 }
663
664 /// Iterator over the neighbors of a node.
665 ///
666 /// Iterator element type is `NodeIndex<Ix>`.
667 ///
668 /// Created with [`.neighbors()`][1], [`.neighbors_directed()`][2].
669 ///
670 /// [1]: struct.MatrixGraph.html#method.neighbors
671 /// [2]: struct.MatrixGraph.html#method.neighbors_directed
672 pub struct Neighbors<'a, Ty: EdgeType, Null: 'a + Nullable, Ix>(Edges<'a, Ty, Null, Ix>);
673
674 impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Neighbors<'a, Ty, Null, Ix> {
675 type Item = NodeIndex<Ix>;
676
next(&mut self) -> Option<Self::Item>677 fn next(&mut self) -> Option<Self::Item> {
678 self.0.next().map(|(_, b, _)| b)
679 }
680 }
681
682 enum NeighborIterDirection {
683 Rows,
684 Columns,
685 }
686
687 /// Iterator over the edges of from or to a node
688 ///
689 /// Created with [`.edges()`][1], [`.edges_directed()`][2].
690 ///
691 /// [1]: struct.MatrixGraph.html#method.edges
692 /// [2]: struct.MatrixGraph.html#method.edges_directed
693 pub struct Edges<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> {
694 iter_direction: NeighborIterDirection,
695 node_adjacencies: &'a [Null],
696 node_capacity: usize,
697 row: usize,
698 column: usize,
699 ty: PhantomData<Ty>,
700 ix: PhantomData<Ix>,
701 }
702
703 impl<'a, Ty: EdgeType, Null: 'a + Nullable, Ix> Edges<'a, Ty, Null, Ix> {
on_columns(row: usize, node_adjacencies: &'a [Null], node_capacity: usize) -> Self704 fn on_columns(row: usize, node_adjacencies: &'a [Null], node_capacity: usize) -> Self {
705 Edges {
706 iter_direction: NeighborIterDirection::Columns,
707 node_adjacencies,
708 node_capacity,
709 row,
710 column: 0,
711 ty: PhantomData,
712 ix: PhantomData,
713 }
714 }
715
on_rows(column: usize, node_adjacencies: &'a [Null], node_capacity: usize) -> Self716 fn on_rows(column: usize, node_adjacencies: &'a [Null], node_capacity: usize) -> Self {
717 Edges {
718 iter_direction: NeighborIterDirection::Rows,
719 node_adjacencies,
720 node_capacity,
721 row: 0,
722 column,
723 ty: PhantomData,
724 ix: PhantomData,
725 }
726 }
727 }
728
729 impl<'a, Ty: EdgeType, Null: Nullable, Ix: IndexType> Iterator for Edges<'a, Ty, Null, Ix> {
730 type Item = (NodeIndex<Ix>, NodeIndex<Ix>, &'a Null::Wrapped);
731
next(&mut self) -> Option<Self::Item>732 fn next(&mut self) -> Option<Self::Item> {
733 use self::NeighborIterDirection::*;
734
735 loop {
736 let (row, column) = (self.row, self.column);
737 if row >= self.node_capacity || column >= self.node_capacity {
738 return None;
739 }
740
741 match self.iter_direction {
742 Rows => self.row += 1,
743 Columns => self.column += 1,
744 }
745
746 let p = to_linearized_matrix_position::<Ty>(row, column, self.node_capacity);
747 if let Some(e) = self.node_adjacencies[p].as_ref() {
748 let (a, b) = match self.iter_direction {
749 Rows => (column, row),
750 Columns => (row, column),
751 };
752
753 return Some((NodeIndex::new(a), NodeIndex::new(b), e));
754 }
755 }
756 }
757 }
758
759 #[inline]
to_linearized_matrix_position<Ty: EdgeType>(row: usize, column: usize, width: usize) -> usize760 fn to_linearized_matrix_position<Ty: EdgeType>(row: usize, column: usize, width: usize) -> usize {
761 if Ty::is_directed() {
762 to_flat_square_matrix_position(row, column, width)
763 } else {
764 to_lower_triangular_matrix_position(row, column)
765 }
766 }
767
768 #[inline]
extend_linearized_matrix<Ty: EdgeType, T: Default>( node_adjacencies: &mut Vec<T>, old_node_capacity: usize, min_node_capacity: usize, ) -> usize769 fn extend_linearized_matrix<Ty: EdgeType, T: Default>(
770 node_adjacencies: &mut Vec<T>,
771 old_node_capacity: usize,
772 min_node_capacity: usize,
773 ) -> usize {
774 if Ty::is_directed() {
775 extend_flat_square_matrix(node_adjacencies, old_node_capacity, min_node_capacity)
776 } else {
777 extend_lower_triangular_matrix(node_adjacencies, min_node_capacity)
778 }
779 }
780
781 #[inline]
to_flat_square_matrix_position(row: usize, column: usize, width: usize) -> usize782 fn to_flat_square_matrix_position(row: usize, column: usize, width: usize) -> usize {
783 row * width + column
784 }
785
786 #[inline]
extend_flat_square_matrix<T: Default>( node_adjacencies: &mut Vec<T>, old_node_capacity: usize, min_node_capacity: usize, ) -> usize787 fn extend_flat_square_matrix<T: Default>(
788 node_adjacencies: &mut Vec<T>,
789 old_node_capacity: usize,
790 min_node_capacity: usize,
791 ) -> usize {
792 let min_node_capacity = (min_node_capacity + 1).next_power_of_two();
793
794 // Optimization: when resizing the matrix this way we skip the first few grows to make
795 // small matrices a bit faster to work with.
796 const MIN_CAPACITY: usize = 4;
797 let new_node_capacity = cmp::max(min_node_capacity, MIN_CAPACITY);
798
799 let mut new_node_adjacencies = vec![];
800 ensure_len(&mut new_node_adjacencies, new_node_capacity.pow(2));
801
802 for c in 0..old_node_capacity {
803 let pos = c * old_node_capacity;
804 let new_pos = c * new_node_capacity;
805
806 let mut old = &mut node_adjacencies[pos..pos + old_node_capacity];
807 let mut new = &mut new_node_adjacencies[new_pos..new_pos + old_node_capacity];
808
809 mem::swap(&mut old, &mut new);
810 }
811
812 mem::swap(node_adjacencies, &mut new_node_adjacencies);
813
814 new_node_capacity
815 }
816
817 #[inline]
to_lower_triangular_matrix_position(row: usize, column: usize) -> usize818 fn to_lower_triangular_matrix_position(row: usize, column: usize) -> usize {
819 let (row, column) = if row > column {
820 (row, column)
821 } else {
822 (column, row)
823 };
824 (row * (row + 1)) / 2 + column
825 }
826
827 #[inline]
extend_lower_triangular_matrix<T: Default>( node_adjacencies: &mut Vec<T>, new_node_capacity: usize, ) -> usize828 fn extend_lower_triangular_matrix<T: Default>(
829 node_adjacencies: &mut Vec<T>,
830 new_node_capacity: usize,
831 ) -> usize {
832 let max_pos = to_lower_triangular_matrix_position(new_node_capacity, new_node_capacity);
833 ensure_len(node_adjacencies, max_pos + 1);
834 new_node_capacity + 1
835 }
836
837 /// 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)838 fn ensure_len<T: Default>(v: &mut Vec<T>, size: usize) {
839 if let Some(n) = size.checked_sub(v.len()) {
840 v.reserve(n);
841 for _ in 0..n {
842 v.push(T::default());
843 }
844 }
845 }
846
847 #[derive(Clone)]
848 struct IdStorage<T> {
849 elements: Vec<Option<T>>,
850 upper_bound: usize,
851 removed_ids: IndexSet<usize>,
852 }
853
854 impl<T> IdStorage<T> {
with_capacity(capacity: usize) -> Self855 fn with_capacity(capacity: usize) -> Self {
856 IdStorage {
857 elements: Vec::with_capacity(capacity),
858 upper_bound: 0,
859 removed_ids: IndexSet::new(),
860 }
861 }
862
add(&mut self, element: T) -> usize863 fn add(&mut self, element: T) -> usize {
864 let id = if let Some(id) = self.removed_ids.pop() {
865 id
866 } else {
867 let id = self.upper_bound;
868 self.upper_bound += 1;
869
870 ensure_len(&mut self.elements, id + 1);
871
872 id
873 };
874
875 self.elements[id] = Some(element);
876
877 id
878 }
879
remove(&mut self, id: usize) -> T880 fn remove(&mut self, id: usize) -> T {
881 let data = self.elements[id].take().unwrap();
882 if self.upper_bound - id == 1 {
883 self.upper_bound -= 1;
884 } else {
885 self.removed_ids.insert(id);
886 }
887 data
888 }
889
clear(&mut self)890 fn clear(&mut self) {
891 self.upper_bound = 0;
892 self.elements.clear();
893 self.removed_ids.clear();
894 }
895
896 #[inline]
len(&self) -> usize897 fn len(&self) -> usize {
898 self.upper_bound - self.removed_ids.len()
899 }
900
iter_ids(&self) -> IdIterator901 fn iter_ids(&self) -> IdIterator {
902 IdIterator {
903 upper_bound: self.upper_bound,
904 removed_ids: &self.removed_ids,
905 current: None,
906 }
907 }
908 }
909
910 impl<T> Index<usize> for IdStorage<T> {
911 type Output = T;
index(&self, index: usize) -> &T912 fn index(&self, index: usize) -> &T {
913 self.elements[index].as_ref().unwrap()
914 }
915 }
916
917 impl<T> IndexMut<usize> for IdStorage<T> {
index_mut(&mut self, index: usize) -> &mut T918 fn index_mut(&mut self, index: usize) -> &mut T {
919 self.elements[index].as_mut().unwrap()
920 }
921 }
922
923 struct IdIterator<'a> {
924 upper_bound: usize,
925 removed_ids: &'a IndexSet<usize>,
926 current: Option<usize>,
927 }
928
929 impl<'a> Iterator for IdIterator<'a> {
930 type Item = usize;
931
next(&mut self) -> Option<Self::Item>932 fn next(&mut self) -> Option<Self::Item> {
933 // initialize / advance
934 let current = {
935 if self.current.is_none() {
936 self.current = Some(0);
937 self.current.as_mut().unwrap()
938 } else {
939 let current = self.current.as_mut().unwrap();
940 *current += 1;
941 current
942 }
943 };
944
945 // skip removed ids
946 while self.removed_ids.contains(current) && *current < self.upper_bound {
947 *current += 1;
948 }
949
950 if *current < self.upper_bound {
951 Some(*current)
952 } else {
953 None
954 }
955 }
956 }
957
958 /// Create a new empty `MatrixGraph`.
959 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Default
960 for MatrixGraph<N, E, Ty, Null, Ix>
961 {
default() -> Self962 fn default() -> Self {
963 Self::with_capacity(0)
964 }
965 }
966
967 impl<N, E> MatrixGraph<N, E, Directed> {
968 /// Create a new `MatrixGraph` with directed edges.
969 ///
970 /// This is a convenience method. Use `MatrixGraph::with_capacity` or `MatrixGraph::default` for
971 /// a constructor that is generic in all the type parameters of `MatrixGraph`.
new() -> Self972 pub fn new() -> Self {
973 MatrixGraph::default()
974 }
975 }
976
977 impl<N, E> MatrixGraph<N, E, Undirected> {
978 /// Create a new `MatrixGraph` with undirected edges.
979 ///
980 /// This is a convenience method. Use `MatrixGraph::with_capacity` or `MatrixGraph::default` for
981 /// a constructor that is generic in all the type parameters of `MatrixGraph`.
new_undirected() -> Self982 pub fn new_undirected() -> Self {
983 MatrixGraph::default()
984 }
985 }
986
987 /// Index the `MatrixGraph` by `NodeIndex` to access node weights.
988 ///
989 /// **Panics** if the node doesn't exist.
990 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Index<NodeIndex<Ix>>
991 for MatrixGraph<N, E, Ty, Null, Ix>
992 {
993 type Output = N;
994
index(&self, ax: NodeIndex<Ix>) -> &N995 fn index(&self, ax: NodeIndex<Ix>) -> &N {
996 self.node_weight(ax)
997 }
998 }
999
1000 /// Index the `MatrixGraph` by `NodeIndex` to access node weights.
1001 ///
1002 /// **Panics** if the node doesn't exist.
1003 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IndexMut<NodeIndex<Ix>>
1004 for MatrixGraph<N, E, Ty, Null, Ix>
1005 {
index_mut(&mut self, ax: NodeIndex<Ix>) -> &mut N1006 fn index_mut(&mut self, ax: NodeIndex<Ix>) -> &mut N {
1007 self.node_weight_mut(ax)
1008 }
1009 }
1010
1011 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeCount
1012 for MatrixGraph<N, E, Ty, Null, Ix>
1013 {
node_count(&self) -> usize1014 fn node_count(&self) -> usize {
1015 MatrixGraph::node_count(self)
1016 }
1017 }
1018
1019 /// Index the `MatrixGraph` by `NodeIndex` pair to access edge weights.
1020 ///
1021 /// Also available with indexing syntax: `&graph[e]`.
1022 ///
1023 /// **Panics** if no edge exists between `a` and `b`.
1024 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType>
1025 Index<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix>
1026 {
1027 type Output = E;
1028
index(&self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &E1029 fn index(&self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &E {
1030 self.edge_weight(ax, bx)
1031 }
1032 }
1033
1034 /// Index the `MatrixGraph` by `NodeIndex` pair to access edge weights.
1035 ///
1036 /// Also available with indexing syntax: `&mut graph[e]`.
1037 ///
1038 /// **Panics** if no edge exists between `a` and `b`.
1039 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType>
1040 IndexMut<(NodeIndex<Ix>, NodeIndex<Ix>)> for MatrixGraph<N, E, Ty, Null, Ix>
1041 {
index_mut(&mut self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &mut E1042 fn index_mut(&mut self, (ax, bx): (NodeIndex<Ix>, NodeIndex<Ix>)) -> &mut E {
1043 self.edge_weight_mut(ax, bx)
1044 }
1045 }
1046
1047 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GetAdjacencyMatrix
1048 for MatrixGraph<N, E, Ty, Null, Ix>
1049 {
1050 type AdjMatrix = ();
1051
adjacency_matrix(&self) -> Self::AdjMatrix1052 fn adjacency_matrix(&self) -> Self::AdjMatrix {}
1053
is_adjacent(&self, _: &Self::AdjMatrix, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool1054 fn is_adjacent(&self, _: &Self::AdjMatrix, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
1055 MatrixGraph::has_edge(self, a, b)
1056 }
1057 }
1058
1059 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Visitable
1060 for MatrixGraph<N, E, Ty, Null, Ix>
1061 {
1062 type Map = FixedBitSet;
1063
visit_map(&self) -> FixedBitSet1064 fn visit_map(&self) -> FixedBitSet {
1065 FixedBitSet::with_capacity(self.node_count())
1066 }
1067
reset_map(&self, map: &mut Self::Map)1068 fn reset_map(&self, map: &mut Self::Map) {
1069 map.clear();
1070 map.grow(self.node_count());
1071 }
1072 }
1073
1074 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphBase
1075 for MatrixGraph<N, E, Ty, Null, Ix>
1076 {
1077 type NodeId = NodeIndex<Ix>;
1078 type EdgeId = (NodeIndex<Ix>, NodeIndex<Ix>);
1079 }
1080
1081 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> GraphProp
1082 for MatrixGraph<N, E, Ty, Null, Ix>
1083 {
1084 type EdgeType = Ty;
1085 }
1086
1087 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Data
1088 for MatrixGraph<N, E, Ty, Null, Ix>
1089 {
1090 type NodeWeight = N;
1091 type EdgeWeight = E;
1092 }
1093
1094 impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeIdentifiers
1095 for &'a MatrixGraph<N, E, Ty, Null, Ix>
1096 {
1097 type NodeIdentifiers = NodeIdentifiers<'a, Ix>;
1098
node_identifiers(self) -> Self::NodeIdentifiers1099 fn node_identifiers(self) -> Self::NodeIdentifiers {
1100 NodeIdentifiers::new(self.nodes.iter_ids())
1101 }
1102 }
1103
1104 impl<'a, N, E: 'a, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNeighbors
1105 for &'a MatrixGraph<N, E, Ty, Null, Ix>
1106 {
1107 type Neighbors = Neighbors<'a, Ty, Null, Ix>;
1108
neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors1109 fn neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors {
1110 MatrixGraph::neighbors(self, a)
1111 }
1112 }
1113
1114 impl<'a, N, E: 'a, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNeighborsDirected
1115 for &'a MatrixGraph<N, E, Directed, Null, Ix>
1116 {
1117 type NeighborsDirected = Neighbors<'a, Directed, Null, Ix>;
1118
neighbors_directed(self, a: NodeIndex<Ix>, d: Direction) -> Self::NeighborsDirected1119 fn neighbors_directed(self, a: NodeIndex<Ix>, d: Direction) -> Self::NeighborsDirected {
1120 MatrixGraph::neighbors_directed(self, a, d)
1121 }
1122 }
1123
1124 impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoNodeReferences
1125 for &'a MatrixGraph<N, E, Ty, Null, Ix>
1126 {
1127 type NodeRef = (NodeIndex<Ix>, &'a N);
1128 type NodeReferences = NodeReferences<'a, N, Ix>;
node_references(self) -> Self::NodeReferences1129 fn node_references(self) -> Self::NodeReferences {
1130 NodeReferences::new(&self.nodes)
1131 }
1132 }
1133
1134 impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdgeReferences
1135 for &'a MatrixGraph<N, E, Ty, Null, Ix>
1136 {
1137 type EdgeRef = (NodeIndex<Ix>, NodeIndex<Ix>, &'a E);
1138 type EdgeReferences = EdgeReferences<'a, Ty, Null, Ix>;
edge_references(self) -> Self::EdgeReferences1139 fn edge_references(self) -> Self::EdgeReferences {
1140 EdgeReferences::new(&self.node_adjacencies, self.node_capacity)
1141 }
1142 }
1143
1144 impl<'a, N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> IntoEdges
1145 for &'a MatrixGraph<N, E, Ty, Null, Ix>
1146 {
1147 type Edges = Edges<'a, Ty, Null, Ix>;
edges(self, a: Self::NodeId) -> Self::Edges1148 fn edges(self, a: Self::NodeId) -> Self::Edges {
1149 MatrixGraph::edges(self, a)
1150 }
1151 }
1152
1153 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeIndexable
1154 for MatrixGraph<N, E, Ty, Null, Ix>
1155 {
node_bound(&self) -> usize1156 fn node_bound(&self) -> usize {
1157 self.node_count()
1158 }
1159
to_index(&self, ix: NodeIndex<Ix>) -> usize1160 fn to_index(&self, ix: NodeIndex<Ix>) -> usize {
1161 ix.index()
1162 }
1163
from_index(&self, ix: usize) -> Self::NodeId1164 fn from_index(&self, ix: usize) -> Self::NodeId {
1165 NodeIndex::new(ix)
1166 }
1167 }
1168
1169 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> NodeCompactIndexable
1170 for MatrixGraph<N, E, Ty, Null, Ix>
1171 {
1172 }
1173
1174 impl<N, E, Ty: EdgeType, Null: Nullable<Wrapped = E>, Ix: IndexType> Build
1175 for MatrixGraph<N, E, Ty, Null, Ix>
1176 {
add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId1177 fn add_node(&mut self, weight: Self::NodeWeight) -> Self::NodeId {
1178 self.add_node(weight)
1179 }
1180
add_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight, ) -> Option<Self::EdgeId>1181 fn add_edge(
1182 &mut self,
1183 a: Self::NodeId,
1184 b: Self::NodeId,
1185 weight: Self::EdgeWeight,
1186 ) -> Option<Self::EdgeId> {
1187 if !self.has_edge(a, b) {
1188 MatrixGraph::update_edge(self, a, b, weight);
1189 Some((a, b))
1190 } else {
1191 None
1192 }
1193 }
1194
update_edge( &mut self, a: Self::NodeId, b: Self::NodeId, weight: Self::EdgeWeight, ) -> Self::EdgeId1195 fn update_edge(
1196 &mut self,
1197 a: Self::NodeId,
1198 b: Self::NodeId,
1199 weight: Self::EdgeWeight,
1200 ) -> Self::EdgeId {
1201 MatrixGraph::update_edge(self, a, b, weight);
1202 (a, b)
1203 }
1204 }
1205
1206 #[cfg(test)]
1207 mod tests {
1208 use super::*;
1209 use crate::{Incoming, Outgoing};
1210
1211 #[test]
test_new()1212 fn test_new() {
1213 let g = MatrixGraph::<i32, i32>::new();
1214 assert_eq!(g.node_count(), 0);
1215 assert_eq!(g.edge_count(), 0);
1216 }
1217
1218 #[test]
test_default()1219 fn test_default() {
1220 let g = MatrixGraph::<i32, i32>::default();
1221 assert_eq!(g.node_count(), 0);
1222 assert_eq!(g.edge_count(), 0);
1223 }
1224
1225 #[test]
test_with_capacity()1226 fn test_with_capacity() {
1227 let g = MatrixGraph::<i32, i32>::with_capacity(10);
1228 assert_eq!(g.node_count(), 0);
1229 assert_eq!(g.edge_count(), 0);
1230 }
1231
1232 #[test]
test_node_indexing()1233 fn test_node_indexing() {
1234 let mut g: MatrixGraph<char, ()> = MatrixGraph::new();
1235 let a = g.add_node('a');
1236 let b = g.add_node('b');
1237 assert_eq!(g.node_count(), 2);
1238 assert_eq!(g.edge_count(), 0);
1239 assert_eq!(g[a], 'a');
1240 assert_eq!(g[b], 'b');
1241 }
1242
1243 #[test]
test_remove_node()1244 fn test_remove_node() {
1245 let mut g: MatrixGraph<char, ()> = MatrixGraph::new();
1246 let a = g.add_node('a');
1247
1248 g.remove_node(a);
1249
1250 assert_eq!(g.node_count(), 0);
1251 assert_eq!(g.edge_count(), 0);
1252 }
1253
1254 #[test]
test_add_edge()1255 fn test_add_edge() {
1256 let mut g = MatrixGraph::new();
1257 let a = g.add_node('a');
1258 let b = g.add_node('b');
1259 let c = g.add_node('c');
1260 g.add_edge(a, b, ());
1261 g.add_edge(b, c, ());
1262 assert_eq!(g.node_count(), 3);
1263 assert_eq!(g.edge_count(), 2);
1264 }
1265
1266 #[test]
test_add_edge_with_weights()1267 fn test_add_edge_with_weights() {
1268 let mut g = MatrixGraph::new();
1269 let a = g.add_node('a');
1270 let b = g.add_node('b');
1271 let c = g.add_node('c');
1272 g.add_edge(a, b, true);
1273 g.add_edge(b, c, false);
1274 assert_eq!(*g.edge_weight(a, b), true);
1275 assert_eq!(*g.edge_weight(b, c), false);
1276 }
1277
1278 #[test]
test_add_edge_with_weights_undirected()1279 fn test_add_edge_with_weights_undirected() {
1280 let mut g = MatrixGraph::new_undirected();
1281 let a = g.add_node('a');
1282 let b = g.add_node('b');
1283 let c = g.add_node('c');
1284 let d = g.add_node('d');
1285 g.add_edge(a, b, "ab");
1286 g.add_edge(a, a, "aa");
1287 g.add_edge(b, c, "bc");
1288 g.add_edge(d, d, "dd");
1289 assert_eq!(*g.edge_weight(a, b), "ab");
1290 assert_eq!(*g.edge_weight(b, c), "bc");
1291 }
1292
1293 /// Shorthand for `.collect::<Vec<_>>()`
1294 trait IntoVec<T> {
into_vec(self) -> Vec<T>1295 fn into_vec(self) -> Vec<T>;
1296 }
1297
1298 impl<It, T> IntoVec<T> for It
1299 where
1300 It: Iterator<Item = T>,
1301 {
into_vec(self) -> Vec<T>1302 fn into_vec(self) -> Vec<T> {
1303 self.collect()
1304 }
1305 }
1306
1307 #[test]
test_clear()1308 fn test_clear() {
1309 let mut g = MatrixGraph::new();
1310 let a = g.add_node('a');
1311 let b = g.add_node('b');
1312 let c = g.add_node('c');
1313 assert_eq!(g.node_count(), 3);
1314
1315 g.add_edge(a, b, ());
1316 g.add_edge(b, c, ());
1317 g.add_edge(c, a, ());
1318 assert_eq!(g.edge_count(), 3);
1319
1320 g.clear();
1321
1322 assert_eq!(g.node_count(), 0);
1323 assert_eq!(g.edge_count(), 0);
1324
1325 let a = g.add_node('a');
1326 let b = g.add_node('b');
1327 let c = g.add_node('c');
1328 assert_eq!(g.node_count(), 3);
1329 assert_eq!(g.edge_count(), 0);
1330
1331 assert_eq!(g.neighbors_directed(a, Incoming).into_vec(), vec![]);
1332 assert_eq!(g.neighbors_directed(b, Incoming).into_vec(), vec![]);
1333 assert_eq!(g.neighbors_directed(c, Incoming).into_vec(), vec![]);
1334
1335 assert_eq!(g.neighbors_directed(a, Outgoing).into_vec(), vec![]);
1336 assert_eq!(g.neighbors_directed(b, Outgoing).into_vec(), vec![]);
1337 assert_eq!(g.neighbors_directed(c, Outgoing).into_vec(), vec![]);
1338 }
1339
1340 #[test]
test_clear_undirected()1341 fn test_clear_undirected() {
1342 let mut g = MatrixGraph::new_undirected();
1343 let a = g.add_node('a');
1344 let b = g.add_node('b');
1345 let c = g.add_node('c');
1346 assert_eq!(g.node_count(), 3);
1347
1348 g.add_edge(a, b, ());
1349 g.add_edge(b, c, ());
1350 g.add_edge(c, a, ());
1351 assert_eq!(g.edge_count(), 3);
1352
1353 g.clear();
1354
1355 assert_eq!(g.node_count(), 0);
1356 assert_eq!(g.edge_count(), 0);
1357
1358 let a = g.add_node('a');
1359 let b = g.add_node('b');
1360 let c = g.add_node('c');
1361 assert_eq!(g.node_count(), 3);
1362 assert_eq!(g.edge_count(), 0);
1363
1364 assert_eq!(g.neighbors(a).into_vec(), vec![]);
1365 assert_eq!(g.neighbors(b).into_vec(), vec![]);
1366 assert_eq!(g.neighbors(c).into_vec(), vec![]);
1367 }
1368
1369 /// Helper trait for always sorting before testing.
1370 trait IntoSortedVec<T> {
into_sorted_vec(self) -> Vec<T>1371 fn into_sorted_vec(self) -> Vec<T>;
1372 }
1373
1374 impl<It, T> IntoSortedVec<T> for It
1375 where
1376 It: Iterator<Item = T>,
1377 T: Ord,
1378 {
into_sorted_vec(self) -> Vec<T>1379 fn into_sorted_vec(self) -> Vec<T> {
1380 let mut v: Vec<T> = self.collect();
1381 v.sort();
1382 v
1383 }
1384 }
1385
1386 /// Helper macro for always sorting before testing.
1387 macro_rules! sorted_vec {
1388 ($($x:expr),*) => {
1389 {
1390 let mut v = vec![$($x,)*];
1391 v.sort();
1392 v
1393 }
1394 }
1395 }
1396
1397 #[test]
test_neighbors()1398 fn test_neighbors() {
1399 let mut g = MatrixGraph::new();
1400 let a = g.add_node('a');
1401 let b = g.add_node('b');
1402 let c = g.add_node('c');
1403 g.add_edge(a, b, ());
1404 g.add_edge(a, c, ());
1405
1406 let a_neighbors = g.neighbors(a).into_sorted_vec();
1407 assert_eq!(a_neighbors, sorted_vec![b, c]);
1408
1409 let b_neighbors = g.neighbors(b).into_sorted_vec();
1410 assert_eq!(b_neighbors, vec![]);
1411
1412 let c_neighbors = g.neighbors(c).into_sorted_vec();
1413 assert_eq!(c_neighbors, vec![]);
1414 }
1415
1416 #[test]
test_neighbors_undirected()1417 fn test_neighbors_undirected() {
1418 let mut g = MatrixGraph::new_undirected();
1419 let a = g.add_node('a');
1420 let b = g.add_node('b');
1421 let c = g.add_node('c');
1422 g.add_edge(a, b, ());
1423 g.add_edge(a, c, ());
1424
1425 let a_neighbors = g.neighbors(a).into_sorted_vec();
1426 assert_eq!(a_neighbors, sorted_vec![b, c]);
1427
1428 let b_neighbors = g.neighbors(b).into_sorted_vec();
1429 assert_eq!(b_neighbors, sorted_vec![a]);
1430
1431 let c_neighbors = g.neighbors(c).into_sorted_vec();
1432 assert_eq!(c_neighbors, sorted_vec![a]);
1433 }
1434
1435 #[test]
test_remove_node_and_edges()1436 fn test_remove_node_and_edges() {
1437 let mut g = MatrixGraph::new();
1438 let a = g.add_node('a');
1439 let b = g.add_node('b');
1440 let c = g.add_node('c');
1441 g.add_edge(a, b, ());
1442 g.add_edge(b, c, ());
1443 g.add_edge(c, a, ());
1444
1445 // removing b should break the `a -> b` and `b -> c` edges
1446 g.remove_node(b);
1447
1448 assert_eq!(g.node_count(), 2);
1449
1450 let a_neighbors = g.neighbors(a).into_sorted_vec();
1451 assert_eq!(a_neighbors, vec![]);
1452
1453 let c_neighbors = g.neighbors(c).into_sorted_vec();
1454 assert_eq!(c_neighbors, vec![a]);
1455 }
1456
1457 #[test]
test_remove_node_and_edges_undirected()1458 fn test_remove_node_and_edges_undirected() {
1459 let mut g = UnMatrix::new_undirected();
1460 let a = g.add_node('a');
1461 let b = g.add_node('b');
1462 let c = g.add_node('c');
1463 g.add_edge(a, b, ());
1464 g.add_edge(b, c, ());
1465 g.add_edge(c, a, ());
1466
1467 // removing a should break the `a - b` and `a - c` edges
1468 g.remove_node(a);
1469
1470 assert_eq!(g.node_count(), 2);
1471
1472 let b_neighbors = g.neighbors(b).into_sorted_vec();
1473 assert_eq!(b_neighbors, vec![c]);
1474
1475 let c_neighbors = g.neighbors(c).into_sorted_vec();
1476 assert_eq!(c_neighbors, vec![b]);
1477 }
1478
1479 #[test]
test_node_identifiers()1480 fn test_node_identifiers() {
1481 let mut g = MatrixGraph::new();
1482 let a = g.add_node('a');
1483 let b = g.add_node('b');
1484 let c = g.add_node('c');
1485 let d = g.add_node('c');
1486 g.add_edge(a, b, ());
1487 g.add_edge(a, c, ());
1488
1489 let node_ids = g.node_identifiers().into_sorted_vec();
1490 assert_eq!(node_ids, sorted_vec![a, b, c, d]);
1491 }
1492
1493 #[test]
test_edges_directed()1494 fn test_edges_directed() {
1495 let g: MatrixGraph<char, bool> = MatrixGraph::from_edges(&[
1496 (0, 5),
1497 (0, 2),
1498 (0, 3),
1499 (0, 1),
1500 (1, 3),
1501 (2, 3),
1502 (2, 4),
1503 (4, 0),
1504 (6, 6),
1505 ]);
1506
1507 assert_eq!(g.edges_directed(node_index(0), Outgoing).count(), 4);
1508 assert_eq!(g.edges_directed(node_index(1), Outgoing).count(), 1);
1509 assert_eq!(g.edges_directed(node_index(2), Outgoing).count(), 2);
1510 assert_eq!(g.edges_directed(node_index(3), Outgoing).count(), 0);
1511 assert_eq!(g.edges_directed(node_index(4), Outgoing).count(), 1);
1512 assert_eq!(g.edges_directed(node_index(5), Outgoing).count(), 0);
1513 assert_eq!(g.edges_directed(node_index(6), Outgoing).count(), 1);
1514
1515 assert_eq!(g.edges_directed(node_index(0), Incoming).count(), 1);
1516 assert_eq!(g.edges_directed(node_index(1), Incoming).count(), 1);
1517 assert_eq!(g.edges_directed(node_index(2), Incoming).count(), 1);
1518 assert_eq!(g.edges_directed(node_index(3), Incoming).count(), 3);
1519 assert_eq!(g.edges_directed(node_index(4), Incoming).count(), 1);
1520 assert_eq!(g.edges_directed(node_index(5), Incoming).count(), 1);
1521 assert_eq!(g.edges_directed(node_index(6), Incoming).count(), 1);
1522 }
1523
1524 #[test]
test_edges_undirected()1525 fn test_edges_undirected() {
1526 let g: UnMatrix<char, bool> = UnMatrix::from_edges(&[
1527 (0, 5),
1528 (0, 2),
1529 (0, 3),
1530 (0, 1),
1531 (1, 3),
1532 (2, 3),
1533 (2, 4),
1534 (4, 0),
1535 (6, 6),
1536 ]);
1537
1538 assert_eq!(g.edges(node_index(0)).count(), 5);
1539 assert_eq!(g.edges(node_index(1)).count(), 2);
1540 assert_eq!(g.edges(node_index(2)).count(), 3);
1541 assert_eq!(g.edges(node_index(3)).count(), 3);
1542 assert_eq!(g.edges(node_index(4)).count(), 2);
1543 assert_eq!(g.edges(node_index(5)).count(), 1);
1544 assert_eq!(g.edges(node_index(6)).count(), 1);
1545 }
1546
1547 #[test]
test_edges_of_absent_node_is_empty_iterator()1548 fn test_edges_of_absent_node_is_empty_iterator() {
1549 let g: MatrixGraph<char, bool> = MatrixGraph::new();
1550 assert_eq!(g.edges(node_index(0)).count(), 0);
1551 }
1552
1553 #[test]
test_neighbors_of_absent_node_is_empty_iterator()1554 fn test_neighbors_of_absent_node_is_empty_iterator() {
1555 let g: MatrixGraph<char, bool> = MatrixGraph::new();
1556 assert_eq!(g.neighbors(node_index(0)).count(), 0);
1557 }
1558
1559 #[test]
test_edge_references()1560 fn test_edge_references() {
1561 let g: MatrixGraph<char, bool> = MatrixGraph::from_edges(&[
1562 (0, 5),
1563 (0, 2),
1564 (0, 3),
1565 (0, 1),
1566 (1, 3),
1567 (2, 3),
1568 (2, 4),
1569 (4, 0),
1570 (6, 6),
1571 ]);
1572
1573 assert_eq!(g.edge_references().count(), 9);
1574 }
1575
1576 #[test]
test_edge_references_undirected()1577 fn test_edge_references_undirected() {
1578 let g: UnMatrix<char, bool> = UnMatrix::from_edges(&[
1579 (0, 5),
1580 (0, 2),
1581 (0, 3),
1582 (0, 1),
1583 (1, 3),
1584 (2, 3),
1585 (2, 4),
1586 (4, 0),
1587 (6, 6),
1588 ]);
1589
1590 assert_eq!(g.edge_references().count(), 9);
1591 }
1592
1593 #[test]
test_id_storage()1594 fn test_id_storage() {
1595 use super::IdStorage;
1596
1597 let mut storage: IdStorage<char> = IdStorage::with_capacity(0);
1598 let a = storage.add('a');
1599 let b = storage.add('b');
1600 let c = storage.add('c');
1601
1602 assert!(a < b && b < c);
1603
1604 // list IDs
1605 assert_eq!(storage.iter_ids().into_vec(), vec![a, b, c]);
1606
1607 storage.remove(b);
1608
1609 // re-use of IDs
1610 let bb = storage.add('B');
1611 assert_eq!(b, bb);
1612
1613 // list IDs
1614 assert_eq!(storage.iter_ids().into_vec(), vec![a, b, c]);
1615 }
1616
1617 #[test]
test_not_zero()1618 fn test_not_zero() {
1619 let mut g: MatrixGraph<(), i32, Directed, NotZero<i32>> = MatrixGraph::default();
1620
1621 let a = g.add_node(());
1622 let b = g.add_node(());
1623
1624 assert!(!g.has_edge(a, b));
1625 assert_eq!(g.edge_count(), 0);
1626
1627 g.add_edge(a, b, 12);
1628
1629 assert!(g.has_edge(a, b));
1630 assert_eq!(g.edge_count(), 1);
1631 assert_eq!(g.edge_weight(a, b), &12);
1632
1633 g.remove_edge(a, b);
1634
1635 assert!(!g.has_edge(a, b));
1636 assert_eq!(g.edge_count(), 0);
1637 }
1638
1639 #[test]
1640 #[should_panic]
test_not_zero_asserted()1641 fn test_not_zero_asserted() {
1642 let mut g: MatrixGraph<(), i32, Directed, NotZero<i32>> = MatrixGraph::default();
1643
1644 let a = g.add_node(());
1645 let b = g.add_node(());
1646
1647 g.add_edge(a, b, 0); // this should trigger an assertion
1648 }
1649
1650 #[test]
test_not_zero_float()1651 fn test_not_zero_float() {
1652 let mut g: MatrixGraph<(), f32, Directed, NotZero<f32>> = MatrixGraph::default();
1653
1654 let a = g.add_node(());
1655 let b = g.add_node(());
1656
1657 assert!(!g.has_edge(a, b));
1658 assert_eq!(g.edge_count(), 0);
1659
1660 g.add_edge(a, b, 12.);
1661
1662 assert!(g.has_edge(a, b));
1663 assert_eq!(g.edge_count(), 1);
1664 assert_eq!(g.edge_weight(a, b), &12.);
1665
1666 g.remove_edge(a, b);
1667
1668 assert!(!g.has_edge(a, b));
1669 assert_eq!(g.edge_count(), 0);
1670 }
1671 }
1672