19278972970

Committed 11 Nov 2025 09:25PM UTC coverage: 62.316% (+14.3%) from 48.052%

Build # 19278972970

Build Type

push

github

Committed by

zommiommy

Commit Message

BatchCodec print stats and encoding time

Run Details

40 of 53 new or added lines in 4 files covered. (75.47%)

814 existing lines in 46 files now uncovered.

5252 of 8428 relevant lines covered (62.32%)

29580067.92 hits per line

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

65.76

/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::{
    breadth_first::{EventPred, FilterArgsPred},
    Sequential,
};
use anyhow::Result;
use nonmax::NonMaxUsize;
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: to
/// minimize resource usage, we count nodes in the filter function, rather than
/// as the result of an event. 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 in parallel 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> {
        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);
            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;
                        }
                        self.distance = 0; // new visits, new distance

                        // 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.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: self.distance,
                        });
                    }
                }
            }
        }
    }
}

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

/// 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.
    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())),
        );
        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 the distance is zero, we are visiting the roots, so we need to
        // return the roots as the first nodes, and put themself as their parents
        // and then re-enqueue them so we can 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 in the queue
            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); // re-enqueue the node to visit its successors later
                return Some(IterFromRootsEvent {
                    parent: node,
                    node,
                    distance: 0,
                });
            } else {
                // finished the roots
                // add a level separator so we know where the distance 1 nodes start
                self.visit.queue.push_back(None);
                // succ and parent were already set to the first root, so we can fall through
            }
        }

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

vigna / webgraph-rs / 19278972970

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