petgraph/
adj.rs

Help
1//! Simple adjacency list.
2use alloc::{boxed::Box, vec::Vec};
3use core::{fmt, ops::Range};
4
5use fixedbitset::FixedBitSet;
6
7use crate::data::{Build, DataMap, DataMapMut};
8use crate::iter_format::NoPretty;
9use crate::visit::{
10    self, EdgeCount, EdgeRef, GetAdjacencyMatrix, IntoEdgeReferences, IntoNeighbors, NodeCount,
11};
12
13#[doc(no_inline)]
14pub use crate::graph::{DefaultIx, IndexType};
15
16/// Adjacency list node index type, a plain integer.
17pub type NodeIndex<Ix = DefaultIx> = Ix;
18
19/// Adjacency list edge index type, a pair of integers.
20#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
21pub struct EdgeIndex<Ix = DefaultIx>
22where
23    Ix: IndexType,
24{
25    /// Source of the edge.
26    from: NodeIndex<Ix>,
27    /// Index of the sucessor in the successor list.
28    successor_index: usize,
29}
30
31iterator_wrap! {
32impl (Iterator) for
33/// An Iterator over the indices of the outgoing edges from a node.
34///
35/// It does not borrow the graph during iteration.
36#[derive(Debug, Clone)]
37struct OutgoingEdgeIndices <Ix> where { Ix: IndexType }
38item: EdgeIndex<Ix>,
39iter: core::iter::Map<core::iter::Zip<Range<usize>, core::iter::Repeat<NodeIndex<Ix>>>, fn((usize, NodeIndex<Ix>)) -> EdgeIndex<Ix>>,
40}
41
42/// Weighted sucessor
43#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
44struct WSuc<E, Ix: IndexType> {
45    /// Index of the sucessor.
46    suc: Ix,
47    /// Weight of the edge to `suc`.
48    weight: E,
49}
50
51/// One row of the adjacency list.
52type Row<E, Ix> = Vec<WSuc<E, Ix>>;
53type RowIter<'a, E, Ix> = core::slice::Iter<'a, WSuc<E, Ix>>;
54
55iterator_wrap! {
56impl (Iterator DoubleEndedIterator ExactSizeIterator) for
57/// An iterator over the indices of the neighbors of a node.
58#[derive(Debug, Clone)]
59struct Neighbors<'a, E, Ix> where { Ix: IndexType }
60item: NodeIndex<Ix>,
61iter: core::iter::Map<RowIter<'a, E, Ix>, fn(&WSuc<E, Ix>) -> NodeIndex<Ix>>,
62}
63
64/// A reference to an edge of the graph.
65#[derive(Debug, Eq, PartialEq, Ord, PartialOrd)]
66pub struct EdgeReference<'a, E, Ix: IndexType> {
67    /// index of the edge
68    id: EdgeIndex<Ix>,
69    /// a reference to the corresponding item in the adjacency list
70    edge: &'a WSuc<E, Ix>,
71}
72
73impl<E, Ix: IndexType> Copy for EdgeReference<'_, E, Ix> {}
74impl<E, Ix: IndexType> Clone for EdgeReference<'_, E, Ix> {
75    fn clone(&self) -> Self {
76        *self
77    }
78}
79
80impl<E, Ix: IndexType> visit::EdgeRef for EdgeReference<'_, E, Ix> {
81    type NodeId = NodeIndex<Ix>;
82    type EdgeId = EdgeIndex<Ix>;
83    type Weight = E;
84    fn source(&self) -> Self::NodeId {
85        self.id.from
86    }
87    fn target(&self) -> Self::NodeId {
88        self.edge.suc
89    }
90    fn id(&self) -> Self::EdgeId {
91        self.id
92    }
93    fn weight(&self) -> &Self::Weight {
94        &self.edge.weight
95    }
96}
97
98#[derive(Debug, Clone)]
99pub struct EdgeIndices<'a, E, Ix: IndexType> {
100    rows: core::iter::Enumerate<core::slice::Iter<'a, Row<E, Ix>>>,
101    row_index: usize,
102    row_len: usize,
103    cur: usize,
104}
105
106impl<E, Ix: IndexType> Iterator for EdgeIndices<'_, E, Ix> {
107    type Item = EdgeIndex<Ix>;
108    fn next(&mut self) -> Option<EdgeIndex<Ix>> {
109        loop {
110            if self.cur < self.row_len {
111                let res = self.cur;
112                self.cur += 1;
113                return Some(EdgeIndex {
114                    from: Ix::new(self.row_index),
115                    successor_index: res,
116                });
117            } else {
118                match self.rows.next() {
119                    Some((index, row)) => {
120                        self.row_index = index;
121                        self.cur = 0;
122                        self.row_len = row.len();
123                    }
124                    None => return None,
125                }
126            }
127        }
128    }
129}
130
131iterator_wrap! {
132    impl (Iterator DoubleEndedIterator ExactSizeIterator) for
133    /// An iterator over all node indices in the graph.
134    #[derive(Debug, Clone)]
135    struct NodeIndices <Ix> where {}
136    item: Ix,
137    iter: core::iter::Map<Range<usize>, fn(usize) -> Ix>,
138}
139
140/// An adjacency list with labeled edges.
141///
142/// Can be interpreted as a directed graph
143/// with unweighted nodes.
144///
145/// This is the most simple adjacency list you can imagine. [`Graph`](../graph/struct.Graph.html), in contrast,
146/// maintains both the list of successors and predecessors for each node,
147/// which is a different trade-off.
148///
149/// Allows parallel edges and self-loops.
150///
151/// This data structure is append-only (except for [`clear`](#method.clear)), so indices
152/// returned at some point for a given graph will stay valid with this same
153/// graph until it is dropped or [`clear`](#method.clear) is called.
154///
155/// Space consumption: **O(|E|)**.
156#[derive(Clone, Default)]
157pub struct List<E, Ix = DefaultIx>
158where
159    Ix: IndexType,
160{
161    suc: Vec<Row<E, Ix>>,
162}
163
164impl<E, Ix: IndexType> List<E, Ix> {
165    /// Creates a new, empty adjacency list.
166    pub fn new() -> List<E, Ix> {
167        List { suc: Vec::new() }
168    }
169
170    /// Creates a new, empty adjacency list tailored for `nodes` nodes.
171    pub fn with_capacity(nodes: usize) -> List<E, Ix> {
172        List {
173            suc: Vec::with_capacity(nodes),
174        }
175    }
176
177    /// Removes all nodes and edges from the list.
178    pub fn clear(&mut self) {
179        self.suc.clear()
180    }
181
182    /// Returns the number of edges in the list
183    ///
184    /// Computes in **O(|V|)** time.
185    pub fn edge_count(&self) -> usize {
186        self.suc.iter().map(|x| x.len()).sum()
187    }
188
189    /// Adds a new node to the list. This allocates a new `Vec` and then should
190    /// run in amortized **O(1)** time.
191    pub fn add_node(&mut self) -> NodeIndex<Ix> {
192        let i = self.suc.len();
193        self.suc.push(Vec::new());
194        Ix::new(i)
195    }
196
197    /// Adds a new node to the list. This allocates a new `Vec` and then should
198    /// run in amortized **O(1)** time.
199    pub fn add_node_with_capacity(&mut self, successors: usize) -> NodeIndex<Ix> {
200        let i = self.suc.len();
201        self.suc.push(Vec::with_capacity(successors));
202        Ix::new(i)
203    }
204
205    /// Adds a new node to the list by giving its list of successors and the corresponding
206    /// weigths.
207    pub fn add_node_from_edges<I: Iterator<Item = (NodeIndex<Ix>, E)>>(
208        &mut self,
209        edges: I,
210    ) -> NodeIndex<Ix> {
211        let i = self.suc.len();
212        self.suc
213            .push(edges.map(|(suc, weight)| WSuc { suc, weight }).collect());
214        Ix::new(i)
215    }
216
217    /// Add an edge from `a` to `b` to the graph, with its associated
218    /// data `weight`.
219    ///
220    /// Return the index of the new edge.
221    ///
222    /// Computes in **O(1)** time.
223    ///
224    /// **Panics** if the source node does not exist.<br>
225    ///
226    /// **Note:** `List` allows adding parallel (“duplicate”) edges. If you want
227    /// to avoid this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead.
228    #[track_caller]
229    pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
230        if b.index() >= self.suc.len() {
231            panic!(
232                "{} is not a valid node index for a {} nodes adjacency list",
233                b.index(),
234                self.suc.len()
235            );
236        }
237        let row = &mut self.suc[a.index()];
238        let rank = row.len();
239        row.push(WSuc { suc: b, weight });
240        EdgeIndex {
241            from: a,
242            successor_index: rank,
243        }
244    }
245
246    fn get_edge(&self, e: EdgeIndex<Ix>) -> Option<&WSuc<E, Ix>> {
247        self.suc
248            .get(e.from.index())
249            .and_then(|row| row.get(e.successor_index))
250    }
251
252    fn get_edge_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut WSuc<E, Ix>> {
253        self.suc
254            .get_mut(e.from.index())
255            .and_then(|row| row.get_mut(e.successor_index))
256    }
257
258    /// Accesses the source and target of edge `e`
259    ///
260    /// Computes in **O(1)**
261    pub fn edge_endpoints(&self, e: EdgeIndex<Ix>) -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)> {
262        self.get_edge(e).map(|x| (e.from, x.suc))
263    }
264
265    pub fn edge_indices_from(&self, a: NodeIndex<Ix>) -> OutgoingEdgeIndices<Ix> {
266        let proj: fn((usize, NodeIndex<Ix>)) -> EdgeIndex<Ix> =
267            |(successor_index, from)| EdgeIndex {
268                from,
269                successor_index,
270            };
271        let iter = (0..(self.suc[a.index()].len()))
272            .zip(core::iter::repeat(a))
273            .map(proj);
274        OutgoingEdgeIndices { iter }
275    }
276
277    /// Lookups whether there is an edge from `a` to `b`.
278    ///
279    /// Computes in **O(e')** time, where **e'** is the number of successors of `a`.
280    pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
281        match self.suc.get(a.index()) {
282            None => false,
283            Some(row) => row.iter().any(|x| x.suc == b),
284        }
285    }
286
287    /// Lookups whether there is an edge from `a` to `b`.
288    ///
289    /// Computes in **O(e')** time, where **e'** is the number of successors of `a`.
290    pub fn find_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<EdgeIndex<Ix>> {
291        self.suc.get(a.index()).and_then(|row| {
292            row.iter()
293                .enumerate()
294                .find(|(_, x)| x.suc == b)
295                .map(|(i, _)| EdgeIndex {
296                    from: a,
297                    successor_index: i,
298                })
299        })
300    }
301
302    /// Returns an iterator over all node indices of the graph.
303    ///
304    /// Consuming the whole iterator take **O(|V|)**.
305    pub fn node_indices(&self) -> NodeIndices<Ix> {
306        NodeIndices {
307            iter: (0..self.suc.len()).map(Ix::new),
308        }
309    }
310
311    /// Returns an iterator over all edge indices of the graph.
312    ///
313    /// Consuming the whole iterator take **O(|V| + |E|)**.
314    pub fn edge_indices(&self) -> EdgeIndices<E, Ix> {
315        EdgeIndices {
316            rows: self.suc.iter().enumerate(),
317            row_index: 0,
318            row_len: 0,
319            cur: 0,
320        }
321    }
322}
323
324/// A very simple adjacency list with no node or label weights.
325pub type UnweightedList<Ix> = List<(), Ix>;
326
327impl<E, Ix: IndexType> Build for List<E, Ix> {
328    /// Adds a new node to the list. This allocates a new `Vec` and then should
329    /// run in amortized **O(1)** time.
330    fn add_node(&mut self, _weight: ()) -> NodeIndex<Ix> {
331        self.add_node()
332    }
333
334    /// Add an edge from `a` to `b` to the graph, with its associated
335    /// data `weight`.
336    ///
337    /// Return the index of the new edge.
338    ///
339    /// Computes in **O(1)** time.
340    ///
341    /// **Panics** if the source node does not exist.<br>
342    ///
343    /// **Note:** `List` allows adding parallel (“duplicate”) edges. If you want
344    /// to avoid this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead.
345    fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> Option<EdgeIndex<Ix>> {
346        Some(self.add_edge(a, b, weight))
347    }
348
349    /// Updates or adds an edge from `a` to `b` to the graph, with its associated
350    /// data `weight`.
351    ///
352    /// Return the index of the new edge.
353    ///
354    /// Computes in **O(e')** time, where **e'** is the number of successors of `a`.
355    ///
356    /// **Panics** if the source node does not exist.<br>
357    fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
358        let row = &mut self.suc[a.index()];
359        for (i, info) in row.iter_mut().enumerate() {
360            if info.suc == b {
361                info.weight = weight;
362                return EdgeIndex {
363                    from: a,
364                    successor_index: i,
365                };
366            }
367        }
368        let rank = row.len();
369        row.push(WSuc { suc: b, weight });
370        EdgeIndex {
371            from: a,
372            successor_index: rank,
373        }
374    }
375}
376
377impl<E, Ix> fmt::Debug for EdgeReferences<'_, E, Ix>
378where
379    E: fmt::Debug,
380    Ix: IndexType,
381{
382    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
383        let mut edge_list = f.debug_list();
384        let iter: Self = self.clone();
385        for e in iter {
386            if core::mem::size_of::<E>() != 0 {
387                edge_list.entry(&(
388                    NoPretty((e.source().index(), e.target().index())),
389                    e.weight(),
390                ));
391            } else {
392                edge_list.entry(&NoPretty((e.source().index(), e.target().index())));
393            }
394        }
395        edge_list.finish()
396    }
397}
398
399impl<E, Ix> fmt::Debug for List<E, Ix>
400where
401    E: fmt::Debug,
402    Ix: IndexType,
403{
404    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
405        let mut fmt_struct = f.debug_struct("adj::List");
406        fmt_struct.field("node_count", &self.node_count());
407        fmt_struct.field("edge_count", &self.edge_count());
408        if self.edge_count() > 0 {
409            fmt_struct.field("edges", &self.edge_references());
410        }
411        fmt_struct.finish()
412    }
413}
414
415impl<E, Ix> visit::GraphBase for List<E, Ix>
416where
417    Ix: IndexType,
418{
419    type NodeId = NodeIndex<Ix>;
420    type EdgeId = EdgeIndex<Ix>;
421}
422
423impl<E, Ix> visit::Visitable for List<E, Ix>
424where
425    Ix: IndexType,
426{
427    type Map = FixedBitSet;
428    fn visit_map(&self) -> FixedBitSet {
429        FixedBitSet::with_capacity(self.node_count())
430    }
431    fn reset_map(&self, map: &mut Self::Map) {
432        map.clear();
433        map.grow(self.node_count());
434    }
435}
436
437impl<E, Ix: IndexType> visit::IntoNodeIdentifiers for &List<E, Ix> {
438    type NodeIdentifiers = NodeIndices<Ix>;
439    fn node_identifiers(self) -> NodeIndices<Ix> {
440        self.node_indices()
441    }
442}
443
444impl<Ix: IndexType> visit::NodeRef for NodeIndex<Ix> {
445    type NodeId = NodeIndex<Ix>;
446    type Weight = ();
447    fn id(&self) -> Self::NodeId {
448        *self
449    }
450    fn weight(&self) -> &Self::Weight {
451        &()
452    }
453}
454
455impl<Ix: IndexType, E> visit::IntoNodeReferences for &List<E, Ix> {
456    type NodeRef = NodeIndex<Ix>;
457    type NodeReferences = NodeIndices<Ix>;
458    fn node_references(self) -> Self::NodeReferences {
459        self.node_indices()
460    }
461}
462
463impl<E, Ix: IndexType> visit::Data for List<E, Ix> {
464    type NodeWeight = ();
465    type EdgeWeight = E;
466}
467
468impl<'a, E, Ix: IndexType> IntoNeighbors for &'a List<E, Ix> {
469    type Neighbors = Neighbors<'a, E, Ix>;
470    /// Returns an iterator of all nodes with an edge starting from `a`.
471    /// Panics if `a` is out of bounds.
472    /// Use [`List::edge_indices_from`] instead if you do not want to borrow the adjacency list while
473    /// iterating.
474    #[track_caller]
475    fn neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors {
476        let proj: fn(&WSuc<E, Ix>) -> NodeIndex<Ix> = |x| x.suc;
477        let iter = self.suc[a.index()].iter().map(proj);
478        Neighbors { iter }
479    }
480}
481
482type SomeIter<'a, E, Ix> = core::iter::Map<
483    core::iter::Zip<core::iter::Enumerate<RowIter<'a, E, Ix>>, core::iter::Repeat<Ix>>,
484    fn(((usize, &'a WSuc<E, Ix>), Ix)) -> EdgeReference<'a, E, Ix>,
485>;
486
487iterator_wrap! {
488impl (Iterator) for
489/// An iterator over the [`EdgeReference`] of all the edges of the graph.
490struct EdgeReferences<'a, E, Ix> where { Ix: IndexType }
491item: EdgeReference<'a, E, Ix>,
492iter: core::iter::FlatMap<
493    core::iter::Enumerate<
494        core::slice::Iter<'a, Row<E, Ix>>
495    >,
496    SomeIter<'a, E, Ix>,
497    fn(
498        (usize, &'a Vec<WSuc<E, Ix>>)
499    ) -> SomeIter<'a, E, Ix>,
500>,
501}
502
503impl<E, Ix: IndexType> Clone for EdgeReferences<'_, E, Ix> {
504    fn clone(&self) -> Self {
505        EdgeReferences {
506            iter: self.iter.clone(),
507        }
508    }
509}
510
511fn proj1<E, Ix: IndexType>(
512    ((successor_index, edge), from): ((usize, &WSuc<E, Ix>), Ix),
513) -> EdgeReference<E, Ix> {
514    let id = EdgeIndex {
515        from,
516        successor_index,
517    };
518    EdgeReference { id, edge }
519}
520fn proj2<E, Ix: IndexType>((row_index, row): (usize, &Vec<WSuc<E, Ix>>)) -> SomeIter<E, Ix> {
521    row.iter()
522        .enumerate()
523        .zip(core::iter::repeat(Ix::new(row_index)))
524        .map(proj1 as _)
525}
526
527impl<'a, Ix: IndexType, E> visit::IntoEdgeReferences for &'a List<E, Ix> {
528    type EdgeRef = EdgeReference<'a, E, Ix>;
529    type EdgeReferences = EdgeReferences<'a, E, Ix>;
530    fn edge_references(self) -> Self::EdgeReferences {
531        let iter = self.suc.iter().enumerate().flat_map(proj2 as _);
532        EdgeReferences { iter }
533    }
534}
535
536iterator_wrap! {
537impl (Iterator) for
538/// Iterator over the [`EdgeReference`] of the outgoing edges from a node.
539#[derive(Debug, Clone)]
540struct OutgoingEdgeReferences<'a, E, Ix> where { Ix: IndexType }
541item: EdgeReference<'a, E, Ix>,
542iter: SomeIter<'a, E, Ix>,
543}
544
545impl<'a, Ix: IndexType, E> visit::IntoEdges for &'a List<E, Ix> {
546    type Edges = OutgoingEdgeReferences<'a, E, Ix>;
547    fn edges(self, a: Self::NodeId) -> Self::Edges {
548        let iter = self.suc[a.index()]
549            .iter()
550            .enumerate()
551            .zip(core::iter::repeat(a))
552            .map(proj1 as _);
553        OutgoingEdgeReferences { iter }
554    }
555}
556
557impl<E, Ix: IndexType> visit::GraphProp for List<E, Ix> {
558    type EdgeType = crate::Directed;
559    fn is_directed(&self) -> bool {
560        true
561    }
562}
563
564impl<E, Ix: IndexType> NodeCount for List<E, Ix> {
565    /// Returns the number of nodes in the list
566    ///
567    /// Computes in **O(1)** time.
568    fn node_count(&self) -> usize {
569        self.suc.len()
570    }
571}
572
573impl<E, Ix: IndexType> EdgeCount for List<E, Ix> {
574    /// Returns the number of edges in the list
575    ///
576    /// Computes in **O(|V|)** time.
577    fn edge_count(&self) -> usize {
578        List::edge_count(self)
579    }
580}
581
582impl<E, Ix: IndexType> visit::NodeIndexable for List<E, Ix> {
583    fn node_bound(&self) -> usize {
584        self.node_count()
585    }
586    #[inline]
587    fn to_index(&self, a: Self::NodeId) -> usize {
588        a.index()
589    }
590    #[inline]
591    fn from_index(&self, i: usize) -> Self::NodeId {
592        Ix::new(i)
593    }
594}
595
596impl<E, Ix: IndexType> visit::NodeCompactIndexable for List<E, Ix> {}
597
598impl<E, Ix: IndexType> DataMap for List<E, Ix> {
599    fn node_weight(&self, n: Self::NodeId) -> Option<&()> {
600        if n.index() < self.suc.len() {
601            Some(&())
602        } else {
603            None
604        }
605    }
606
607    /// Accesses the weight of edge `e`
608    ///
609    /// Computes in **O(1)**
610    fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E> {
611        self.get_edge(e).map(|x| &x.weight)
612    }
613}
614
615impl<E, Ix: IndexType> DataMapMut for List<E, Ix> {
616    fn node_weight_mut(&mut self, n: Self::NodeId) -> Option<&mut ()> {
617        if n.index() < self.suc.len() {
618            // A hack to produce a &'static mut ()
619            // It does not actually allocate according to godbolt
620            let b = Box::new(());
621            Some(Box::leak(b))
622        } else {
623            None
624        }
625    }
626    /// Accesses the weight of edge `e`
627    ///
628    /// Computes in **O(1)**
629    fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E> {
630        self.get_edge_mut(e).map(|x| &mut x.weight)
631    }
632}
633
634/// The adjacency matrix for **List** is a bitmap that's computed by
635/// `.adjacency_matrix()`.
636impl<E, Ix> GetAdjacencyMatrix for List<E, Ix>
637where
638    Ix: IndexType,
639{
640    type AdjMatrix = FixedBitSet;
641
642    fn adjacency_matrix(&self) -> FixedBitSet {
643        let n = self.node_count();
644        let mut matrix = FixedBitSet::with_capacity(n * n);
645        for edge in self.edge_references() {
646            let i = edge.source().index() * n + edge.target().index();
647            matrix.put(i);
648        }
649        matrix
650    }
651
652    fn is_adjacent(&self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
653        let n = self.node_count();
654        let index = n * a.index() + b.index();
655        matrix.contains(index)
656    }
657}
petgraph/adj.rs

petgraph/
adj.rs
