graphos_adapters/plugins/algorithms/
traits.rs

1//! Core traits and types for graph algorithms.
2//!
3//! This module provides the fundamental building blocks for implementing
4//! high-performance graph algorithms, inspired by rustworkx patterns.
5
6use graphos_common::types::{EdgeId, NodeId, Value};
7use graphos_common::utils::error::Result;
8use graphos_core::graph::lpg::LpgStore;
9use std::cmp::Ordering;
10use std::collections::HashMap;
11
12use super::super::{AlgorithmResult, ParameterDef, Parameters};
13
14// ============================================================================
15// Control Flow
16// ============================================================================
17
18/// Control flow for algorithm visitors.
19///
20/// Returned by visitor callbacks to control traversal behavior.
21#[derive(Debug, Clone, Copy, PartialEq, Eq)]
22pub enum Control<B = ()> {
23    /// Continue the algorithm normally.
24    Continue,
25    /// Stop the algorithm and return the break value.
26    Break(B),
27    /// Skip the current subtree (for traversals) but continue the algorithm.
28    Prune,
29}
30
31impl<B> Control<B> {
32    /// Returns `true` if this is `Continue`.
33    #[inline]
34    pub fn is_continue(&self) -> bool {
35        matches!(self, Control::Continue)
36    }
37
38    /// Returns `true` if this is `Break`.
39    #[inline]
40    pub fn is_break(&self) -> bool {
41        matches!(self, Control::Break(_))
42    }
43
44    /// Returns `true` if this is `Prune`.
45    #[inline]
46    pub fn is_prune(&self) -> bool {
47        matches!(self, Control::Prune)
48    }
49
50    /// Converts to an option containing the break value.
51    pub fn break_value(self) -> Option<B> {
52        match self {
53            Control::Break(b) => Some(b),
54            _ => None,
55        }
56    }
57}
58
59impl<B> Default for Control<B> {
60    fn default() -> Self {
61        Control::Continue
62    }
63}
64
65// ============================================================================
66// Traversal Events
67// ============================================================================
68
69/// Events emitted during graph traversal (BFS/DFS).
70///
71/// These events follow the visitor pattern, allowing algorithms to
72/// react to different stages of the traversal.
73#[derive(Debug, Clone, Copy, PartialEq, Eq)]
74pub enum TraversalEvent {
75    /// A node is discovered for the first time.
76    Discover(NodeId),
77
78    /// A tree edge is traversed (edge to an undiscovered node).
79    TreeEdge {
80        /// The source node of the edge.
81        source: NodeId,
82        /// The target node of the edge.
83        target: NodeId,
84        /// The edge ID.
85        edge: EdgeId,
86    },
87
88    /// A non-tree edge is traversed (edge to an already-discovered node).
89    /// In BFS, this is a cross edge. In DFS, this could be a back edge or cross edge.
90    NonTreeEdge {
91        /// The source node of the edge.
92        source: NodeId,
93        /// The target node of the edge.
94        target: NodeId,
95        /// The edge ID.
96        edge: EdgeId,
97    },
98
99    /// A back edge is traversed (DFS only - edge to an ancestor).
100    BackEdge {
101        /// The source node of the edge.
102        source: NodeId,
103        /// The target node of the edge.
104        target: NodeId,
105        /// The edge ID.
106        edge: EdgeId,
107    },
108
109    /// Processing of a node is complete.
110    Finish(NodeId),
111}
112
113impl TraversalEvent {
114    /// Returns the source node of this event, if applicable.
115    pub fn source(&self) -> Option<NodeId> {
116        match self {
117            TraversalEvent::Discover(n) | TraversalEvent::Finish(n) => Some(*n),
118            TraversalEvent::TreeEdge { source, .. }
119            | TraversalEvent::NonTreeEdge { source, .. }
120            | TraversalEvent::BackEdge { source, .. } => Some(*source),
121        }
122    }
123
124    /// Returns the target node of this event, if applicable.
125    pub fn target(&self) -> Option<NodeId> {
126        match self {
127            TraversalEvent::Discover(n) | TraversalEvent::Finish(n) => Some(*n),
128            TraversalEvent::TreeEdge { target, .. }
129            | TraversalEvent::NonTreeEdge { target, .. }
130            | TraversalEvent::BackEdge { target, .. } => Some(*target),
131        }
132    }
133}
134
135// ============================================================================
136// Priority Queue Support
137// ============================================================================
138
139/// Wrapper for priority queue ordering (min-heap behavior).
140///
141/// Rust's `BinaryHeap` is a max-heap, so we reverse the ordering
142/// to get min-heap behavior for Dijkstra and A*.
143#[derive(Clone, Copy, Debug)]
144pub struct MinScored<K, T>(pub K, pub T);
145
146impl<K, T> MinScored<K, T> {
147    /// Creates a new `MinScored` with the given score and value.
148    pub fn new(score: K, value: T) -> Self {
149        MinScored(score, value)
150    }
151
152    /// Returns the score.
153    pub fn score(&self) -> &K {
154        &self.0
155    }
156
157    /// Returns the value.
158    pub fn value(&self) -> &T {
159        &self.1
160    }
161
162    /// Consumes self and returns the value.
163    pub fn into_value(self) -> T {
164        self.1
165    }
166}
167
168impl<K: PartialOrd, T> PartialEq for MinScored<K, T> {
169    fn eq(&self, other: &Self) -> bool {
170        self.0 == other.0
171    }
172}
173
174impl<K: PartialOrd, T> Eq for MinScored<K, T> {}
175
176impl<K: PartialOrd, T> PartialOrd for MinScored<K, T> {
177    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
178        // Reverse ordering for min-heap
179        other.0.partial_cmp(&self.0)
180    }
181}
182
183impl<K: PartialOrd, T> Ord for MinScored<K, T> {
184    fn cmp(&self, other: &Self) -> Ordering {
185        self.partial_cmp(other).unwrap_or(Ordering::Equal)
186    }
187}
188
189// ============================================================================
190// Graph Algorithm Traits
191// ============================================================================
192
193/// A graph algorithm that can be executed on an LPG store.
194///
195/// This trait extends the base `Algorithm` trait with graph-specific
196/// functionality, providing direct access to the graph store.
197pub trait GraphAlgorithm: Send + Sync {
198    /// Returns the name of the algorithm.
199    fn name(&self) -> &str;
200
201    /// Returns a description of the algorithm.
202    fn description(&self) -> &str;
203
204    /// Returns the parameter definitions for this algorithm.
205    fn parameters(&self) -> &[ParameterDef];
206
207    /// Executes the algorithm on the given graph store.
208    fn execute(&self, store: &LpgStore, params: &Parameters) -> Result<AlgorithmResult>;
209}
210
211/// A graph algorithm that supports parallel execution.
212///
213/// Algorithms implementing this trait can automatically switch between
214/// sequential and parallel execution based on graph size.
215pub trait ParallelGraphAlgorithm: GraphAlgorithm {
216    /// Minimum node count to trigger parallelization.
217    ///
218    /// Below this threshold, sequential execution is used to avoid
219    /// parallelization overhead.
220    fn parallel_threshold(&self) -> usize {
221        50
222    }
223
224    /// Executes the algorithm with explicit parallelism control.
225    fn execute_parallel(
226        &self,
227        store: &LpgStore,
228        params: &Parameters,
229        num_threads: usize,
230    ) -> Result<AlgorithmResult>;
231}
232
233// ============================================================================
234// Distance Map
235// ============================================================================
236
237/// A map from nodes to distances/costs.
238///
239/// This trait abstracts over different distance map implementations,
240/// allowing algorithms to work with various storage strategies.
241pub trait DistanceMap<K> {
242    /// Gets the distance to a node, if known.
243    fn get(&self, node: NodeId) -> Option<&K>;
244
245    /// Sets the distance to a node.
246    fn insert(&mut self, node: NodeId, dist: K);
247
248    /// Returns `true` if the node has a recorded distance.
249    fn contains(&self, node: NodeId) -> bool {
250        self.get(node).is_some()
251    }
252}
253
254impl<K> DistanceMap<K> for HashMap<NodeId, K> {
255    fn get(&self, node: NodeId) -> Option<&K> {
256        HashMap::get(self, &node)
257    }
258
259    fn insert(&mut self, node: NodeId, dist: K) {
260        HashMap::insert(self, node, dist);
261    }
262}
263
264// ============================================================================
265// Result Builders
266// ============================================================================
267
268/// Helper for building algorithm results with node ID and value columns.
269pub struct NodeValueResultBuilder {
270    node_ids: Vec<u64>,
271    values: Vec<Value>,
272    value_column_name: String,
273}
274
275impl NodeValueResultBuilder {
276    /// Creates a new builder with the given value column name.
277    #[allow(dead_code)]
278    pub fn new(value_column_name: impl Into<String>) -> Self {
279        Self {
280            node_ids: Vec::new(),
281            values: Vec::new(),
282            value_column_name: value_column_name.into(),
283        }
284    }
285
286    /// Creates a new builder with pre-allocated capacity.
287    pub fn with_capacity(value_column_name: impl Into<String>, capacity: usize) -> Self {
288        Self {
289            node_ids: Vec::with_capacity(capacity),
290            values: Vec::with_capacity(capacity),
291            value_column_name: value_column_name.into(),
292        }
293    }
294
295    /// Adds a node ID and value pair.
296    pub fn push(&mut self, node: NodeId, value: impl Into<Value>) {
297        self.node_ids.push(node.0);
298        self.values.push(value.into());
299    }
300
301    /// Builds the algorithm result.
302    pub fn build(self) -> AlgorithmResult {
303        let mut result = AlgorithmResult::new(vec!["node_id".to_string(), self.value_column_name]);
304        for (node_id, value) in self.node_ids.into_iter().zip(self.values) {
305            result.add_row(vec![Value::Int64(node_id as i64), value]);
306        }
307        result
308    }
309}
310
311/// Helper for building algorithm results with component information.
312pub struct ComponentResultBuilder {
313    node_ids: Vec<u64>,
314    component_ids: Vec<u64>,
315}
316
317impl ComponentResultBuilder {
318    /// Creates a new builder.
319    pub fn new() -> Self {
320        Self {
321            node_ids: Vec::new(),
322            component_ids: Vec::new(),
323        }
324    }
325
326    /// Creates a new builder with pre-allocated capacity.
327    pub fn with_capacity(capacity: usize) -> Self {
328        Self {
329            node_ids: Vec::with_capacity(capacity),
330            component_ids: Vec::with_capacity(capacity),
331        }
332    }
333
334    /// Adds a node ID and component ID pair.
335    pub fn push(&mut self, node: NodeId, component: u64) {
336        self.node_ids.push(node.0);
337        self.component_ids.push(component);
338    }
339
340    /// Builds the algorithm result.
341    pub fn build(self) -> AlgorithmResult {
342        let mut result =
343            AlgorithmResult::new(vec!["node_id".to_string(), "component_id".to_string()]);
344        for (node_id, component_id) in self.node_ids.into_iter().zip(self.component_ids) {
345            result.add_row(vec![
346                Value::Int64(node_id as i64),
347                Value::Int64(component_id as i64),
348            ]);
349        }
350        result
351    }
352}
353
354impl Default for ComponentResultBuilder {
355    fn default() -> Self {
356        Self::new()
357    }
358}
graphos_adapters/plugins/algorithms/traits.rs

graphos_adapters/plugins/algorithms/
traits.rs
