/rust/registry/src/index.crates.io-1949cf8c6b5b557f/petgraph-0.8.3/src/adj.rs

Source
//! Simple adjacency list.
use alloc::{boxed::Box, vec::Vec};
use core::{fmt, ops::Range};

use fixedbitset::FixedBitSet;

use crate::data::{Build, DataMap, DataMapMut};
use crate::iter_format::NoPretty;
use crate::visit::{
    self, EdgeCount, EdgeRef, GetAdjacencyMatrix, IntoEdgeReferences, IntoNeighbors, NodeCount,
};

#[doc(no_inline)]
pub use crate::graph::{DefaultIx, IndexType};

/// Adjacency list node index type, a plain integer.
pub type NodeIndex<Ix = DefaultIx> = Ix;

/// Adjacency list edge index type, a pair of integers.
#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct EdgeIndex<Ix = DefaultIx>
where
    Ix: IndexType,
{
    /// Source of the edge.
    from: NodeIndex<Ix>,
    /// Index of the successor in the successor list.
    successor_index: usize,
}

iterator_wrap! {
impl (Iterator) for
/// An Iterator over the indices of the outgoing edges from a node.
///
/// It does not borrow the graph during iteration.
#[derive(Debug, Clone)]
struct OutgoingEdgeIndices <Ix> where { Ix: IndexType }
item: EdgeIndex<Ix>,
iter: core::iter::Map<core::iter::Zip<Range<usize>, core::iter::Repeat<NodeIndex<Ix>>>, fn((usize, NodeIndex<Ix>)) -> EdgeIndex<Ix>>,
}

/// Weighted successor
#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
struct WSuc<E, Ix: IndexType> {
    /// Index of the successor.
    suc: Ix,
    /// Weight of the edge to `suc`.
    weight: E,
}

/// One row of the adjacency list.
type Row<E, Ix> = Vec<WSuc<E, Ix>>;
type RowIter<'a, E, Ix> = core::slice::Iter<'a, WSuc<E, Ix>>;

iterator_wrap! {
impl (Iterator DoubleEndedIterator ExactSizeIterator) for
/// An iterator over the indices of the neighbors of a node.
#[derive(Debug, Clone)]
struct Neighbors<'a, E, Ix> where { Ix: IndexType }
item: NodeIndex<Ix>,
iter: core::iter::Map<RowIter<'a, E, Ix>, fn(&WSuc<E, Ix>) -> NodeIndex<Ix>>,
}

/// A reference to an edge of the graph.
#[derive(Debug, Eq, PartialEq, Ord, PartialOrd)]
pub struct EdgeReference<'a, E, Ix: IndexType> {
    /// index of the edge
    id: EdgeIndex<Ix>,
    /// a reference to the corresponding item in the adjacency list
    edge: &'a WSuc<E, Ix>,
}

impl<E, Ix: IndexType> Copy for EdgeReference<'_, E, Ix> {}
impl<E, Ix: IndexType> Clone for EdgeReference<'_, E, Ix> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<E, Ix: IndexType> visit::EdgeRef for EdgeReference<'_, E, Ix> {
    type NodeId = NodeIndex<Ix>;
    type EdgeId = EdgeIndex<Ix>;
    type Weight = E;
    fn source(&self) -> Self::NodeId {
        self.id.from
    }
    fn target(&self) -> Self::NodeId {
        self.edge.suc
    }
    fn id(&self) -> Self::EdgeId {
        self.id
    }
    fn weight(&self) -> &Self::Weight {
        &self.edge.weight
    }
}

#[derive(Debug, Clone)]
pub struct EdgeIndices<'a, E, Ix: IndexType> {
    rows: core::iter::Enumerate<core::slice::Iter<'a, Row<E, Ix>>>,
    row_index: usize,
    row_len: usize,
    cur: usize,
}

impl<E, Ix: IndexType> Iterator for EdgeIndices<'_, E, Ix> {
    type Item = EdgeIndex<Ix>;
    fn next(&mut self) -> Option<EdgeIndex<Ix>> {
        loop {
            if self.cur < self.row_len {
                let res = self.cur;
                self.cur += 1;
                return Some(EdgeIndex {
                    from: Ix::new(self.row_index),
                    successor_index: res,
                });
            } else {
                match self.rows.next() {
                    Some((index, row)) => {
                        self.row_index = index;
                        self.cur = 0;
                        self.row_len = row.len();
                    }
                    None => return None,
                }
            }
        }
    }
}

iterator_wrap! {
    impl (Iterator DoubleEndedIterator ExactSizeIterator) for
    /// An iterator over all node indices in the graph.
    #[derive(Debug, Clone)]
    struct NodeIndices <Ix> where {}
    item: Ix,
    iter: core::iter::Map<Range<usize>, fn(usize) -> Ix>,
}

