yuuang_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<'a, E, Ix: IndexType> Copy for EdgeReference<'a, E, Ix> {}
72impl<'a, E, Ix: IndexType> Clone for EdgeReference<'a, E, Ix> {
73    fn clone(&self) -> Self {
74        EdgeReference {
75            id: self.id,
76            edge: self.edge,
77        }
78    }
79}
80
81impl<'a, E, Ix: IndexType> visit::EdgeRef for EdgeReference<'a, E, Ix> {
82    type NodeId = NodeIndex<Ix>;
83    type EdgeId = EdgeIndex<Ix>;
84    type Weight = E;
85    fn source(&self) -> Self::NodeId {
86        self.id.from
87    }
88    fn target(&self) -> Self::NodeId {
89        self.edge.suc
90    }
91    fn id(&self) -> Self::EdgeId {
92        self.id
93    }
94    fn weight(&self) -> &Self::Weight {
95        &self.edge.weight
96    }
97}
98
99#[derive(Debug, Clone)]
100pub struct EdgeIndices<'a, E, Ix: IndexType> {
101    rows: std::iter::Enumerate<std::slice::Iter<'a, Row<E, Ix>>>,
102    row_index: usize,
103    row_len: usize,
104    cur: usize,
105}
106
107impl<'a, E, Ix: IndexType> Iterator for EdgeIndices<'a, E, Ix> {
108    type Item = EdgeIndex<Ix>;
109    fn next(&mut self) -> Option<EdgeIndex<Ix>> {
110        loop {
111            if self.cur < self.row_len {
112                let res = self.cur;
113                self.cur += 1;
114                return Some(EdgeIndex {
115                    from: Ix::new(self.row_index),
116                    successor_index: res,
117                });
118            } else {
119                match self.rows.next() {
120                    Some((index, row)) => {
121                        self.row_index = index;
122                        self.cur = 0;
123                        self.row_len = row.len();
124                    }
125                    None => return None,
126                }
127            }
128        }
129    }
130}
131
132iterator_wrap! {
133    impl (Iterator DoubleEndedIterator ExactSizeIterator) for
134    /// An iterator over all node indices in the graph.
135    #[derive(Debug, Clone)]
136    struct NodeIndices <Ix> where {}
137    item: Ix,
138    iter: std::iter::Map<Range<usize>, fn(usize) -> Ix>,
139}
140
141/// An adjacency list with labeled edges.
142///
143/// Can be interpreted as a directed graph
144/// with unweighted nodes.
145///
146/// This is the most simple adjacency list you can imagine. [`Graph`](../graph/struct.Graph.html), in contrast,
147/// maintains both the list of successors and predecessors for each node,
148/// which is a different trade-off.
149///
150/// Allows parallel edges and self-loops.
151///
152/// This data structure is append-only (except for [`clear`](#method.clear)), so indices
153/// returned at some point for a given graph will stay valid with this same
154/// graph until it is dropped or [`clear`](#method.clear) is called.
155///
156/// Space consumption: **O(|E|)**.
157#[derive(Clone, Default)]
158pub struct List<E, Ix = DefaultIx>
159where
160    Ix: IndexType,
161{
162    suc: Vec<Row<E, Ix>>,
163}
164
165impl<E, Ix: IndexType> List<E, Ix> {
166    /// Creates a new, empty adjacency list.
167    pub fn new() -> List<E, Ix> {
168        List { suc: Vec::new() }
169    }
170
171    /// Creates a new, empty adjacency list tailored for `nodes` nodes.
172    pub fn with_capacity(nodes: usize) -> List<E, Ix> {
173        List {
174            suc: Vec::with_capacity(nodes),
175        }
176    }
177
178    /// Removes all nodes and edges from the list.
179    pub fn clear(&mut self) {
180        self.suc.clear()
181    }
182
183    /// Returns the number of edges in the list
184    ///
185    /// Computes in **O(|V|)** time.
186    pub fn edge_count(&self) -> usize {
187        self.suc.iter().map(|x| x.len()).sum()
188    }
189
190    /// Adds a new node to the list. This allocates a new `Vec` and then should
191    /// run in amortized **O(1)** time.
192    pub fn add_node(&mut self) -> NodeIndex<Ix> {
193        let i = self.suc.len();
194        self.suc.push(Vec::new());
195        Ix::new(i)
196    }
197
198    /// Adds a new node to the list. This allocates a new `Vec` and then should
199    /// run in amortized **O(1)** time.
200    pub fn add_node_with_capacity(&mut self, successors: usize) -> NodeIndex<Ix> {
201        let i = self.suc.len();
202        self.suc.push(Vec::with_capacity(successors));
203        Ix::new(i)
204    }
205
206    /// Adds a new node to the list by giving its list of successors and the corresponding
207    /// weigths.
208    pub fn add_node_from_edges<I: Iterator<Item = (NodeIndex<Ix>, E)>>(
209        &mut self,
210        edges: I,
211    ) -> NodeIndex<Ix> {
212        let i = self.suc.len();
213        self.suc
214            .push(edges.map(|(suc, weight)| WSuc { suc, weight }).collect());
215        Ix::new(i)
216    }
217
218    /// Add an edge from `a` to `b` to the graph, with its associated
219    /// data `weight`.
220    ///
221    /// Return the index of the new edge.
222    ///
223    /// Computes in **O(1)** time.
224    ///
225    /// **Panics** if the source node does not exist.<br>
226    ///
227    /// **Note:** `List` allows adding parallel (“duplicate”) edges. If you want
228    /// to avoid this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead.
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(std::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<'a, E, Ix> fmt::Debug for EdgeReferences<'a, 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 std::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<'a, E, Ix: IndexType> visit::IntoNodeIdentifiers for &'a 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<'a, Ix: IndexType, E> visit::IntoNodeReferences for &'a 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    fn neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors {
475        let proj: fn(&WSuc<E, Ix>) -> NodeIndex<Ix> = |x| x.suc;
476        let iter = self.suc[a.index()].iter().map(proj);
477        Neighbors { iter }
478    }
479}
480
481type SomeIter<'a, E, Ix> = std::iter::Map<
482    std::iter::Zip<std::iter::Enumerate<RowIter<'a, E, Ix>>, std::iter::Repeat<Ix>>,
483    fn(((usize, &'a WSuc<E, Ix>), Ix)) -> EdgeReference<'a, E, Ix>,
484>;
485
486iterator_wrap! {
487impl (Iterator) for
488/// An iterator over the [`EdgeReference`] of all the edges of the graph.
489struct EdgeReferences<'a, E, Ix> where { Ix: IndexType }
490item: EdgeReference<'a, E, Ix>,
491iter: std::iter::FlatMap<
492    std::iter::Enumerate<
493        std::slice::Iter<'a, Row<E, Ix>>
494    >,
495    SomeIter<'a, E, Ix>,
496    fn(
497        (usize, &'a Vec<WSuc<E, Ix>>)
498    ) -> SomeIter<'a, E, Ix>,
499>,
500}
501
502impl<'a, E, Ix: IndexType> Clone for EdgeReferences<'a, E, Ix> {
503    fn clone(&self) -> Self {
504        EdgeReferences {
505            iter: self.iter.clone(),
506        }
507    }
508}
509
510fn proj1<E, Ix: IndexType>(
511    ((successor_index, edge), from): ((usize, &WSuc<E, Ix>), Ix),
512) -> EdgeReference<E, Ix> {
513    let id = EdgeIndex {
514        from,
515        successor_index,
516    };
517    EdgeReference { id, edge }
518}
519fn proj2<E, Ix: IndexType>((row_index, row): (usize, &Vec<WSuc<E, Ix>>)) -> SomeIter<E, Ix> {
520    row.iter()
521        .enumerate()
522        .zip(std::iter::repeat(Ix::new(row_index)))
523        .map(proj1 as _)
524}
525
526impl<'a, Ix: IndexType, E> visit::IntoEdgeReferences for &'a List<E, Ix> {
527    type EdgeRef = EdgeReference<'a, E, Ix>;
528    type EdgeReferences = EdgeReferences<'a, E, Ix>;
529    fn edge_references(self) -> Self::EdgeReferences {
530        let iter = self.suc.iter().enumerate().flat_map(proj2 as _);
531        EdgeReferences { iter }
532    }
533}
534
535iterator_wrap! {
536impl (Iterator) for
537/// Iterator over the [`EdgeReference`] of the outgoing edges from a node.
538#[derive(Debug, Clone)]
539struct OutgoingEdgeReferences<'a, E, Ix> where { Ix: IndexType }
540item: EdgeReference<'a, E, Ix>,
541iter: SomeIter<'a, E, Ix>,
542}
543
544impl<'a, Ix: IndexType, E> visit::IntoEdges for &'a List<E, Ix> {
545    type Edges = OutgoingEdgeReferences<'a, E, Ix>;
546    fn edges(self, a: Self::NodeId) -> Self::Edges {
547        let iter = self.suc[a.index()]
548            .iter()
549            .enumerate()
550            .zip(std::iter::repeat(a))
551            .map(proj1 as _);
552        OutgoingEdgeReferences { iter }
553    }
554}
555
556impl<E, Ix: IndexType> visit::GraphProp for List<E, Ix> {
557    type EdgeType = crate::Directed;
558    fn is_directed(&self) -> bool {
559        true
560    }
561}
562
563impl<E, Ix: IndexType> NodeCount for List<E, Ix> {
564    /// Returns the number of nodes in the list
565    ///
566    /// Computes in **O(1)** time.
567    fn node_count(&self) -> usize {
568        self.suc.len()
569    }
570}
571
572impl<E, Ix: IndexType> EdgeCount for List<E, Ix> {
573    /// Returns the number of edges in the list
574    ///
575    /// Computes in **O(|V|)** time.
576    fn edge_count(&self) -> usize {
577        List::edge_count(self)
578    }
579}
580
581impl<E, Ix: IndexType> visit::NodeIndexable for List<E, Ix> {
582    fn node_bound(&self) -> usize {
583        self.node_count()
584    }
585    #[inline]
586    fn to_index(&self, a: Self::NodeId) -> usize {
587        a.index()
588    }
589    #[inline]
590    fn from_index(&self, i: usize) -> Self::NodeId {
591        Ix::new(i)
592    }
593}
594
595impl<E, Ix: IndexType> visit::NodeCompactIndexable for List<E, Ix> {}
596
597impl<E, Ix: IndexType> DataMap for List<E, Ix> {
598    fn node_weight(&self, n: Self::NodeId) -> Option<&()> {
599        if n.index() < self.suc.len() {
600            Some(&())
601        } else {
602            None
603        }
604    }
605
606    /// Accesses the weight of edge `e`
607    ///
608    /// Computes in **O(1)**
609    fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E> {
610        self.get_edge(e).map(|x| &x.weight)
611    }
612}
613
614impl<E, Ix: IndexType> DataMapMut for List<E, Ix> {
615    fn node_weight_mut(&mut self, n: Self::NodeId) -> Option<&mut ()> {
616        if n.index() < self.suc.len() {
617            // A hack to produce a &'static mut ()
618            // It does not actually allocate according to godbolt
619            let b = Box::new(());
620            Some(Box::leak(b))
621        } else {
622            None
623        }
624    }
625    /// Accesses the weight of edge `e`
626    ///
627    /// Computes in **O(1)**
628    fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E> {
629        self.get_edge_mut(e).map(|x| &mut x.weight)
630    }
631}
632
633/// The adjacency matrix for **List** is a bitmap that's computed by
634/// `.adjacency_matrix()`.
635impl<E, Ix> GetAdjacencyMatrix for List<E, Ix>
636where
637    Ix: IndexType,
638{
639    type AdjMatrix = FixedBitSet;
640
641    fn adjacency_matrix(&self) -> FixedBitSet {
642        let n = self.node_count();
643        let mut matrix = FixedBitSet::with_capacity(n * n);
644        for edge in self.edge_references() {
645            let i = edge.source().index() * n + edge.target().index();
646            matrix.put(i);
647
648            let j = edge.source().index() + n * edge.target().index();
649            matrix.put(j);
650        }
651        matrix
652    }
653
654    fn is_adjacent(&self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
655        let n = self.edge_count();
656        let index = n * a.index() + b.index();
657        matrix.contains(index)
658    }
659}