graph_api_lib/walker/steps/
reduce.rs

1use crate::ElementId;
2use crate::graph::{
3    EdgeReference as GraphEdgeReference, Graph, VertexReference as GraphVertexReference,
4};
5use crate::walker::builder::{EdgeWalkerBuilder, VertexWalkerBuilder};
6use crate::walker::{EdgeWalker, VertexWalker, Walker};
7use include_doc::function_body;
8use std::marker::PhantomData;
9// ================ REDUCE IMPLEMENTATION ================
10
11pub struct VertexReduce<'graph, Parent, Reducer>
12where
13    Parent: Walker<'graph>,
14{
15    _phantom_data: PhantomData<&'graph ()>,
16    parent: Parent,
17    reducer: Reducer,
18}
19
20impl<'graph, Parent, Reducer> VertexReduce<'graph, Parent, Reducer>
21where
22    Parent: Walker<'graph>,
23{
24    pub(crate) fn new(parent: Parent, reducer: Reducer) -> Self {
25        VertexReduce {
26            _phantom_data: Default::default(),
27            parent,
28            reducer,
29        }
30    }
31}
32
33impl<'graph, Parent, Reducer> Walker<'graph> for VertexReduce<'graph, Parent, Reducer>
34where
35    Parent: VertexWalker<'graph>,
36    Parent::Graph: 'graph,
37    Reducer: for<'a> Fn(
38        &'a <Parent::Graph as Graph>::VertexReference<'graph>,
39        &'a <Parent::Graph as Graph>::VertexReference<'graph>,
40        &Parent::Context,
41    ) -> &'a <Parent::Graph as Graph>::VertexReference<'graph>,
42{
43    type Graph = Parent::Graph;
44    type Context = Parent::Context;
45
46    fn next_element(&mut self, graph: &'graph Self::Graph) -> Option<ElementId<Self::Graph>> {
47        self.next(graph).map(ElementId::Vertex)
48    }
49
50    fn ctx(&self) -> &Self::Context {
51        self.parent.ctx()
52    }
53
54    fn ctx_mut(&mut self) -> &mut Self::Context {
55        self.parent.ctx_mut()
56    }
57}
58
59impl<'graph, Parent, Reducer> VertexWalker<'graph> for VertexReduce<'graph, Parent, Reducer>
60where
61    Parent: VertexWalker<'graph>,
62    Parent::Graph: 'graph,
63    Reducer: for<'a> Fn(
64        &'a <Parent::Graph as Graph>::VertexReference<'graph>,
65        &'a <Parent::Graph as Graph>::VertexReference<'graph>,
66        &Parent::Context,
67    ) -> &'a <Parent::Graph as Graph>::VertexReference<'graph>,
68    Parent::Context: Clone,
69{
70    fn next(&mut self, graph: &'graph Self::Graph) -> Option<<Self::Graph as Graph>::VertexId> {
71        let mut acc_vertex = None;
72        loop {
73            if let Some(next) = self.parent.next(graph) {
74                let vertex_reference = graph.vertex(next).expect("vertex must exist");
75                if let Some(acc_vertex_ref) = &acc_vertex {
76                    let result =
77                        (self.reducer)(acc_vertex_ref, &vertex_reference, self.parent.ctx());
78
79                    if std::ptr::eq(result, &vertex_reference) {
80                        acc_vertex = Some(vertex_reference);
81                    }
82                } else {
83                    // For the first element, we don't apply the reducer, just set it as the accumulator
84                    acc_vertex = Some(vertex_reference);
85                }
86            } else {
87                return acc_vertex.map(|acc| acc.id());
88            }
89        }
90    }
91}
92
93pub struct EdgeReduce<'graph, Parent, Reducer>
94where
95    Parent: Walker<'graph>,
96{
97    _phantom_data: PhantomData<&'graph ()>,
98    parent: Parent,
99    reducer: Reducer,
100}
101
102impl<'graph, Parent, Reducer> EdgeReduce<'graph, Parent, Reducer>
103where
104    Parent: Walker<'graph>,
105{
106    pub(crate) fn new(parent: Parent, reducer: Reducer) -> Self {
107        EdgeReduce {
108            _phantom_data: Default::default(),
109            parent,
110            reducer,
111        }
112    }
113}
114
115impl<'graph, Parent, Reducer> Walker<'graph> for EdgeReduce<'graph, Parent, Reducer>
116where
117    Parent: EdgeWalker<'graph>,
118    Parent::Graph: 'graph,
119    Reducer: for<'a> Fn(
120        &'a <Parent::Graph as Graph>::EdgeReference<'graph>,
121        &'a <Parent::Graph as Graph>::EdgeReference<'graph>,
122        &Parent::Context,
123    ) -> &'a <Parent::Graph as Graph>::EdgeReference<'graph>,
124{
125    type Graph = Parent::Graph;
126    type Context = Parent::Context;
127
128    fn next_element(&mut self, graph: &'graph Self::Graph) -> Option<ElementId<Self::Graph>> {
129        self.next(graph).map(ElementId::Edge)
130    }
131
132    fn ctx(&self) -> &Self::Context {
133        self.parent.ctx()
134    }
135
136    fn ctx_mut(&mut self) -> &mut Self::Context {
137        self.parent.ctx_mut()
138    }
139}
140
141impl<'graph, Parent, Reducer> EdgeWalker<'graph> for EdgeReduce<'graph, Parent, Reducer>
142where
143    Parent: EdgeWalker<'graph>,
144    Parent::Graph: 'graph,
145    Reducer: for<'a> Fn(
146        &'a <Parent::Graph as Graph>::EdgeReference<'graph>,
147        &'a <Parent::Graph as Graph>::EdgeReference<'graph>,
148        &Parent::Context,
149    ) -> &'a <Parent::Graph as Graph>::EdgeReference<'graph>,
150    Parent::Context: Clone,
151{
152    fn next(&mut self, graph: &'graph Self::Graph) -> Option<<Self::Graph as Graph>::EdgeId> {
153        let mut acc_edge = None;
154        loop {
155            if let Some(next) = self.parent.next(graph) {
156                let edge_reference = graph.edge(next).expect("edge must exist");
157                if let Some(acc_edge_ref) = &acc_edge {
158                    let result = (self.reducer)(acc_edge_ref, &edge_reference, self.parent.ctx());
159
160                    if std::ptr::eq(result, &edge_reference) {
161                        acc_edge = Some(edge_reference);
162                    }
163                } else {
164                    // For the first element, we don't apply the reducer, just set it as the accumulator
165                    acc_edge = Some(edge_reference);
166                }
167            } else {
168                return acc_edge.map(|acc| acc.id());
169            }
170        }
171    }
172}
173
174// ================ BUILDER METHODS ================
175
176impl<'graph, Mutability, Graph, Walker> VertexWalkerBuilder<'graph, Mutability, Graph, Walker>
177where
178    Graph: crate::graph::Graph + 'graph,
179    Walker: VertexWalker<'graph, Graph = Graph>,
180{
181    /// # Reduce Step
182    ///
183    /// The `reduce` step combines elements in a traversal using a reducer function,
184    /// with the first element as the initial accumulator.
185    ///
186    /// ## Visual Diagram
187    ///
188    /// Before reduce step (traversal position on vertices):
189    /// ```text
190    ///   [A]* --- edge1 ---> [B]* --- edge2 ---> [C]*  
191    ///    ^                                         
192    ///    |                                         
193    ///   edge3                                       
194    ///    |                                         
195    ///   [D]*                                        
196    /// ```
197    ///
198    /// After reduce step (a single vertex containing the combined result):
199    /// ```text
200    ///   [Result]* --- ... ---> [More Traversal Steps]
201    /// ```
202    ///
203    /// ## Parameters
204    /// - `reducer`: A closure that takes:
205    ///   - The current accumulated element (left)
206    ///   - The next element to combine (right)
207    ///   - The parent walker's context (passed through)
208    ///   - Returns either the left or right element to continue the reduction
209    ///
210    /// ## Return Value
211    ///
212    /// Returns a walker containing a single vertex representing the final reduced value.
213    /// If the input traversal is empty, the walker will yield nothing.
214    ///
215    /// ## Example
216    ///
217    /// ```rust
218    #[doc = function_body!("examples/reduce.rs", vertex_example, [])]
219    /// ```
220    ///
221    /// ## Notes
222    ///
223    /// - The reduce step is a non-terminal operation - it can be chained with other operations
224    /// - The walker will yield a single vertex - the final result of combining all input vertices
225    /// - If the traversal is empty, the walker will yield nothing
226    /// - The first element serves as the initial accumulator value
227    /// - Useful for finding maximum/minimum values or combining elements in a custom way
228    /// - Unlike `fold`, reduce doesn't require an initial value and can still participate in further traversal
229    /// - The reducer function must return a reference to one of the two input elements
230    /// - The returned element becomes the new accumulator for the next reduction step
231    /// - The reducer function operates on the elements only, the context remains unchanged
232    pub fn reduce<Reducer>(
233        self,
234        reducer: Reducer,
235    ) -> VertexWalkerBuilder<'graph, Mutability, Graph, VertexReduce<'graph, Walker, Reducer>>
236    where
237        Reducer: for<'a> Fn(
238            &'a Graph::VertexReference<'graph>,
239            &'a Graph::VertexReference<'graph>,
240            &Walker::Context,
241        ) -> &'a Graph::VertexReference<'graph>,
242    {
243        self.with_vertex_walker(|walker| walker.reduce(reducer))
244    }
245}
246
247impl<'graph, Mutability, Graph, Walker> EdgeWalkerBuilder<'graph, Mutability, Graph, Walker>
248where
249    Graph: crate::graph::Graph + 'graph,
250    Walker: EdgeWalker<'graph, Graph = Graph>,
251{
252    /// # Reduce Step
253    ///
254    /// Combines edges in the traversal using a reducer function, with the first edge as the initial accumulator.
255    ///
256    /// ## Visual Diagram
257    ///
258    /// Before reduce step (traversal position on edges):
259    /// ```text
260    ///   [A] --- edge1* ---> [B] --- edge2* ---> [C]  
261    ///    ^                                         
262    ///    |                                         
263    ///   edge3*                                     
264    ///    |                                         
265    ///   [D]                                        
266    /// ```
267    ///
268    /// After reduce step (a single edge containing the combined result):
269    /// ```text
270    ///   [Source] --- [Result]* ---> [Target] --- ... ---> [More Traversal Steps]
271    /// ```
272    ///
273    /// ## Parameters
274    /// - `reducer`: A closure that takes:
275    ///   - The current accumulated edge (left)
276    ///   - The next edge to combine (right)
277    ///   - The parent walker's context (passed through)
278    ///   - Returns either the left or right edge to continue the reduction
279    ///
280    /// ## Return Value
281    ///
282    /// Returns a walker containing a single edge representing the final reduced value.
283    /// If the input traversal is empty, the walker will yield nothing.
284    ///
285    /// ## Example
286    ///
287    /// ```rust
288    #[doc = function_body!("examples/reduce.rs", edge_example, [])]
289    /// ```
290    ///
291    /// ## Notes
292    ///
293    /// - The reduce step is a non-terminal operation - it can be chained with other operations
294    /// - The walker will yield a single edge - the final result of combining all input edges
295    /// - If the traversal is empty, the walker will yield nothing
296    /// - The first element serves as the initial accumulator value
297    /// - The reducer function must return a reference to one of the two input elements
298    /// - The returned element becomes the new accumulator for the next reduction step
299    /// - The reducer function operates on the elements only, the context remains unchanged
300    pub fn reduce<Reducer>(
301        self,
302        reducer: Reducer,
303    ) -> EdgeWalkerBuilder<'graph, Mutability, Graph, EdgeReduce<'graph, Walker, Reducer>>
304    where
305        Reducer: for<'a> Fn(
306            &'a Graph::EdgeReference<'graph>,
307            &'a Graph::EdgeReference<'graph>,
308            &Walker::Context,
309        ) -> &'a Graph::EdgeReference<'graph>,
310    {
311        self.with_edge_walker(|walker| walker.reduce(reducer))
312    }
313}
graph_api_lib/walker/steps/reduce.rs

graph_api_lib/walker/steps/
reduce.rs
