weavatrix_graph/algo/walk/
basic.rs

1use super::TraversalWorkspace;
2use crate::IndexGraphView;
3use crate::algo::traversal::{Direction, for_each_neighbor};
4
5fn accept_all<Edge>(_: Edge) -> bool {
6    true
7}
8
9/// Lazy breadth-first traversal backed by reusable allocation storage.
10pub struct Bfs<'graph, 'workspace, G, F>
11where
12    G: IndexGraphView,
13{
14    graph: &'graph G,
15    workspace: &'workspace mut TraversalWorkspace<G::Node>,
16    direction: Direction,
17    keep_edge: F,
18}
19
20impl<'graph, 'workspace, G> Bfs<'graph, 'workspace, G, fn(G::Edge) -> bool>
21where
22    G: IndexGraphView,
23{
24    #[must_use]
25    pub fn new(
26        graph: &'graph G,
27        start: G::Node,
28        workspace: &'workspace mut TraversalWorkspace<G::Node>,
29    ) -> Self {
30        Self::filtered(graph, start, Direction::Outgoing, workspace, accept_all)
31    }
32}
33
34impl<'graph, 'workspace, G, F> Bfs<'graph, 'workspace, G, F>
35where
36    G: IndexGraphView,
37    F: FnMut(G::Edge) -> bool,
38{
39    #[must_use]
40    pub fn filtered(
41        graph: &'graph G,
42        start: G::Node,
43        direction: Direction,
44        workspace: &'workspace mut TraversalWorkspace<G::Node>,
45        keep_edge: F,
46    ) -> Self {
47        workspace.begin(graph.node_bound());
48        if graph.contains_node(start) && workspace.mark(G::node_slot(start)) {
49            workspace.queue.push_back(start);
50        }
51        Self {
52            graph,
53            workspace,
54            direction,
55            keep_edge,
56        }
57    }
58}
59
60impl<G, F> Iterator for Bfs<'_, '_, G, F>
61where
62    G: IndexGraphView,
63    F: FnMut(G::Edge) -> bool,
64{
65    type Item = G::Node;
66
67    fn next(&mut self) -> Option<Self::Item> {
68        let node = self.workspace.queue.pop_front()?;
69        let workspace = &mut *self.workspace;
70        for_each_neighbor(
71            self.graph,
72            node,
73            self.direction,
74            &mut self.keep_edge,
75            |neighbor| {
76                if workspace.mark(G::node_slot(neighbor)) {
77                    workspace.queue.push_back(neighbor);
78                }
79            },
80        );
81        Some(node)
82    }
83}
84
85/// Lazy depth-first traversal backed by reusable allocation storage.
86pub struct Dfs<'graph, 'workspace, G, F>
87where
88    G: IndexGraphView,
89{
90    graph: &'graph G,
91    workspace: &'workspace mut TraversalWorkspace<G::Node>,
92    direction: Direction,
93    keep_edge: F,
94}
95
96impl<'graph, 'workspace, G> Dfs<'graph, 'workspace, G, fn(G::Edge) -> bool>
97where
98    G: IndexGraphView,
99{
100    #[must_use]
101    pub fn new(
102        graph: &'graph G,
103        start: G::Node,
104        workspace: &'workspace mut TraversalWorkspace<G::Node>,
105    ) -> Self {
106        Self::filtered(graph, start, Direction::Outgoing, workspace, accept_all)
107    }
108}
109
110impl<'graph, 'workspace, G, F> Dfs<'graph, 'workspace, G, F>
111where
112    G: IndexGraphView,
113    F: FnMut(G::Edge) -> bool,
114{
115    #[must_use]
116    pub fn filtered(
117        graph: &'graph G,
118        start: G::Node,
119        direction: Direction,
120        workspace: &'workspace mut TraversalWorkspace<G::Node>,
121        keep_edge: F,
122    ) -> Self {
123        workspace.begin(graph.node_bound());
124        if graph.contains_node(start) && workspace.mark(G::node_slot(start)) {
125            workspace.stack.push(start);
126        }
127        Self {
128            graph,
129            workspace,
130            direction,
131            keep_edge,
132        }
133    }
134}
135
136impl<G, F> Iterator for Dfs<'_, '_, G, F>
137where
138    G: IndexGraphView,
139    F: FnMut(G::Edge) -> bool,
140{
141    type Item = G::Node;
142
143    fn next(&mut self) -> Option<Self::Item> {
144        let node = self.workspace.stack.pop()?;
145        self.workspace.scratch.clear();
146        let workspace = &mut *self.workspace;
147        for_each_neighbor(
148            self.graph,
149            node,
150            self.direction,
151            &mut self.keep_edge,
152            |neighbor| {
153                if workspace.mark(G::node_slot(neighbor)) {
154                    workspace.scratch.push(neighbor);
155                }
156            },
157        );
158        while let Some(neighbor) = self.workspace.scratch.pop() {
159            self.workspace.stack.push(neighbor);
160        }
161        Some(node)
162    }
163}
164
165#[must_use]
166pub fn bfs_iter<'graph, 'workspace, G>(
167    graph: &'graph G,
168    start: G::Node,
169    workspace: &'workspace mut TraversalWorkspace<G::Node>,
170) -> Bfs<'graph, 'workspace, G, fn(G::Edge) -> bool>
171where
172    G: IndexGraphView,
173{
174    Bfs::new(graph, start, workspace)
175}
176
177#[must_use]
178pub fn bfs_iter_filtered<'graph, 'workspace, G, F>(
179    graph: &'graph G,
180    start: G::Node,
181    direction: Direction,
182    workspace: &'workspace mut TraversalWorkspace<G::Node>,
183    keep_edge: F,
184) -> Bfs<'graph, 'workspace, G, F>
185where
186    G: IndexGraphView,
187    F: FnMut(G::Edge) -> bool,
188{
189    Bfs::filtered(graph, start, direction, workspace, keep_edge)
190}
191
192#[must_use]
193pub fn dfs_iter<'graph, 'workspace, G>(
194    graph: &'graph G,
195    start: G::Node,
196    workspace: &'workspace mut TraversalWorkspace<G::Node>,
197) -> Dfs<'graph, 'workspace, G, fn(G::Edge) -> bool>
198where
199    G: IndexGraphView,
200{
201    Dfs::new(graph, start, workspace)
202}
203
204#[must_use]
205pub fn dfs_iter_filtered<'graph, 'workspace, G, F>(
206    graph: &'graph G,
207    start: G::Node,
208    direction: Direction,
209    workspace: &'workspace mut TraversalWorkspace<G::Node>,
210    keep_edge: F,
211) -> Dfs<'graph, 'workspace, G, F>
212where
213    G: IndexGraphView,
214    F: FnMut(G::Edge) -> bool,
215{
216    Dfs::filtered(graph, start, direction, workspace, keep_edge)
217}
weavatrix_graph/algo/walk/basic.rs

weavatrix_graph/algo/walk/
basic.rs
