avian3d/data_structures/
graph.rs

1//! A stripped down version of petgraph's `UnGraph`.
2//!
3//! - Index types always use `u32`.
4//! - Edge iteration order after serialization/deserialization is preserved.
5//! - Fewer iterators and helpers, and a few new ones.
6
7use core::cmp::max;
8use core::ops::{Index, IndexMut};
9
10use derive_more::derive::From;
11
12/// A node identifier for a graph structure.
13#[derive(Clone, Copy, Debug, Default, PartialEq, PartialOrd, Eq, Ord, Hash, From)]
14#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
15pub struct NodeIndex(pub u32);
16
17impl NodeIndex {
18    /// A special index used to denote the final node,
19    /// for example at the end of an adjacency list.
20    ///
21    /// Equivalent to `NodeIndex(u32::MAX)`.
22    pub const END: NodeIndex = NodeIndex(u32::MAX);
23
24    /// Returns the inner `u32` value as a `usize`.
25    pub fn index(self) -> usize {
26        self.0 as usize
27    }
28
29    /// Returns `true` if this is the special `END` index.
30    pub fn is_end(self) -> bool {
31        self == NodeIndex::END
32    }
33}
34
35/// An edge identifier for a graph structure.
36#[derive(Clone, Copy, Debug, Default, PartialEq, PartialOrd, Eq, Ord, Hash, From)]
37#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
38pub struct EdgeIndex(pub u32);
39
40impl EdgeIndex {
41    /// A special index used to denote the abscence of an edge,
42    /// for example at the end of an adjacency list.
43    ///
44    /// Equivalent to `EdgeIndex(u32::MAX)`.
45    pub const END: EdgeIndex = EdgeIndex(u32::MAX);
46
47    /// Returns the inner `u32` value as a `usize`.
48    pub fn index(self) -> usize {
49        self.0 as usize
50    }
51
52    /// Returns `true` if this is the special `END` index.
53    pub fn is_end(self) -> bool {
54        self == EdgeIndex::END
55    }
56}
57
58/// The direction of a graph edge.
59#[derive(Clone, Copy, Debug, PartialEq, PartialOrd, Ord, Eq, Hash)]
60#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
61#[repr(usize)]
62pub enum EdgeDirection {
63    /// An `Outgoing` edge is an outward edge *from* the current node.
64    Outgoing = 0,
65    /// An `Incoming` edge is an inbound edge *to* the current node.
66    Incoming = 1,
67}
68
69impl EdgeDirection {
70    /// The two possible directions for an edge.
71    pub const ALL: [EdgeDirection; 2] = [EdgeDirection::Outgoing, EdgeDirection::Incoming];
72}
73
74/// The node type for a graph structure.
75#[derive(Clone, Copy, Debug)]
76#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
77pub struct Node<N> {
78    /// Associated node data.
79    pub weight: N,
80    /// Next edge in outgoing and incoming edge lists.
81    pub(super) next: [EdgeIndex; 2],
82}
83
84/// The edge type for a graph structure.
85#[derive(Clone, Copy, Debug)]
86#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
87pub struct Edge<E> {
88    /// Associated edge data.
89    pub weight: E,
90    /// Next edge in outgoing and incoming edge lists.
91    pub(super) next: [EdgeIndex; 2],
92    /// Start and End node index
93    pub(super) node: [NodeIndex; 2],
94}
95
96impl<E> Edge<E> {
97    /// Return the source node index.
98    pub fn source(&self) -> NodeIndex {
99        self.node[0]
100    }
101
102    /// Return the target node index.
103    pub fn target(&self) -> NodeIndex {
104        self.node[1]
105    }
106}
107
108/// A graph with undirected edges.
109///
110/// The graph can invalidate node or edge indices when items are removed.
111/// If you need stable indices, use [`StableUnGraph`](super::stable_graph::StableUnGraph).
112#[derive(Clone, Debug)]
113#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
114pub struct UnGraph<N, E> {
115    pub(super) nodes: Vec<Node<N>>,
116    pub(super) edges: Vec<Edge<E>>,
117}
118
119impl<N, E> Default for UnGraph<N, E> {
120    fn default() -> Self {
121        Self {
122            nodes: Vec::new(),
123            edges: Vec::new(),
124        }
125    }
126}
127
128pub(super) enum Pair<T> {
129    Both(T, T),
130    One(T),
131    None,
132}
133
134/// Get mutable references at index `a` and `b`.
135pub(super) fn index_twice<T>(arr: &mut [T], a: usize, b: usize) -> Pair<&mut T> {
136    if max(a, b) >= arr.len() {
137        Pair::None
138    } else if a == b {
139        Pair::One(&mut arr[max(a, b)])
140    } else {
141        // safe because `a` and `b` are in bounds and distinct.
142        unsafe {
143            let ar = &mut *(arr.get_unchecked_mut(a) as *mut _);
144            let br = &mut *(arr.get_unchecked_mut(b) as *mut _);
145            Pair::Both(ar, br)
146        }
147    }
148}
149
150impl<N, E> UnGraph<N, E> {
151    /// Creates a new [`UnGraph`] with estimated capacity.
152    pub fn with_capacity(nodes: usize, edges: usize) -> Self {
153        UnGraph {
154            nodes: Vec::with_capacity(nodes),
155            edges: Vec::with_capacity(edges),
156        }
157    }
158
159    /// Returns the number of nodes in the graph.
160    ///
161    /// Computes in **O(1)** time.
162    pub fn node_count(&self) -> usize {
163        self.nodes.len()
164    }
165
166    /// Returns the number of edges in the graph.
167    ///
168    /// Computes in **O(1)** time.
169    pub fn edge_count(&self) -> usize {
170        self.edges.len()
171    }
172
173    /// Adds a node (also called vertex) with associated data `weight` to the graph.
174    ///
175    /// Computes in **O(1)** time.
176    ///
177    /// Returns the index of the new node.
178    ///
179    /// # Panics
180    ///
181    /// Panics if the graph is at the maximum number of nodes.
182    pub fn add_node(&mut self, weight: N) -> NodeIndex {
183        let node = Node {
184            weight,
185            next: [EdgeIndex::END, EdgeIndex::END],
186        };
187        assert!(self.nodes.len() as u32 != u32::MAX);
188        let node_idx = NodeIndex(self.nodes.len() as u32);
189        self.nodes.push(node);
190        node_idx
191    }
192
193    /// Accesses the weight for node `a`.
194    ///
195    /// Also available with indexing syntax: `&graph[a]`.
196    pub fn node_weight(&self, a: NodeIndex) -> Option<&N> {
197        self.nodes.get(a.index()).map(|n| &n.weight)
198    }
199
200    /// Adds an edge from `a` to `b` to the graph, with its associated
201    /// data `weight`.
202    ///
203    /// Returns the index of the new edge.
204    ///
205    /// Computes in **O(1)** time.
206    ///
207    /// **Note:** `UnGraph` allows adding parallel (“duplicate”) edges. If you want
208    /// to avoid this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead.
209    ///
210    /// # Panics
211    ///
212    /// Panics if any of the nodes don't exist or the graph is at the maximum number of edges.
213    pub fn add_edge(&mut self, a: NodeIndex, b: NodeIndex, weight: E) -> EdgeIndex {
214        assert!(self.edges.len() as u32 != u32::MAX);
215        let edge_idx = EdgeIndex(self.edges.len() as u32);
216        let mut edge = Edge {
217            weight,
218            node: [a, b],
219            next: [EdgeIndex::END; 2],
220        };
221        match index_twice(&mut self.nodes, a.index(), b.index()) {
222            Pair::None => panic!("`UnGraph::add_edge`: node indices out of bounds"),
223            Pair::One(an) => {
224                edge.next = an.next;
225                an.next[0] = edge_idx;
226                an.next[1] = edge_idx;
227            }
228            Pair::Both(an, bn) => {
229                // `a` and `b` are different indices
230                edge.next = [an.next[0], bn.next[1]];
231                an.next[0] = edge_idx;
232                bn.next[1] = edge_idx;
233            }
234        }
235        self.edges.push(edge);
236        edge_idx
237    }
238
239    /// Adds or updates an edge from `a` to `b`.
240    /// If the edge already exists, its weight is updated.
241    ///
242    /// Returns the index of the affected edge.
243    ///
244    /// Computes in **O(e')** time, where **e'** is the number of edges
245    /// connected to `a` (and `b`, if the graph edges are undirected).
246    ///
247    /// # Panics
248    ///
249    /// Panics if any of the nodes doesn't exist.
250    pub fn update_edge(&mut self, a: NodeIndex, b: NodeIndex, weight: E) -> EdgeIndex {
251        if let Some(ix) = self.find_edge(a, b)
252            && let Some(ed) = self.edge_weight_mut(ix)
253        {
254            *ed = weight;
255            return ix;
256        }
257        self.add_edge(a, b, weight)
258    }
259
260    /// Accesses the weight for edge `e`.
261    ///
262    /// Also available with indexing syntax: `&graph[e]`.
263    pub fn edge_weight(&self, e: EdgeIndex) -> Option<&E> {
264        self.edges.get(e.index()).map(|e| &e.weight)
265    }
266
267    /// Accesses the weight for edge `e` mutably.
268    ///
269    /// Also available with indexing syntax: `&mut graph[e]`.
270    pub fn edge_weight_mut(&mut self, e: EdgeIndex) -> Option<&mut E> {
271        self.edges.get_mut(e.index()).map(|e| &mut e.weight)
272    }
273
274    /// Accesses the source and target nodes for `e`.
275    pub fn edge_endpoints(&self, e: EdgeIndex) -> Option<(NodeIndex, NodeIndex)> {
276        self.edges
277            .get(e.index())
278            .map(|ed| (ed.source(), ed.target()))
279    }
280
281    /// Removes `a` from the graph if it exists, calling `edge_callback` for each of its edges,
282    /// and returns its weight. If it doesn't exist in the graph, returns `None`.
283    ///
284    /// Apart from `a`, this invalidates the last node index in the graph
285    /// (that node will adopt the removed node index). Edge indices are
286    /// invalidated as they would be following the removal of each edge
287    /// with an endpoint in `a`.
288    ///
289    /// Computes in **O(e')** time, where **e'** is the number of affected
290    /// edges, including *n* calls to [`remove_edge`](Self::remove_edge),
291    /// where *n* is the number of edges with an endpoint in `a`,
292    /// and including the edges with an endpoint in the displaced node.
293    pub fn remove_node_with<F>(&mut self, a: NodeIndex, mut edge_callback: F) -> Option<N>
294    where
295        F: FnMut(E),
296    {
297        if a.index() >= self.nodes.len() {
298            return None;
299        }
300
301        for d in EdgeDirection::ALL {
302            let k = d as usize;
303
304            // Remove all edges from and to this node.
305            loop {
306                let next = self.nodes[a.index()].next[k];
307                if next == EdgeIndex::END {
308                    break;
309                }
310                let edge = self.remove_edge(next).expect("edge not found for removal");
311                edge_callback(edge);
312            }
313        }
314
315        // Use `swap_remove` -- only the swapped-in node is going to change
316        // `NodeIndex`, so we only have to walk its edges and update them.
317
318        let node = self.nodes.swap_remove(a.index());
319
320        // Find the edge lists of the node that had to relocate.
321        // It may be that no node had to relocate, then we are done already.
322        let swap_edges = match self.nodes.get(a.index()) {
323            None => return Some(node.weight),
324            Some(ed) => ed.next,
325        };
326
327        // The swapped element's old index
328        let old_index = NodeIndex(self.nodes.len() as u32);
329        let new_index = a;
330
331        // Adjust the starts of the out edges, and ends of the in edges.
332        for d in EdgeDirection::ALL {
333            let k = d as usize;
334            let mut edges = EdgesWalkerMut {
335                edges: &mut self.edges,
336                next: swap_edges[k],
337                dir: d,
338            };
339            while let Some(curedge) = edges.next_edge() {
340                debug_assert!(curedge.node[k] == old_index);
341                curedge.node[k] = new_index;
342            }
343        }
344        Some(node.weight)
345    }
346
347    /// For edge `e` with endpoints `edge_node`, replaces links to it
348    /// with links to `edge_next`.
349    pub(super) fn change_edge_links(
350        &mut self,
351        edge_node: [NodeIndex; 2],
352        e: EdgeIndex,
353        edge_next: [EdgeIndex; 2],
354    ) {
355        for d in EdgeDirection::ALL {
356            let k = d as usize;
357            let node = match self.nodes.get_mut(edge_node[k].index()) {
358                Some(r) => r,
359                None => {
360                    debug_assert!(
361                        false,
362                        "Edge's endpoint dir={:?} index={:?} not found",
363                        d, edge_node[k]
364                    );
365                    return;
366                }
367            };
368            let fst = node.next[k];
369            if fst == e {
370                node.next[k] = edge_next[k];
371            } else {
372                let mut edges = EdgesWalkerMut {
373                    edges: &mut self.edges,
374                    next: fst,
375                    dir: d,
376                };
377                while let Some(curedge) = edges.next_edge() {
378                    if curedge.next[k] == e {
379                        curedge.next[k] = edge_next[k];
380                        // The edge can only be present once in the list.
381                        break;
382                    }
383                }
384            }
385        }
386    }
387
388    /// Removes an edge and returns its edge weight, or `None` if it didn't exist.
389    ///
390    /// Apart from `e`, this invalidates the last edge index in the graph
391    /// (that edge will adopt the removed edge index).
392    ///
393    /// Computes in **O(e')** time, where **e'** is the size of four particular edge lists, for
394    /// the vertices of `e` and the vertices of another affected edge.
395    pub fn remove_edge(&mut self, e: EdgeIndex) -> Option<E> {
396        // Every edge is part of two lists, outgoing and incoming edges.
397        // Remove it from both.
398        let (edge_node, edge_next) = match self.edges.get(e.index()) {
399            None => return None,
400            Some(x) => (x.node, x.next),
401        };
402
403        // Remove the edge from its in and out lists by replacing it with
404        // a link to the next in the list.
405        self.change_edge_links(edge_node, e, edge_next);
406        self.remove_edge_adjust_indices(e)
407    }
408
409    fn remove_edge_adjust_indices(&mut self, e: EdgeIndex) -> Option<E> {
410        // `swap_remove` the edge -- only the removed edge
411        // and the edge swapped into place are affected and need updating
412        // indices.
413        let edge = self.edges.swap_remove(e.index());
414        let swap = match self.edges.get(e.index()) {
415            // No element needed to be swapped.
416            None => return Some(edge.weight),
417            Some(ed) => ed.node,
418        };
419        let swapped_e = EdgeIndex(self.edges.len() as u32);
420
421        // Update the edge lists by replacing links to the old index by references to the new
422        // edge index.
423        self.change_edge_links(swap, swapped_e, [e, e]);
424
425        Some(edge.weight)
426    }
427
428    /// Returns an iterator of all nodes with an edge connected to `a`.
429    ///
430    /// Produces an empty iterator if the node doesn't exist.
431    ///
432    /// The iterator element type is `NodeIndex`.
433    pub fn neighbors(&self, a: NodeIndex) -> Neighbors<'_, E> {
434        Neighbors {
435            skip_start: a,
436            edges: &self.edges,
437            next: match self.nodes.get(a.index()) {
438                None => [EdgeIndex::END, EdgeIndex::END],
439                Some(n) => n.next,
440            },
441        }
442    }
443
444    /// Returns an iterator of all edges connected to `a`.
445    ///
446    /// Produces an empty iterator if the node doesn't exist.
447    ///
448    /// The iterator element type is `EdgeReference<E>`.
449    pub fn edges(&self, a: NodeIndex) -> Edges<'_, E> {
450        Edges {
451            skip_start: a,
452            edges: &self.edges,
453            direction: EdgeDirection::Outgoing,
454            next: match self.nodes.get(a.index()) {
455                None => [EdgeIndex::END, EdgeIndex::END],
456                Some(n) => n.next,
457            },
458        }
459    }
460
461    /// Returns a mutable iterator of all edges connected to `a`.
462    ///
463    /// Produces an empty iterator if the node doesn't exist.
464    ///
465    /// The iterator element type is `EdgeReference<E>`.
466    pub fn edges_mut(&mut self, a: NodeIndex) -> EdgesMut<'_, N, E> {
467        let incoming_edge = self.first_edge(a, EdgeDirection::Incoming);
468        let outgoing_edge = self.first_edge(a, EdgeDirection::Outgoing);
469
470        EdgesMut {
471            graph: self,
472            incoming_edge,
473            outgoing_edge,
474        }
475    }
476
477    /// Returns an iterator over all edges between `a` and `b`.
478    ///
479    /// The iterator element type is `EdgeReference<E>`.
480    pub fn edges_between(&self, a: NodeIndex, b: NodeIndex) -> EdgesBetween<'_, E> {
481        EdgesBetween {
482            target_node: b,
483            edges: self.edges(a),
484        }
485    }
486
487    /// Looks up if there is an edge from `a` to `b`.
488    ///
489    /// Computes in **O(e')** time, where **e'** is the number of edges
490    /// connected to `a` (and `b`, if the graph edges are undirected).
491    pub fn contains_edge(&self, a: NodeIndex, b: NodeIndex) -> bool {
492        self.find_edge(a, b).is_some()
493    }
494
495    /// Looks up an edge from `a` to `b`.
496    ///
497    /// Computes in **O(e')** time, where **e'** is the number of edges
498    /// connected to `a` (and `b`, if the graph edges are undirected).
499    pub fn find_edge(&self, a: NodeIndex, b: NodeIndex) -> Option<EdgeIndex> {
500        self.find_edge_from_node(self.nodes.get(a.index())?, b)
501    }
502
503    pub(super) fn find_edge_from_node(&self, node: &Node<N>, b: NodeIndex) -> Option<EdgeIndex> {
504        for &d in &EdgeDirection::ALL {
505            let k = d as usize;
506            let mut edix = node.next[k];
507            while let Some(edge) = self.edges.get(edix.index()) {
508                if edge.node[1 - k] == b {
509                    return Some(edix);
510                }
511                edix = edge.next[k];
512            }
513        }
514        None
515    }
516
517    /// Returns an iterator yielding immutable access to edge weights for edges from or to `a`.
518    pub fn edge_weights(&self, a: NodeIndex) -> EdgeWeights<'_, E> {
519        EdgeWeights {
520            skip_start: a,
521            edges: &self.edges,
522            direction: EdgeDirection::Outgoing,
523            next: match self.nodes.get(a.index()) {
524                None => [EdgeIndex::END, EdgeIndex::END],
525                Some(n) => n.next,
526            },
527        }
528    }
529
530    /// Returns an iterator yielding mutable access to edge weights for edges from or to `a`.
531    pub fn edge_weights_mut(&mut self, a: NodeIndex) -> EdgeWeightsMut<'_, N, E> {
532        let incoming_edge = self.first_edge(a, EdgeDirection::Incoming);
533        let outgoing_edge = self.first_edge(a, EdgeDirection::Outgoing);
534
535        EdgeWeightsMut {
536            graph: self,
537            incoming_edge,
538            outgoing_edge,
539        }
540    }
541
542    /// Returns an iterator yielding immutable access to all edge weights.
543    ///
544    /// The order in which weights are yielded matches the order of their
545    /// edge indices.
546    pub fn all_edge_weights(&self) -> AllEdgeWeights<'_, E> {
547        AllEdgeWeights {
548            edges: self.edges.iter(),
549        }
550    }
551
552    /// Returns an iterator yielding mutable access to all edge weights.
553    ///
554    /// The order in which weights are yielded matches the order of their
555    /// edge indices.
556    pub fn all_edge_weights_mut(&mut self) -> AllEdgeWeightsMut<'_, E> {
557        AllEdgeWeightsMut {
558            edges: self.edges.iter_mut(),
559        }
560    }
561
562    /// Accesses the internal node array.
563    pub fn raw_nodes(&self) -> &[Node<N>] {
564        &self.nodes
565    }
566
567    /// Accesses the internal node array mutably.
568    pub fn raw_nodes_mut(&mut self) -> &mut [Node<N>] {
569        &mut self.nodes
570    }
571
572    /// Accesses the internal edge array.
573    pub fn raw_edges(&self) -> &[Edge<E>] {
574        &self.edges
575    }
576
577    /// Accesses the internal edge array mutably.
578    pub fn raw_edges_mut(&mut self) -> &mut [Edge<E>] {
579        &mut self.edges
580    }
581
582    /// Accessor for data structure internals: returns the first edge in the given direction.
583    pub fn first_edge(&self, a: NodeIndex, dir: EdgeDirection) -> Option<EdgeIndex> {
584        match self.nodes.get(a.index()) {
585            None => None,
586            Some(node) => {
587                let edix = node.next[dir as usize];
588                if edix == EdgeIndex::END {
589                    None
590                } else {
591                    Some(edix)
592                }
593            }
594        }
595    }
596
597    /// Accessor for data structure internals: returns the next edge for the given direction.
598    pub fn next_edge(&self, e: EdgeIndex, dir: EdgeDirection) -> Option<EdgeIndex> {
599        match self.edges.get(e.index()) {
600            None => None,
601            Some(node) => {
602                let edix = node.next[dir as usize];
603                if edix == EdgeIndex::END {
604                    None
605                } else {
606                    Some(edix)
607                }
608            }
609        }
610    }
611
612    /// Removes all nodes and edges.
613    pub fn clear(&mut self) {
614        self.nodes.clear();
615        self.edges.clear();
616    }
617
618    /// Removes all edges.
619    pub fn clear_edges(&mut self) {
620        self.edges.clear();
621        for node in &mut self.nodes {
622            node.next = [EdgeIndex::END, EdgeIndex::END];
623        }
624    }
625
626    /// Returns the current node capacity of the graph.
627    pub fn nodes_capacity(&self) -> usize {
628        self.nodes.capacity()
629    }
630
631    /// Returns the current edge capacity of the graph.
632    pub fn edges_capacity(&self) -> usize {
633        self.edges.capacity()
634    }
635
636    /// Reserves capacity for at least `additional` more nodes to be inserted in
637    /// the graph. Graph may reserve more space to avoid frequent reallocations.
638    ///
639    /// # Panics
640    ///
641    /// Panics if the new capacity overflows `usize`.
642    pub fn reserve_nodes(&mut self, additional: usize) {
643        self.nodes.reserve(additional);
644    }
645
646    /// Reserves capacity for at least `additional` more edges to be inserted in
647    /// the graph. Graph may reserve more space to avoid frequent reallocations.
648    ///
649    /// # Panics
650    ///
651    /// Panics if the new capacity overflows `usize`.
652    pub fn reserve_edges(&mut self, additional: usize) {
653        self.edges.reserve(additional);
654    }
655}
656
657/// An iterator over the neighbors of a node.
658///
659/// The iterator element type is `NodeIndex`.
660#[derive(Debug)]
661pub struct Neighbors<'a, E: 'a> {
662    /// The starting node to skip over.
663    skip_start: NodeIndex,
664
665    /// The edges to iterate over.
666    edges: &'a [Edge<E>],
667
668    /// The next edge to visit.
669    next: [EdgeIndex; 2],
670}
671
672impl<E> Iterator for Neighbors<'_, E> {
673    type Item = NodeIndex;
674
675    fn next(&mut self) -> Option<NodeIndex> {
676        // First any outgoing edges.
677        match self.edges.get(self.next[0].index()) {
678            None => {}
679            Some(edge) => {
680                self.next[0] = edge.next[0];
681                return Some(edge.node[1]);
682            }
683        }
684
685        // Then incoming edges.
686        // For an "undirected" iterator, make sure we don't double
687        // count self-loops by skipping them in the incoming list.
688        while let Some(edge) = self.edges.get(self.next[1].index()) {
689            self.next[1] = edge.next[1];
690            if edge.node[0] != self.skip_start {
691                return Some(edge.node[0]);
692            }
693        }
694        None
695    }
696}
697
698impl<E> Clone for Neighbors<'_, E> {
699    fn clone(&self) -> Self {
700        Neighbors {
701            skip_start: self.skip_start,
702            edges: self.edges,
703            next: self.next,
704        }
705    }
706}
707
708/// An iterator over edges from or to a node.
709pub struct Edges<'a, E: 'a> {
710    /// The starting node to skip over.
711    skip_start: NodeIndex,
712
713    /// The edges to iterate over.
714    edges: &'a [Edge<E>],
715
716    /// The next edge to visit.
717    next: [EdgeIndex; 2],
718
719    /// The direction of edges.
720    direction: EdgeDirection,
721}
722
723impl<'a, E> Iterator for Edges<'a, E> {
724    type Item = EdgeReference<'a, E>;
725
726    fn next(&mut self) -> Option<Self::Item> {
727        // Outgoing
728        let i = self.next[0].index();
729        if let Some(Edge {
730            node, weight, next, ..
731        }) = self.edges.get(i)
732        {
733            self.next[0] = next[0];
734            return Some(EdgeReference {
735                index: EdgeIndex(i as u32),
736                node: if self.direction == EdgeDirection::Incoming {
737                    swap_pair(*node)
738                } else {
739                    *node
740                },
741                weight,
742            });
743        }
744
745        // Incoming
746        while let Some(Edge { node, weight, next }) = self.edges.get(self.next[1].index()) {
747            let edge_index = self.next[1];
748            self.next[1] = next[1];
749
750            // In any of the "both" situations, self-loops would be iterated over twice.
751            // Skip them here.
752            if node[0] == self.skip_start {
753                continue;
754            }
755
756            return Some(EdgeReference {
757                index: edge_index,
758                node: if self.direction == EdgeDirection::Outgoing {
759                    swap_pair(*node)
760                } else {
761                    *node
762                },
763                weight,
764            });
765        }
766
767        None
768    }
769}
770
771impl<E> Clone for Edges<'_, E> {
772    fn clone(&self) -> Self {
773        Edges {
774            skip_start: self.skip_start,
775            edges: self.edges,
776            next: self.next,
777            direction: self.direction,
778        }
779    }
780}
781
782/// An iterator over mutable references to all edges from or to a node.
783pub struct EdgesMut<'a, N, E> {
784    graph: &'a mut UnGraph<N, E>,
785    incoming_edge: Option<EdgeIndex>,
786    outgoing_edge: Option<EdgeIndex>,
787}
788
789impl<'a, N: Copy, E> Iterator for EdgesMut<'a, N, E> {
790    type Item = EdgeMut<'a, E>;
791
792    #[inline]
793    fn next(&mut self) -> Option<EdgeMut<'a, E>> {
794        if let Some(edge) = self.incoming_edge {
795            self.incoming_edge = self.graph.next_edge(edge, EdgeDirection::Incoming);
796            let weights = &mut self.graph[edge];
797            return Some(EdgeMut {
798                index: edge,
799                weight: unsafe { core::mem::transmute::<&mut E, &'a mut E>(weights) },
800            });
801        }
802
803        let edge = self.outgoing_edge?;
804        self.outgoing_edge = self.graph.next_edge(edge, EdgeDirection::Outgoing);
805        let weights = &mut self.graph[edge];
806        Some(EdgeMut {
807            index: edge,
808            weight: unsafe { core::mem::transmute::<&mut E, &'a mut E>(weights) },
809        })
810    }
811}
812
813/// Iterator over the edges between a source node and a target node.
814#[derive(Clone)]
815pub struct EdgesBetween<'a, E: 'a> {
816    target_node: NodeIndex,
817    edges: Edges<'a, E>,
818}
819
820impl<'a, E> Iterator for EdgesBetween<'a, E> {
821    type Item = EdgeReference<'a, E>;
822
823    fn next(&mut self) -> Option<EdgeReference<'a, E>> {
824        let target_node = self.target_node;
825        self.edges
826            .by_ref()
827            .find(|&edge| edge.target() == target_node)
828    }
829
830    fn size_hint(&self) -> (usize, Option<usize>) {
831        let (_, upper) = self.edges.size_hint();
832        (0, upper)
833    }
834}
835
836fn swap_pair<T>(mut x: [T; 2]) -> [T; 2] {
837    x.swap(0, 1);
838    x
839}
840
841// TODO: Reduce duplication between `Edges` variants.
842/// An iterator over edge weights for edges from or to a node.
843pub struct EdgeWeights<'a, E: 'a> {
844    /// The starting node to skip over.
845    skip_start: NodeIndex,
846
847    /// The edges to iterate over.
848    edges: &'a [Edge<E>],
849
850    /// The next edge to visit.
851    next: [EdgeIndex; 2],
852
853    /// The direction of edges.
854    direction: EdgeDirection,
855}
856
857impl<'a, E> Iterator for EdgeWeights<'a, E> {
858    type Item = &'a E;
859
860    fn next(&mut self) -> Option<Self::Item> {
861        let i = self.next[0].index();
862        if let Some(Edge { weight, next, .. }) = self.edges.get(i) {
863            self.next[0] = next[0];
864            return Some(weight);
865        }
866
867        while let Some(Edge { node, weight, next }) = self.edges.get(self.next[1].index()) {
868            self.next[1] = next[1];
869
870            // In any of the "both" situations, self-loops would be iterated over twice.
871            // Skip them here.
872            if node[0] == self.skip_start {
873                continue;
874            }
875
876            return Some(weight);
877        }
878
879        None
880    }
881}
882
883impl<E> Clone for EdgeWeights<'_, E> {
884    fn clone(&self) -> Self {
885        EdgeWeights {
886            skip_start: self.skip_start,
887            edges: self.edges,
888            next: self.next,
889            direction: self.direction,
890        }
891    }
892}
893
894/// An iterator over mutable references to all edge weights from or to a node.
895pub struct EdgeWeightsMut<'a, N, E> {
896    /// A mutable reference to the graph.
897    pub graph: &'a mut UnGraph<N, E>,
898
899    /// The next incoming edge to visit.
900    pub incoming_edge: Option<EdgeIndex>,
901
902    /// The next outgoing edge to visit.
903    pub outgoing_edge: Option<EdgeIndex>,
904}
905
906impl<'a, N: Copy, E> Iterator for EdgeWeightsMut<'a, N, E> {
907    type Item = &'a mut E;
908
909    #[inline]
910    fn next(&mut self) -> Option<&'a mut E> {
911        if let Some(edge) = self.incoming_edge {
912            self.incoming_edge = self.graph.next_edge(edge, EdgeDirection::Incoming);
913            let weight = &mut self.graph[edge];
914            return Some(unsafe { core::mem::transmute::<&mut E, &'a mut E>(weight) });
915        }
916
917        let edge = self.outgoing_edge?;
918        self.outgoing_edge = self.graph.next_edge(edge, EdgeDirection::Outgoing);
919        let weight = &mut self.graph[edge];
920        Some(unsafe { core::mem::transmute::<&mut E, &'a mut E>(weight) })
921    }
922}
923
924/// An iterator yielding immutable access to all edge weights.
925pub struct AllEdgeWeights<'a, E: 'a> {
926    edges: core::slice::Iter<'a, Edge<E>>,
927}
928
929impl<'a, E> Iterator for AllEdgeWeights<'a, E> {
930    type Item = &'a E;
931
932    fn next(&mut self) -> Option<&'a E> {
933        self.edges.next().map(|edge| &edge.weight)
934    }
935
936    fn size_hint(&self) -> (usize, Option<usize>) {
937        self.edges.size_hint()
938    }
939}
940
941/// An iterator yielding mutable access to all edge weights.
942#[derive(Debug)]
943pub struct AllEdgeWeightsMut<'a, E: 'a> {
944    edges: core::slice::IterMut<'a, Edge<E>>,
945}
946
947impl<'a, E> Iterator for AllEdgeWeightsMut<'a, E> {
948    type Item = &'a mut E;
949
950    fn next(&mut self) -> Option<&'a mut E> {
951        self.edges.next().map(|edge| &mut edge.weight)
952    }
953
954    fn size_hint(&self) -> (usize, Option<usize>) {
955        self.edges.size_hint()
956    }
957}
958
959struct EdgesWalkerMut<'a, E: 'a> {
960    edges: &'a mut [Edge<E>],
961    next: EdgeIndex,
962    dir: EdgeDirection,
963}
964
965impl<E> EdgesWalkerMut<'_, E> {
966    fn next_edge(&mut self) -> Option<&mut Edge<E>> {
967        self.next().map(|t| t.1)
968    }
969
970    fn next(&mut self) -> Option<(EdgeIndex, &mut Edge<E>)> {
971        let this_index = self.next;
972        let k = self.dir as usize;
973        match self.edges.get_mut(self.next.index()) {
974            None => None,
975            Some(edge) => {
976                self.next = edge.next[k];
977                Some((this_index, edge))
978            }
979        }
980    }
981}
982
983/// Indexes the `UnGraph` by `NodeIndex` to access node weights.
984///
985/// # Panics
986///
987/// Panics if the node doesn't exist.
988impl<N, E> Index<NodeIndex> for UnGraph<N, E> {
989    type Output = N;
990    fn index(&self, index: NodeIndex) -> &N {
991        &self.nodes[index.index()].weight
992    }
993}
994
995/// Indexes the `UnGraph` by `NodeIndex` to access node weights.
996///
997/// # Panics
998///
999/// Panics if the node doesn't exist.
1000impl<N, E> IndexMut<NodeIndex> for UnGraph<N, E> {
1001    fn index_mut(&mut self, index: NodeIndex) -> &mut N {
1002        &mut self.nodes[index.index()].weight
1003    }
1004}
1005
1006/// Indexes the `UnGraph` by `EdgeIndex` to access edge weights.
1007///
1008/// # Panics
1009///
1010/// Panics if the edge doesn't exist.
1011impl<N, E> Index<EdgeIndex> for UnGraph<N, E> {
1012    type Output = E;
1013    fn index(&self, index: EdgeIndex) -> &E {
1014        &self.edges[index.index()].weight
1015    }
1016}
1017
1018/// Indexes the `UnGraph` by `EdgeIndex` to access edge weights.
1019///
1020/// # Panics
1021///
1022/// Panics if the edge doesn't exist.
1023impl<N, E> IndexMut<EdgeIndex> for UnGraph<N, E> {
1024    fn index_mut(&mut self, index: EdgeIndex) -> &mut E {
1025        &mut self.edges[index.index()].weight
1026    }
1027}
1028
1029/// A reference to a graph edge.
1030#[derive(Debug)]
1031pub struct EdgeReference<'a, E: 'a> {
1032    index: EdgeIndex,
1033    node: [NodeIndex; 2],
1034    weight: &'a E,
1035}
1036
1037impl<'a, E: 'a> EdgeReference<'a, E> {
1038    /// Returns the index of the edge.
1039    #[inline]
1040    pub fn index(&self) -> EdgeIndex {
1041        self.index
1042    }
1043
1044    /// Returns the source node index.
1045    #[inline]
1046    pub fn source(&self) -> NodeIndex {
1047        self.node[0]
1048    }
1049
1050    /// Returns the target node index.
1051    #[inline]
1052    pub fn target(&self) -> NodeIndex {
1053        self.node[1]
1054    }
1055
1056    /// Returns the weight of the edge.
1057    #[inline]
1058    pub fn weight(&self) -> &'a E {
1059        self.weight
1060    }
1061}
1062
1063impl<E> Clone for EdgeReference<'_, E> {
1064    fn clone(&self) -> Self {
1065        *self
1066    }
1067}
1068
1069impl<E> Copy for EdgeReference<'_, E> {}
1070
1071impl<E> PartialEq for EdgeReference<'_, E>
1072where
1073    E: PartialEq,
1074{
1075    fn eq(&self, rhs: &Self) -> bool {
1076        self.index == rhs.index && self.weight == rhs.weight
1077    }
1078}
1079
1080/// A mutable reference to a graph edge.
1081#[derive(Debug)]
1082pub struct EdgeMut<'a, E: 'a> {
1083    index: EdgeIndex,
1084    weight: &'a mut E,
1085}
1086
1087impl<E> EdgeMut<'_, E> {
1088    /// Returns the index of the edge.
1089    #[inline]
1090    pub fn index(&self) -> EdgeIndex {
1091        self.index
1092    }
1093
1094    /// Returns the weight of the edge.
1095    #[inline]
1096    pub fn weight(&self) -> &E {
1097        self.weight
1098    }
1099
1100    /// Returns the weight of the edge mutably.
1101    #[inline]
1102    pub fn weight_mut(&mut self) -> &mut E {
1103        self.weight
1104    }
1105}
1106
1107impl<E> PartialEq for EdgeMut<'_, E>
1108where
1109    E: PartialEq,
1110{
1111    fn eq(&self, rhs: &Self) -> bool {
1112        self.index == rhs.index && self.weight == rhs.weight
1113    }
1114}
avian3d/data_structures/graph.rs

avian3d/data_structures/
graph.rs