/// An adjacency list with labeled edges.
///
/// Can be interpreted as a directed graph
/// with unweighted nodes.
///
/// This is the most simple adjacency list you can imagine. [`Graph`](../graph/struct.Graph.html), in contrast,
/// maintains both the list of successors and predecessors for each node,
/// which is a different trade-off.
///
/// Allows parallel edges and self-loops.
///
/// This data structure is append-only (except for [`clear`](#method.clear)), so indices
/// returned at some point for a given graph will stay valid with this same
/// graph until it is dropped or [`clear`](#method.clear) is called.
///
/// Space consumption: **O(|E|)**.
#[derive(Clone, Default)]
pub struct List<E, Ix = DefaultIx>
where
    Ix: IndexType,
{
    suc: Vec<Row<E, Ix>>,
}

impl<E, Ix: IndexType> List<E, Ix> {
    /// Creates a new, empty adjacency list.
    pub fn new() -> List<E, Ix> {
        List { suc: Vec::new() }
    }

    /// Creates a new, empty adjacency list tailored for `nodes` nodes.
    pub fn with_capacity(nodes: usize) -> List<E, Ix> {
        List {
            suc: Vec::with_capacity(nodes),
        }
    }

    /// Removes all nodes and edges from the list.
    pub fn clear(&mut self) {
        self.suc.clear()
    }

    /// Returns the number of edges in the list
    ///
    /// Computes in **O(|V|)** time.
    pub fn edge_count(&self) -> usize {
        self.suc.iter().map(|x| x.len()).sum()
    }

    /// Adds a new node to the list. This allocates a new `Vec` and then should
    /// run in amortized **O(1)** time.
    pub fn add_node(&mut self) -> NodeIndex<Ix> {
        let i = self.suc.len();
        self.suc.push(Vec::new());
        Ix::new(i)
    }

    /// Adds a new node to the list. This allocates a new `Vec` and then should
    /// run in amortized **O(1)** time.
    pub fn add_node_with_capacity(&mut self, successors: usize) -> NodeIndex<Ix> {
        let i = self.suc.len();
        self.suc.push(Vec::with_capacity(successors));
        Ix::new(i)
    }

    /// Adds a new node to the list by giving its list of successors and the corresponding
    /// weigths.
    pub fn add_node_from_edges<I: Iterator<Item = (NodeIndex<Ix>, E)>>(
        &mut self,
        edges: I,
    ) -> NodeIndex<Ix> {
        let i = self.suc.len();
        self.suc
            .push(edges.map(|(suc, weight)| WSuc { suc, weight }).collect());
        Ix::new(i)
    }

    /// Add an edge from `a` to `b` to the graph, with its associated
    /// data `weight`.
    ///
    /// Return the index of the new edge.
    ///
    /// Computes in **O(1)** time.
    ///
    /// **Panics** if the source node does not exist.<br>
    ///
    /// **Note:** `List` allows adding parallel (“duplicate”) edges. If you want
    /// to avoid this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead.
    #[track_caller]
    pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
        if b.index() >= self.suc.len() {
            panic!(
                "{} is not a valid node index for a {} nodes adjacency list",
                b.index(),
                self.suc.len()
            );
        }
        let row = &mut self.suc[a.index()];
        let rank = row.len();
        row.push(WSuc { suc: b, weight });
        EdgeIndex {
            from: a,
            successor_index: rank,
        }
    }

    fn get_edge(&self, e: EdgeIndex<Ix>) -> Option<&WSuc<E, Ix>> {
        self.suc
            .get(e.from.index())
            .and_then(|row| row.get(e.successor_index))
    }

    fn get_edge_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut WSuc<E, Ix>> {
        self.suc
            .get_mut(e.from.index())
            .and_then(|row| row.get_mut(e.successor_index))
    }

    /// Accesses the source and target of edge `e`
    ///
    /// Computes in **O(1)**
    pub fn edge_endpoints(&self, e: EdgeIndex<Ix>) -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)> {
        self.get_edge(e).map(|x| (e.from, x.suc))
    }

    pub fn edge_indices_from(&self, a: NodeIndex<Ix>) -> OutgoingEdgeIndices<Ix> {
        let proj: fn((usize, NodeIndex<Ix>)) -> EdgeIndex<Ix> =
            |(successor_index, from)| EdgeIndex {
                from,
                successor_index,
            };
        let iter = (0..(self.suc[a.index()].len()))
            .zip(core::iter::repeat(a))
            .map(proj);
        OutgoingEdgeIndices { iter }
    }

    /// Lookups whether there is an edge from `a` to `b`.
    ///
    /// Computes in **O(e')** time, where **e'** is the number of successors of `a`.
    pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
        match self.suc.get(a.index()) {
            None => false,
            Some(row) => row.iter().any(|x| x.suc == b),
        }
    }

    /// Lookups whether there is an edge from `a` to `b`.
    ///
    /// Computes in **O(e')** time, where **e'** is the number of successors of `a`.
    pub fn find_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<EdgeIndex<Ix>> {
        self.suc.get(a.index()).and_then(|row| {
            row.iter()
                .enumerate()
                .find(|(_, x)| x.suc == b)
                .map(|(i, _)| EdgeIndex {
                    from: a,
                    successor_index: i,
                })
        })
    }

    /// Returns an iterator over all node indices of the graph.
    ///
    /// Consuming the whole iterator take **O(|V|)**.
    pub fn node_indices(&self) -> NodeIndices<Ix> {
        NodeIndices {
            iter: (0..self.suc.len()).map(Ix::new),
        }
    }

    /// Returns an iterator over all edge indices of the graph.
    ///
    /// Consuming the whole iterator take **O(|V| + |E|)**.
    pub fn edge_indices(&self) -> EdgeIndices<'_, E, Ix> {
        EdgeIndices {
            rows: self.suc.iter().enumerate(),
            row_index: 0,
            row_len: 0,
            cur: 0,
        }
    }
}

