]>
Commit | Line | Data |
---|---|---|
f9f354fc XL |
1 | //! `GraphMap<N, E, Ty>` is a graph datastructure where node values are mapping |
2 | //! keys. | |
3 | ||
f035d41b XL |
4 | use indexmap::map::Keys; |
5 | use indexmap::map::{Iter as IndexMapIter, IterMut as IndexMapIterMut}; | |
6 | use indexmap::IndexMap; | |
f9f354fc | 7 | use std::cmp::Ordering; |
f9f354fc | 8 | use std::fmt; |
f035d41b | 9 | use std::hash::{self, Hash}; |
f9f354fc | 10 | use std::iter::FromIterator; |
f035d41b | 11 | use std::iter::{Cloned, DoubleEndedIterator}; |
f9f354fc | 12 | use std::marker::PhantomData; |
f035d41b XL |
13 | use std::ops::{Deref, Index, IndexMut}; |
14 | use std::slice::Iter; | |
15 | ||
16 | use crate::{Directed, Direction, EdgeType, Incoming, Outgoing, Undirected}; | |
f9f354fc | 17 | |
f035d41b XL |
18 | use crate::graph::node_index; |
19 | use crate::graph::Graph; | |
20 | use crate::visit::{IntoEdgeReferences, IntoEdges, NodeCompactIndexable}; | |
21 | use crate::visit::{IntoNodeIdentifiers, IntoNodeReferences, NodeCount, NodeIndexable}; | |
22 | use crate::IntoWeightedEdge; | |
f9f354fc XL |
23 | |
24 | /// A `GraphMap` with undirected edges. | |
25 | /// | |
26 | /// For example, an edge between *1* and *2* is equivalent to an edge between | |
27 | /// *2* and *1*. | |
28 | pub type UnGraphMap<N, E> = GraphMap<N, E, Undirected>; | |
29 | /// A `GraphMap` with directed edges. | |
30 | /// | |
31 | /// For example, an edge from *1* to *2* is distinct from an edge from *2* to | |
32 | /// *1*. | |
33 | pub type DiGraphMap<N, E> = GraphMap<N, E, Directed>; | |
34 | ||
35 | /// `GraphMap<N, E, Ty>` is a graph datastructure using an associative array | |
36 | /// of its node weights `N`. | |
37 | /// | |
38 | /// It uses an combined adjacency list and sparse adjacency matrix | |
39 | /// representation, using **O(|V| + |E|)** space, and allows testing for edge | |
f035d41b | 40 | /// existence in constant time. |
f9f354fc XL |
41 | /// |
42 | /// `GraphMap` is parameterized over: | |
43 | /// | |
44 | /// - Associated data `N` for nodes and `E` for edges, called *weights*. | |
45 | /// - The node weight `N` must implement `Copy` and will be used as node | |
46 | /// identifier, duplicated into several places in the data structure. | |
47 | /// It must be suitable as a hash table key (implementing `Eq + Hash`). | |
48 | /// The node type must also implement `Ord` so that the implementation can | |
49 | /// order the pair (`a`, `b`) for an edge connecting any two nodes `a` and `b`. | |
50 | /// - `E` can be of arbitrary type. | |
51 | /// - Edge type `Ty` that determines whether the graph edges are directed or | |
52 | /// undirected. | |
53 | /// | |
54 | /// You can use the type aliases `UnGraphMap` and `DiGraphMap` for convenience. | |
55 | /// | |
56 | /// `GraphMap` does not allow parallel edges, but self loops are allowed. | |
57 | /// | |
58 | /// Depends on crate feature `graphmap` (default). | |
59 | #[derive(Clone)] | |
60 | pub struct GraphMap<N, E, Ty> { | |
f035d41b XL |
61 | nodes: IndexMap<N, Vec<(N, CompactDirection)>>, |
62 | edges: IndexMap<(N, N), E>, | |
f9f354fc XL |
63 | ty: PhantomData<Ty>, |
64 | } | |
65 | ||
66 | impl<N: Eq + Hash + fmt::Debug, E: fmt::Debug, Ty: EdgeType> fmt::Debug for GraphMap<N, E, Ty> { | |
67 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
68 | self.nodes.fmt(f) | |
69 | } | |
70 | } | |
71 | ||
72 | /// A trait group for `GraphMap`'s node identifier. | |
f035d41b | 73 | pub trait NodeTrait: Copy + Ord + Hash {} |
f9f354fc XL |
74 | impl<N> NodeTrait for N where N: Copy + Ord + Hash {} |
75 | ||
76 | // non-repr(usize) version of Direction | |
77 | #[derive(Copy, Clone, Debug, PartialEq)] | |
78 | enum CompactDirection { | |
79 | Outgoing, | |
80 | Incoming, | |
81 | } | |
82 | ||
83 | impl From<Direction> for CompactDirection { | |
84 | fn from(d: Direction) -> Self { | |
85 | match d { | |
86 | Outgoing => CompactDirection::Outgoing, | |
87 | Incoming => CompactDirection::Incoming, | |
88 | } | |
89 | } | |
90 | } | |
91 | ||
92 | impl PartialEq<Direction> for CompactDirection { | |
93 | fn eq(&self, rhs: &Direction) -> bool { | |
94 | (*self as usize) == (*rhs as usize) | |
95 | } | |
96 | } | |
97 | ||
98 | impl<N, E, Ty> GraphMap<N, E, Ty> | |
f035d41b XL |
99 | where |
100 | N: NodeTrait, | |
101 | Ty: EdgeType, | |
f9f354fc XL |
102 | { |
103 | /// Create a new `GraphMap` | |
104 | pub fn new() -> Self { | |
105 | Self::default() | |
106 | } | |
107 | ||
108 | /// Create a new `GraphMap` with estimated capacity. | |
109 | pub fn with_capacity(nodes: usize, edges: usize) -> Self { | |
110 | GraphMap { | |
f035d41b XL |
111 | nodes: IndexMap::with_capacity(nodes), |
112 | edges: IndexMap::with_capacity(edges), | |
f9f354fc XL |
113 | ty: PhantomData, |
114 | } | |
115 | } | |
116 | ||
117 | /// Return the current node and edge capacity of the graph. | |
118 | pub fn capacity(&self) -> (usize, usize) { | |
119 | (self.nodes.capacity(), self.edges.capacity()) | |
120 | } | |
121 | ||
f035d41b | 122 | /// Use their natural order to map the node pair (a, b) to a canonical edge id. |
f9f354fc XL |
123 | #[inline] |
124 | fn edge_key(a: N, b: N) -> (N, N) { | |
f035d41b | 125 | if Ty::is_directed() || a <= b { |
f9f354fc XL |
126 | (a, b) |
127 | } else { | |
f035d41b | 128 | (b, a) |
f9f354fc XL |
129 | } |
130 | } | |
131 | ||
132 | /// Whether the graph has directed edges. | |
133 | pub fn is_directed(&self) -> bool { | |
134 | Ty::is_directed() | |
135 | } | |
136 | ||
137 | /// Create a new `GraphMap` from an iterable of edges. | |
138 | /// | |
139 | /// Node values are taken directly from the list. | |
140 | /// Edge weights `E` may either be specified in the list, | |
141 | /// or they are filled with default values. | |
142 | /// | |
143 | /// Nodes are inserted automatically to match the edges. | |
144 | /// | |
145 | /// ``` | |
146 | /// use petgraph::graphmap::UnGraphMap; | |
147 | /// | |
148 | /// // Create a new undirected GraphMap. | |
149 | /// // Use a type hint to have `()` be the edge weight type. | |
150 | /// let gr = UnGraphMap::<_, ()>::from_edges(&[ | |
151 | /// (0, 1), (0, 2), (0, 3), | |
152 | /// (1, 2), (1, 3), | |
153 | /// (2, 3), | |
154 | /// ]); | |
155 | /// ``` | |
156 | pub fn from_edges<I>(iterable: I) -> Self | |
f035d41b XL |
157 | where |
158 | I: IntoIterator, | |
159 | I::Item: IntoWeightedEdge<E, NodeId = N>, | |
f9f354fc XL |
160 | { |
161 | Self::from_iter(iterable) | |
162 | } | |
163 | ||
164 | /// Return the number of nodes in the graph. | |
165 | pub fn node_count(&self) -> usize { | |
166 | self.nodes.len() | |
167 | } | |
168 | ||
169 | /// Return the number of edges in the graph. | |
170 | pub fn edge_count(&self) -> usize { | |
171 | self.edges.len() | |
172 | } | |
173 | ||
174 | /// Remove all nodes and edges | |
175 | pub fn clear(&mut self) { | |
176 | self.nodes.clear(); | |
177 | self.edges.clear(); | |
178 | } | |
179 | ||
180 | /// Add node `n` to the graph. | |
181 | pub fn add_node(&mut self, n: N) -> N { | |
182 | self.nodes.entry(n).or_insert(Vec::new()); | |
183 | n | |
184 | } | |
185 | ||
186 | /// Return `true` if node `n` was removed. | |
f035d41b XL |
187 | /// |
188 | /// Computes in **O(V)** time, due to the removal of edges with other nodes. | |
f9f354fc XL |
189 | pub fn remove_node(&mut self, n: N) -> bool { |
190 | let links = match self.nodes.swap_remove(&n) { | |
191 | None => return false, | |
192 | Some(sus) => sus, | |
193 | }; | |
194 | for (succ, _) in links { | |
195 | // remove all successor links | |
196 | self.remove_single_edge(&succ, &n, Incoming); | |
197 | // Remove all edge values | |
198 | self.edges.swap_remove(&Self::edge_key(n, succ)); | |
199 | } | |
200 | true | |
201 | } | |
202 | ||
203 | /// Return `true` if the node is contained in the graph. | |
204 | pub fn contains_node(&self, n: N) -> bool { | |
205 | self.nodes.contains_key(&n) | |
206 | } | |
207 | ||
208 | /// Add an edge connecting `a` and `b` to the graph, with associated | |
209 | /// data `weight`. For a directed graph, the edge is directed from `a` | |
210 | /// to `b`. | |
211 | /// | |
212 | /// Inserts nodes `a` and/or `b` if they aren't already part of the graph. | |
213 | /// | |
214 | /// Return `None` if the edge did not previously exist, otherwise, | |
215 | /// the associated data is updated and the old value is returned | |
216 | /// as `Some(old_weight)`. | |
217 | /// | |
218 | /// ``` | |
219 | /// // Create a GraphMap with directed edges, and add one edge to it | |
220 | /// use petgraph::graphmap::DiGraphMap; | |
221 | /// | |
222 | /// let mut g = DiGraphMap::new(); | |
223 | /// g.add_edge("x", "y", -1); | |
224 | /// assert_eq!(g.node_count(), 2); | |
225 | /// assert_eq!(g.edge_count(), 1); | |
226 | /// assert!(g.contains_edge("x", "y")); | |
227 | /// assert!(!g.contains_edge("y", "x")); | |
228 | /// ``` | |
229 | pub fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E> { | |
230 | if let old @ Some(_) = self.edges.insert(Self::edge_key(a, b), weight) { | |
231 | old | |
232 | } else { | |
233 | // insert in the adjacency list if it's a new edge | |
f035d41b XL |
234 | self.nodes |
235 | .entry(a) | |
236 | .or_insert_with(|| Vec::with_capacity(1)) | |
237 | .push((b, CompactDirection::Outgoing)); | |
f9f354fc XL |
238 | if a != b { |
239 | // self loops don't have the Incoming entry | |
f035d41b XL |
240 | self.nodes |
241 | .entry(b) | |
242 | .or_insert_with(|| Vec::with_capacity(1)) | |
243 | .push((a, CompactDirection::Incoming)); | |
f9f354fc XL |
244 | } |
245 | None | |
246 | } | |
247 | } | |
248 | ||
249 | /// Remove edge relation from a to b | |
250 | /// | |
251 | /// Return `true` if it did exist. | |
252 | fn remove_single_edge(&mut self, a: &N, b: &N, dir: Direction) -> bool { | |
253 | match self.nodes.get_mut(a) { | |
254 | None => false, | |
255 | Some(sus) => { | |
256 | if Ty::is_directed() { | |
f035d41b XL |
257 | match sus |
258 | .iter() | |
259 | .position(|elt| elt == &(*b, CompactDirection::from(dir))) | |
260 | { | |
261 | Some(index) => { | |
262 | sus.swap_remove(index); | |
263 | true | |
264 | } | |
f9f354fc XL |
265 | None => false, |
266 | } | |
267 | } else { | |
268 | match sus.iter().position(|elt| &elt.0 == b) { | |
f035d41b XL |
269 | Some(index) => { |
270 | sus.swap_remove(index); | |
271 | true | |
272 | } | |
f9f354fc XL |
273 | None => false, |
274 | } | |
275 | } | |
276 | } | |
277 | } | |
278 | } | |
279 | ||
280 | /// Remove edge from `a` to `b` from the graph and return the edge weight. | |
281 | /// | |
282 | /// Return `None` if the edge didn't exist. | |
283 | /// | |
284 | /// ``` | |
285 | /// // Create a GraphMap with undirected edges, and add and remove an edge. | |
286 | /// use petgraph::graphmap::UnGraphMap; | |
287 | /// | |
288 | /// let mut g = UnGraphMap::new(); | |
289 | /// g.add_edge("x", "y", -1); | |
290 | /// | |
291 | /// let edge_data = g.remove_edge("y", "x"); | |
292 | /// assert_eq!(edge_data, Some(-1)); | |
293 | /// assert_eq!(g.edge_count(), 0); | |
294 | /// ``` | |
295 | pub fn remove_edge(&mut self, a: N, b: N) -> Option<E> { | |
296 | let exist1 = self.remove_single_edge(&a, &b, Outgoing); | |
297 | let exist2 = if a != b { | |
298 | self.remove_single_edge(&b, &a, Incoming) | |
f035d41b XL |
299 | } else { |
300 | exist1 | |
301 | }; | |
f9f354fc XL |
302 | let weight = self.edges.remove(&Self::edge_key(a, b)); |
303 | debug_assert!(exist1 == exist2 && exist1 == weight.is_some()); | |
304 | weight | |
305 | } | |
306 | ||
307 | /// Return `true` if the edge connecting `a` with `b` is contained in the graph. | |
308 | pub fn contains_edge(&self, a: N, b: N) -> bool { | |
309 | self.edges.contains_key(&Self::edge_key(a, b)) | |
310 | } | |
311 | ||
312 | /// Return an iterator over the nodes of the graph. | |
313 | /// | |
314 | /// Iterator element type is `N`. | |
315 | pub fn nodes(&self) -> Nodes<N> { | |
f035d41b XL |
316 | Nodes { |
317 | iter: self.nodes.keys().cloned(), | |
318 | } | |
f9f354fc XL |
319 | } |
320 | ||
321 | /// Return an iterator of all nodes with an edge starting from `a`. | |
322 | /// | |
323 | /// - `Directed`: Outgoing edges from `a`. | |
324 | /// - `Undirected`: All edges from or to `a`. | |
325 | /// | |
326 | /// Produces an empty iterator if the node doesn't exist.<br> | |
327 | /// Iterator element type is `N`. | |
328 | pub fn neighbors(&self, a: N) -> Neighbors<N, Ty> { | |
329 | Neighbors { | |
330 | iter: match self.nodes.get(&a) { | |
331 | Some(neigh) => neigh.iter(), | |
332 | None => [].iter(), | |
333 | }, | |
334 | ty: self.ty, | |
335 | } | |
336 | } | |
337 | ||
338 | /// Return an iterator of all neighbors that have an edge between them and | |
339 | /// `a`, in the specified direction. | |
340 | /// If the graph's edges are undirected, this is equivalent to *.neighbors(a)*. | |
341 | /// | |
342 | /// - `Directed`, `Outgoing`: All edges from `a`. | |
343 | /// - `Directed`, `Incoming`: All edges to `a`. | |
344 | /// - `Undirected`: All edges from or to `a`. | |
345 | /// | |
346 | /// Produces an empty iterator if the node doesn't exist.<br> | |
347 | /// Iterator element type is `N`. | |
f035d41b | 348 | pub fn neighbors_directed(&self, a: N, dir: Direction) -> NeighborsDirected<N, Ty> { |
f9f354fc XL |
349 | NeighborsDirected { |
350 | iter: match self.nodes.get(&a) { | |
351 | Some(neigh) => neigh.iter(), | |
352 | None => [].iter(), | |
353 | }, | |
f035d41b XL |
354 | start_node: a, |
355 | dir, | |
f9f354fc XL |
356 | ty: self.ty, |
357 | } | |
358 | } | |
359 | ||
360 | /// Return an iterator of target nodes with an edge starting from `a`, | |
361 | /// paired with their respective edge weights. | |
362 | /// | |
363 | /// - `Directed`: Outgoing edges from `a`. | |
364 | /// - `Undirected`: All edges from or to `a`. | |
365 | /// | |
366 | /// Produces an empty iterator if the node doesn't exist.<br> | |
367 | /// Iterator element type is `(N, &E)`. | |
368 | pub fn edges(&self, from: N) -> Edges<N, E, Ty> { | |
369 | Edges { | |
f035d41b | 370 | from, |
f9f354fc XL |
371 | iter: self.neighbors(from), |
372 | edges: &self.edges, | |
373 | } | |
374 | } | |
375 | ||
376 | /// Return a reference to the edge weight connecting `a` with `b`, or | |
377 | /// `None` if the edge does not exist in the graph. | |
378 | pub fn edge_weight(&self, a: N, b: N) -> Option<&E> { | |
379 | self.edges.get(&Self::edge_key(a, b)) | |
380 | } | |
381 | ||
382 | /// Return a mutable reference to the edge weight connecting `a` with `b`, or | |
383 | /// `None` if the edge does not exist in the graph. | |
384 | pub fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E> { | |
385 | self.edges.get_mut(&Self::edge_key(a, b)) | |
386 | } | |
387 | ||
388 | /// Return an iterator over all edges of the graph with their weight in arbitrary order. | |
389 | /// | |
390 | /// Iterator element type is `(N, N, &E)` | |
391 | pub fn all_edges(&self) -> AllEdges<N, E, Ty> { | |
392 | AllEdges { | |
393 | inner: self.edges.iter(), | |
394 | ty: self.ty, | |
395 | } | |
396 | } | |
397 | ||
398 | /// Return an iterator over all edges of the graph in arbitrary order, with a mutable reference | |
399 | /// to their weight. | |
400 | /// | |
401 | /// Iterator element type is `(N, N, &mut E)` | |
402 | pub fn all_edges_mut(&mut self) -> AllEdgesMut<N, E, Ty> { | |
403 | AllEdgesMut { | |
404 | inner: self.edges.iter_mut(), | |
405 | ty: self.ty, | |
406 | } | |
407 | } | |
408 | ||
409 | /// Return a `Graph` that corresponds to this `GraphMap`. | |
410 | /// | |
411 | /// 1. Note that node and edge indices in the `Graph` have nothing in common | |
412 | /// with the `GraphMap`s node weights `N`. The node weights `N` are used as | |
413 | /// node weights in the resulting `Graph`, too. | |
414 | /// 2. Note that the index type is user-chosen. | |
415 | /// | |
416 | /// Computes in **O(|V| + |E|)** time (average). | |
417 | /// | |
418 | /// **Panics** if the number of nodes or edges does not fit with | |
419 | /// the resulting graph's index type. | |
420 | pub fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix> | |
f035d41b XL |
421 | where |
422 | Ix: crate::graph::IndexType, | |
f9f354fc XL |
423 | { |
424 | // assuming two successive iterations of the same hashmap produce the same order | |
425 | let mut gr = Graph::with_capacity(self.node_count(), self.edge_count()); | |
426 | for (&node, _) in &self.nodes { | |
427 | gr.add_node(node); | |
428 | } | |
429 | for ((a, b), edge_weight) in self.edges { | |
430 | let (ai, _, _) = self.nodes.get_full(&a).unwrap(); | |
431 | let (bi, _, _) = self.nodes.get_full(&b).unwrap(); | |
432 | gr.add_edge(node_index(ai), node_index(bi), edge_weight); | |
433 | } | |
434 | gr | |
435 | } | |
436 | } | |
437 | ||
438 | /// Create a new `GraphMap` from an iterable of edges. | |
439 | impl<N, E, Ty, Item> FromIterator<Item> for GraphMap<N, E, Ty> | |
f035d41b XL |
440 | where |
441 | Item: IntoWeightedEdge<E, NodeId = N>, | |
442 | N: NodeTrait, | |
443 | Ty: EdgeType, | |
f9f354fc XL |
444 | { |
445 | fn from_iter<I>(iterable: I) -> Self | |
f035d41b XL |
446 | where |
447 | I: IntoIterator<Item = Item>, | |
f9f354fc XL |
448 | { |
449 | let iter = iterable.into_iter(); | |
450 | let (low, _) = iter.size_hint(); | |
451 | let mut g = Self::with_capacity(0, low); | |
452 | g.extend(iter); | |
453 | g | |
454 | } | |
455 | } | |
456 | ||
457 | /// Extend the graph from an iterable of edges. | |
458 | /// | |
459 | /// Nodes are inserted automatically to match the edges. | |
460 | impl<N, E, Ty, Item> Extend<Item> for GraphMap<N, E, Ty> | |
f035d41b XL |
461 | where |
462 | Item: IntoWeightedEdge<E, NodeId = N>, | |
463 | N: NodeTrait, | |
464 | Ty: EdgeType, | |
f9f354fc XL |
465 | { |
466 | fn extend<I>(&mut self, iterable: I) | |
f035d41b XL |
467 | where |
468 | I: IntoIterator<Item = Item>, | |
f9f354fc XL |
469 | { |
470 | let iter = iterable.into_iter(); | |
471 | let (low, _) = iter.size_hint(); | |
472 | self.edges.reserve(low); | |
473 | ||
474 | for elt in iter { | |
475 | let (source, target, weight) = elt.into_weighted_edge(); | |
476 | self.add_edge(source, target, weight); | |
477 | } | |
478 | } | |
479 | } | |
480 | ||
481 | macro_rules! iterator_wrap { | |
482 | ($name: ident <$($typarm:tt),*> where { $($bounds: tt)* } | |
483 | item: $item: ty, | |
484 | iter: $iter: ty, | |
485 | ) => ( | |
486 | pub struct $name <$($typarm),*> where $($bounds)* { | |
487 | iter: $iter, | |
488 | } | |
489 | impl<$($typarm),*> Iterator for $name <$($typarm),*> | |
490 | where $($bounds)* | |
491 | { | |
492 | type Item = $item; | |
493 | #[inline] | |
494 | fn next(&mut self) -> Option<Self::Item> { | |
495 | self.iter.next() | |
496 | } | |
497 | ||
498 | #[inline] | |
499 | fn size_hint(&self) -> (usize, Option<usize>) { | |
500 | self.iter.size_hint() | |
501 | } | |
502 | } | |
503 | ); | |
504 | } | |
505 | ||
506 | iterator_wrap! { | |
507 | Nodes <'a, N> where { N: 'a + NodeTrait } | |
508 | item: N, | |
509 | iter: Cloned<Keys<'a, N, Vec<(N, CompactDirection)>>>, | |
510 | } | |
511 | ||
512 | pub struct Neighbors<'a, N, Ty = Undirected> | |
f035d41b XL |
513 | where |
514 | N: 'a, | |
515 | Ty: EdgeType, | |
f9f354fc XL |
516 | { |
517 | iter: Iter<'a, (N, CompactDirection)>, | |
518 | ty: PhantomData<Ty>, | |
519 | } | |
520 | ||
521 | impl<'a, N, Ty> Iterator for Neighbors<'a, N, Ty> | |
f035d41b XL |
522 | where |
523 | N: NodeTrait, | |
524 | Ty: EdgeType, | |
f9f354fc XL |
525 | { |
526 | type Item = N; | |
527 | fn next(&mut self) -> Option<N> { | |
528 | if Ty::is_directed() { | |
529 | (&mut self.iter) | |
f035d41b | 530 | .filter_map(|&(n, dir)| if dir == Outgoing { Some(n) } else { None }) |
f9f354fc XL |
531 | .next() |
532 | } else { | |
533 | self.iter.next().map(|&(n, _)| n) | |
534 | } | |
535 | } | |
536 | } | |
537 | ||
538 | pub struct NeighborsDirected<'a, N, Ty> | |
f035d41b XL |
539 | where |
540 | N: 'a, | |
541 | Ty: EdgeType, | |
f9f354fc XL |
542 | { |
543 | iter: Iter<'a, (N, CompactDirection)>, | |
f035d41b | 544 | start_node: N, |
f9f354fc XL |
545 | dir: Direction, |
546 | ty: PhantomData<Ty>, | |
547 | } | |
548 | ||
549 | impl<'a, N, Ty> Iterator for NeighborsDirected<'a, N, Ty> | |
f035d41b XL |
550 | where |
551 | N: NodeTrait, | |
552 | Ty: EdgeType, | |
f9f354fc XL |
553 | { |
554 | type Item = N; | |
555 | fn next(&mut self) -> Option<N> { | |
556 | if Ty::is_directed() { | |
557 | let self_dir = self.dir; | |
f035d41b | 558 | let start_node = self.start_node; |
f9f354fc | 559 | (&mut self.iter) |
f035d41b XL |
560 | .filter_map(move |&(n, dir)| { |
561 | if dir == self_dir || n == start_node { | |
562 | Some(n) | |
563 | } else { | |
564 | None | |
565 | } | |
566 | }) | |
f9f354fc XL |
567 | .next() |
568 | } else { | |
569 | self.iter.next().map(|&(n, _)| n) | |
570 | } | |
571 | } | |
572 | } | |
573 | ||
574 | pub struct Edges<'a, N, E: 'a, Ty> | |
f035d41b XL |
575 | where |
576 | N: 'a + NodeTrait, | |
577 | Ty: EdgeType, | |
f9f354fc XL |
578 | { |
579 | from: N, | |
f035d41b | 580 | edges: &'a IndexMap<(N, N), E>, |
f9f354fc XL |
581 | iter: Neighbors<'a, N, Ty>, |
582 | } | |
583 | ||
584 | impl<'a, N, E, Ty> Iterator for Edges<'a, N, E, Ty> | |
f035d41b XL |
585 | where |
586 | N: 'a + NodeTrait, | |
587 | E: 'a, | |
588 | Ty: EdgeType, | |
f9f354fc XL |
589 | { |
590 | type Item = (N, N, &'a E); | |
591 | fn next(&mut self) -> Option<Self::Item> { | |
592 | match self.iter.next() { | |
593 | None => None, | |
594 | Some(b) => { | |
595 | let a = self.from; | |
596 | match self.edges.get(&GraphMap::<N, E, Ty>::edge_key(a, b)) { | |
597 | None => unreachable!(), | |
f035d41b | 598 | Some(edge) => Some((a, b, edge)), |
f9f354fc XL |
599 | } |
600 | } | |
601 | } | |
602 | } | |
603 | } | |
604 | ||
605 | impl<'a, N: 'a, E: 'a, Ty> IntoEdgeReferences for &'a GraphMap<N, E, Ty> | |
f035d41b XL |
606 | where |
607 | N: NodeTrait, | |
608 | Ty: EdgeType, | |
f9f354fc XL |
609 | { |
610 | type EdgeRef = (N, N, &'a E); | |
611 | type EdgeReferences = AllEdges<'a, N, E, Ty>; | |
612 | fn edge_references(self) -> Self::EdgeReferences { | |
613 | self.all_edges() | |
614 | } | |
615 | } | |
616 | ||
f035d41b XL |
617 | pub struct AllEdges<'a, N, E: 'a, Ty> |
618 | where | |
619 | N: 'a + NodeTrait, | |
620 | { | |
621 | inner: IndexMapIter<'a, (N, N), E>, | |
f9f354fc XL |
622 | ty: PhantomData<Ty>, |
623 | } | |
624 | ||
625 | impl<'a, N, E, Ty> Iterator for AllEdges<'a, N, E, Ty> | |
f035d41b XL |
626 | where |
627 | N: 'a + NodeTrait, | |
628 | E: 'a, | |
629 | Ty: EdgeType, | |
f9f354fc XL |
630 | { |
631 | type Item = (N, N, &'a E); | |
f035d41b | 632 | fn next(&mut self) -> Option<Self::Item> { |
f9f354fc XL |
633 | match self.inner.next() { |
634 | None => None, | |
f035d41b | 635 | Some((&(a, b), v)) => Some((a, b, v)), |
f9f354fc XL |
636 | } |
637 | } | |
638 | ||
639 | fn size_hint(&self) -> (usize, Option<usize>) { | |
640 | self.inner.size_hint() | |
641 | } | |
642 | ||
643 | fn count(self) -> usize { | |
644 | self.inner.count() | |
645 | } | |
646 | ||
647 | fn nth(&mut self, n: usize) -> Option<Self::Item> { | |
f035d41b XL |
648 | self.inner |
649 | .nth(n) | |
650 | .map(|(&(n1, n2), weight)| (n1, n2, weight)) | |
f9f354fc XL |
651 | } |
652 | ||
653 | fn last(self) -> Option<Self::Item> { | |
f035d41b XL |
654 | self.inner |
655 | .last() | |
656 | .map(|(&(n1, n2), weight)| (n1, n2, weight)) | |
f9f354fc XL |
657 | } |
658 | } | |
659 | ||
660 | impl<'a, N, E, Ty> DoubleEndedIterator for AllEdges<'a, N, E, Ty> | |
f035d41b XL |
661 | where |
662 | N: 'a + NodeTrait, | |
663 | E: 'a, | |
664 | Ty: EdgeType, | |
f9f354fc XL |
665 | { |
666 | fn next_back(&mut self) -> Option<Self::Item> { | |
f035d41b XL |
667 | self.inner |
668 | .next_back() | |
669 | .map(|(&(n1, n2), weight)| (n1, n2, weight)) | |
f9f354fc XL |
670 | } |
671 | } | |
672 | ||
f035d41b XL |
673 | pub struct AllEdgesMut<'a, N, E: 'a, Ty> |
674 | where | |
675 | N: 'a + NodeTrait, | |
676 | { | |
677 | inner: IndexMapIterMut<'a, (N, N), E>, | |
f9f354fc XL |
678 | ty: PhantomData<Ty>, |
679 | } | |
680 | ||
681 | impl<'a, N, E, Ty> Iterator for AllEdgesMut<'a, N, E, Ty> | |
f035d41b XL |
682 | where |
683 | N: 'a + NodeTrait, | |
684 | E: 'a, | |
685 | Ty: EdgeType, | |
f9f354fc XL |
686 | { |
687 | type Item = (N, N, &'a mut E); | |
688 | fn next(&mut self) -> Option<Self::Item> { | |
f035d41b XL |
689 | self.inner |
690 | .next() | |
691 | .map(|(&(n1, n2), weight)| (n1, n2, weight)) | |
f9f354fc XL |
692 | } |
693 | ||
694 | fn size_hint(&self) -> (usize, Option<usize>) { | |
695 | self.inner.size_hint() | |
696 | } | |
697 | ||
698 | fn count(self) -> usize { | |
699 | self.inner.count() | |
700 | } | |
701 | ||
702 | fn nth(&mut self, n: usize) -> Option<Self::Item> { | |
f035d41b XL |
703 | self.inner |
704 | .nth(n) | |
705 | .map(|(&(n1, n2), weight)| (n1, n2, weight)) | |
f9f354fc XL |
706 | } |
707 | ||
708 | fn last(self) -> Option<Self::Item> { | |
f035d41b XL |
709 | self.inner |
710 | .last() | |
711 | .map(|(&(n1, n2), weight)| (n1, n2, weight)) | |
f9f354fc XL |
712 | } |
713 | } | |
714 | ||
715 | impl<'a, N, E, Ty> DoubleEndedIterator for AllEdgesMut<'a, N, E, Ty> | |
f035d41b XL |
716 | where |
717 | N: 'a + NodeTrait, | |
718 | E: 'a, | |
719 | Ty: EdgeType, | |
f9f354fc XL |
720 | { |
721 | fn next_back(&mut self) -> Option<Self::Item> { | |
f035d41b XL |
722 | self.inner |
723 | .next_back() | |
724 | .map(|(&(n1, n2), weight)| (n1, n2, weight)) | |
f9f354fc XL |
725 | } |
726 | } | |
727 | ||
728 | impl<'a, N: 'a, E: 'a, Ty> IntoEdges for &'a GraphMap<N, E, Ty> | |
f035d41b XL |
729 | where |
730 | N: NodeTrait, | |
731 | Ty: EdgeType, | |
f9f354fc XL |
732 | { |
733 | type Edges = Edges<'a, N, E, Ty>; | |
734 | fn edges(self, a: Self::NodeId) -> Self::Edges { | |
735 | self.edges(a) | |
736 | } | |
737 | } | |
738 | ||
f9f354fc XL |
739 | /// Index `GraphMap` by node pairs to access edge weights. |
740 | impl<N, E, Ty> Index<(N, N)> for GraphMap<N, E, Ty> | |
f035d41b XL |
741 | where |
742 | N: NodeTrait, | |
743 | Ty: EdgeType, | |
f9f354fc XL |
744 | { |
745 | type Output = E; | |
f035d41b | 746 | fn index(&self, index: (N, N)) -> &E { |
f9f354fc | 747 | let index = Self::edge_key(index.0, index.1); |
f035d41b XL |
748 | self.edge_weight(index.0, index.1) |
749 | .expect("GraphMap::index: no such edge") | |
f9f354fc XL |
750 | } |
751 | } | |
752 | ||
753 | /// Index `GraphMap` by node pairs to access edge weights. | |
754 | impl<N, E, Ty> IndexMut<(N, N)> for GraphMap<N, E, Ty> | |
f035d41b XL |
755 | where |
756 | N: NodeTrait, | |
757 | Ty: EdgeType, | |
f9f354fc XL |
758 | { |
759 | fn index_mut(&mut self, index: (N, N)) -> &mut E { | |
760 | let index = Self::edge_key(index.0, index.1); | |
f035d41b XL |
761 | self.edge_weight_mut(index.0, index.1) |
762 | .expect("GraphMap::index: no such edge") | |
f9f354fc XL |
763 | } |
764 | } | |
765 | ||
766 | /// Create a new empty `GraphMap`. | |
767 | impl<N, E, Ty> Default for GraphMap<N, E, Ty> | |
f035d41b XL |
768 | where |
769 | N: NodeTrait, | |
770 | Ty: EdgeType, | |
f9f354fc | 771 | { |
f035d41b XL |
772 | fn default() -> Self { |
773 | GraphMap::with_capacity(0, 0) | |
774 | } | |
f9f354fc XL |
775 | } |
776 | ||
777 | /// A reference that is hashed and compared by its pointer value. | |
778 | /// | |
779 | /// `Ptr` is used for certain configurations of `GraphMap`, | |
780 | /// in particular in the combination where the node type for | |
781 | /// `GraphMap` is something of type for example `Ptr(&Cell<T>)`, | |
782 | /// with the `Cell<T>` being `TypedArena` allocated. | |
783 | pub struct Ptr<'b, T: 'b>(pub &'b T); | |
784 | ||
785 | impl<'b, T> Copy for Ptr<'b, T> {} | |
f035d41b XL |
786 | impl<'b, T> Clone for Ptr<'b, T> { |
787 | fn clone(&self) -> Self { | |
788 | *self | |
789 | } | |
f9f354fc XL |
790 | } |
791 | ||
f9f354fc XL |
792 | fn ptr_eq<T>(a: *const T, b: *const T) -> bool { |
793 | a == b | |
794 | } | |
795 | ||
f035d41b | 796 | impl<'b, T> PartialEq for Ptr<'b, T> { |
f9f354fc XL |
797 | /// Ptr compares by pointer equality, i.e if they point to the same value |
798 | fn eq(&self, other: &Ptr<'b, T>) -> bool { | |
799 | ptr_eq(self.0, other.0) | |
800 | } | |
801 | } | |
802 | ||
f035d41b | 803 | impl<'b, T> PartialOrd for Ptr<'b, T> { |
f9f354fc XL |
804 | fn partial_cmp(&self, other: &Ptr<'b, T>) -> Option<Ordering> { |
805 | Some(self.cmp(other)) | |
806 | } | |
807 | } | |
808 | ||
f035d41b | 809 | impl<'b, T> Ord for Ptr<'b, T> { |
f9f354fc XL |
810 | /// Ptr is ordered by pointer value, i.e. an arbitrary but stable and total order. |
811 | fn cmp(&self, other: &Ptr<'b, T>) -> Ordering { | |
812 | let a: *const T = self.0; | |
813 | let b: *const T = other.0; | |
814 | a.cmp(&b) | |
815 | } | |
816 | } | |
817 | ||
818 | impl<'b, T> Deref for Ptr<'b, T> { | |
819 | type Target = T; | |
820 | fn deref(&self) -> &T { | |
821 | self.0 | |
822 | } | |
823 | } | |
824 | ||
825 | impl<'b, T> Eq for Ptr<'b, T> {} | |
826 | ||
f035d41b XL |
827 | impl<'b, T> Hash for Ptr<'b, T> { |
828 | fn hash<H: hash::Hasher>(&self, st: &mut H) { | |
f9f354fc XL |
829 | let ptr = (self.0) as *const T; |
830 | ptr.hash(st) | |
831 | } | |
832 | } | |
833 | ||
834 | impl<'b, T: fmt::Debug> fmt::Debug for Ptr<'b, T> { | |
835 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
836 | self.0.fmt(f) | |
837 | } | |
838 | } | |
839 | ||
840 | impl<'a, N, E: 'a, Ty> IntoNodeIdentifiers for &'a GraphMap<N, E, Ty> | |
f035d41b XL |
841 | where |
842 | N: NodeTrait, | |
843 | Ty: EdgeType, | |
f9f354fc XL |
844 | { |
845 | type NodeIdentifiers = NodeIdentifiers<'a, N, E, Ty>; | |
846 | ||
847 | fn node_identifiers(self) -> Self::NodeIdentifiers { | |
848 | NodeIdentifiers { | |
849 | iter: self.nodes.iter(), | |
850 | ty: self.ty, | |
851 | edge_ty: PhantomData, | |
852 | } | |
853 | } | |
854 | } | |
855 | ||
856 | impl<N, E, Ty> NodeCount for GraphMap<N, E, Ty> | |
f035d41b XL |
857 | where |
858 | N: NodeTrait, | |
859 | Ty: EdgeType, | |
f9f354fc XL |
860 | { |
861 | fn node_count(&self) -> usize { | |
862 | (*self).node_count() | |
863 | } | |
864 | } | |
865 | ||
f035d41b XL |
866 | pub struct NodeIdentifiers<'a, N, E: 'a, Ty> |
867 | where | |
868 | N: 'a + NodeTrait, | |
869 | { | |
870 | iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>, | |
f9f354fc XL |
871 | ty: PhantomData<Ty>, |
872 | edge_ty: PhantomData<E>, | |
873 | } | |
874 | ||
875 | impl<'a, N, E, Ty> Iterator for NodeIdentifiers<'a, N, E, Ty> | |
f035d41b XL |
876 | where |
877 | N: 'a + NodeTrait, | |
878 | E: 'a, | |
879 | Ty: EdgeType, | |
f9f354fc XL |
880 | { |
881 | type Item = N; | |
f035d41b | 882 | fn next(&mut self) -> Option<Self::Item> { |
f9f354fc XL |
883 | self.iter.next().map(|(&n, _)| n) |
884 | } | |
885 | } | |
886 | ||
887 | impl<'a, N, E, Ty> IntoNodeReferences for &'a GraphMap<N, E, Ty> | |
f035d41b XL |
888 | where |
889 | N: NodeTrait, | |
890 | Ty: EdgeType, | |
f9f354fc XL |
891 | { |
892 | type NodeRef = (N, &'a N); | |
893 | type NodeReferences = NodeReferences<'a, N, E, Ty>; | |
894 | fn node_references(self) -> Self::NodeReferences { | |
895 | NodeReferences { | |
896 | iter: self.nodes.iter(), | |
897 | ty: self.ty, | |
898 | edge_ty: PhantomData, | |
899 | } | |
900 | } | |
901 | } | |
902 | ||
f035d41b XL |
903 | pub struct NodeReferences<'a, N, E: 'a, Ty> |
904 | where | |
905 | N: 'a + NodeTrait, | |
906 | { | |
907 | iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>, | |
f9f354fc XL |
908 | ty: PhantomData<Ty>, |
909 | edge_ty: PhantomData<E>, | |
910 | } | |
911 | ||
912 | impl<'a, N, E, Ty> Iterator for NodeReferences<'a, N, E, Ty> | |
f035d41b XL |
913 | where |
914 | N: 'a + NodeTrait, | |
915 | E: 'a, | |
916 | Ty: EdgeType, | |
f9f354fc XL |
917 | { |
918 | type Item = (N, &'a N); | |
f035d41b | 919 | fn next(&mut self) -> Option<Self::Item> { |
f9f354fc XL |
920 | self.iter.next().map(|(n, _)| (*n, n)) |
921 | } | |
922 | } | |
923 | ||
924 | impl<N, E, Ty> NodeIndexable for GraphMap<N, E, Ty> | |
f035d41b XL |
925 | where |
926 | N: NodeTrait, | |
927 | Ty: EdgeType, | |
f9f354fc | 928 | { |
f035d41b XL |
929 | fn node_bound(&self) -> usize { |
930 | self.node_count() | |
931 | } | |
f9f354fc XL |
932 | fn to_index(&self, ix: Self::NodeId) -> usize { |
933 | let (i, _, _) = self.nodes.get_full(&ix).unwrap(); | |
934 | i | |
935 | } | |
936 | fn from_index(&self, ix: usize) -> Self::NodeId { | |
937 | let (&key, _) = self.nodes.get_index(ix).unwrap(); | |
938 | key | |
939 | } | |
940 | } | |
941 | ||
942 | impl<N, E, Ty> NodeCompactIndexable for GraphMap<N, E, Ty> | |
f035d41b XL |
943 | where |
944 | N: NodeTrait, | |
945 | Ty: EdgeType, | |
f9f354fc XL |
946 | { |
947 | } |