query_planning/plan/graph_algorithm/
structure.rs

1//! Graph structure, edge normalization, and structural algorithm contracts.
2use std::fmt;
3
4use super::{GraphConstructionOptions, GraphEdgeColumnBindings};
5
6/// Edge-list normalization inserted before raw cuGraph construction.
7///
8/// The Python-compatible policy drops duplicate directed edges and inserts
9/// reverse edges for undirected graphs before cuGraph construction. Weighted
10/// duplicate conflicts use [`EdgeWeightCombiner`] to define the retained value.
11#[derive(Debug, Clone, PartialEq, Eq)]
12pub struct EdgeNormalizeSpec {
13    /// Edge-list columns used by normalization.
14    pub edge_columns: GraphEdgeColumnBindings,
15    /// Whether reverse edges are inserted before deduplication.
16    pub add_reverse: bool,
17    /// Duplicate-edge retention policy.
18    pub dedup: EdgeDedupStrategy,
19    /// Duplicate-weight conflict policy.
20    pub weight_combiner: EdgeWeightCombiner,
21}
22
23impl EdgeNormalizeSpec {
24    /// Build the Python-compatible edge normalization spec.
25    pub fn python_cugraph(edge_columns: GraphEdgeColumnBindings, graph_options: &GraphConstructionOptions) -> Self {
26        let has_weight = edge_columns.weight.is_some();
27        let (dedup, weight_combiner) = match (graph_options.directed, has_weight) {
28            (_, false) => (EdgeDedupStrategy::KeepLast, EdgeWeightCombiner::None),
29            (true, true) => (EdgeDedupStrategy::KeepLast, EdgeWeightCombiner::KeepLastInputOrder),
30            (false, true) => (EdgeDedupStrategy::KeepFirst, EdgeWeightCombiner::MinWeight),
31        };
32        Self { edge_columns, add_reverse: !graph_options.directed, dedup, weight_combiner }
33    }
34}
35
36/// Duplicate-edge handling applied by edge-list normalization.
37#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
38pub enum EdgeDedupStrategy {
39    /// Keep duplicate edges.
40    None,
41    /// Keep the first duplicate edge in input order.
42    KeepFirst,
43    /// Keep the last duplicate edge in input order.
44    KeepLast,
45}
46
47impl EdgeDedupStrategy {
48    /// Stable lowercase duplicate-edge policy code.
49    pub const fn as_str(self) -> &'static str {
50        match self {
51            Self::None => "none",
52            Self::KeepFirst => "keep_first",
53            Self::KeepLast => "keep_last",
54        }
55    }
56}
57
58impl fmt::Display for EdgeDedupStrategy {
59    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
60        f.write_str(self.as_str())
61    }
62}
63
64/// Weighted duplicate-edge conflict policy.
65#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
66pub enum EdgeWeightCombiner {
67    /// No weight combination is required.
68    None,
69    /// Keep the minimum weight among duplicate edges.
70    MinWeight,
71    /// Keep the weight from the last duplicate in input order.
72    KeepLastInputOrder,
73}
74
75impl EdgeWeightCombiner {
76    /// Stable lowercase weight-combiner code.
77    pub const fn as_str(self) -> &'static str {
78        match self {
79            Self::None => "none",
80            Self::MinWeight => "min_weight",
81            Self::KeepLastInputOrder => "keep_last_input_order",
82        }
83    }
84}
85
86impl fmt::Display for EdgeWeightCombiner {
87    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
88        f.write_str(self.as_str())
89    }
90}
91
92/// Degree direction for core-number and k-core computations.
93///
94/// Mirrors `cugraph::structure::KCoreDegreeType` without depending on the
95/// cugraph feature so the native IR can be constructed without the cuGraph
96/// feature.
97#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
98pub enum GraphKCoreDegreeType {
99    /// Use incoming edges.
100    In,
101    /// Use outgoing edges.
102    Out,
103    #[default]
104    /// Use both incoming and outgoing edges.
105    InOut,
106}
107
108impl GraphKCoreDegreeType {
109    /// Stable lowercase degree-type code.
110    pub const fn as_str(self) -> &'static str {
111        match self {
112            Self::In => "in",
113            Self::Out => "out",
114            Self::InOut => "in_out",
115        }
116    }
117}
118
119impl fmt::Display for GraphKCoreDegreeType {
120    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
121        f.write_str(self.as_str())
122    }
123}
124
125/// Zero-argument all-vertex degree computation.
126///
127/// No algorithm-specific options beyond the shared graph construction options.
128#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
129pub struct GraphDegreesAllParams;
130
131/// Zero-argument all-vertex in-degree computation.
132///
133/// Direction is fixed by the algorithm; shared graph construction options
134/// still control directedness, renumbering, and edge normalization.
135#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
136pub struct GraphInDegreesAllParams;
137
138/// Zero-argument all-vertex out-degree computation.
139///
140/// Direction is fixed by the algorithm; shared graph construction options
141/// still control directedness, renumbering, and edge normalization.
142#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
143pub struct GraphOutDegreesAllParams;
144
145/// Zero-argument all-vertex triangle count.
146///
147/// Output schema is fixed by [`crate::plan::stable_graph_result_schema`].
148#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
149pub struct GraphTriangleCountAllParams;
150
151/// Parameters for core-number computation.
152#[derive(Debug, Clone, Copy, PartialEq, Eq)]
153pub struct GraphCoreNumberParams {
154    /// Which edge direction to use when computing core numbers.
155    pub degree_type: GraphKCoreDegreeType,
156}
157
158impl Default for GraphCoreNumberParams {
159    fn default() -> Self {
160        Self { degree_type: GraphKCoreDegreeType::InOut }
161    }
162}
163
164/// Parameters for k-core subgraph extraction.
165///
166/// Mirrors `cugraph::structure::KCoreParams` without the `cugraph` crate's
167/// newtype wrappers so the native IR can be constructed without the cuGraph feature.
168#[derive(Debug, Clone, Copy, PartialEq, Eq)]
169pub struct GraphKCoreParams {
170    /// K value for the extracted core. Must be >= 1.
171    pub k: u32,
172    /// Degree direction to use when computing core numbers internally.
173    pub degree_type: GraphKCoreDegreeType,
174}
175
176impl Default for GraphKCoreParams {
177    fn default() -> Self {
178        Self { k: 2, degree_type: GraphKCoreDegreeType::InOut }
179    }
180}
181
182/// Parameters for minimum spanning tree extraction.
183///
184/// No algorithm-specific options beyond the shared graph construction options.
185#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
186pub struct GraphMstParams;
query_planning/plan/graph_algorithm/structure.rs

query_planning/plan/graph_algorithm/
structure.rs
