webgraph_algo/visits/breadth_first/
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//! Breadth-first visits.
9//!
10//! Implementations must accept a callback function with argument
11//! [`EventNoPred`], or [`EventPred`] if the visit keeps track of parent nodes.
12//! The associated filter argument types are [`FilterArgsNoPred`] and
13//! [`FilterArgsPred`], respectively.
14//!
15//! Note that since [`EventPred`] contains the predecessor of the visited node,
16//! all post-initialization visit events can be interpreted as arc events. The
17//! only exception is the [`Unknown`](EventPred::Unknown) event at the root.
18
19mod seq;
20pub use seq::*;
21
22mod par_fair;
23pub use par_fair::*;
24
25mod par_low_mem;
26pub use par_low_mem::*;
27
28/// Types of callback events generated during breadth-first visits
29/// keeping track of parent nodes.
30#[derive(Debug, Clone, Hash, PartialEq, Eq)]
31pub enum EventPred {
32    /// This event should be used to set up state at the start of the visit.
33    ///
34    /// Note that this event will not happen if the visit is empty, that
35    /// is, all of the roots are already visited or filtered.
36    Init {},
37    /// The node has been encountered for the first time: we are traversing a
38    /// new tree arc, unless all node fields are equal to the root.
39    Unknown {
40        /// The current node.
41        node: usize,
42        /// The predecessor of [node](`EventPred::Unknown::node`).
43        pred: usize,
44        /// The distance of the current node from the roots.
45        distance: usize,
46    },
47    /// The node has been encountered before: we are traversing a back arc, a
48    /// forward arc, or a cross arc.
49    ///
50    /// Note however that in parallel contexts it might happen that callback
51    /// with event [`Unknown`](`EventPred::Unknown`) has not been called yet by
52    /// the thread who discovered the node.
53    Known {
54        /// The current node.
55        node: usize,
56        /// The predecessor of [node](`EventPred::Known::node`).
57        pred: usize,
58    },
59    /// The visit has been completed.
60    ///
61    /// Note that this event will not happen if the visit is empty (that is, if
62    /// the root has already been visited) or if the visit is stopped by a
63    /// callback returning an error.
64    Done {},
65}
66
67/// Filter arguments for visits that keep track of predecessors.
68#[derive(Debug, Clone, Hash, PartialEq, Eq)]
69pub struct FilterArgsPred {
70    /// The current node.
71    pub node: usize,
72    /// The predecessor of [node](`Self::node`).
73    pub pred: usize,
74    /// The distance of the current node from the roots.
75    pub distance: usize,
76}
77
78impl super::Event for EventPred {
79    type FilterArgs = FilterArgsPred;
80}
81
82/// Types of callback events generated during breadth-first visits
83/// not keeping track of parent nodes.
84#[derive(Debug, Clone, Hash, PartialEq, Eq)]
85pub enum EventNoPred {
86    /// This event should be used to set up state at the start of the visit.
87    ///
88    /// Note that this event will not happen if the visit is empty, that
89    /// is, all of the roots are already visited or filtered.
90    Init {},
91    /// The node has been encountered for the first time: we are traversing a
92    /// new tree arc, unless all node fields are equal to the root.
93    Unknown {
94        /// The current node.
95        node: usize,
96        /// The distance of the current node from the roots.
97        distance: usize,
98    },
99    /// The node has been encountered before: we are traversing a back arc, a
100    /// forward arc, or a cross arc.
101    ///
102    /// Note however that in parallel contexts it might happen that callback
103    /// with event [`Unknown`](`EventNoPred::Unknown`) has not been called yet
104    /// by the thread who discovered the node.
105    Known {
106        /// The current node.
107        node: usize,
108    },
109    /// The visit has been completed.
110    ///
111    /// Note that this event will not happen if the visit is empty (that is, if
112    /// the root has already been visited) or if the visit is stopped by a
113    /// callback returning an error.
114    Done {},
115}
116
117/// Filter arguments for visits that do not keep track of predecessors.
118#[derive(Debug, Clone, Hash, PartialEq, Eq)]
119pub struct FilterArgsNoPred {
120    /// The current node.
121    pub node: usize,
122    /// The distance of the current node from the roots.
123    pub distance: usize,
124}
125
126impl super::Event for EventNoPred {
127    type FilterArgs = FilterArgsNoPred;
128}
webgraph_algo/visits/breadth_first/mod.rs

webgraph_algo/visits/breadth_first/
mod.rs