/// A very simple adjacency list with no node or label weights.
pub type UnweightedList<Ix> = List<(), Ix>;

impl<E, Ix: IndexType> Build for List<E, Ix> {
    /// Adds a new node to the list. This allocates a new `Vec` and then should
    /// run in amortized **O(1)** time.
    fn add_node(&mut self, _weight: ()) -> NodeIndex<Ix> {
        self.add_node()
    }

    /// Add an edge from `a` to `b` to the graph, with its associated
    /// data `weight`.
    ///
    /// Return the index of the new edge.
    ///
    /// Computes in **O(1)** time.
    ///
    /// **Panics** if the source node does not exist.<br>
    ///
    /// **Note:** `List` allows adding parallel (“duplicate”) edges. If you want
    /// to avoid this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead.
    fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> Option<EdgeIndex<Ix>> {
        Some(self.add_edge(a, b, weight))
    }

    /// Updates or adds an edge from `a` to `b` to the graph, with its associated
    /// data `weight`.
    ///
    /// Return the index of the new edge.
    ///
    /// Computes in **O(e')** time, where **e'** is the number of successors of `a`.
    ///
    /// **Panics** if the source node does not exist.<br>
    fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
        let row = &mut self.suc[a.index()];
        for (i, info) in row.iter_mut().enumerate() {
            if info.suc == b {
                info.weight = weight;
                return EdgeIndex {
                    from: a,
                    successor_index: i,
                };
            }
        }
        let rank = row.len();
        row.push(WSuc { suc: b, weight });
        EdgeIndex {
            from: a,
            successor_index: rank,
        }
    }
}

impl<E, Ix> fmt::Debug for EdgeReferences<'_, E, Ix>
where
    E: fmt::Debug,
    Ix: IndexType,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut edge_list = f.debug_list();
        let iter: Self = self.clone();
        for e in iter {
            if core::mem::size_of::<E>() != 0 {
                edge_list.entry(&(
                    NoPretty((e.source().index(), e.target().index())),
                    e.weight(),
                ));
            } else {
                edge_list.entry(&NoPretty((e.source().index(), e.target().index())));
            }
        }
        edge_list.finish()
    }
}

impl<E, Ix> fmt::Debug for List<E, Ix>
where
    E: fmt::Debug,
    Ix: IndexType,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let mut fmt_struct = f.debug_struct("adj::List");
        fmt_struct.field("node_count", &self.node_count());
        fmt_struct.field("edge_count", &self.edge_count());
        if self.edge_count() > 0 {
            fmt_struct.field("edges", &self.edge_references());
        }
        fmt_struct.finish()
    }
}

impl<E, Ix> visit::GraphBase for List<E, Ix>
where
    Ix: IndexType,
{
    type NodeId = NodeIndex<Ix>;
    type EdgeId = EdgeIndex<Ix>;
}

impl<E, Ix> visit::Visitable for List<E, Ix>
where
    Ix: IndexType,
{
    type Map = FixedBitSet;
    fn visit_map(&self) -> FixedBitSet {
        FixedBitSet::with_capacity(self.node_count())
    }
    fn reset_map(&self, map: &mut Self::Map) {
        map.clear();
        map.grow(self.node_count());
    }
}

impl<E, Ix: IndexType> visit::IntoNodeIdentifiers for &List<E, Ix> {
    type NodeIdentifiers = NodeIndices<Ix>;
    fn node_identifiers(self) -> NodeIndices<Ix> {
        self.node_indices()
    }
}

impl<Ix: IndexType> visit::NodeRef for NodeIndex<Ix> {
    type NodeId = NodeIndex<Ix>;
    type Weight = ();
    fn id(&self) -> Self::NodeId {
        *self
    }
    fn weight(&self) -> &Self::Weight {
        &()
    }
}

impl<Ix: IndexType, E> visit::IntoNodeReferences for &List<E, Ix> {
    type NodeRef = NodeIndex<Ix>;
    type NodeReferences = NodeIndices<Ix>;
    fn node_references(self) -> Self::NodeReferences {
        self.node_indices()
    }
}

impl<E, Ix: IndexType> visit::Data for List<E, Ix> {
    type NodeWeight = ();
    type EdgeWeight = E;
}

impl<'a, E, Ix: IndexType> IntoNeighbors for &'a List<E, Ix> {
    type Neighbors = Neighbors<'a, E, Ix>;
    /// Returns an iterator of all nodes with an edge starting from `a`.
    /// Panics if `a` is out of bounds.
    /// Use [`List::edge_indices_from`] instead if you do not want to borrow the adjacency list while
    /// iterating.
    #[track_caller]
    fn neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors {
        let proj: fn(&WSuc<E, Ix>) -> NodeIndex<Ix> = |x| x.suc;
        let iter = self.suc[a.index()].iter().map(proj);
        Neighbors { iter }
    }
}

