graph_api_lib/walker/
mod.rs

1use crate::graph::Graph;
2use crate::search::vertex::VertexSearch;
3use crate::walker::builder::{ImmutableMarker, VertexWalkerBuilder};
4use crate::walker::steps::{
5    Detour, EdgeContext, EdgeControlFlow, EdgeFilter, EdgeReduce, EdgeTake, Edges, End, Endpoints,
6    VertexContext, VertexControlFlow, VertexFilter, VertexIter, VertexReduce, VertexTake, Vertices,
7    Waypoint,
8};
9use crate::{EdgeSearch, ElementId};
10
11pub mod builder;
12mod iter;
13pub mod steps;
14
15/// A trait that defines the basic behavior of a graph walker.
16///
17/// The `Walker` trait is the foundation for traversing and exploring graphs in the
18/// graph-api-lib crate. It defines the core methods that all walkers must implement,
19/// such as `next_element` to retrieve the next vertex or edge in the graph, and
20/// `ctx` to access the walker's internal context.
21///
22/// Implementors of this trait are responsible for defining the specific graph
23/// representation they work with (via the `Graph` associated type) and the
24/// internal state they need to track during the walk (via the `Context`
25/// associated type).
26pub trait Walker<'graph>
27where
28    Self: Sized,
29{
30    /// The graph that the traversal is applied to.
31    type Graph: Graph;
32
33    /// The current context of the walker, this allows users to collect data as they traverse
34    /// a graph.
35    type Context: Clone + 'static;
36
37    /// Return the next element in the traversal.
38    fn next_element(&mut self, graph: &'graph Self::Graph) -> Option<ElementId<Self::Graph>>;
39
40    /// Returns the current context of the walker.
41    fn ctx(&self) -> &Self::Context;
42
43    /// Returns the mutable current context of the walker.
44    fn ctx_mut(&mut self) -> &mut Self::Context;
45}
46
47/// A trait that defines the basic behavior of a vertex walker, which is a specialized
48/// type of graph walker that focuses on traversing and exploring the vertices in a graph.
49///
50/// The `VertexWalker` trait provides a set of methods for working with vertices, such as
51/// filtering vertices based on a predicate, limiting the number of vertices returned,
52/// and collecting the vertices into a specific data structure.
53///
54/// Implementors of this trait are responsible for defining the specific graph
55/// representation they work with (via the `Graph` associated type) and the
56/// internal state they need to track during the walk (via the `Context`
57/// associated type).
58pub trait VertexWalker<'graph>: Walker<'graph> {
59    fn vertices_by_id<Iter>(self, vertex_ids: Iter) -> VertexIter<'graph, Self, Iter::IntoIter>
60    where
61        Iter: IntoIterator<Item = <Self::Graph as Graph>::VertexId>,
62    {
63        VertexIter::new(self, vertex_ids.into_iter())
64    }
65
66    fn vertices<'search>(
67        self,
68        vertex_search: VertexSearch<'search, Self::Graph>,
69    ) -> Vertices<'search, 'graph, Self> {
70        Vertices::new(self, vertex_search)
71    }
72
73    fn filter<Predicate>(self, predicate: Predicate) -> VertexFilter<'graph, Self, Predicate>
74    where
75        Predicate: Fn(&<Self::Graph as Graph>::VertexReference<'_>, &Self::Context) -> bool,
76    {
77        VertexFilter::new(self, predicate)
78    }
79
80    fn control_flow<Predicate>(
81        self,
82        predicate: Predicate,
83    ) -> VertexControlFlow<'graph, Self, Predicate>
84    where
85        Self: 'graph,
86        for<'a> Predicate: Fn(
87            &'a <Self::Graph as Graph>::VertexReference<'graph>,
88            &mut Self::Context,
89        ) -> std::ops::ControlFlow<
90            Option<&'a <Self::Graph as Graph>::VertexReference<'graph>>,
91            Option<&'a <Self::Graph as Graph>::VertexReference<'graph>>,
92        >,
93    {
94        VertexControlFlow::new(self, predicate)
95    }
96
97    fn take(self, n: usize) -> VertexTake<'graph, Self> {
98        VertexTake::new(self, n)
99    }
100
101    fn detour<Path, Terminal, WalkerBuilder>(
102        self,
103        path: Path,
104    ) -> Detour<'graph, Self, Path, Terminal>
105    where
106        Path: Fn(
107            VertexWalkerBuilder<
108                'graph,
109                ImmutableMarker,
110                Self::Graph,
111                Waypoint<'graph, Self::Graph, Self::Context>,
112            >,
113        ) -> WalkerBuilder,
114        WalkerBuilder: Into<builder::WalkerBuilder<'graph, ImmutableMarker, Self::Graph, Terminal>>,
115        Terminal: Walker<'graph, Graph = Self::Graph>,
116        <Self as Walker<'graph>>::Graph: 'graph,
117    {
118        Detour::new(self, path)
119    }
120
121    fn context<Callback, Context>(
122        self,
123        predicate: Callback,
124    ) -> VertexContext<'graph, Self, Callback, Context>
125    where
126        Callback: Fn(&<Self::Graph as Graph>::VertexReference<'_>, &Self::Context) -> Context,
127    {
128        VertexContext::new(self, predicate)
129    }
130
131    fn edges(self, search: EdgeSearch<Self::Graph>) -> Edges<'_, 'graph, Self> {
132        Edges::new(self, search)
133    }
134
135    fn reduce<Reducer>(self, reducer: Reducer) -> VertexReduce<'graph, Self, Reducer>
136    where
137        Reducer: for<'a> Fn(
138            &'a <Self::Graph as Graph>::VertexReference<'graph>,
139            &'a <Self::Graph as Graph>::VertexReference<'graph>,
140            &Self::Context,
141        ) -> &'a <Self::Graph as Graph>::VertexReference<'graph>,
142        <Self as Walker<'graph>>::Graph: 'graph,
143    {
144        VertexReduce::new(self, reducer)
145    }
146
147    /// Returns the next vertex ID in the traversal.
148    ///
149    /// This method advances the walker and returns the ID of the next vertex,
150    /// or None if there are no more vertices to traverse.
151    ///
152    /// # Parameters
153    /// - `graph`: The graph being traversed
154    ///
155    /// # Returns
156    /// The ID of the next vertex, or None if the traversal is complete
157    fn next(&mut self, graph: &'graph Self::Graph) -> Option<<Self::Graph as Graph>::VertexId>;
158}
159
160/// Trait for walking over edges in a graph.
161///
162/// This trait provides methods for working with edges in a graph, including
163/// filtering, limiting, and collecting edges. It also provides methods for
164/// accessing the head and tail of an edge.
165///
166/// Implementors of this trait are expected to be able to walk over the edges
167/// of a graph, and to provide access to the edge references and the context
168/// associated with the edge walker.
169pub trait EdgeWalker<'graph>: Walker<'graph> {
170    fn context<Callback, Context>(
171        self,
172        predicate: Callback,
173    ) -> EdgeContext<'graph, Self, Callback, Context>
174    where
175        Callback: Fn(&<Self::Graph as Graph>::EdgeReference<'_>, &Self::Context) -> Context,
176    {
177        EdgeContext::new(self, predicate)
178    }
179
180    fn filter<Predicate>(self, predicate: Predicate) -> EdgeFilter<'graph, Self, Predicate>
181    where
182        Predicate: Fn(&<Self::Graph as Graph>::EdgeReference<'_>, &Self::Context) -> bool,
183    {
184        EdgeFilter::new(self, predicate)
185    }
186
187    fn control_flow<Predicate>(
188        self,
189        predicate: Predicate,
190    ) -> EdgeControlFlow<'graph, Self, Predicate>
191    where
192        Self: 'graph,
193        for<'a> Predicate: Fn(
194            &'a <Self::Graph as Graph>::EdgeReference<'graph>,
195            &mut Self::Context,
196        ) -> std::ops::ControlFlow<
197            Option<&'a <Self::Graph as Graph>::EdgeReference<'graph>>,
198            Option<&'a <Self::Graph as Graph>::EdgeReference<'graph>>,
199        >,
200    {
201        EdgeControlFlow::new(self, predicate)
202    }
203
204    fn head(self) -> Endpoints<'graph, Self> {
205        Endpoints::new(self, End::Head)
206    }
207
208    fn tail(self) -> Endpoints<'graph, Self> {
209        Endpoints::new(self, End::Tail)
210    }
211
212    fn take(self, n: usize) -> EdgeTake<'graph, Self> {
213        EdgeTake::new(self, n)
214    }
215
216    fn reduce<Reducer>(self, reducer: Reducer) -> EdgeReduce<'graph, Self, Reducer>
217    where
218        Reducer: for<'a> Fn(
219            &'a <Self::Graph as Graph>::EdgeReference<'graph>,
220            &'a <Self::Graph as Graph>::EdgeReference<'graph>,
221            &Self::Context,
222        ) -> &'a <Self::Graph as Graph>::EdgeReference<'graph>,
223        <Self as Walker<'graph>>::Graph: 'graph,
224    {
225        EdgeReduce::new(self, reducer)
226    }
227
228    /// Returns the next edge ID in the traversal.
229    ///
230    /// This method advances the walker and returns the ID of the next edge,
231    /// or None if there are no more edges to traverse.
232    ///
233    /// # Parameters
234    /// - `graph`: The graph being traversed
235    ///
236    /// # Returns
237    /// The ID of the next edge, or None if the traversal is complete
238    fn next(&mut self, graph: &'graph Self::Graph) -> Option<<Self::Graph as Graph>::EdgeId>;
239}
graph_api_lib/walker/mod.rs

graph_api_lib/walker/
mod.rs
