petgraph/
adj.rs

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

petgraph/
adj.rs
