23365769388

Committed 20 Mar 2026 10:52PM UTC coverage: 68.228% (-3.0%) from 71.245%

Build # 23365769388

Build Type

push

github

Committed by

vigna

Commit Message

No le_bins,be_bins for webgraph

Coverage Stats

6655 of 9754 relevant lines covered (68.23%)

46582760.24 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

91.67

/webgraph/src/graphs/btree_graph.rs

/*
 * SPDX-FileCopyrightText: 2023-2025 Inria
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use crate::prelude::*;

use lender::prelude::*;
use std::{collections::BTreeMap, iter::FusedIterator};

/// A mutable [`LabeledRandomAccessGraph`] implementation based on a vector of
/// [`BTreeMap`].
///
/// This implementation is slower and uses more resources than a
/// [`LabeledVecGraph`](crate::graphs::vec_graph::LabeledVecGraph),
/// but it is more flexible as arcs can be added in any order.
///
/// By setting the feature `serde`, this struct can be serialized and
/// deserialized using [serde](https://crates.io/crates/serde).
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct LabeledBTreeGraph<L: Clone + 'static = ()> {
    /// The number of arcs in the graph.
    num_arcs: u64,
    /// For each node, its list of successors.
    succ: Vec<BTreeMap<usize, L>>,
}

impl<L: Clone + 'static> core::default::Default for LabeledBTreeGraph<L> {
    fn default() -> Self {
        Self::new()
    }
}

impl<L: Clone + 'static> LabeledBTreeGraph<L> {
    /// Creates a new empty graph.
    pub fn new() -> Self {
        Self {
            num_arcs: 0,
            succ: vec![],
        }
    }

    /// Creates a new empty graph with `n` nodes.
    pub fn empty(n: usize) -> Self {
        Self {
            num_arcs: 0,
            succ: Vec::from_iter((0..n).map(|_| BTreeMap::new())),
        }
    }

    /// Adds an isolated node to the graph and returns true if it is a new node.
    ///
    /// If the node index is greater than the current number of nodes,
    /// the missing nodes will be added (as isolated nodes).
    pub fn add_node(&mut self, node: usize) -> bool {
        let len = self.succ.len();
        self.succ.extend((len..=node).map(|_| BTreeMap::new()));
        len <= node
    }

    /// Adds a labeled arc to the graph and returns whether it is a new one.
    pub fn add_arc(&mut self, u: usize, v: usize, l: L) -> bool {
        let max = u.max(v);
        if max >= self.succ.len() {
            panic!(
                "Node {} does not exist (the graph has {} nodes)",
                max,
                self.succ.len(),
            );
        }
        let is_new_arc = self.succ[u].insert(v, l).is_none();
        self.num_arcs += is_new_arc as u64;
        is_new_arc
    }

    /// Removes an arc from the graph and returns whether it was present or not.
    pub fn remove_arc(&mut self, u: usize, v: usize) -> bool {
        let max = u.max(v);
        if max >= self.succ.len() {
            panic!(
                "Node {} does not exist (the graph has {} nodes)",
                max,
                self.succ.len(),
            );
        }
        let arc_existed = self.succ[u].remove(&v).is_some();
        self.num_arcs -= arc_existed as u64;
        arc_existed
    }

    /// Adds nodes and labeled successors from an [`IntoLender`] yielding a
    /// [`NodeLabelsLender`].
    pub fn add_lender<I: IntoLender>(&mut self, iter_nodes: I)
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
    {
        for_!( (node, succ) in iter_nodes {
            self.add_node(node);
            for (v, l) in succ {
                self.add_node(v);
                self.add_arc(node, v, l);
            }
        });
    }

    /// Creates a new graph from an [`IntoLender`] yielding a
    /// [`NodeLabelsLender`].
    pub fn from_lender<I: IntoLender>(iter_nodes: I) -> Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
    {
        let mut g = Self::new();
        g.add_lender(iter_nodes);
        g
    }

    /// Adds labeled arcs from an [`IntoIterator`], adding new nodes as needed.
    ///
    /// The items must be labeled pairs of the form `((usize, usize), l)` specifying an
    /// arc and its label.
    pub fn add_arcs(&mut self, arcs: impl IntoIterator<Item = ((usize, usize), L)>) {
        for ((u, v), l) in arcs {
            self.add_node(u);
            self.add_node(v);
            self.add_arc(u, v, l);
        }
    }

    /// Creates a new graph from an [`IntoIterator`].
    ///
    /// The items must be labeled pairs of the form `((usize, usize), l)` specifying an
    /// arc and its label.
    pub fn from_arcs(arcs: impl IntoIterator<Item = ((usize, usize), L)>) -> Self {
        let mut g = Self::new();
        g.add_arcs(arcs);
        g
    }

    /// Shrinks the capacity of the graph to fit its current size.
    ///
    /// # Implementation Notes
    ///
    /// This method just shrinks the capacity of the successor vector, as
    /// [`BTreeMap`] does not have a `shrink_to_fit` method.
    pub fn shrink_to_fit(&mut self) {
        self.succ.shrink_to_fit();
    }
}

impl<L: Clone + 'static> SequentialLabeling for LabeledBTreeGraph<L> {
    type Label = (usize, L);
    type Lender<'a>
        = LenderImpl<'a, Self>
    where
        Self: 'a;

    #[inline(always)]
    fn num_nodes(&self) -> usize {
        self.succ.len()
    }

    #[inline(always)]
    fn num_arcs_hint(&self) -> Option<u64> {
        Some(self.num_arcs())
    }

    #[inline(always)]
    fn iter_from(&self, from: usize) -> Self::Lender<'_> {
        LenderImpl {
            labeling: self,
            nodes: (from..self.num_nodes()),
        }
    }
}

/// Convenience implementation that makes it possible to iterate
/// over the graph using the [`for_`] macro
/// (see the [crate documentation](crate)).
impl<'a, L: Clone + 'static> IntoLender for &'a LabeledBTreeGraph<L> {
    type Lender = <LabeledBTreeGraph<L> as SequentialLabeling>::Lender<'a>;

    #[inline(always)]
    fn into_lender(self) -> Self::Lender {
        self.iter()
    }
}

impl<L: Clone + 'static> LabeledSequentialGraph<L> for LabeledBTreeGraph<L> {}

impl<L: Clone + 'static> RandomAccessLabeling for LabeledBTreeGraph<L> {
    type Labels<'succ>
        = LabeledSucc<'succ, L>
    where
        L: 'succ;
    #[inline(always)]
    fn num_arcs(&self) -> u64 {
        self.num_arcs
    }

    #[inline(always)]
    fn outdegree(&self, node: usize) -> usize {
        self.succ[node].len()
    }

    #[inline(always)]
    fn labels(&self, node: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {
        LabeledSucc(self.succ[node].iter())
    }
}

impl<L: Clone + 'static> LabeledRandomAccessGraph<L> for LabeledBTreeGraph<L> {}

impl<L: Clone + Sync> SplitLabeling for LabeledBTreeGraph<L> {
    type SplitLender<'a>
        = split::ra::Lender<'a, LabeledBTreeGraph<L>>
    where
        Self: 'a;

    type IntoIterator<'a>
        = split::ra::IntoIterator<'a, LabeledBTreeGraph<L>>
    where
        Self: 'a;

    fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {
        split::ra::Iter::new(self, cutpoints)
    }
}

/// A mutable [`RandomAccessGraph`] implementation based on a vector of
/// [`BTreeMap`].
///
/// This implementation is slower and uses more resources than a [`VecGraph`],
/// but it is more flexible as arcs can be added in any order.
///
/// By setting the feature `serde`, this struct can be serialized and
/// deserialized using [serde](https://crates.io/crates/serde).
///
/// # Implementation Notes
///
/// This is just a newtype for a [`LabeledBTreeGraph`] with
/// [`()`](https://doc.rust-lang.org/std/primitive.unit.html) labels. All
/// mutation methods are delegated.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct BTreeGraph(LabeledBTreeGraph<()>);

impl BTreeGraph {
    /// Creates a new empty graph.
    pub fn new() -> Self {
        Self(LabeledBTreeGraph::new())
    }

    /// Creates a new empty graph with `n` nodes.
    pub fn empty(n: usize) -> Self {
        LabeledBTreeGraph::empty(n).into()
    }

    /// Adds an isolated node to the graph and returns true if it is a new node.
    pub fn add_node(&mut self, node: usize) -> bool {
        self.0.add_node(node)
    }

    /// Adds an arc to the graph and returns whether it is a new one.
    pub fn add_arc(&mut self, u: usize, v: usize) -> bool {
        self.0.add_arc(u, v, ())
    }

    /// Adds nodes and successors from an [`IntoLender`] yielding a
    /// [`NodeLabelsLender`].
    pub fn add_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
    {
        self.0.add_lender(UnitLender(iter_nodes.into_lender()));
        self
    }

    /// Creates a new graph from an [`IntoLender`] yielding a
    /// [`NodeLabelsLender`].
    pub fn from_lender<I: IntoLender>(iter_nodes: I) -> Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
    {
        let mut g = Self::new();
        g.add_lender(iter_nodes);
        g
    }

    /// Adds arcs from an [`IntoIterator`], adding new nodes as needed.
    ///
    /// The items must be pairs of the form `(usize, usize)` specifying an arc.
    pub fn add_arcs(&mut self, arcs: impl IntoIterator<Item = (usize, usize)>) {
        self.0.add_arcs(arcs.into_iter().map(|pair| (pair, ())));
    }

    /// Creates a new graph from an [`IntoIterator`].
    ///
    /// The items must be pairs of the form `(usize, usize)` specifying
    /// an arc.
    pub fn from_arcs(arcs: impl IntoIterator<Item = (usize, usize)>) -> Self {
        let mut g = Self::new();
        g.add_arcs(arcs);
        g
    }

    /// Shrinks the capacity of the graph to fit its current size.
    ///
    /// # Implementation Notes
    ///
    /// This method just shrinks the capacity of the successor vector, as
    /// [`BTreeMap`] does not have a `shrink_to_fit` method.
    pub fn shrink_to_fit(&mut self) {
        self.0.shrink_to_fit();
    }
}

/// Convenience implementation that makes it possible to iterate
/// over the graph using the [`for_`] macro
/// (see the [crate documentation](crate)).
impl<'a> IntoLender for &'a BTreeGraph {
    type Lender = <BTreeGraph as SequentialLabeling>::Lender<'a>;

    #[inline(always)]
    fn into_lender(self) -> Self::Lender {
        self.iter()
    }
}

impl SequentialLabeling for BTreeGraph {
    type Label = usize;
    type Lender<'a>
        = LenderImpl<'a, Self>
    where
        Self: 'a;

    #[inline(always)]
    fn num_nodes(&self) -> usize {
        self.0.succ.len()
    }

    #[inline(always)]
    fn num_arcs_hint(&self) -> Option<u64> {
        Some(self.num_arcs())
    }

    #[inline(always)]
    fn iter_from(&self, from: usize) -> Self::Lender<'_> {
        LenderImpl {
            labeling: self,
            nodes: (from..self.num_nodes()),
        }
    }
}

impl SequentialGraph for BTreeGraph {}

impl RandomAccessLabeling for BTreeGraph {
    type Labels<'succ> = Succ<'succ>;

    #[inline(always)]
    fn num_arcs(&self) -> u64 {
        self.0.num_arcs
    }

    #[inline(always)]
    fn outdegree(&self, node: usize) -> usize {
        self.0.succ[node].len()
    }

    #[inline(always)]
    fn labels(&self, node: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {
        Succ(self.0.succ[node].keys().copied())
    }
}

impl RandomAccessGraph for BTreeGraph {}

impl From<LabeledBTreeGraph<()>> for BTreeGraph {
    fn from(g: LabeledBTreeGraph<()>) -> Self {
        BTreeGraph(g)
    }
}

#[doc(hidden)]
#[repr(transparent)]
pub struct LabeledSucc<'a, L: Clone + 'static>(std::collections::btree_map::Iter<'a, usize, L>);

// SAFETY: successors are stored in a BTreeMap, which iterates in sorted order.
unsafe impl<L: Clone + 'static> SortedIterator for LabeledSucc<'_, L> {}

impl<L: Clone + 'static> Iterator for LabeledSucc<'_, L> {
    type Item = (usize, L);
    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next().map(|(succ, labels)| (*succ, labels.clone()))
    }

    #[inline(always)]
    fn count(self) -> usize {
        self.len()
    }
}

impl<L: Clone + 'static> ExactSizeIterator for LabeledSucc<'_, L> {
    #[inline(always)]
    fn len(&self) -> usize {
        self.0.len()
    }
}

impl<L: Clone + 'static> FusedIterator for LabeledSucc<'_, L> {}

#[doc(hidden)]
#[repr(transparent)]
pub struct Succ<'succ>(core::iter::Copied<std::collections::btree_map::Keys<'succ, usize, ()>>);

// SAFETY: successors are stored in a BTreeMap, which iterates in sorted order.
unsafe impl SortedIterator for Succ<'_> {}

impl Iterator for Succ<'_> {
    type Item = usize;
    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }

    #[inline(always)]
    fn count(self) -> usize {
        self.len()
    }
}

impl ExactSizeIterator for Succ<'_> {
    #[inline(always)]
    fn len(&self) -> usize {
        self.0.len()
    }
}

impl FusedIterator for Succ<'_> {}

impl SplitLabeling for BTreeGraph {
    type SplitLender<'a>
        = split::ra::Lender<'a, BTreeGraph>
    where
        Self: 'a;

    type IntoIterator<'a>
        = split::ra::IntoIterator<'a, BTreeGraph>
    where
        Self: 'a;

    fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {
        split::ra::Iter::new(self, cutpoints)
    }
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test_btree_graph() {
        let mut arcs = vec![
            ((0, 1), Some(1.0)),
            ((0, 2), None),
            ((1, 2), Some(2.0)),
            ((2, 4), Some(f64::INFINITY)),
            ((3, 4), Some(f64::NEG_INFINITY)),
            ((1, 3), Some(f64::NAN)),
        ];
        let g = LabeledBTreeGraph::<_>::from_arcs(arcs.iter().copied());
        assert_ne!(
            g, g,
            "The label contains a NaN which is not equal to itself so the graph must be not equal to itself"
        );

        arcs.pop();
        let g = LabeledBTreeGraph::<_>::from_arcs(arcs);
        assert_eq!(g, g, "Without NaN the graph should be equal to itself");
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2023-2025 Inria
3	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	use crate::prelude::*;
9
10	use lender::prelude::*;
11	use std::{collections::BTreeMap, iter::FusedIterator};
12
13	/// A mutable [`LabeledRandomAccessGraph`] implementation based on a vector of
14	/// [`BTreeMap`].
15	///
16	/// This implementation is slower and uses more resources than a
17	/// [`LabeledVecGraph`](crate::graphs::vec_graph::LabeledVecGraph),
18	/// but it is more flexible as arcs can be added in any order.
19	///
20	/// By setting the feature `serde`, this struct can be serialized and
21	/// deserialized using [serde](https://crates.io/crates/serde).
22	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
23	#[derive(Clone, Debug, PartialEq, Eq)]
24	pub struct LabeledBTreeGraph<L: Clone + 'static = ()> {
25	/// The number of arcs in the graph.
26	num_arcs: u64,
27	/// For each node, its list of successors.
28	succ: Vec<BTreeMap<usize, L>>,
29	}
30
31	impl<L: Clone + 'static> core::default::Default for LabeledBTreeGraph<L> {
32	fn default() -> Self {	1✔
33	Self::new()	1✔
34	}
35	}
36
37	impl<L: Clone + 'static> LabeledBTreeGraph<L> {
38	/// Creates a new empty graph.
39	pub fn new() -> Self {	4,920✔
40	Self {
41	num_arcs: 0,
42	succ: vec![],	4,920✔
43	}
44	}
45
46	/// Creates a new empty graph with `n` nodes.
47	pub fn empty(n: usize) -> Self {	5✔
48	Self {
49	num_arcs: 0,
50	succ: Vec::from_iter((0..n).map(\|_\| BTreeMap::new())),	40✔
51	}
52	}
53
54	/// Adds an isolated node to the graph and returns true if it is a new node.
55	///
56	/// If the node index is greater than the current number of nodes,
57	/// the missing nodes will be added (as isolated nodes).
58	pub fn add_node(&mut self, node: usize) -> bool {	20,125✔
59	let len = self.succ.len();	60,375✔
60	self.succ.extend((len..=node).map(\|_\| BTreeMap::new()));	472,684✔
61	len <= node	20,125✔
62	}
63
64	/// Adds a labeled arc to the graph and returns whether it is a new one.
65	pub fn add_arc(&mut self, u: usize, v: usize, l: L) -> bool {	1,731,707✔
66	let max = u.max(v);	6,926,828✔
67	if max >= self.succ.len() {	3,463,414✔
68	panic!(	10✔
69	"Node {} does not exist (the graph has {} nodes)",	×
70	max,	×
71	self.succ.len(),	20✔
72	);
73	}
74	let is_new_arc = self.succ[u].insert(v, l).is_none();	8,658,485✔
75	self.num_arcs += is_new_arc as u64;	1,731,697✔
76	is_new_arc	1,731,697✔
77	}
78
79	/// Removes an arc from the graph and returns whether it was present or not.
80	pub fn remove_arc(&mut self, u: usize, v: usize) -> bool {	3✔
81	let max = u.max(v);	12✔
82	if max >= self.succ.len() {	6✔
83	panic!(	1✔
84	"Node {} does not exist (the graph has {} nodes)",	×
85	max,	×
86	self.succ.len(),	2✔
87	);
88	}
89	let arc_existed = self.succ[u].remove(&v).is_some();	8✔
90	self.num_arcs -= arc_existed as u64;	2✔
91	arc_existed	2✔
92	}
93
94	/// Adds nodes and labeled successors from an [`IntoLender`] yielding a
95	/// [`NodeLabelsLender`].
96	pub fn add_lender<I: IntoLender>(&mut self, iter_nodes: I)	7✔
97	where
98	I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
99	{
100	for_!( (node, succ) in iter_nodes {	445✔
101	self.add_node(node);	657✔
102	for (v, l) in succ {	6,384✔
103	self.add_node(v);	8,220✔
104	self.add_arc(node, v, l);	8,220✔
105	}
106	});
107	}
108
109	/// Creates a new graph from an [`IntoLender`] yielding a
110	/// [`NodeLabelsLender`].
111	pub fn from_lender<I: IntoLender>(iter_nodes: I) -> Self	3✔
112	where
113	I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
114	{
115	let mut g = Self::new();	6✔
116	g.add_lender(iter_nodes);	9✔
117	g	3✔
118	}
119
120	/// Adds labeled arcs from an [`IntoIterator`], adding new nodes as needed.
121	///
122	/// The items must be labeled pairs of the form `((usize, usize), l)` specifying an
123	/// arc and its label.
124	pub fn add_arcs(&mut self, arcs: impl IntoIterator<Item = ((usize, usize), L)>) {	4,369✔
125	for ((u, v), l) in arcs {	19,985✔
126	self.add_node(u);	15,616✔
127	self.add_node(v);	15,616✔
128	self.add_arc(u, v, l);	15,616✔
129	}
130	}
131
132	/// Creates a new graph from an [`IntoIterator`].
133	///
134	/// The items must be labeled pairs of the form `((usize, usize), l)` specifying an
135	/// arc and its label.
136	pub fn from_arcs(arcs: impl IntoIterator<Item = ((usize, usize), L)>) -> Self {	10✔
137	let mut g = Self::new();	20✔
138	g.add_arcs(arcs);	30✔
139	g	10✔
140	}
141
142	/// Shrinks the capacity of the graph to fit its current size.
143	///
144	/// # Implementation Notes
145	///
146	/// This method just shrinks the capacity of the successor vector, as
147	/// [`BTreeMap`] does not have a `shrink_to_fit` method.
148	pub fn shrink_to_fit(&mut self) {	5✔
149	self.succ.shrink_to_fit();	10✔
150	}
151	}
152
153	impl<L: Clone + 'static> SequentialLabeling for LabeledBTreeGraph<L> {
154	type Label = (usize, L);
155	type Lender<'a>
156	= LenderImpl<'a, Self>
157	where
158	Self: 'a;
159
160	#[inline(always)]
161	fn num_nodes(&self) -> usize {	5✔
162	self.succ.len()	10✔
163	}
164
165	#[inline(always)]
166	fn num_arcs_hint(&self) -> Option<u64> {	1✔
167	Some(self.num_arcs())	1✔
168	}
169
170	#[inline(always)]
171	fn iter_from(&self, from: usize) -> Self::Lender<'_> {	8✔
172	LenderImpl {
173	labeling: self,
174	nodes: (from..self.num_nodes()),	16✔
175	}
176	}
177	}
178
179	/// Convenience implementation that makes it possible to iterate
180	/// over the graph using the [`for_`] macro
181	/// (see the [crate documentation](crate)).
182	impl<'a, L: Clone + 'static> IntoLender for &'a LabeledBTreeGraph<L> {
183	type Lender = <LabeledBTreeGraph<L> as SequentialLabeling>::Lender<'a>;
184
185	#[inline(always)]
186	fn into_lender(self) -> Self::Lender {	1✔
187	self.iter()	2✔
188	}
189	}
190
191	impl<L: Clone + 'static> LabeledSequentialGraph<L> for LabeledBTreeGraph<L> {}
192
193	impl<L: Clone + 'static> RandomAccessLabeling for LabeledBTreeGraph<L> {
194	type Labels<'succ>
195	= LabeledSucc<'succ, L>
196	where
197	L: 'succ;
198	#[inline(always)]
199	fn num_arcs(&self) -> u64 {	6✔
200	self.num_arcs	6✔
201	}
202
203	#[inline(always)]
204	fn outdegree(&self, node: usize) -> usize {	3✔
205	self.succ[node].len()	6✔
206	}
207
208	#[inline(always)]
209	fn labels(&self, node: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {	28✔
210	LabeledSucc(self.succ[node].iter())	28✔
211	}
212	}
213
214	impl<L: Clone + 'static> LabeledRandomAccessGraph<L> for LabeledBTreeGraph<L> {}
215
216	impl<L: Clone + Sync> SplitLabeling for LabeledBTreeGraph<L> {
217	type SplitLender<'a>
218	= split::ra::Lender<'a, LabeledBTreeGraph<L>>
219	where
220	Self: 'a;
221
222	type IntoIterator<'a>
223	= split::ra::IntoIterator<'a, LabeledBTreeGraph<L>>
224	where
225	Self: 'a;
226
227	fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {	×
228	split::ra::Iter::new(self, cutpoints)	×
229	}
230	}
231
232	/// A mutable [`RandomAccessGraph`] implementation based on a vector of
233	/// [`BTreeMap`].
234	///
235	/// This implementation is slower and uses more resources than a [`VecGraph`],
236	/// but it is more flexible as arcs can be added in any order.
237	///
238	/// By setting the feature `serde`, this struct can be serialized and
239	/// deserialized using [serde](https://crates.io/crates/serde).
240	///
241	/// # Implementation Notes
242	///
243	/// This is just a newtype for a [`LabeledBTreeGraph`] with
244	/// [`()`](https://doc.rust-lang.org/std/primitive.unit.html) labels. All
245	/// mutation methods are delegated.
246	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
247	#[derive(Clone, Debug, Default, PartialEq, Eq)]
248	pub struct BTreeGraph(LabeledBTreeGraph<()>);
249
250	impl BTreeGraph {
251	/// Creates a new empty graph.
252	pub fn new() -> Self {	4,905✔
253	Self(LabeledBTreeGraph::new())	4,905✔
254	}
255
256	/// Creates a new empty graph with `n` nodes.
257	pub fn empty(n: usize) -> Self {	5✔
258	LabeledBTreeGraph::empty(n).into()	15✔
259	}
260
261	/// Adds an isolated node to the graph and returns true if it is a new node.
262	pub fn add_node(&mut self, node: usize) -> bool {	490✔
263	self.0.add_node(node)	1,470✔
264	}
265
266	/// Adds an arc to the graph and returns whether it is a new one.
267	pub fn add_arc(&mut self, u: usize, v: usize) -> bool {	1,717,300✔
268	self.0.add_arc(u, v, ())	8,586,500✔
269	}
270
271	/// Adds nodes and successors from an [`IntoLender`] yielding a
272	/// [`NodeLabelsLender`].
273	pub fn add_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self	4✔
274	where
275	I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
276	{
277	self.0.add_lender(UnitLender(iter_nodes.into_lender()));	12✔
278	self	4✔
279	}
280
281	/// Creates a new graph from an [`IntoLender`] yielding a
282	/// [`NodeLabelsLender`].
283	pub fn from_lender<I: IntoLender>(iter_nodes: I) -> Self	4✔
284	where
285	I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
286	{
287	let mut g = Self::new();	8✔
288	g.add_lender(iter_nodes);	12✔
289	g	4✔
290	}
291
292	/// Adds arcs from an [`IntoIterator`], adding new nodes as needed.
293	///
294	/// The items must be pairs of the form `(usize, usize)` specifying an arc.
295	pub fn add_arcs(&mut self, arcs: impl IntoIterator<Item = (usize, usize)>) {	4,359✔
296	self.0.add_arcs(arcs.into_iter().map(\|pair\| (pair, ())));	29,535✔
297	}
298
299	/// Creates a new graph from an [`IntoIterator`].
300	///
301	/// The items must be pairs of the form `(usize, usize)` specifying
302	/// an arc.
303	pub fn from_arcs(arcs: impl IntoIterator<Item = (usize, usize)>) -> Self {	4,358✔
304	let mut g = Self::new();	8,716✔
305	g.add_arcs(arcs);	13,074✔
306	g	4,358✔
307	}
308
309	/// Shrinks the capacity of the graph to fit its current size.
310	///
311	/// # Implementation Notes
312	///
313	/// This method just shrinks the capacity of the successor vector, as
314	/// [`BTreeMap`] does not have a `shrink_to_fit` method.
315	pub fn shrink_to_fit(&mut self) {	5✔
316	self.0.shrink_to_fit();	10✔
317	}
318	}
319
320	/// Convenience implementation that makes it possible to iterate
321	/// over the graph using the [`for_`] macro
322	/// (see the [crate documentation](crate)).
323	impl<'a> IntoLender for &'a BTreeGraph {
324	type Lender = <BTreeGraph as SequentialLabeling>::Lender<'a>;
325
326	#[inline(always)]
327	fn into_lender(self) -> Self::Lender {	1✔
328	self.iter()	2✔
329	}
330	}
331
332	impl SequentialLabeling for BTreeGraph {
333	type Label = usize;
334	type Lender<'a>
335	= LenderImpl<'a, Self>
336	where
337	Self: 'a;
338
339	#[inline(always)]
340	fn num_nodes(&self) -> usize {	637,190✔
341	self.0.succ.len()	1,274,380✔
342	}
343
344	#[inline(always)]
345	fn num_arcs_hint(&self) -> Option<u64> {	1✔
346	Some(self.num_arcs())	1✔
347	}
348
349	#[inline(always)]
350	fn iter_from(&self, from: usize) -> Self::Lender<'_> {	2,501,385✔
351	LenderImpl {
352	labeling: self,
353	nodes: (from..self.num_nodes()),	5,002,770✔
354	}
355	}
356	}
357
358	impl SequentialGraph for BTreeGraph {}
359
360	impl RandomAccessLabeling for BTreeGraph {
361	type Labels<'succ> = Succ<'succ>;
362
363	#[inline(always)]
364	fn num_arcs(&self) -> u64 {	26,750✔
365	self.0.num_arcs	26,750✔
366	}
367
368	#[inline(always)]
369	fn outdegree(&self, node: usize) -> usize {	730,635✔
370	self.0.succ[node].len()	1,461,270✔
371	}
372
373	#[inline(always)]
374	fn labels(&self, node: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {	249,980,165✔
375	Succ(self.0.succ[node].keys().copied())	499,960,330✔
376	}
377	}
378
379	impl RandomAccessGraph for BTreeGraph {}
380
381	impl From<LabeledBTreeGraph<()>> for BTreeGraph {
382	fn from(g: LabeledBTreeGraph<()>) -> Self {	5✔
383	BTreeGraph(g)	5✔
384	}
385	}
386
387	#[doc(hidden)]
388	#[repr(transparent)]
389	pub struct LabeledSucc<'a, L: Clone + 'static>(std::collections::btree_map::Iter<'a, usize, L>);
390
391	// SAFETY: successors are stored in a BTreeMap, which iterates in sorted order.
392	unsafe impl<L: Clone + 'static> SortedIterator for LabeledSucc<'_, L> {}
393
394	impl<L: Clone + 'static> Iterator for LabeledSucc<'_, L> {
395	type Item = (usize, L);
396	#[inline(always)]
397	fn next(&mut self) -> Option<Self::Item> {	52✔
398	self.0.next().map(\|(succ, labels)\| (*succ, labels.clone()))	246✔
399	}
400
401	#[inline(always)]
402	fn count(self) -> usize {	×
403	self.len()	×
404	}
405	}
406
407	impl<L: Clone + 'static> ExactSizeIterator for LabeledSucc<'_, L> {
408	#[inline(always)]
409	fn len(&self) -> usize {	×
410	self.0.len()	×
411	}
412	}
413
414	impl<L: Clone + 'static> FusedIterator for LabeledSucc<'_, L> {}
415
416	#[doc(hidden)]
417	#[repr(transparent)]
418	pub struct Succ<'succ>(core::iter::Copied<std::collections::btree_map::Keys<'succ, usize, ()>>);
419
420	// SAFETY: successors are stored in a BTreeMap, which iterates in sorted order.
421	unsafe impl SortedIterator for Succ<'_> {}
422
423	impl Iterator for Succ<'_> {
424	type Item = usize;
425	#[inline(always)]
426	fn next(&mut self) -> Option<Self::Item> {	1,395,440,690✔
427	self.0.next()	2,147,483,647✔
428	}
429
430	#[inline(always)]
431	fn count(self) -> usize {	365,290✔
432	self.len()	730,580✔
433	}
434	}
435
436	impl ExactSizeIterator for Succ<'_> {
437	#[inline(always)]
438	fn len(&self) -> usize {	365,295✔
439	self.0.len()	730,590✔
440	}
441	}
442
443	impl FusedIterator for Succ<'_> {}
444
445	impl SplitLabeling for BTreeGraph {
446	type SplitLender<'a>
447	= split::ra::Lender<'a, BTreeGraph>
448	where
449	Self: 'a;
450
451	type IntoIterator<'a>
452	= split::ra::IntoIterator<'a, BTreeGraph>
453	where
454	Self: 'a;
455
456	fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {	622,080✔
457	split::ra::Iter::new(self, cutpoints)	1,866,240✔
458	}
459	}
460
461	#[cfg(test)]
462	mod test {
463	use super::*;
464	#[test]
465	fn test_btree_graph() {
466	let mut arcs = vec![
467	((0, 1), Some(1.0)),
468	((0, 2), None),
469	((1, 2), Some(2.0)),
470	((2, 4), Some(f64::INFINITY)),
471	((3, 4), Some(f64::NEG_INFINITY)),
472	((1, 3), Some(f64::NAN)),
473	];
474	let g = LabeledBTreeGraph::<_>::from_arcs(arcs.iter().copied());
475	assert_ne!(
476	g, g,
477	"The label contains a NaN which is not equal to itself so the graph must be not equal to itself"
478	);
479
480	arcs.pop();
481	let g = LabeledBTreeGraph::<_>::from_arcs(arcs);
482	assert_eq!(g, g, "Without NaN the graph should be equal to itself");
483	}
484	}

vigna / webgraph-rs / 23365769388

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous