22350210654

Committed 24 Feb 2026 12:10PM UTC coverage: 71.503% (-0.2%) from 71.724%

Build # 22350210654

Build Type

push

github

Committed by

vigna

Commit Message

code_to_str now returns None instead of panicking

Coverage Stats

10 of 33 new or added lines in 6 files covered. (30.3%)

5 existing lines in 1 file now uncovered.

6278 of 8780 relevant lines covered (71.5%)

51288774.37 hits per line

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

92.78

/webgraph/src/visits/breadth_first/seq.rs

/*
 * SPDX-FileCopyrightText: 2024 Matteo Dell'Acqua
 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
 * SPDX-FileCopyrightText: 2025 Fontana Tommaso
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use crate::traits::{RandomAccessGraph, RandomAccessLabeling};
use crate::visits::{
    Sequential,
    breadth_first::{EventPred, FilterArgsPred},
};
use anyhow::Result;
use nonmax::NonMaxUsize;
use std::iter::FusedIterator;
use std::{collections::VecDeque, ops::ControlFlow, ops::ControlFlow::Continue};
use sux::bits::BitVec;
use sux::traits::BitVecOpsMut;

/// A sequential breadth-first visit.
///
/// This implementation uses an algorithm that is slightly different from the
/// classical textbook algorithm, as we do not store parents or distances of the
/// nodes from the root: Parents and distances are computed on the fly and
/// passed to the callback function by visiting nodes when they are discovered,
/// rather than when they are extracted from the queue.
///
/// This approach requires inserting a level separator between nodes at
/// different distances: to obtain this result in a compact way, nodes are
/// represented using [`NonMaxUsize`], so the `None` variant of
/// `Option<NonMaxUsize>` can be used as a separator.
///
/// # Examples
///
/// Let's compute the distances from 0:
///
/// ```
/// use webgraph::visits::*;
/// use webgraph::graphs::vec_graph::VecGraph;
/// use webgraph::labels::proj::Left;
/// use std::ops::ControlFlow::Continue;
/// use no_break::NoBreak;
///
/// let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 0), (1, 3)]);
/// let mut visit = breadth_first::Seq::new(&graph);
/// let mut d = [0; 4];
/// visit.visit(
///     [0],
///     |event| {
///          // Set distance from 0
///          if let breadth_first::EventPred::Visit { node, distance, .. } = event {
///              d[node] = distance;
///          }
///          Continue(())
///     },
/// ).continue_value_no_break();
///
/// assert_eq!(d, [0, 1, 2, 2]);
/// ```
///
/// Here instead we compute the size of the ball of radius two around node 0: we
/// count nodes in the filter function, rather than as the result of an event,
/// to avoid adding them to the queue. In this way, node at distance two are
/// counted but not included in the queue, as it would happen if we were
/// counting during an [`EventPred::Visit`] event.
///
/// ```
/// use std::convert::Infallible;
/// use webgraph::visits::*;
/// use webgraph::graphs::vec_graph::VecGraph;
/// use webgraph::labels::proj::Left;
/// use std::ops::ControlFlow::Continue;
/// use no_break::NoBreak;
///
/// let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4)]);
/// let mut visit = breadth_first::Seq::new(&graph);
/// let mut count = 0;
/// visit.visit_filtered(
///     [0],
///     |event| { Continue(()) },
///     |breadth_first::FilterArgsPred { distance, .. }| {
///         if distance > 2 {
///             false
///         } else {
///             count += 1;
///             true
///         }
///     },
/// ).continue_value_no_break();
/// assert_eq!(count, 3);
/// ```
///
/// The visit also implements the [`IntoIterator`] trait, so it can be used
/// in a `for` loop to iterate over all nodes in the order they are visited:
///
/// ```rust
/// use webgraph::visits::*;
/// use webgraph::graphs::vec_graph::VecGraph;
///
/// let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4)]);
/// for event in &mut breadth_first::Seq::new(&graph) {
///    println!("Event: {:?}", event);
/// }
/// ```
///
/// Note that the iterator modifies the state of the visit, so it can re-use
/// the allocations.
pub struct Seq<'a, G: RandomAccessGraph> {
    graph: &'a G,
    visited: BitVec,
    /// The visit queue; to avoid storing distances, we use `None` as a
    /// separator between levels. [`NonMaxUsize`] is used to avoid
    /// storage for the option variant tag.
    queue: VecDeque<Option<NonMaxUsize>>,
}

impl<'a, G: RandomAccessGraph> Seq<'a, G> {
    /// Creates a new sequential visit.
    ///
    /// # Arguments
    /// * `graph`: an immutable reference to the graph to visit.
    pub fn new(graph: &'a G) -> Self {
        let num_nodes = graph.num_nodes();
        assert_ne!(
            num_nodes,
            usize::MAX,
            "The BFS Seq visit cannot be used on graphs with usize::MAX nodes."
        );
        Self {
            graph,
            visited: BitVec::new(num_nodes),
            queue: VecDeque::new(),
        }
    }

    /// Returns an iterator over the nodes visited by a BFS visit starting from multiple nodes.
    pub fn iter_from_roots(
        &mut self,
        roots: impl IntoIterator<Item = usize>,
    ) -> Result<BfsOrderFromRoots<'_, 'a, G>> {
        BfsOrderFromRoots::new(self, roots)
    }
}

impl<'a, G: RandomAccessGraph> Sequential<EventPred> for Seq<'a, G> {
    fn visit_filtered_with<
        R: IntoIterator<Item = usize>,
        T,
        E,
        C: FnMut(&mut T, EventPred) -> ControlFlow<E, ()>,
        F: FnMut(&mut T, FilterArgsPred) -> bool,
    >(
        &mut self,
        roots: R,
        mut init: T,
        mut callback: C,
        mut filter: F,
    ) -> ControlFlow<E, ()> {
        self.queue.clear();

        for root in roots {
            if self.visited[root]
                || !filter(
                    &mut init,
                    FilterArgsPred {
                        node: root,
                        pred: root,
                        distance: 0,
                    },
                )
            {
                continue;
            }

            // We call the init event only if there are some non-filtered roots
            if self.queue.is_empty() {
                callback(&mut init, EventPred::Init {})?;
            }

            self.visited.set(root, true);
            self.queue.push_back(Some(
                NonMaxUsize::new(root).expect("node index should never be usize::MAX"),
            ));

            callback(
                &mut init,
                EventPred::Visit {
                    node: root,
                    pred: root,
                    distance: 0,
                },
            )?;
        }

        if self.queue.is_empty() {
            return Continue(());
        }

        callback(
            &mut init,
            EventPred::FrontierSize {
                distance: 0,
                size: self.queue.len(),
            },
        )?;

        // Insert marker
        self.queue.push_back(None);
        let mut distance = 1;

        while let Some(current_node) = self.queue.pop_front() {
            match current_node {
                Some(node) => {
                    let node = node.into();
                    for succ in self.graph.successors(node) {
                        let (node, pred) = (succ, node);
                        if !self.visited[succ] {
                            if filter(
                                &mut init,
                                FilterArgsPred {
                                    node,
                                    pred,

                                    distance,
                                },
                            ) {
                                self.visited.set(succ, true);
                                callback(
                                    &mut init,
                                    EventPred::Visit {
                                        node,
                                        pred,

                                        distance,
                                    },
                                )?;
                                self.queue.push_back(Some(
                                    NonMaxUsize::new(succ)
                                        .expect("node index should never be usize::MAX"),
                                ))
                            }
                        } else {
                            callback(&mut init, EventPred::Revisit { node, pred })?;
                        }
                    }
                }
                None => {
                    // We are at the end of the current level, so
                    // we increment the distance and add a separator.
                    if !self.queue.is_empty() {
                        callback(
                            &mut init,
                            EventPred::FrontierSize {
                                distance,
                                size: self.queue.len(),
                            },
                        )?;
                        distance += 1;
                        self.queue.push_back(None);
                    }
                }
            }
        }

        callback(&mut init, EventPred::Done {})
    }

    fn reset(&mut self) {
        self.queue.clear();
        self.visited.fill(false);
    }
}

impl<'a, 'b, G: RandomAccessGraph> IntoIterator for &'a mut Seq<'b, G> {
    type Item = IterEvent;
    type IntoIter = BfsOrder<'a, 'b, G>;

    fn into_iter(self) -> Self::IntoIter {
        BfsOrder::new(self)
    }
}

/// Iterator on **all nodes** of the graph in a BFS order
pub struct BfsOrder<'a, 'b, G: RandomAccessGraph> {
    visit: &'a mut Seq<'b, G>,
    /// The root of the current visit.
    root: usize,
    /// The current node being enumerated, i.e. the parent of the nodes returned
    /// by `succ`
    parent: usize,
    /// The current distance from the root.
    distance: usize,
    /// The successors of the `parent` node, this is done to be able to return
    /// also the parent.
    succ: <<G as RandomAccessLabeling>::Labels<'a> as IntoIterator>::IntoIter,
    /// Number of visited nodes, used to compute the length of the iterator.
    visited_nodes: usize,
}

impl<'a, 'b, G: RandomAccessGraph> BfsOrder<'a, 'b, G> {
    pub fn new(visit: &'a mut Seq<'b, G>) -> BfsOrder<'a, 'b, G> {
        assert!(
            visit.graph.num_nodes() > 0,
            "BfsOrder requires a non-empty graph"
        );
        visit.reset(); // ensure we start from a clean state
        let succ = visit.graph.successors(0).into_iter();
        BfsOrder {
            visit,
            root: 0,
            parent: 0,
            distance: 0,
            succ,
            visited_nodes: 0,
        }
    }
}

/// An event returned by the BFS iterator [`BfsOrder`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct IterEvent {
    /// The root of the current visit
    pub root: usize,
    /// The parent of the current node
    pub parent: usize,
    /// The current node being visited
    pub node: usize,
    /// The distance of the current node from the root
    pub distance: usize,
}

impl<'a, 'b, G: RandomAccessGraph> Iterator for BfsOrder<'a, 'b, G> {
    type Item = IterEvent;

    fn next(&mut self) -> Option<Self::Item> {
        // handle the first node separately, as we need to pre-fill the succ
        // iterator to be able to implement `new`
        if self.visited_nodes == 0 {
            self.visited_nodes += 1;
            self.visit.visited.set(self.root, true);
            self.visit.queue.push_back(None);
            self.distance = 1;
            return Some(IterEvent {
                root: self.root,
                parent: self.root,
                node: self.root,
                distance: 0,
            });
        }
        loop {
            // fast path, if the successors iterator is not exhausted, we can just return the next node
            for succ in &mut self.succ {
                if self.visit.visited[succ] {
                    continue; // skip already visited nodes
                }

                // if it's a new node, we visit it and add it to the queue
                // of nodes whose successors we will visit
                let node = NonMaxUsize::new(succ);
                debug_assert!(node.is_some(), "Node index should never be usize::MAX");
                let node = unsafe { node.unwrap_unchecked() };
                self.visit.queue.push_back(Some(node));

                self.visit.visited.set(succ as _, true);
                self.visited_nodes += 1;
                return Some(IterEvent {
                    root: self.root,
                    parent: self.parent,
                    node: succ,
                    distance: self.distance,
                });
            }

            // the successors are exhausted, so we need to move to the next node
            loop {
                match self.visit.queue.pop_front().expect(
                    "Queue should never be empty here, as we always add a level separator after the first node.",
                ) {
                    // if we have a node, we can continue visiting its successors
                    Some(node) => {
                        self.parent = node.into();
                        // reset the successors iterator for the new current node
                        self.succ = self.visit.graph.successors(self.parent).into_iter();
                        break;
                    }
                    // new level separator, so we increment the distance
                    None => {
                        // if the queue is not empty, we need to add a new level separator
                        if !self.visit.queue.is_empty() {
                            self.distance += 1;
                            self.visit.queue.push_back(None);
                            continue;
                        }
                        // the queue is empty, we need to find the next unvisited node
                        while self.visit.visited[self.root] {
                            self.root += 1;
                            if self.root >= self.visit.graph.num_nodes() {
                                return None;
                            }
                        }

                        self.visited_nodes += 1;
                        self.visit.visited.set(self.root, true);
                        self.visit.queue.push_back(None);
                        self.distance = 1;

                        self.parent = self.root;
                        self.succ = self.visit.graph.successors(self.root).into_iter();

                        return Some(IterEvent {
                            root: self.root,
                            parent: self.root,
                            node: self.root,
                            distance: 0,
                        });
                    }
                }
            }
        }
    }

    fn count(self) -> usize {
        self.len()
    }
}

impl<'a, 'b, G: RandomAccessGraph> ExactSizeIterator for BfsOrder<'a, 'b, G> {
    fn len(&self) -> usize {
        self.visit.graph.num_nodes() - self.visited_nodes
    }
}

impl<'a, 'b, G: RandomAccessGraph> FusedIterator for BfsOrder<'a, 'b, G> {}

/// Iterator on the nodes reachable from the given roots in a BFS order.
pub struct BfsOrderFromRoots<'a, 'b, G: RandomAccessGraph> {
    visit: &'a mut Seq<'b, G>,
    /// The current node being enumerated, i.e. the parent of the nodes returned
    /// by `succ`.
    parent: usize,
    /// The current distance from the root. A value of zero means that we are
    /// still in the root phase (returning the roots themselves).
    distance: usize,
    /// The successors of the `parent` node, this is done to be able to return
    /// also the parent.
    succ: <<G as RandomAccessLabeling>::Labels<'a> as IntoIterator>::IntoIter,
}

/// An event returned by the BFS iterator that starts from possibly multiple roots [`BfsOrderFromRoots`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct IterFromRootsEvent {
    /// The parent of the current node
    pub parent: usize,
    /// The current node being visited
    pub node: usize,
    /// The distance of the current node from the root
    pub distance: usize,
}

impl<'a, 'b, G: RandomAccessGraph> BfsOrderFromRoots<'a, 'b, G> {
    pub fn new(
        visit: &'a mut Seq<'b, G>,
        roots: impl IntoIterator<Item = usize>,
    ) -> Result<BfsOrderFromRoots<'a, 'b, G>> {
        visit.reset(); // ensure we start from a clean state
        // put the roots in the queue, and add a level separator
        visit.queue.extend(
            roots
                .into_iter()
                .map(|root| Some(NonMaxUsize::new(root).unwrap())),
        );
        anyhow::ensure!(
            !visit.queue.is_empty(),
            "Cannot create BfsOrderFromRoots with empty roots"
        );
        visit.queue.push_back(None);

        // setup the succ iterator for after we finish visiting the roots
        let first_root: usize = visit.queue[0].unwrap().into();
        let succ = visit.graph.successors(first_root).into_iter();
        Ok(BfsOrderFromRoots {
            visit,
            parent: first_root,
            distance: 0,
            succ,
        })
    }
}

impl<'a, 'b, G: RandomAccessGraph> Iterator for BfsOrderFromRoots<'a, 'b, G> {
    type Item = IterFromRootsEvent;
    fn next(&mut self) -> Option<Self::Item> {
        // If we are still in the root phase (distance == 0), return the
        // roots as the first nodes, and re-enqueue them so we visit
        // their successors.
        if self.distance == 0 {
            // We always put the None level separator at the end of the
            // queue, so there will always be at least one element.
            let element = self.visit.queue.pop_front().unwrap();

            if let Some(node) = element {
                let node = node.into();
                self.visit.visited.set(node, true);
                self.visit.queue.push_back(element);
                return Some(IterFromRootsEvent {
                    parent: node,
                    node,
                    distance: 0,
                });
            } else {
                // Finished the roots: add a level separator and
                // transition to the successor-processing phase.
                self.distance = 1;
                self.visit.queue.push_back(None);
            }
        }

        loop {
            for succ in &mut self.succ {
                if self.visit.visited[succ] {
                    continue;
                }

                let node = NonMaxUsize::new(succ);
                debug_assert!(node.is_some(), "Node index should never be usize::MAX");
                let node = unsafe { node.unwrap_unchecked() };
                self.visit.queue.push_back(Some(node));

                self.visit.visited.set(succ as _, true);
                return Some(IterFromRootsEvent {
                    parent: self.parent,
                    node: succ,
                    distance: self.distance,
                });
            }

            'inner: loop {
                // Successors exhausted, look in the queue.
                match self.visit.queue.pop_front().expect(
                    "Queue should never be empty here, as we always add a level separator after the first node.",
                ) {
                    Some(node) => {
                        self.parent = node.into();
                        self.succ = self.visit.graph.successors(self.parent).into_iter();
                        break 'inner;
                    }
                    None => {
                        if self.visit.queue.is_empty() {
                            return None;
                        }
                        self.visit.queue.push_back(None);
                        self.distance += 1;
                        continue 'inner;
                    }
                }
            }
        }
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2024 Matteo Dell'Acqua
3	* SPDX-FileCopyrightText: 2025 Sebastiano Vigna
4	* SPDX-FileCopyrightText: 2025 Fontana Tommaso
5	*
6	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
7	*/
8
9	use crate::traits::{RandomAccessGraph, RandomAccessLabeling};
10	use crate::visits::{
11	Sequential,
12	breadth_first::{EventPred, FilterArgsPred},
13	};
14	use anyhow::Result;
15	use nonmax::NonMaxUsize;
16	use std::iter::FusedIterator;
17	use std::{collections::VecDeque, ops::ControlFlow, ops::ControlFlow::Continue};
18	use sux::bits::BitVec;
19	use sux::traits::BitVecOpsMut;
20
21	/// A sequential breadth-first visit.
22	///
23	/// This implementation uses an algorithm that is slightly different from the
24	/// classical textbook algorithm, as we do not store parents or distances of the
25	/// nodes from the root: Parents and distances are computed on the fly and
26	/// passed to the callback function by visiting nodes when they are discovered,
27	/// rather than when they are extracted from the queue.
28	///
29	/// This approach requires inserting a level separator between nodes at
30	/// different distances: to obtain this result in a compact way, nodes are
31	/// represented using [`NonMaxUsize`], so the `None` variant of
32	/// `Option<NonMaxUsize>` can be used as a separator.
33	///
34	/// # Examples
35	///
36	/// Let's compute the distances from 0:
37	///
38	/// ```
39	/// use webgraph::visits::*;
40	/// use webgraph::graphs::vec_graph::VecGraph;
41	/// use webgraph::labels::proj::Left;
42	/// use std::ops::ControlFlow::Continue;
43	/// use no_break::NoBreak;
44	///
45	/// let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 0), (1, 3)]);
46	/// let mut visit = breadth_first::Seq::new(&graph);
47	/// let mut d = [0; 4];
48	/// visit.visit(
49	/// [0],
50	/// \|event\| {
51	/// // Set distance from 0
52	/// if let breadth_first::EventPred::Visit { node, distance, .. } = event {
53	/// d[node] = distance;
54	/// }
55	/// Continue(())
56	/// },
57	/// ).continue_value_no_break();
58	///
59	/// assert_eq!(d, [0, 1, 2, 2]);
60	/// ```
61	///
62	/// Here instead we compute the size of the ball of radius two around node 0: we
63	/// count nodes in the filter function, rather than as the result of an event,
64	/// to avoid adding them to the queue. In this way, node at distance two are
65	/// counted but not included in the queue, as it would happen if we were
66	/// counting during an [`EventPred::Visit`] event.
67	///
68	/// ```
69	/// use std::convert::Infallible;
70	/// use webgraph::visits::*;
71	/// use webgraph::graphs::vec_graph::VecGraph;
72	/// use webgraph::labels::proj::Left;
73	/// use std::ops::ControlFlow::Continue;
74	/// use no_break::NoBreak;
75	///
76	/// let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4)]);
77	/// let mut visit = breadth_first::Seq::new(&graph);
78	/// let mut count = 0;
79	/// visit.visit_filtered(
80	/// [0],
81	/// \|event\| { Continue(()) },
82	/// \|breadth_first::FilterArgsPred { distance, .. }\| {
83	/// if distance > 2 {
84	/// false
85	/// } else {
86	/// count += 1;
87	/// true
88	/// }
89	/// },
90	/// ).continue_value_no_break();
91	/// assert_eq!(count, 3);
92	/// ```
93	///
94	/// The visit also implements the [`IntoIterator`] trait, so it can be used
95	/// in a `for` loop to iterate over all nodes in the order they are visited:
96	///
97	/// ```rust
98	/// use webgraph::visits::*;
99	/// use webgraph::graphs::vec_graph::VecGraph;
100	///
101	/// let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4)]);
102	/// for event in &mut breadth_first::Seq::new(&graph) {
103	/// println!("Event: {:?}", event);
104	/// }
105	/// ```
106	///
107	/// Note that the iterator modifies the state of the visit, so it can re-use
108	/// the allocations.
109	pub struct Seq<'a, G: RandomAccessGraph> {
110	graph: &'a G,
111	visited: BitVec,
112	/// The visit queue; to avoid storing distances, we use `None` as a
113	/// separator between levels. [`NonMaxUsize`] is used to avoid
114	/// storage for the option variant tag.
115	queue: VecDeque<Option<NonMaxUsize>>,
116	}
117
118	impl<'a, G: RandomAccessGraph> Seq<'a, G> {
119	/// Creates a new sequential visit.
120	///
121	/// # Arguments
122	/// * `graph`: an immutable reference to the graph to visit.
123	pub fn new(graph: &'a G) -> Self {	59✔
124	let num_nodes = graph.num_nodes();	177✔
125	assert_ne!(	59✔
126	num_nodes,	×
127	usize::MAX,	×
128	"The BFS Seq visit cannot be used on graphs with usize::MAX nodes."	×
129	);
130	Self {
131	graph,
132	visited: BitVec::new(num_nodes),	118✔
133	queue: VecDeque::new(),	59✔
134	}
135	}
136
137	/// Returns an iterator over the nodes visited by a BFS visit starting from multiple nodes.
138	pub fn iter_from_roots(	14✔
139	&mut self,
140	roots: impl IntoIterator<Item = usize>,
141	) -> Result<BfsOrderFromRoots<'_, 'a, G>> {
142	BfsOrderFromRoots::new(self, roots)	42✔
143	}
144	}
145
146	impl<'a, G: RandomAccessGraph> Sequential<EventPred> for Seq<'a, G> {
147	fn visit_filtered_with<	325,890✔
148	R: IntoIterator<Item = usize>,
149	T,
150	E,
151	C: FnMut(&mut T, EventPred) -> ControlFlow<E, ()>,
152	F: FnMut(&mut T, FilterArgsPred) -> bool,
153	>(
154	&mut self,
155	roots: R,
156	mut init: T,
157	mut callback: C,
158	mut filter: F,
159	) -> ControlFlow<E, ()> {
160	self.queue.clear();	651,780✔
161
162	for root in roots {	651,784✔
163	if self.visited[root]	325,894✔
164	\|\| !filter(	648✔
165	&mut init,	648✔
166	FilterArgsPred {	324✔
167	node: root,	324✔
168	pred: root,	324✔
169	distance: 0,	324✔
170	},
171	)
172	{
173	continue;	325,570✔
174	}
175
176	// We call the init event only if there are some non-filtered roots
177	if self.queue.is_empty() {	648✔
178	callback(&mut init, EventPred::Init {})?;	640✔
179	}
180
181	self.visited.set(root, true);	972✔
182	self.queue.push_back(Some(	972✔
183	NonMaxUsize::new(root).expect("node index should never be usize::MAX"),	972✔
184	));
185
186	callback(
187	&mut init,	648✔
188	EventPred::Visit {	324✔
189	node: root,	324✔
190	pred: root,	324✔
191	distance: 0,	324✔
192	},
193	)?;
194	}
195
196	if self.queue.is_empty() {	651,780✔
197	return Continue(());	325,570✔
198	}
199
200	callback(
201	&mut init,	640✔
202	EventPred::FrontierSize {	320✔
203	distance: 0,	320✔
204	size: self.queue.len(),	320✔
205	},
206	)?;
207
208	// Insert marker
209	self.queue.push_back(None);	960✔
210	let mut distance = 1;	640✔
211
212	while let Some(current_node) = self.queue.pop_front() {	1,358,781✔
213	match current_node {	679,231✔
214	Some(node) => {	676,854✔
215	let node = node.into();	2,030,562✔
216	for succ in self.graph.successors(node) {	8,546,307✔
217	let (node, pred) = (succ, node);	19,547,235✔
218	if !self.visited[succ] {	6,515,745✔
219	if filter(
220	&mut init,	1,353,066✔
221	FilterArgsPred {	676,533✔
222	node,	1,353,066✔
223	pred,	676,533✔
224
225	distance,	676,533✔
226	},
227	) {
228	self.visited.set(succ, true);	2,029,593✔
229	callback(
230	&mut init,	1,353,062✔
231	EventPred::Visit {	676,531✔
232	node,	1,353,062✔
233	pred,	676,531✔
234
235	distance,	676,531✔
236	},
237	)?;
238	self.queue.push_back(Some(	2,029,590✔
239	NonMaxUsize::new(succ)	2,029,590✔
240	.expect("node index should never be usize::MAX"),	676,530✔
241	))
242	}
243	} else {
244	callback(&mut init, EventPred::Revisit { node, pred })?;	17,517,636✔
245	}
246	}
247	}
248	None => {	×
249	// We are at the end of the current level, so
250	// we increment the distance and add a separator.
251	if !self.queue.is_empty() {	2,377✔
252	callback(
253	&mut init,	4,116✔
254	EventPred::FrontierSize {	2,058✔
255	distance,	4,116✔
256	size: self.queue.len(),	2,058✔
257	},
258	)?;
259	distance += 1;	2,058✔
260	self.queue.push_back(None);	6,174✔
261	}
262	}
263	}
264	}
265
266	callback(&mut init, EventPred::Done {})	638✔
267	}
268
269	fn reset(&mut self) {	340✔
270	self.queue.clear();	680✔
271	self.visited.fill(false);	680✔
272	}
273	}
274
275	impl<'a, 'b, G: RandomAccessGraph> IntoIterator for &'a mut Seq<'b, G> {
276	type Item = IterEvent;
277	type IntoIter = BfsOrder<'a, 'b, G>;
278
279	fn into_iter(self) -> Self::IntoIter {	22✔
280	BfsOrder::new(self)	44✔
281	}
282	}
283
284	/// Iterator on all nodes of the graph in a BFS order
285	pub struct BfsOrder<'a, 'b, G: RandomAccessGraph> {
286	visit: &'a mut Seq<'b, G>,
287	/// The root of the current visit.
288	root: usize,
289	/// The current node being enumerated, i.e. the parent of the nodes returned
290	/// by `succ`
291	parent: usize,
292	/// The current distance from the root.
293	distance: usize,
294	/// The successors of the `parent` node, this is done to be able to return
295	/// also the parent.
296	succ: <<G as RandomAccessLabeling>::Labels<'a> as IntoIterator>::IntoIter,
297	/// Number of visited nodes, used to compute the length of the iterator.
298	visited_nodes: usize,
299	}
300
301	impl<'a, 'b, G: RandomAccessGraph> BfsOrder<'a, 'b, G> {
302	pub fn new(visit: &'a mut Seq<'b, G>) -> BfsOrder<'a, 'b, G> {	24✔
303	assert!(	24✔
304	visit.graph.num_nodes() > 0,	24✔
305	"BfsOrder requires a non-empty graph"	×
306	);
307	visit.reset(); // ensure we start from a clean state	48✔
308	let succ = visit.graph.successors(0).into_iter();	96✔
309	BfsOrder {
310	visit,
311	root: 0,
312	parent: 0,
313	distance: 0,
314	succ,
315	visited_nodes: 0,
316	}
317	}
318	}
319
320	/// An event returned by the BFS iterator [`BfsOrder`].
321	#[derive(Debug, Clone, Copy, PartialEq, Eq)]
322	pub struct IterEvent {
323	/// The root of the current visit
324	pub root: usize,
325	/// The parent of the current node
326	pub parent: usize,
327	/// The current node being visited
328	pub node: usize,
329	/// The distance of the current node from the root
330	pub distance: usize,
331	}
332
333	impl<'a, 'b, G: RandomAccessGraph> Iterator for BfsOrder<'a, 'b, G> {
334	type Item = IterEvent;
335
336	fn next(&mut self) -> Option<Self::Item> {	1,627,901✔
337	// handle the first node separately, as we need to pre-fill the succ
338	// iterator to be able to implement `new`
339	if self.visited_nodes == 0 {	1,627,901✔
340	self.visited_nodes += 1;	24✔
341	self.visit.visited.set(self.root, true);	72✔
342	self.visit.queue.push_back(None);	72✔
343	self.distance = 1;	24✔
344	return Some(IterEvent {	24✔
345	root: self.root,	48✔
346	parent: self.root,	24✔
347	node: self.root,	24✔
348	distance: 0,	24✔
349	});
350	}
351	loop {	×
352	// fast path, if the successors iterator is not exhausted, we can just return the next node
353	for succ in &mut self.succ {	19,336,533✔
354	if self.visit.visited[succ] {	16,080,843✔
355	continue; // skip already visited nodes	14,453,030✔
356	}
357
358	// if it's a new node, we visit it and add it to the queue
359	// of nodes whose successors we will visit
360	let node = NonMaxUsize::new(succ);	4,883,439✔
361	debug_assert!(node.is_some(), "Node index should never be usize::MAX");	4,883,439✔
362	let node = unsafe { node.unwrap_unchecked() };	4,883,439✔
363	self.visit.queue.push_back(Some(node));	4,883,439✔
364
365	self.visit.visited.set(succ as _, true);	4,883,439✔
366	self.visited_nodes += 1;	1,627,813✔
367	return Some(IterEvent {	1,627,813✔
368	root: self.root,	3,255,626✔
369	parent: self.parent,	3,255,626✔
370	node: succ,	1,627,813✔
371	distance: self.distance,	1,627,813✔
372	});
373	}
374
375	// the successors are exhausted, so we need to move to the next node
376	loop {	×
377	match self.visit.queue.pop_front().expect(	4,884,423✔
378	"Queue should never be empty here, as we always add a level separator after the first node.",	1,628,141✔
379	) {
380	// if we have a node, we can continue visiting its successors
381	Some(node) => {	1,627,813✔
382	self.parent = node.into();	1,627,813✔
383	// reset the successors iterator for the new current node
384	self.succ = self.visit.graph.successors(self.parent).into_iter();	8,139,065✔
385	break;	1,627,813✔
386	}
387	// new level separator, so we increment the distance
388	None => {	×
389	// if the queue is not empty, we need to add a new level separator
390	if !self.visit.queue.is_empty() {	328✔
391	self.distance += 1;	264✔
392	self.visit.queue.push_back(None);	792✔
393	continue;	264✔
394	}
395	// the queue is empty, we need to find the next unvisited node
396	while self.visit.visited[self.root] {	1,627,917✔
397	self.root += 1;	1,627,877✔
398	if self.root >= self.visit.graph.num_nodes() {	3,255,754✔
399	return None;	24✔
400	}
401	}
402
403	self.visited_nodes += 1;	40✔
404	self.visit.visited.set(self.root, true);	120✔
405	self.visit.queue.push_back(None);	120✔
406	self.distance = 1;	40✔
407
408	self.parent = self.root;	40✔
409	self.succ = self.visit.graph.successors(self.root).into_iter();	200✔
410
411	return Some(IterEvent {	40✔
412	root: self.root,	80✔
413	parent: self.root,	40✔
414	node: self.root,	40✔
415	distance: 0,	40✔
416	});
417	}
418	}
419	}
420	}
421	}
422
NEW 423	fn count(self) -> usize {	×
NEW 424	self.len()	×
425	}
426	}
427
428	impl<'a, 'b, G: RandomAccessGraph> ExactSizeIterator for BfsOrder<'a, 'b, G> {
429	fn len(&self) -> usize {	5✔
430	self.visit.graph.num_nodes() - self.visited_nodes	10✔
431	}
432	}
433
434	impl<'a, 'b, G: RandomAccessGraph> FusedIterator for BfsOrder<'a, 'b, G> {}
435
436	/// Iterator on the nodes reachable from the given roots in a BFS order.
437	pub struct BfsOrderFromRoots<'a, 'b, G: RandomAccessGraph> {
438	visit: &'a mut Seq<'b, G>,
439	/// The current node being enumerated, i.e. the parent of the nodes returned
440	/// by `succ`.
441	parent: usize,
442	/// The current distance from the root. A value of zero means that we are
443	/// still in the root phase (returning the roots themselves).
444	distance: usize,
445	/// The successors of the `parent` node, this is done to be able to return
446	/// also the parent.
447	succ: <<G as RandomAccessLabeling>::Labels<'a> as IntoIterator>::IntoIter,
448	}
449
450	/// An event returned by the BFS iterator that starts from possibly multiple roots [`BfsOrderFromRoots`].
451	#[derive(Debug, Clone, Copy, PartialEq, Eq)]
452	pub struct IterFromRootsEvent {
453	/// The parent of the current node
454	pub parent: usize,
455	/// The current node being visited
456	pub node: usize,
457	/// The distance of the current node from the root
458	pub distance: usize,
459	}
460
461	impl<'a, 'b, G: RandomAccessGraph> BfsOrderFromRoots<'a, 'b, G> {
462	pub fn new(	14✔
463	visit: &'a mut Seq<'b, G>,
464	roots: impl IntoIterator<Item = usize>,
465	) -> Result<BfsOrderFromRoots<'a, 'b, G>> {
466	visit.reset(); // ensure we start from a clean state	28✔
467	// put the roots in the queue, and add a level separator
468	visit.queue.extend(	28✔
469	roots	14✔
470	.into_iter()	14✔
471	.map(\|root\| Some(NonMaxUsize::new(root).unwrap())),	74✔
472	);
473	anyhow::ensure!(	14✔
474	!visit.queue.is_empty(),	14✔
475	"Cannot create BfsOrderFromRoots with empty roots"	×
476	);
477	visit.queue.push_back(None);	39✔
478
479	// setup the succ iterator for after we finish visiting the roots
480	let first_root: usize = visit.queue[0].unwrap().into();	65✔
481	let succ = visit.graph.successors(first_root).into_iter();	65✔
482	Ok(BfsOrderFromRoots {	13✔
483	visit,	26✔
484	parent: first_root,	13✔
485	distance: 0,	13✔
486	succ,	13✔
487	})
488	}
489	}
490
491	impl<'a, 'b, G: RandomAccessGraph> Iterator for BfsOrderFromRoots<'a, 'b, G> {
492	type Item = IterFromRootsEvent;
493	fn next(&mut self) -> Option<Self::Item> {	62✔
494	// If we are still in the root phase (distance == 0), return the
495	// roots as the first nodes, and re-enqueue them so we visit
496	// their successors.
497	if self.distance == 0 {	62✔
498	// We always put the None level separator at the end of the
499	// queue, so there will always be at least one element.
500	let element = self.visit.queue.pop_front().unwrap();	132✔
501
502	if let Some(node) = element {	53✔
503	let node = node.into();	60✔
504	self.visit.visited.set(node, true);	60✔
505	self.visit.queue.push_back(element);	60✔
506	return Some(IterFromRootsEvent {	20✔
507	parent: node,	20✔
508	node,	20✔
509	distance: 0,	20✔
510	});
511	} else {
512	// Finished the roots: add a level separator and
513	// transition to the successor-processing phase.
514	self.distance = 1;	26✔
515	self.visit.queue.push_back(None);	26✔
516	}
517	}
518
519	loop {	×
520	for succ in &mut self.succ {	144✔
521	if self.visit.visited[succ] {	53✔
522	continue;	24✔
523	}
524
525	let node = NonMaxUsize::new(succ);	87✔
526	debug_assert!(node.is_some(), "Node index should never be usize::MAX");	87✔
527	let node = unsafe { node.unwrap_unchecked() };	87✔
528	self.visit.queue.push_back(Some(node));	87✔
529
530	self.visit.visited.set(succ as _, true);	87✔
531	return Some(IterFromRootsEvent {	29✔
532	parent: self.parent,	58✔
533	node: succ,	29✔
534	distance: self.distance,	29✔
535	});
536	}
537
538	'inner: loop {	×
539	// Successors exhausted, look in the queue.
540	match self.visit.queue.pop_front().expect(	243✔
541	"Queue should never be empty here, as we always add a level separator after the first node.",	81✔
542	) {
543	Some(node) => {	49✔
544	self.parent = node.into();	49✔
545	self.succ = self.visit.graph.successors(self.parent).into_iter();	245✔
546	break 'inner;	49✔
547	}
548	None => {	×
549	if self.visit.queue.is_empty() {	64✔
550	return None;	13✔
551	}
552	self.visit.queue.push_back(None);	57✔
553	self.distance += 1;	19✔
554	continue 'inner;	19✔
555	}
556	}
557	}
558	}
559	}
560	}

vigna / webgraph-rs / 22350210654

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