webgraph_algo/visits/depth_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//! Depth-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 are the previsit and postvisit events of the root.
18
19mod seq;
20pub use seq::*;
21
22/// Types of callback events generated during depth-first visits
23/// not keeping track of parent nodes.
24#[derive(Debug, Clone, Hash, PartialEq, Eq)]
25pub enum EventNoPred {
26    /// This event should be used to set up state at the start of the visit.
27    ///
28    /// Note that this event will not happen if the visit is empty, that
29    /// is, all of the roots are already visited or filtered.
30    Init {
31        /// The root of the current visit tree, that is, the first node that
32        /// will be visited.
33        root: usize,
34    },
35    /// The node has been encountered for the first time: we are traversing a
36    /// new tree arc, unless all fields are equal to the root.
37    Previsit {
38        /// The current node.
39        node: usize,
40        /// The root of the current visit tree.
41        root: usize,
42        /// The depth of the visit, that is, the length of the visit path from
43        /// the [root](`EventNoPred::Previsit::root`) to
44        /// [node](`EventNoPred::Previsit::node`).
45        depth: usize,
46    },
47    /// The node has been encountered before: we are traversing a back arc, a
48    /// forward arc, or a cross arc.
49    Revisit {
50        /// The current node.
51        node: usize,
52        /// The root of the current visit tree.
53        root: usize,
54        /// The depth of the visit, that is, the length of the visit path from
55        /// the [root](`EventNoPred::Revisit::root`) to
56        /// [node](`EventNoPred::Revisit::node`).
57        depth: 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        /// The root of the current visit tree.
66        root: usize,
67    },
68}
69
70/// Filter arguments for visits that do not keep track of predecessors.
71#[derive(Debug, Clone, Hash, PartialEq, Eq)]
72pub struct FilterArgsNoPred {
73    /// The current node.
74    pub node: usize,
75    /// The root of the current visit tree.
76    pub root: usize,
77    /// The depth of the visit, that is, the length of the visit path from the
78    /// [root](`Self::root`) to [node](`Self::node`).
79    pub depth: usize,
80}
81
82impl super::Event for EventNoPred {
83    type FilterArgs = FilterArgsNoPred;
84}
85
86/// Types of callback events generated during depth-first visits
87/// keeping track of parent nodes (and possibly of the visit path).
88#[derive(Debug, Clone, Hash, PartialEq, Eq)]
89pub enum EventPred {
90    /// This event should be used to set up state at the start of the visit.
91    ///
92    /// Note that this event will not happen if the visit is empty, that
93    /// is, all of the roots are already visited or filtered.
94    Init {
95        /// The root of the current visit tree, that is, the first node that
96        /// will be visited.
97        root: usize,
98    },
99    /// The node has been encountered for the first time: we are traversing a
100    /// new tree arc, unless all node fields are equal to the root.
101    Previsit {
102        /// The current node.
103        node: usize,
104        /// The parent of [node](`EventPred::Previsit::node`) in the visit tree.
105        pred: usize,
106        /// The root of the current visit tree.
107        root: usize,
108        /// The depth of the visit, that is, the length of the visit path from the
109        /// [root](`EventPred::Previsit::root`) to [node](`EventPred::Previsit::node`).
110        depth: usize,
111    },
112    /// The node has been encountered before: we are traversing a back arc, a
113    /// forward arc, or a cross arc.
114    Revisit {
115        /// The current node.
116        node: usize,
117        /// The parent of [node](`EventPred::Revisit::node`) in the visit tree.
118        pred: usize,
119        /// The root of the current visit tree.
120        root: usize,
121        /// The depth of the visit, that is, the length of the visit path from the
122        /// [root](`EventPred::Revisit::root`) to [curr](`EventPred::Revisit::node`).
123        depth: usize,
124        /// Whether the node is currently on the visit path, that is, if we are
125        /// traversing a back arc, and retreating from it. This might be always
126        /// false if the visit does not keep track of the visit path.
127        on_stack: bool,
128    },
129    /// The enumeration of the successors of the node has been completed: we are
130    /// retreating from a tree arc, unless all node fields are equal to
131    /// the root.
132    Postvisit {
133        /// The current node.
134        node: usize,
135        /// The parent of [curr](`EventPred::Postvisit::node`) in the visit tree.
136        pred: usize,
137        /// The root of the current visit tree.
138        root: usize,
139        /// The depth of the visit, that is, the length of the visit path from
140        /// the [root](`EventPred::Postvisit::root`) to
141        /// [node](`EventPred::Postvisit::node`).
142        depth: usize,
143    },
144    /// The visit has been completed.
145    ///
146    /// Note that this event will not happen if the visit is empty (that is, if
147    /// the root has already been visited) or if the visit is stopped by a
148    /// callback returning an error.
149    Done {
150        /// The root of the current visit tree.
151        root: usize,
152    },
153}
154
155/// Filter arguments for visit that keep track of predecessors.
156#[derive(Debug, Clone, Hash, PartialEq, Eq)]
157pub struct FilterArgsPred {
158    /// The current node.
159    pub node: usize,
160    /// The parent of [node](`Self::node`) in the visit tree.
161    pub pred: usize,
162    /// The root of the current visit tree.
163    pub root: usize,
164    /// The depth of the visit, that is, the length of the visit path from the
165    /// [root](`Self::root`) to [node](`Self::node`).
166    pub depth: usize,
167}
168
169impl super::Event for EventPred {
170    type FilterArgs = FilterArgsPred;
171}
webgraph_algo/visits/depth_first/mod.rs

webgraph_algo/visits/depth_first/
mod.rs
