webgraph_algo/visits/
mod.rs

1/*
2 * SPDX-FileCopyrightText: 2024 Matteo Dell'Acqua
3 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
4 *
5 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6 */
7
8//! Visits on graphs.
9//!
10//! Implementation of [sequential](Sequential) and [parallel][Parallel] visits
11//! depend on a type parameter `A` implementing the trait [`Event`]; they
12//! provide visit methods accepting a callback function with argument `A` and
13//! returning a `ControlFlow<E, ()>`, where `E` is a type parameter of the visit
14//! method: for example, `E` might be [`StoppedWhenDone`] when completing early,
15//! [`Interrupted`] when interrupted or [`Infallible`](std::convert::Infallible)
16//! if the visit cannot be interrupted.
17//!
18//! If a callback returns [`Break`](ControlFlow::Break), the visit will be
19//! interrupted, and the interrupt propagated to the caller of the visit method;
20//! for uninterruptible visits we suggest to use the
21//! [`no-break`](https://crates.io/crates/no-break) crate and its
22//! [`continue_value_no_break`](no_break::NoBreak::continue_value_no_break)
23//! method on the result to let type inference run smoothly.
24//!
25//! Note that an interruption does not necessarily denote an error condition
26//! (see, e.g., [`StoppedWhenDone`]).
27//!
28//! [Sequential visits](Sequential) are visits that are executed in a single
29//! thread, whereas [parallel visits](Parallel) use multiple threads. The
30//! signature of callbacks reflects this difference ([`FnMut`] for the sequential
31//! case vs. [`Fn`] + [`Sync`] for the parallel case).
32//!
33//! In case of interruption sequential visits usually return immediately to the
34//! caller, whereas in general parallel visits might need to complete part of
35//! their subtasks before returning to the caller.
36//!
37//! Additionally, implementations might accepts a filter function accepting a
38//! [`Event::FilterArgs`] that will be called when a new node is discovered. If
39//! the filter returns false, the node will be ignored, that is, not even marked
40//! as known. Note that in case of parallel visits the filter might be called
41//! multiple times on the same node (and with a different predecessor, if
42//! available) due to race conditions.
43//!
44//! All visits have also methods accepting an `init` item similarly to the
45//! [Rayon](rayon) [`map_with`](rayon::iter::ParallelIterator::map_with) method. For
46//! parallel visits, the item will be cloned.
47//!
48//! There is a blanket implementation of the [`Parallel`] trait for all types
49//! implementing the [`Sequential`] trait. This approach makes it possible to
50//! have structures that can use both sequential and parallel visits.
51//!
52//! Visit must provide a `reset` method that makes it possible to reuse the
53//! visit.
54//!
55//! # Examples
56//!
57//! There are examples of visits in
58//! [`SeqIter`](crate::visits::depth_first::SeqIter),
59//! [`ParFair`](crate::visits::breadth_first::ParFair) and
60//! [`ParLowMem`](crate::visits::breadth_first::ParLowMem).
61
62pub mod breadth_first;
63pub mod depth_first;
64
65use rayon::ThreadPool;
66use std::ops::ControlFlow;
67use thiserror::Error;
68
69#[derive(Error, Debug)]
70/// The visit was interrupted.
71#[error("The visit was interrupted")]
72pub struct Interrupted;
73
74#[derive(Error, Debug)]
75/// The result of the visit was computed without completing the visit; for
76/// example, during an acyclicity test a single arc pointing at the visit path
77/// is sufficient to compute the result.
78#[error("Stopped when done")]
79pub struct StoppedWhenDone;
80
81/// Types usable as arguments for the callbacks in visits.
82///
83/// Arguments are usually enums in which variants represent visit events
84/// (previsits, postvisits, etc.). Each variant then contains additional data
85/// related to the specific event.
86///
87/// The associated type [`Event::FilterArgs`] is the type of the arguments
88/// passed to the filter associated with the visit. It can be set to `()` if
89/// filtering is not supported
90pub trait Event {
91    /// The type passed as input to the filter.
92    type FilterArgs;
93}
94
95/// A convenience type alias for the filter arguments of an event.
96///
97/// It is useful to write match patterns using destructuring syntax.
98pub type FilterArgs<A> = <A as Event>::FilterArgs;
99
100/// A sequential visit.
101///
102/// Implementation of this trait must provide the
103/// [`visit_filtered_with`](Sequential::visit_filtered_with) method, which
104/// should perform a visit of a graph starting from a given set of nodes. Note
105/// that different visits types might interpret the set of nodes differently:
106/// for example, a [breadth-first visit](breadth_first) will interpret the set
107/// of nodes as the initial queue, whereas a [depth-first visit](depth_first)
108/// will interpret the set of nodes as a list of nodes from which to start
109/// visits.
110pub trait Sequential<A: Event> {
111    /// Visits the graph from the specified nodes with an initialization value
112    /// and a filter function.
113    ///
114    /// # Arguments
115    ///
116    /// * `roots`: The nodes to start the visit from.
117    ///
118    /// * `init`: a value the will be passed to the callback function.
119    ///
120    /// * `callback`: The callback function.
121    ///
122    /// * `filter`: The filter function.
123    fn visit_filtered_with<
124        R: IntoIterator<Item = usize>,
125        T,
126        E,
127        C: FnMut(&mut T, A) -> ControlFlow<E, ()>,
128        F: FnMut(&mut T, A::FilterArgs) -> bool,
129    >(
130        &mut self,
131        roots: R,
132        init: T,
133        callback: C,
134        filter: F,
135    ) -> ControlFlow<E, ()>;
136
137    /// Visits the graph from the specified nodes with a filter function.
138    ///
139    /// # Arguments
140    ///
141    /// * `roots`: The nodes to start the visit from.
142    ///
143    /// * `callback`: The callback function.
144    ///
145    /// * `filter`: The filter function.
146    fn visit_filtered<
147        R: IntoIterator<Item = usize>,
148        E,
149        C: FnMut(A) -> ControlFlow<E, ()>,
150        F: FnMut(A::FilterArgs) -> bool,
151    >(
152        &mut self,
153        roots: R,
154        mut callback: C,
155        mut filter: F,
156    ) -> ControlFlow<E, ()> {
157        self.visit_filtered_with(roots, (), |(), a| callback(a), |(), a| filter(a))
158    }
159
160    /// Visits the graph from the specified nodes with an initialization value.
161    ///
162    /// # Arguments
163    ///
164    /// * `roots`: The nodes to start the visit from.
165    ///
166    /// * `init`: a value the will be passed to the callback function.
167    ///
168    /// * `callback`: The callback function.
169    fn visit_with<
170        R: IntoIterator<Item = usize>,
171        T,
172        E,
173        C: FnMut(&mut T, A) -> ControlFlow<E, ()>,
174    >(
175        &mut self,
176        roots: R,
177        init: T,
178        callback: C,
179    ) -> ControlFlow<E, ()> {
180        self.visit_filtered_with(roots, init, callback, |_, _| true)
181    }
182
183    /// Visits the graph from the specified nodes.
184    ///
185    /// # Arguments
186    ///
187    /// * `roots`: The nodes to start the visit from.
188    ///
189    /// * `callback`: The callback function.
190    fn visit<R: IntoIterator<Item = usize>, E, C: FnMut(A) -> ControlFlow<E, ()>>(
191        &mut self,
192        roots: R,
193        callback: C,
194    ) -> ControlFlow<E, ()> {
195        self.visit_filtered(roots, callback, |_| true)
196    }
197
198    /// Resets the visit status, making it possible to reuse it.
199    fn reset(&mut self);
200}
201
202/// A parallel visit.
203///
204/// Implementation of this trait must provide the
205/// [`par_visit_filtered_with`](Parallel::par_visit_filtered_with) method, which
206/// should perform a parallel visit of a graph starting from a given set of
207/// nodes. Note that different visits types might interpret the set of nodes
208/// differently: for example, a [breadth-first visit](breadth_first) will
209/// interpret the set of nodes as the initial queue, whereas a [depth-first
210/// visit](depth_first) will interpret the set of nodes as a list of nodes from
211/// which to start visits.
212pub trait Parallel<A: Event> {
213    /// Visits the graph from the specified nodes with an initialization value
214    /// and a filter function.
215    ///
216    /// # Arguments
217    ///
218    /// * `roots`: The nodes to start the visit from.
219    ///
220    /// * `init`: a value the will be cloned and passed to the callback
221    ///   function.
222    ///
223    /// * `callback`: The callback function.
224    ///
225    /// * `filter`: The filter function.
226    ///
227    /// * `thread_pool`: The thread pool to use for parallel computation.
228    fn par_visit_filtered_with<
229        R: IntoIterator<Item = usize>,
230        T: Clone + Send + Sync + Sync,
231        E: Send,
232        C: Fn(&mut T, A) -> ControlFlow<E, ()> + Sync,
233        F: Fn(&mut T, A::FilterArgs) -> bool + Sync,
234    >(
235        &mut self,
236        roots: R,
237        init: T,
238        callback: C,
239        filter: F,
240        thread_pool: &ThreadPool,
241    ) -> ControlFlow<E, ()>;
242
243    /// Visits the graph from the specified nodes with a filter function.
244    ///
245    /// # Arguments
246    ///
247    /// * `roots`: The nodes to start the visit from.
248    ///
249    /// * `callback`: The callback function.
250    ///
251    /// * `filter`: The filter function.
252    ///
253    /// * `thread_pool`: The thread pool to use for parallel computation.
254    fn par_visit_filtered<
255        R: IntoIterator<Item = usize>,
256        E: Send,
257        C: Fn(A) -> ControlFlow<E, ()> + Sync,
258        F: Fn(A::FilterArgs) -> bool + Sync,
259    >(
260        &mut self,
261        roots: R,
262        callback: C,
263        filter: F,
264        thread_pool: &ThreadPool,
265    ) -> ControlFlow<E, ()> {
266        self.par_visit_filtered_with(
267            roots,
268            (),
269            |(), a| callback(a),
270            |(), a| filter(a),
271            thread_pool,
272        )
273    }
274
275    /// Visits the graph from the specified nodes with an initialization value.
276    ///
277    /// # Arguments
278    ///
279    /// * `roots`: The nodes to start the visit from.
280    ///
281    /// * `init`: a value the will be cloned and passed to the callback
282    ///   function.
283    ///
284    /// * `callback`: The callback function.
285    ///
286    /// * `thread_pool`: The thread pool to use for parallel computation.
287    fn par_visit_with<
288        R: IntoIterator<Item = usize>,
289        T: Clone + Send + Sync + Sync,
290        E: Send,
291        C: Fn(&mut T, A) -> ControlFlow<E, ()> + Sync,
292    >(
293        &mut self,
294        roots: R,
295        init: T,
296        callback: C,
297        thread_pool: &ThreadPool,
298    ) -> ControlFlow<E, ()> {
299        self.par_visit_filtered_with(roots, init, callback, |_, _| true, thread_pool)
300    }
301
302    /// Visits the graph from the specified nodes.
303    ///
304    /// # Arguments
305    ///
306    /// * `roots`: The nodes to start the visit from.
307    ///
308    /// * `callback`: The callback function.
309    ///
310    /// * `thread_pool`: The thread pool to use for parallel computation.
311    fn par_visit<R: IntoIterator<Item = usize>, E: Send, C: Fn(A) -> ControlFlow<E, ()> + Sync>(
312        &mut self,
313        roots: R,
314        callback: C,
315        thread_pool: &ThreadPool,
316    ) -> ControlFlow<E, ()> {
317        self.par_visit_filtered(roots, callback, |_| true, thread_pool)
318    }
319
320    /// Resets the visit status, making it possible to reuse it.
321    fn reset(&mut self);
322}
webgraph_algo/visits/mod.rs

webgraph_algo/visits/
mod.rs