type SomeIter<'a, E, Ix> = core::iter::Map<
    core::iter::Zip<core::iter::Enumerate<RowIter<'a, E, Ix>>, core::iter::Repeat<Ix>>,
    fn(((usize, &'a WSuc<E, Ix>), Ix)) -> EdgeReference<'a, E, Ix>,
>;

iterator_wrap! {
impl (Iterator) for
/// An iterator over the [`EdgeReference`] of all the edges of the graph.
struct EdgeReferences<'a, E, Ix> where { Ix: IndexType }
item: EdgeReference<'a, E, Ix>,
iter: core::iter::FlatMap<
    core::iter::Enumerate<
        core::slice::Iter<'a, Row<E, Ix>>
    >,
    SomeIter<'a, E, Ix>,
    fn(
        (usize, &'a Vec<WSuc<E, Ix>>)
    ) -> SomeIter<'a, E, Ix>,
>,
}

impl<E, Ix: IndexType> Clone for EdgeReferences<'_, E, Ix> {
    fn clone(&self) -> Self {
        EdgeReferences {
            iter: self.iter.clone(),
        }
    }
}

fn proj1<E, Ix: IndexType>(
    ((successor_index, edge), from): ((usize, &WSuc<E, Ix>), Ix),
) -> EdgeReference<'_, E, Ix> {
    let id = EdgeIndex {
        from,
        successor_index,
    };
    EdgeReference { id, edge }
}
fn proj2<E, Ix: IndexType>((row_index, row): (usize, &Vec<WSuc<E, Ix>>)) -> SomeIter<'_, E, Ix> {
    row.iter()
        .enumerate()
        .zip(core::iter::repeat(Ix::new(row_index)))
        .map(proj1 as _)
}

impl<'a, Ix: IndexType, E> visit::IntoEdgeReferences for &'a List<E, Ix> {
    type EdgeRef = EdgeReference<'a, E, Ix>;
    type EdgeReferences = EdgeReferences<'a, E, Ix>;
    fn edge_references(self) -> Self::EdgeReferences {
        let iter = self.suc.iter().enumerate().flat_map(proj2 as _);
        EdgeReferences { iter }
    }
}

iterator_wrap! {
impl (Iterator) for
/// Iterator over the [`EdgeReference`] of the outgoing edges from a node.
#[derive(Debug, Clone)]
struct OutgoingEdgeReferences<'a, E, Ix> where { Ix: IndexType }
item: EdgeReference<'a, E, Ix>,
iter: SomeIter<'a, E, Ix>,
}

impl<'a, Ix: IndexType, E> visit::IntoEdges for &'a List<E, Ix> {
    type Edges = OutgoingEdgeReferences<'a, E, Ix>;
    fn edges(self, a: Self::NodeId) -> Self::Edges {
        let iter = self.suc[a.index()]
            .iter()
            .enumerate()
            .zip(core::iter::repeat(a))
            .map(proj1 as _);
        OutgoingEdgeReferences { iter }
    }
}

impl<E, Ix: IndexType> visit::GraphProp for List<E, Ix> {
    type EdgeType = crate::Directed;
    fn is_directed(&self) -> bool {
        true
    }
}

impl<E, Ix: IndexType> NodeCount for List<E, Ix> {
    /// Returns the number of nodes in the list
    ///
    /// Computes in **O(1)** time.
    fn node_count(&self) -> usize {
        self.suc.len()
    }
}

impl<E, Ix: IndexType> EdgeCount for List<E, Ix> {
    /// Returns the number of edges in the list
    ///
    /// Computes in **O(|V|)** time.
    fn edge_count(&self) -> usize {
        List::edge_count(self)
    }
}

impl<E, Ix: IndexType> visit::NodeIndexable for List<E, Ix> {
    fn node_bound(&self) -> usize {
        self.node_count()
    }
    #[inline]
    fn to_index(&self, a: Self::NodeId) -> usize {
        a.index()
    }
    #[inline]
    fn from_index(&self, i: usize) -> Self::NodeId {
        Ix::new(i)
    }
}

impl<E, Ix: IndexType> visit::NodeCompactIndexable for List<E, Ix> {}

impl<E, Ix: IndexType> DataMap for List<E, Ix> {
    fn node_weight(&self, n: Self::NodeId) -> Option<&()> {
        if n.index() < self.suc.len() {
            Some(&())
        } else {
            None
        }
    }

    /// Accesses the weight of edge `e`
    ///
    /// Computes in **O(1)**
    fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E> {
        self.get_edge(e).map(|x| &x.weight)
    }
}

impl<E, Ix: IndexType> DataMapMut for List<E, Ix> {
    fn node_weight_mut(&mut self, n: Self::NodeId) -> Option<&mut ()> {
        if n.index() < self.suc.len() {
            // A hack to produce a &'static mut ()
            // It does not actually allocate according to godbolt
            let b = Box::new(());
            Some(Box::leak(b))
        } else {
            None
        }
    }
    /// Accesses the weight of edge `e`
    ///
    /// Computes in **O(1)**
    fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E> {
        self.get_edge_mut(e).map(|x| &mut x.weight)
    }
}

/// The adjacency matrix for **List** is a bitmap that's computed by
/// `.adjacency_matrix()`.
impl<E, Ix> GetAdjacencyMatrix for List<E, Ix>
where
    Ix: IndexType,
{
    type AdjMatrix = FixedBitSet;

    fn adjacency_matrix(&self) -> FixedBitSet {
        let n = self.node_count();
        let mut matrix = FixedBitSet::with_capacity(n * n);
        for edge in self.edge_references() {
            let i = edge.source().index() * n + edge.target().index();
            matrix.put(i);
        }
        matrix
    }

    fn is_adjacent(&self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
        let n = self.node_count();
        let index = n * a.index() + b.index();
        matrix.contains(index)
    }
}

Coverage Report

Created: 2025-12-11 06:38

Line	Count	Source
1		//! Simple adjacency list.
2		use alloc::{boxed::Box, vec::Vec};
3		use core::{fmt, ops::Range};
4
5		use fixedbitset::FixedBitSet;
6
7		use crate::data::{Build, DataMap, DataMapMut};
8		use crate::iter_format::NoPretty;
9		use crate::visit::{
10		self, EdgeCount, EdgeRef, GetAdjacencyMatrix, IntoEdgeReferences, IntoNeighbors, NodeCount,
11		};
12
13		#[doc(no_inline)]
14		pub use crate::graph::{DefaultIx, IndexType};
15
16		/// Adjacency list node index type, a plain integer.
17		pub 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)]
21		pub struct EdgeIndex<Ix = DefaultIx>
22		where
23		Ix: IndexType,
24		{
25		/// Source of the edge.
26		from: NodeIndex<Ix>,
27		/// Index of the successor in the successor list.
28		successor_index: usize,
29		}
30
31		iterator_wrap! {
32		impl (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)]
37		struct OutgoingEdgeIndices <Ix> where { Ix: IndexType }
38		item: EdgeIndex<Ix>,
39		iter: core::iter::Map<core::iter::Zip<Range<usize>, core::iter::Repeat<NodeIndex<Ix>>>, fn((usize, NodeIndex<Ix>)) -> EdgeIndex<Ix>>,
40		}
41
42		/// Weighted successor
43		#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
44		struct WSuc<E, Ix: IndexType> {
45		/// Index of the successor.
46		suc: Ix,
47		/// Weight of the edge to `suc`.
48		weight: E,
49		}
50
51		/// One row of the adjacency list.
52		type Row<E, Ix> = Vec<WSuc<E, Ix>>;
53		type RowIter<'a, E, Ix> = core::slice::Iter<'a, WSuc<E, Ix>>;
54
55		iterator_wrap! {
56		impl (Iterator DoubleEndedIterator ExactSizeIterator) for
57		/// An iterator over the indices of the neighbors of a node.
58		#[derive(Debug, Clone)]
59		struct Neighbors<'a, E, Ix> where { Ix: IndexType }
60		item: NodeIndex<Ix>,
61		iter: 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)]
66		pub 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
73		impl<E, Ix: IndexType> Copy for EdgeReference<'_, E, Ix> {}
74		impl<E, Ix: IndexType> Clone for EdgeReference<'_, E, Ix> {
75	0	fn clone(&self) -> Self {
76	0	*self
77	0	}
78		}
79
80		impl<E, Ix: IndexType> visit::EdgeRef for EdgeReference<'_, E, Ix> {
81		type NodeId = NodeIndex<Ix>;
82		type EdgeId = EdgeIndex<Ix>;
83		type Weight = E;
84	0	fn source(&self) -> Self::NodeId {
85	0	self.id.from
86	0	}
87	0	fn target(&self) -> Self::NodeId {
88	0	self.edge.suc
89	0	}
90	0	fn id(&self) -> Self::EdgeId {
91	0	self.id
92	0	}
93	0	fn weight(&self) -> &Self::Weight {
94	0	&self.edge.weight
95	0	}
96		}
97
98		#[derive(Debug, Clone)]
99		pub 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
106		impl<E, Ix: IndexType> Iterator for EdgeIndices<'_, E, Ix> {
107		type Item = EdgeIndex<Ix>;
108	0	fn next(&mut self) -> Option<EdgeIndex<Ix>> {
109		loop {
110	0	if self.cur < self.row_len {
111	0	let res = self.cur;
112	0	self.cur += 1;
113	0	return Some(EdgeIndex {
114	0	from: Ix::new(self.row_index),
115	0	successor_index: res,
116	0	});
117		} else {
118	0	match self.rows.next() {
119	0	Some((index, row)) => {
120	0	self.row_index = index;
121	0	self.cur = 0;
122	0	self.row_len = row.len();
123	0	}
124	0	None => return None,
125		}
126		}
127		}
128	0	}
129		}
130
131		iterator_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)]
157		pub struct List<E, Ix = DefaultIx>
158		where
159		Ix: IndexType,
160		{
161		suc: Vec<Row<E, Ix>>,
162		}
163
164		impl<E, Ix: IndexType> List<E, Ix> {
165		/// Creates a new, empty adjacency list.
166	0	pub fn new() -> List<E, Ix> {
167	0	List { suc: Vec::new() }
168	0	}
169
170		/// Creates a new, empty adjacency list tailored for `nodes` nodes.
171	0	pub fn with_capacity(nodes: usize) -> List<E, Ix> {
172	0	List {
173	0	suc: Vec::with_capacity(nodes),
174	0	}
175	0	}
176
177		/// Removes all nodes and edges from the list.
178	0	pub fn clear(&mut self) {
179	0	self.suc.clear()
180	0	}
181
182		/// Returns the number of edges in the list
183		///
184		/// Computes in O(\|V\|) time.
185	0	pub fn edge_count(&self) -> usize {
186	0	self.suc.iter().map(\|x\| x.len()).sum()
187	0	}
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	0	pub fn add_node(&mut self) -> NodeIndex<Ix> {
192	0	let i = self.suc.len();
193	0	self.suc.push(Vec::new());
194	0	Ix::new(i)
195	0	}
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	0	pub fn add_node_with_capacity(&mut self, successors: usize) -> NodeIndex<Ix> {
200	0	let i = self.suc.len();
201	0	self.suc.push(Vec::with_capacity(successors));
202	0	Ix::new(i)
203	0	}
204
205		/// Adds a new node to the list by giving its list of successors and the corresponding
206		/// weigths.
207	0	pub fn add_node_from_edges<I: Iterator<Item = (NodeIndex<Ix>, E)>>(
208	0	&mut self,
209	0	edges: I,
210	0	) -> NodeIndex<Ix> {
211	0	let i = self.suc.len();
212	0	self.suc
213	0	.push(edges.map(\|(suc, weight)\| WSuc { suc, weight }).collect());
214	0	Ix::new(i)
215	0	}
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	0	pub fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
230	0	if b.index() >= self.suc.len() {
231	0	panic!(
232	0	"{} is not a valid node index for a {} nodes adjacency list",
233	0	b.index(),
234	0	self.suc.len()
235		);
236	0	}
237	0	let row = &mut self.suc[a.index()];
238	0	let rank = row.len();
239	0	row.push(WSuc { suc: b, weight });
240	0	EdgeIndex {
241	0	from: a,
242	0	successor_index: rank,
243	0	}
244	0	}
245
246	0	fn get_edge(&self, e: EdgeIndex<Ix>) -> Option<&WSuc<E, Ix>> {
247	0	self.suc
248	0	.get(e.from.index())
249	0	.and_then(\|row\| row.get(e.successor_index))
250	0	}
251
252	0	fn get_edge_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut WSuc<E, Ix>> {
253	0	self.suc
254	0	.get_mut(e.from.index())
255	0	.and_then(\|row\| row.get_mut(e.successor_index))
256	0	}
257
258		/// Accesses the source and target of edge `e`
259		///
260		/// Computes in O(1)
261	0	pub fn edge_endpoints(&self, e: EdgeIndex<Ix>) -> Option<(NodeIndex<Ix>, NodeIndex<Ix>)> {
262	0	self.get_edge(e).map(\|x\| (e.from, x.suc))
263	0	}
264
265	0	pub fn edge_indices_from(&self, a: NodeIndex<Ix>) -> OutgoingEdgeIndices<Ix> {
266	0	let proj: fn((usize, NodeIndex<Ix>)) -> EdgeIndex<Ix> =
267		\|(successor_index, from)\| EdgeIndex {
268	0	from,
269	0	successor_index,
270	0	};
271	0	let iter = (0..(self.suc[a.index()].len()))
272	0	.zip(core::iter::repeat(a))
273	0	.map(proj);
274	0	OutgoingEdgeIndices { iter }
275	0	}
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	0	pub fn contains_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
281	0	match self.suc.get(a.index()) {
282	0	None => false,
283	0	Some(row) => row.iter().any(\|x\| x.suc == b),
284		}
285	0	}
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	0	pub fn find_edge(&self, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> Option<EdgeIndex<Ix>> {
291	0	self.suc.get(a.index()).and_then(\|row\| {
292	0	row.iter()
293	0	.enumerate()
294	0	.find(\|(_, x)\| x.suc == b)
295	0	.map(\|(i, _)\| EdgeIndex {
296	0	from: a,
297	0	successor_index: i,
298	0	})
299	0	})
300	0	}
301
302		/// Returns an iterator over all node indices of the graph.
303		///
304		/// Consuming the whole iterator take O(\|V\|).
305	0	pub fn node_indices(&self) -> NodeIndices<Ix> {
306	0	NodeIndices {
307	0	iter: (0..self.suc.len()).map(Ix::new),
308	0	}
309	0	}
310
311		/// Returns an iterator over all edge indices of the graph.
312		///
313		/// Consuming the whole iterator take O(\|V\| + \|E\|).
314	0	pub fn edge_indices(&self) -> EdgeIndices<'_, E, Ix> {
315	0	EdgeIndices {
316	0	rows: self.suc.iter().enumerate(),
317	0	row_index: 0,
318	0	row_len: 0,
319	0	cur: 0,
320	0	}
321	0	}
322		}
323
324		/// A very simple adjacency list with no node or label weights.
325		pub type UnweightedList<Ix> = List<(), Ix>;
326
327		impl<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	0	fn add_node(&mut self, _weight: ()) -> NodeIndex<Ix> {
331	0	self.add_node()
332	0	}
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	0	fn add_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> Option<EdgeIndex<Ix>> {
346	0	Some(self.add_edge(a, b, weight))
347	0	}
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	0	fn update_edge(&mut self, a: NodeIndex<Ix>, b: NodeIndex<Ix>, weight: E) -> EdgeIndex<Ix> {
358	0	let row = &mut self.suc[a.index()];
359	0	for (i, info) in row.iter_mut().enumerate() {
360	0	if info.suc == b {
361	0	info.weight = weight;
362	0	return EdgeIndex {
363	0	from: a,
364	0	successor_index: i,
365	0	};
366	0	}
367		}
368	0	let rank = row.len();
369	0	row.push(WSuc { suc: b, weight });
370	0	EdgeIndex {
371	0	from: a,
372	0	successor_index: rank,
373	0	}
374	0	}
375		}
376
377		impl<E, Ix> fmt::Debug for EdgeReferences<'_, E, Ix>
378		where
379		E: fmt::Debug,
380		Ix: IndexType,
381		{
382	0	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
383	0	let mut edge_list = f.debug_list();
384	0	let iter: Self = self.clone();
385	0	for e in iter {
386	0	if core::mem::size_of::<E>() != 0 {
387	0	edge_list.entry(&(
388	0	NoPretty((e.source().index(), e.target().index())),
389	0	e.weight(),
390	0	));
391	0	} else {
392	0	edge_list.entry(&NoPretty((e.source().index(), e.target().index())));
393	0	}
394		}
395	0	edge_list.finish()
396	0	}
397		}
398
399		impl<E, Ix> fmt::Debug for List<E, Ix>
400		where
401		E: fmt::Debug,
402		Ix: IndexType,
403		{
404	0	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
405	0	let mut fmt_struct = f.debug_struct("adj::List");
406	0	fmt_struct.field("node_count", &self.node_count());
407	0	fmt_struct.field("edge_count", &self.edge_count());
408	0	if self.edge_count() > 0 {
409	0	fmt_struct.field("edges", &self.edge_references());
410	0	}
411	0	fmt_struct.finish()
412	0	}
413		}
414
415		impl<E, Ix> visit::GraphBase for List<E, Ix>
416		where
417		Ix: IndexType,
418		{
419		type NodeId = NodeIndex<Ix>;
420		type EdgeId = EdgeIndex<Ix>;
421		}
422
423		impl<E, Ix> visit::Visitable for List<E, Ix>
424		where
425		Ix: IndexType,
426		{
427		type Map = FixedBitSet;
428	0	fn visit_map(&self) -> FixedBitSet {
429	0	FixedBitSet::with_capacity(self.node_count())
430	0	}
431	0	fn reset_map(&self, map: &mut Self::Map) {
432	0	map.clear();
433	0	map.grow(self.node_count());
434	0	}
435		}
436
437		impl<E, Ix: IndexType> visit::IntoNodeIdentifiers for &List<E, Ix> {
438		type NodeIdentifiers = NodeIndices<Ix>;
439	0	fn node_identifiers(self) -> NodeIndices<Ix> {
440	0	self.node_indices()
441	0	}
442		}
443
444		impl<Ix: IndexType> visit::NodeRef for NodeIndex<Ix> {
445		type NodeId = NodeIndex<Ix>;
446		type Weight = ();
447	0	fn id(&self) -> Self::NodeId {
448	0	*self
449	0	}
450	0	fn weight(&self) -> &Self::Weight {
451	0	&()
452	0	}
453		}
454
455		impl<Ix: IndexType, E> visit::IntoNodeReferences for &List<E, Ix> {
456		type NodeRef = NodeIndex<Ix>;
457		type NodeReferences = NodeIndices<Ix>;
458	0	fn node_references(self) -> Self::NodeReferences {
459	0	self.node_indices()
460	0	}
461		}
462
463		impl<E, Ix: IndexType> visit::Data for List<E, Ix> {
464		type NodeWeight = ();
465		type EdgeWeight = E;
466		}
467
468		impl<'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	0	fn neighbors(self, a: NodeIndex<Ix>) -> Self::Neighbors {
476	0	let proj: fn(&WSuc<E, Ix>) -> NodeIndex<Ix> = \|x\| x.suc;
477	0	let iter = self.suc[a.index()].iter().map(proj);
478	0	Neighbors { iter }
479	0	}
480		}
481
482		type 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
487		iterator_wrap! {
488		impl (Iterator) for
489		/// An iterator over the [`EdgeReference`] of all the edges of the graph.
490		struct EdgeReferences<'a, E, Ix> where { Ix: IndexType }
491		item: EdgeReference<'a, E, Ix>,
492		iter: 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
503		impl<E, Ix: IndexType> Clone for EdgeReferences<'_, E, Ix> {
504	0	fn clone(&self) -> Self {
505	0	EdgeReferences {
506	0	iter: self.iter.clone(),
507	0	}
508	0	}
509		}
510
511	0	fn proj1<E, Ix: IndexType>(
512	0	((successor_index, edge), from): ((usize, &WSuc<E, Ix>), Ix),
513	0	) -> EdgeReference<'_, E, Ix> {
514	0	let id = EdgeIndex {
515	0	from,
516	0	successor_index,
517	0	};
518	0	EdgeReference { id, edge }
519	0	}
520	0	fn proj2<E, Ix: IndexType>((row_index, row): (usize, &Vec<WSuc<E, Ix>>)) -> SomeIter<'_, E, Ix> {
521	0	row.iter()
522	0	.enumerate()
523	0	.zip(core::iter::repeat(Ix::new(row_index)))
524	0	.map(proj1 as _)
525	0	}
526
527		impl<'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	0	fn edge_references(self) -> Self::EdgeReferences {
531	0	let iter = self.suc.iter().enumerate().flat_map(proj2 as _);
532	0	EdgeReferences { iter }
533	0	}
534		}
535
536		iterator_wrap! {
537		impl (Iterator) for
538		/// Iterator over the [`EdgeReference`] of the outgoing edges from a node.
539		#[derive(Debug, Clone)]
540		struct OutgoingEdgeReferences<'a, E, Ix> where { Ix: IndexType }
541		item: EdgeReference<'a, E, Ix>,
542		iter: SomeIter<'a, E, Ix>,
543		}
544
545		impl<'a, Ix: IndexType, E> visit::IntoEdges for &'a List<E, Ix> {
546		type Edges = OutgoingEdgeReferences<'a, E, Ix>;
547	0	fn edges(self, a: Self::NodeId) -> Self::Edges {
548	0	let iter = self.suc[a.index()]
549	0	.iter()
550	0	.enumerate()
551	0	.zip(core::iter::repeat(a))
552	0	.map(proj1 as _);
553	0	OutgoingEdgeReferences { iter }
554	0	}
555		}
556
557		impl<E, Ix: IndexType> visit::GraphProp for List<E, Ix> {
558		type EdgeType = crate::Directed;
559	0	fn is_directed(&self) -> bool {
560	0	true
561	0	}
562		}
563
564		impl<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	0	fn node_count(&self) -> usize {
569	0	self.suc.len()
570	0	}
571		}
572
573		impl<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	0	fn edge_count(&self) -> usize {
578	0	List::edge_count(self)
579	0	}
580		}
581
582		impl<E, Ix: IndexType> visit::NodeIndexable for List<E, Ix> {
583	0	fn node_bound(&self) -> usize {
584	0	self.node_count()
585	0	}
586		#[inline]
587	0	fn to_index(&self, a: Self::NodeId) -> usize {
588	0	a.index()
589	0	}
590		#[inline]
591	0	fn from_index(&self, i: usize) -> Self::NodeId {
592	0	Ix::new(i)
593	0	}
594		}
595
596		impl<E, Ix: IndexType> visit::NodeCompactIndexable for List<E, Ix> {}
597
598		impl<E, Ix: IndexType> DataMap for List<E, Ix> {
599	0	fn node_weight(&self, n: Self::NodeId) -> Option<&()> {
600	0	if n.index() < self.suc.len() {
601	0	Some(&())
602		} else {
603	0	None
604		}
605	0	}
606
607		/// Accesses the weight of edge `e`
608		///
609		/// Computes in O(1)
610	0	fn edge_weight(&self, e: EdgeIndex<Ix>) -> Option<&E> {
611	0	self.get_edge(e).map(\|x\| &x.weight)
612	0	}
613		}
614
615		impl<E, Ix: IndexType> DataMapMut for List<E, Ix> {
616	0	fn node_weight_mut(&mut self, n: Self::NodeId) -> Option<&mut ()> {
617	0	if n.index() < self.suc.len() {
618		// A hack to produce a &'static mut ()
619		// It does not actually allocate according to godbolt
620	0	let b = Box::new(());
621	0	Some(Box::leak(b))
622		} else {
623	0	None
624		}
625	0	}
626		/// Accesses the weight of edge `e`
627		///
628		/// Computes in O(1)
629	0	fn edge_weight_mut(&mut self, e: EdgeIndex<Ix>) -> Option<&mut E> {
630	0	self.get_edge_mut(e).map(\|x\| &mut x.weight)
631	0	}
632		}
633
634		/// The adjacency matrix for List is a bitmap that's computed by
635		/// `.adjacency_matrix()`.
636		impl<E, Ix> GetAdjacencyMatrix for List<E, Ix>
637		where
638		Ix: IndexType,
639		{
640		type AdjMatrix = FixedBitSet;
641
642	0	fn adjacency_matrix(&self) -> FixedBitSet {
643	0	let n = self.node_count();
644	0	let mut matrix = FixedBitSet::with_capacity(n * n);
645	0	for edge in self.edge_references() {
646	0	let i = edge.source().index() * n + edge.target().index();
647	0	matrix.put(i);
648	0	}
649	0	matrix
650	0	}
651
652	0	fn is_adjacent(&self, matrix: &FixedBitSet, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool {
653	0	let n = self.node_count();
654	0	let index = n * a.index() + b.index();
655	0	matrix.contains(index)
656	0	}
657		}