query_planning/plan/graph_algorithm/
definition.rs

1//! Graph algorithm definitions, registry metadata, and construction contracts.
2use std::{fmt, sync::Arc};
3
4use arrow::datatypes::DataType;
5
6use super::{
7    Field, GraphAlgorithmParams, GraphBetweennessCentralityParams, GraphBfsParams, GraphCoreNumberParams,
8    GraphDegreesAllParams, GraphEcgParams, GraphEdgeBetweennessCentralityParams, GraphEigenvectorCentralityParams,
9    GraphForceAtlas2Params, GraphHitsParams, GraphInDegreesAllParams, GraphKCoreParams, GraphKatzCentralityParams,
10    GraphLayoutRequirement, GraphLeidenParams, GraphLouvainParams, GraphMstParams, GraphOutDegreesAllParams,
11    GraphPageRankParams, GraphPersonalizedPageRankParams, GraphSccParams, GraphSimilarityParams,
12    GraphSpectralClusteringParams, GraphSsspParams, GraphSsspSource, GraphTriangleCountAllParams, GraphWccParams,
13    Schema, SchemaRef, stable_graph_result_schema,
14};
15
16/// Native graph algorithm supported by the cuGraph operator boundary.
17///
18/// Every variant must have a matching entry in [`GRAPH_OPERATION_REGISTRY`].
19/// The cuGraph C API index is at <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/>.
20#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
21pub enum GraphAlgorithm {
22    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/centrality/#_CPPv416cugraph_pagerankPK25cugraph_resource_handle_tP15cugraph_graph_tPK39cugraph_type_erased_device_array_view_tPK39cugraph_type_erased_device_array_view_tPK39cugraph_type_erased_device_array_view_tPK39cugraph_type_erased_device_array_view_tdd6size_t6bool_tPP27cugraph_centrality_result_tPP15cugraph_error_t>
23    PageRank,
24    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/centrality/#_CPPv429cugraph_personalized_pagerankPK25cugraph_resource_handle_tP15cugraph_graph_tPK39cugraph_type_erased_device_array_view_tPK39cugraph_type_erased_device_array_view_tPK39cugraph_type_erased_device_array_view_tPK39cugraph_type_erased_device_array_view_tPK39cugraph_type_erased_device_array_view_tPK39cugraph_type_erased_device_array_view_tdd6size_t6bool_tPP27cugraph_centrality_result_tPP15cugraph_error_t>
25    PersonalizedPageRank,
26    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/traversal/#_CPPv411cugraph_bfsPK25cugraph_resource_handle_tP15cugraph_graph_tP39cugraph_type_erased_device_array_view_t6bool_t6size_t6bool_t6bool_tPP22cugraph_paths_result_tPP15cugraph_error_t>
27    Bfs,
28    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/community/#_CPPv415cugraph_louvainPK25cugraph_resource_handle_tP15cugraph_graph_t6size_tdd6bool_tPP40cugraph_hierarchical_clustering_result_tPP15cugraph_error_t>
29    Louvain,
30    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/centrality/#_CPPv430cugraph_eigenvector_centralityPK25cugraph_resource_handle_tP15cugraph_graph_td6size_t6bool_tPP27cugraph_centrality_result_tPP15cugraph_error_t>
31    EigenvectorCentrality,
32    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/centrality/#_CPPv423cugraph_katz_centralityPK25cugraph_resource_handle_tP15cugraph_graph_tPK39cugraph_type_erased_device_array_view_tddd6size_t6bool_tPP27cugraph_centrality_result_tPP15cugraph_error_t>
33    KatzCentrality,
34    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/centrality/#_CPPv412cugraph_hitsPK25cugraph_resource_handle_tP15cugraph_graph_td6size_tPK39cugraph_type_erased_device_array_view_tPK39cugraph_type_erased_device_array_view_t6bool_t6bool_tPP21cugraph_hits_result_tPP15cugraph_error_t>
35    Hits,
36    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/centrality/#_CPPv430cugraph_betweenness_centralityPK25cugraph_resource_handle_tP15cugraph_graph_tPK39cugraph_type_erased_device_array_view_t6bool_t6bool_t6bool_tPP27cugraph_centrality_result_tPP15cugraph_error_t>
37    BetweennessCentrality,
38    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/centrality/#_CPPv435cugraph_edge_betweenness_centralityPK25cugraph_resource_handle_tP15cugraph_graph_tPK39cugraph_type_erased_device_array_view_t6bool_t6bool_tPP32cugraph_edge_centrality_result_tPP15cugraph_error_t>
39    EdgeBetweennessCentrality,
40    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/traversal/#_CPPv412cugraph_ssspPK25cugraph_resource_handle_tP15cugraph_graph_t6size_td6bool_t6bool_tPP22cugraph_paths_result_tPP15cugraph_error_t>
41    Sssp,
42    /// In-degree and out-degree for every vertex.
43    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/graph/#_CPPv415cugraph_degreesPK25cugraph_resource_handle_tP15cugraph_graph_tPK39cugraph_type_erased_device_array_view_t6bool_tPP24cugraph_degrees_result_tPP15cugraph_error_t>
44    DegreesAll,
45    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/graph/#_CPPv418cugraph_in_degreesPK25cugraph_resource_handle_tP15cugraph_graph_tPK39cugraph_type_erased_device_array_view_t6bool_tPP24cugraph_degrees_result_tPP15cugraph_error_t>
46    InDegreesAll,
47    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/graph/#_CPPv419cugraph_out_degreesPK25cugraph_resource_handle_tP15cugraph_graph_tPK39cugraph_type_erased_device_array_view_t6bool_tPP24cugraph_degrees_result_tPP15cugraph_error_t>
48    OutDegreesAll,
49    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/labeling/#_CPPv435cugraph_weakly_connected_componentsPK25cugraph_resource_handle_tP15cugraph_graph_t6bool_tPP25cugraph_labeling_result_tPP15cugraph_error_t>
50    WeaklyConnectedComponents,
51    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/labeling/#_CPPv437cugraph_strongly_connected_componentsPK25cugraph_resource_handle_tP15cugraph_graph_t6bool_tPP25cugraph_labeling_result_tPP15cugraph_error_t>
52    StronglyConnectedComponents,
53    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/community/#_CPPv422cugraph_triangle_countPK25cugraph_resource_handle_tP15cugraph_graph_tPK39cugraph_type_erased_device_array_view_t6bool_tPP31cugraph_triangle_count_result_tPP15cugraph_error_t>
54    TriangleCountAll,
55    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/core/#_CPPv419cugraph_core_numberPK25cugraph_resource_handle_tP15cugraph_graph_t28cugraph_k_core_degree_type_t6bool_tPP21cugraph_core_result_tPP15cugraph_error_t>
56    CoreNumber,
57    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/core/#_CPPv414cugraph_k_corePK25cugraph_resource_handle_tP15cugraph_graph_t6size_t28cugraph_k_core_degree_type_tPK21cugraph_core_result_t6bool_tPP23cugraph_k_core_result_tPP15cugraph_error_t>
58    KCore,
59    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/tree/#_CPPv429cugraph_minimum_spanning_treePK25cugraph_resource_handle_tP15cugraph_graph_t6bool_tPP33cugraph_induced_subgraph_result_tPP15cugraph_error_t>
60    MinimumSpanningTree,
61    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/community/#_CPPv414cugraph_leidenPK25cugraph_resource_handle_tP19cugraph_rng_state_tP15cugraph_graph_t6size_tdd6bool_tPP40cugraph_hierarchical_clustering_result_tPP15cugraph_error_t>
62    Leiden,
63    /// Ensemble clustering for graphs.
64    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/community/#_CPPv411cugraph_ecgPK25cugraph_resource_handle_tP19cugraph_rng_state_tP15cugraph_graph_td6size_t6size_tdd6bool_tPP40cugraph_hierarchical_clustering_result_tPP15cugraph_error_t>
65    Ecg,
66    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/community/#_CPPv440cugraph_spectral_modularity_maximizationPK25cugraph_resource_handle_tP19cugraph_rng_state_tP15cugraph_graph_t6size_t6size_tdidi6bool_tPP27cugraph_clustering_result_tPP15cugraph_error_t>
67    SpectralModularityMaximization,
68    /// Force-directed graph layout.
69    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/layout/#_CPPv420cugraph_force_atlas2PK25cugraph_resource_handle_tP19cugraph_rng_state_tP15cugraph_graph_tiP39cugraph_type_erased_device_array_view_tP39cugraph_type_erased_device_array_view_tP39cugraph_type_erased_device_array_view_t6bool_t6bool_t6bool_tP39cugraph_type_erased_device_array_view_tP39cugraph_type_erased_device_array_view_tddd6bool_tdd6bool_tdP39cugraph_type_erased_device_array_view_tP39cugraph_type_erased_device_array_view_tP39cugraph_type_erased_device_array_view_tP39cugraph_type_erased_device_array_view_t6bool_t6bool_tPP23cugraph_layout_result_tPP15cugraph_error_t>
70    ForceAtlas2,
71    /// Explicit-pair Jaccard similarity coefficient.
72    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/similarity/#_CPPv428cugraph_jaccard_coefficientsPK25cugraph_resource_handle_tP15cugraph_graph_tPK22cugraph_vertex_pairs_t6bool_t6bool_tPP27cugraph_similarity_result_tPP15cugraph_error_t>
73    Jaccard,
74    /// Explicit-pair Sorensen similarity coefficient.
75    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/similarity/#_CPPv429cugraph_sorensen_coefficientsPK25cugraph_resource_handle_tP15cugraph_graph_tPK22cugraph_vertex_pairs_t6bool_t6bool_tPP27cugraph_similarity_result_tPP15cugraph_error_t>
76    Sorensen,
77    /// Explicit-pair overlap similarity coefficient.
78    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/similarity/#_CPPv428cugraph_overlap_coefficientsPK25cugraph_resource_handle_tP15cugraph_graph_tPK22cugraph_vertex_pairs_t6bool_t6bool_tPP27cugraph_similarity_result_tPP15cugraph_error_t>
79    Overlap,
80    /// Explicit-pair cosine similarity coefficient.
81    /// <https://docs.nvidia.com/cugraph/latest/api_docs/cugraph_c/similarity/#_CPPv438cugraph_cosine_similarity_coefficientsPK25cugraph_resource_handle_tP15cugraph_graph_tPK22cugraph_vertex_pairs_t6bool_t6bool_tPP27cugraph_similarity_result_tPP15cugraph_error_t>
82    Cosine,
83}
84
85impl GraphAlgorithm {
86    /// Stable lowercase algorithm code.
87    pub const fn as_str(self) -> &'static str {
88        match self {
89            Self::PageRank => "pagerank",
90            Self::PersonalizedPageRank => "personalized_pagerank",
91            Self::Bfs => "bfs",
92            Self::Louvain => "louvain",
93            Self::EigenvectorCentrality => "eigenvector_centrality",
94            Self::KatzCentrality => "katz_centrality",
95            Self::Hits => "hits",
96            Self::BetweennessCentrality => "betweenness_centrality",
97            Self::EdgeBetweennessCentrality => "edge_betweenness_centrality",
98            Self::Sssp => "sssp",
99            Self::DegreesAll => "degrees_all",
100            Self::InDegreesAll => "in_degrees_all",
101            Self::OutDegreesAll => "out_degrees_all",
102            Self::WeaklyConnectedComponents => "weakly_connected_components",
103            Self::StronglyConnectedComponents => "strongly_connected_components",
104            Self::TriangleCountAll => "triangle_count_all",
105            Self::CoreNumber => "core_number",
106            Self::KCore => "k_core",
107            Self::MinimumSpanningTree => "minimum_spanning_tree",
108            Self::Leiden => "leiden",
109            Self::Ecg => "ecg",
110            Self::SpectralModularityMaximization => "spectral_modularity_maximization",
111            Self::ForceAtlas2 => "force_atlas2",
112            Self::Jaccard => "jaccard",
113            Self::Sorensen => "sorensen",
114            Self::Overlap => "overlap",
115            Self::Cosine => "cosine",
116        }
117    }
118
119    /// Whether this algorithm is one of the explicit-pair similarity metrics.
120    pub const fn is_similarity(self) -> bool {
121        matches!(self, Self::Jaccard | Self::Sorensen | Self::Overlap | Self::Cosine)
122    }
123
124    /// Look up the registry definition for this algorithm.
125    ///
126    /// Panics if the algorithm variant lacks a registry entry. The registry is
127    /// the single source of truth for algorithm metadata; new
128    /// [`GraphAlgorithm`] variants must add an entry to
129    /// [`GRAPH_OPERATION_REGISTRY`].
130    pub fn definition(self) -> &'static GraphOperationDefinition {
131        GRAPH_OPERATION_REGISTRY
132            .iter()
133            .find(|def| def.algorithm == self)
134            .expect("graph operation registry is missing an algorithm variant")
135    }
136
137    /// All algorithms exposed by the registry, in registry order.
138    pub fn all() -> impl ExactSizeIterator<Item = Self> + Clone {
139        GRAPH_OPERATION_REGISTRY.iter().map(|def| def.algorithm)
140    }
141
142    /// Whether this algorithm reads edge weights as a semantic input.
143    ///
144    /// When `false`, a bound `weight` column is irrelevant to the result and a
145    /// null weight must not cause its edge to be dropped from the graph.
146    pub fn consumes_weight(self) -> bool {
147        self.definition().weight_policy().consumes_weight()
148    }
149
150    /// Whether this algorithm requires a source vertex argument.
151    pub fn requires_source_vertex(self) -> bool {
152        self.definition().source_vertex_requirement().requires_source_vertex()
153    }
154
155    /// Weight-column policy declared by the native graph descriptor.
156    pub fn weight_policy(self) -> GraphWeightPolicy {
157        self.definition().weight_policy()
158    }
159
160    /// Output-schema shape declared by the native graph descriptor.
161    pub fn output_schema_kind(self) -> GraphOutputSchemaKind {
162        self.definition().output_schema_kind()
163    }
164
165    /// Vertex-id dtype support declared by the native graph descriptor.
166    pub fn vertex_id_type_support(self) -> GraphVertexIdTypeSupport {
167        self.definition().vertex_id_type_support()
168    }
169}
170
171impl fmt::Display for GraphAlgorithm {
172    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
173        f.write_str(self.as_str())
174    }
175}
176
177/// Vertex-id dtype support for a native graph algorithm.
178#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
179pub enum GraphVertexIdTypeSupport {
180    /// The operation accepts Int32 and Int64 vertex id columns.
181    Int32OrInt64,
182    /// cuGraph C API operation whose edge type dispatch only supports
183    /// Int32 vertex id columns. The graph node validates Int32 columns; the
184    /// SQL adapter maps other vertex domains to Int32 ids before the node.
185    Int32OnlyLegacyEdgeType,
186}
187
188impl GraphVertexIdTypeSupport {
189    /// Stable lowercase capability code.
190    pub(crate) const fn as_str(self) -> &'static str {
191        match self {
192            Self::Int32OrInt64 => "int32_or_int64",
193            Self::Int32OnlyLegacyEdgeType => "int32_only_legacy_edge_type",
194        }
195    }
196
197    /// SQL/diagnostic label for supported dtypes.
198    pub const fn supported_dtypes_label(self) -> &'static str {
199        match self {
200            Self::Int32OrInt64 => "Int32|Int64",
201            Self::Int32OnlyLegacyEdgeType => "Int32",
202        }
203    }
204
205    /// Whether the Arrow dtype is supported for vertex id columns.
206    pub fn accepts_arrow_data_type(self, data_type: &DataType) -> bool {
207        match self {
208            Self::Int32OrInt64 => matches!(data_type, DataType::Int32 | DataType::Int64),
209            Self::Int32OnlyLegacyEdgeType => matches!(data_type, DataType::Int32),
210        }
211    }
212}
213
214impl fmt::Display for GraphVertexIdTypeSupport {
215    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
216        f.write_str(self.as_str())
217    }
218}
219
220/// Source-vertex contract for a graph algorithm.
221#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
222pub enum GraphSourceVertexRequirement {
223    /// The algorithm does not accept a source vertex.
224    None,
225    /// The algorithm requires exactly one source vertex.
226    Required,
227}
228
229impl GraphSourceVertexRequirement {
230    /// Whether the algorithm requires a source vertex.
231    pub const fn requires_source_vertex(self) -> bool {
232        matches!(self, Self::Required)
233    }
234}
235
236/// Weight-column policy for a graph algorithm.
237#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
238pub enum GraphWeightPolicy {
239    /// A bound weight column is accepted as graph-construction metadata but is
240    /// ignored by the algorithm's current semantic result.
241    Ignored,
242    /// A bound weight column is optional and changes algorithm results when
243    /// present.
244    Optional,
245    /// A bound weight column is required for semantically valid execution.
246    Required,
247}
248
249impl GraphWeightPolicy {
250    /// Whether this policy means the native executor consumes weights as an
251    /// algorithm input when a weight column is bound.
252    pub const fn consumes_weight(self) -> bool {
253        matches!(self, Self::Optional | Self::Required)
254    }
255
256    /// Whether a weight column is mandatory for this algorithm.
257    pub const fn requires_weight(self) -> bool {
258        matches!(self, Self::Required)
259    }
260}
261
262/// Native output-schema descriptor for a graph algorithm.
263#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
264pub enum GraphOutputSchemaKind {
265    /// The SQL-visible schema is the native stable base schema.
266    Fixed,
267    /// The native descriptor owns the base schema, while an adapter layer may
268    /// expose call-specific modes derived from it.
269    DefaultMode,
270}
271
272/// Engine-owned behavior when a graph operation receives no usable edges.
273///
274/// The executor applies this after null edge rows have been removed and before
275/// graph admission or cuGraph construction. This keeps empty-input semantics
276/// independent of libcugraph's incidental behavior and distinguishes a valid
277/// empty result from an operation that requires an actual graph or side input.
278#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
279pub struct EmptyGraphInputPolicy {
280    /// Action for an empty edge list after input sanitization.
281    pub edge_input: EmptyGraphEdgeInputAction,
282    /// Contract for any relation-backed algorithm inputs.
283    pub side_inputs: EmptyGraphSideInputPolicy,
284}
285
286impl EmptyGraphInputPolicy {
287    const RETURN_EMPTY: Self =
288        Self { edge_input: EmptyGraphEdgeInputAction::ReturnEmpty, side_inputs: EmptyGraphSideInputPolicy::None };
289    const VALIDATE_SELECTORS_THEN_RETURN_EMPTY: Self = Self {
290        edge_input: EmptyGraphEdgeInputAction::ValidateSelectorsThenReturnEmpty,
291        side_inputs: EmptyGraphSideInputPolicy::None,
292    };
293    const REQUIRE_GRAPH: Self =
294        Self { edge_input: EmptyGraphEdgeInputAction::Reject, side_inputs: EmptyGraphSideInputPolicy::None };
295    const REQUIRE_GRAPH_AND_PERSONALIZATION: Self = Self {
296        edge_input: EmptyGraphEdgeInputAction::Reject,
297        side_inputs: EmptyGraphSideInputPolicy::RequirePersonalization,
298    };
299    const SIMILARITY: Self = Self {
300        edge_input: EmptyGraphEdgeInputAction::SimilarityVertexPairs,
301        side_inputs: EmptyGraphSideInputPolicy::RequireVertexPairs,
302    };
303    const BFS: Self = Self {
304        edge_input: EmptyGraphEdgeInputAction::BfsEndpointPolicy,
305        side_inputs: EmptyGraphSideInputPolicy::BfsPredicates,
306    };
307}
308
309/// Action for a sanitized empty graph edge list.
310#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
311pub enum EmptyGraphEdgeInputAction {
312    /// The operation has a schema-correct zero-row result.
313    ReturnEmpty,
314    /// Validate explicit vertex selectors first, then return the zero-row
315    /// result only when no selector requires a vertex.
316    ValidateSelectorsThenReturnEmpty,
317    /// The operation cannot run without at least one graph edge/vertex.
318    Reject,
319    /// BFS delegates empty-edge behavior to its explicit endpoint policy.
320    BfsEndpointPolicy,
321    /// Explicit-pair similarity returns a stable empty result for an empty
322    /// pair relation and rejects non-empty pairs against an empty graph.
323    SimilarityVertexPairs,
324}
325
326impl EmptyGraphEdgeInputAction {
327    /// Stable policy label for diagnostics and contract tests.
328    pub const fn as_str(self) -> &'static str {
329        match self {
330            Self::ReturnEmpty => "return_empty",
331            Self::ValidateSelectorsThenReturnEmpty => "validate_selectors_then_return_empty",
332            Self::Reject => "reject",
333            Self::BfsEndpointPolicy => "bfs_endpoint_policy",
334            Self::SimilarityVertexPairs => "similarity_vertex_pairs",
335        }
336    }
337}
338
339/// Relation-backed input contract for an empty graph operation.
340#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
341pub enum EmptyGraphSideInputPolicy {
342    /// The operation accepts no relation-backed side input.
343    None,
344    /// Personalized PageRank requires a non-empty personalization relation.
345    RequirePersonalization,
346    /// BFS has role-specific source and predicate semantics owned by its
347    /// traversal executor.
348    BfsPredicates,
349    /// Explicit-pair similarity owns pair-cardinality and endpoint behavior.
350    RequireVertexPairs,
351}
352
353impl EmptyGraphSideInputPolicy {
354    /// Stable policy label for diagnostics and contract tests.
355    pub const fn as_str(self) -> &'static str {
356        match self {
357            Self::None => "none",
358            Self::RequirePersonalization => "require_personalization",
359            Self::BfsPredicates => "bfs_predicates",
360            Self::RequireVertexPairs => "require_vertex_pairs",
361        }
362    }
363}
364
365/// Registry-level metadata for a graph operation.
366///
367/// One entry per [`GraphAlgorithm`] variant. The registry is the place new
368/// algorithms must declare their layout requirement, stable SQL name, and any
369/// future metadata fields (parameter schema, weighted-edge support, etc.) so
370/// the planner, executor, and SQL surface stay in sync.
371#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
372pub struct GraphOperationDefinition {
373    /// Algorithm variant described by this registry row.
374    pub algorithm: GraphAlgorithm,
375    /// Stable identifier used in plan display, runtime metrics, and SQL
376    /// function naming (`cugraph_<name>`).
377    pub name: &'static str,
378    /// cuGraph layout requirement for this operation.
379    pub layout_requirement: GraphLayoutRequirement,
380    /// Engine-owned empty-edge and side-input behavior.
381    pub empty_input_policy: EmptyGraphInputPolicy,
382}
383
384impl GraphOperationDefinition {
385    /// Result columns whose dtype is the graph's vertex-id domain.
386    pub(crate) const fn vertex_output_columns(&self) -> &'static [&'static str] {
387        match self.algorithm {
388            GraphAlgorithm::Bfs => &["vertex", "predecessor", "source", "target"],
389            GraphAlgorithm::Sssp => &["vertex", "predecessor"],
390            GraphAlgorithm::EdgeBetweennessCentrality => &["src", "dst"],
391            GraphAlgorithm::KCore | GraphAlgorithm::MinimumSpanningTree => &["src", "dst"],
392            GraphAlgorithm::Jaccard | GraphAlgorithm::Sorensen | GraphAlgorithm::Overlap | GraphAlgorithm::Cosine => {
393                &["first", "second"]
394            },
395            GraphAlgorithm::PageRank
396            | GraphAlgorithm::PersonalizedPageRank
397            | GraphAlgorithm::Louvain
398            | GraphAlgorithm::EigenvectorCentrality
399            | GraphAlgorithm::KatzCentrality
400            | GraphAlgorithm::Hits
401            | GraphAlgorithm::BetweennessCentrality
402            | GraphAlgorithm::DegreesAll
403            | GraphAlgorithm::InDegreesAll
404            | GraphAlgorithm::OutDegreesAll
405            | GraphAlgorithm::WeaklyConnectedComponents
406            | GraphAlgorithm::StronglyConnectedComponents
407            | GraphAlgorithm::TriangleCountAll
408            | GraphAlgorithm::CoreNumber
409            | GraphAlgorithm::Leiden
410            | GraphAlgorithm::Ecg
411            | GraphAlgorithm::SpectralModularityMaximization
412            | GraphAlgorithm::ForceAtlas2 => &["vertex"],
413        }
414    }
415
416    /// Source-vertex requirement for this algorithm.
417    pub const fn source_vertex_requirement(&self) -> GraphSourceVertexRequirement {
418        match self.algorithm {
419            GraphAlgorithm::Bfs | GraphAlgorithm::Sssp => GraphSourceVertexRequirement::Required,
420            _ => GraphSourceVertexRequirement::None,
421        }
422    }
423
424    /// Weight-column policy for this algorithm.
425    pub const fn weight_policy(&self) -> GraphWeightPolicy {
426        match self.algorithm {
427            GraphAlgorithm::MinimumSpanningTree => GraphWeightPolicy::Required,
428            GraphAlgorithm::PageRank
429            | GraphAlgorithm::PersonalizedPageRank
430            | GraphAlgorithm::Sssp
431            | GraphAlgorithm::ForceAtlas2
432            | GraphAlgorithm::Jaccard
433            | GraphAlgorithm::Sorensen
434            | GraphAlgorithm::Overlap
435            | GraphAlgorithm::Cosine => GraphWeightPolicy::Optional,
436            _ => GraphWeightPolicy::Ignored,
437        }
438    }
439
440    /// Base output-schema descriptor for this algorithm.
441    pub const fn output_schema_kind(&self) -> GraphOutputSchemaKind {
442        match self.algorithm {
443            GraphAlgorithm::Bfs => GraphOutputSchemaKind::DefaultMode,
444            _ => GraphOutputSchemaKind::Fixed,
445        }
446    }
447
448    /// Whether the stable result contains at most one row for each `vertex`.
449    pub(crate) const fn output_vertex_is_unique(&self) -> bool {
450        matches!(
451            self.algorithm,
452            GraphAlgorithm::PageRank
453                | GraphAlgorithm::PersonalizedPageRank
454                | GraphAlgorithm::Bfs
455                | GraphAlgorithm::Louvain
456                | GraphAlgorithm::EigenvectorCentrality
457                | GraphAlgorithm::KatzCentrality
458                | GraphAlgorithm::Hits
459                | GraphAlgorithm::BetweennessCentrality
460                | GraphAlgorithm::Sssp
461                | GraphAlgorithm::DegreesAll
462                | GraphAlgorithm::InDegreesAll
463                | GraphAlgorithm::OutDegreesAll
464                | GraphAlgorithm::WeaklyConnectedComponents
465                | GraphAlgorithm::StronglyConnectedComponents
466                | GraphAlgorithm::TriangleCountAll
467                | GraphAlgorithm::CoreNumber
468                | GraphAlgorithm::Leiden
469                | GraphAlgorithm::Ecg
470                | GraphAlgorithm::SpectralModularityMaximization
471                | GraphAlgorithm::ForceAtlas2
472        )
473    }
474
475    /// Required graph directedness, when the cuGraph operation only accepts
476    /// one graph property.
477    pub const fn required_graph_directedness(&self) -> Option<bool> {
478        match self.algorithm {
479            GraphAlgorithm::WeaklyConnectedComponents
480            | GraphAlgorithm::MinimumSpanningTree
481            | GraphAlgorithm::SpectralModularityMaximization
482            | GraphAlgorithm::Jaccard
483            | GraphAlgorithm::Sorensen
484            | GraphAlgorithm::Overlap
485            | GraphAlgorithm::Cosine => Some(false),
486            GraphAlgorithm::StronglyConnectedComponents => Some(true),
487            _ => None,
488        }
489    }
490
491    pub(crate) const fn vertex_id_type_support(&self) -> GraphVertexIdTypeSupport {
492        match self.algorithm {
493            GraphAlgorithm::MinimumSpanningTree | GraphAlgorithm::SpectralModularityMaximization => {
494                GraphVertexIdTypeSupport::Int32OnlyLegacyEdgeType
495            },
496            _ => GraphVertexIdTypeSupport::Int32OrInt64,
497        }
498    }
499
500    /// Engine-owned contract for empty graph inputs.
501    pub const fn empty_input_policy(&self) -> EmptyGraphInputPolicy {
502        self.empty_input_policy
503    }
504
505    /// Native base result schema for this algorithm.
506    ///
507    /// See [`stable_graph_result_schema`] for BFS's raw result contract and the
508    /// SQL adapter's separate vertex-result schema.
509    pub fn output_schema(&self) -> SchemaRef {
510        stable_graph_result_schema(self.algorithm)
511    }
512
513    /// Native base result schema for this algorithm.
514    pub fn base_result_schema(&self) -> SchemaRef {
515        stable_graph_result_schema(self.algorithm)
516    }
517
518    /// Shared graph-construction defaults after algorithm-level overrides.
519    pub fn default_graph_options(&self, defaults: &GraphConstructionOptions) -> GraphConstructionOptions {
520        let mut options = defaults.clone();
521        if matches!(
522            self.algorithm,
523            GraphAlgorithm::Louvain
524                | GraphAlgorithm::WeaklyConnectedComponents
525                | GraphAlgorithm::TriangleCountAll
526                | GraphAlgorithm::CoreNumber
527                | GraphAlgorithm::KCore
528                | GraphAlgorithm::MinimumSpanningTree
529                | GraphAlgorithm::Leiden
530                | GraphAlgorithm::Ecg
531                | GraphAlgorithm::SpectralModularityMaximization
532                | GraphAlgorithm::ForceAtlas2
533                | GraphAlgorithm::Jaccard
534                | GraphAlgorithm::Sorensen
535                | GraphAlgorithm::Overlap
536                | GraphAlgorithm::Cosine
537        ) {
538            options.directed = false;
539        }
540        options
541    }
542
543    /// Default native parameter payload for metadata and planning projections.
544    ///
545    /// Source-vertex algorithms use `0` as a placeholder because the real
546    /// source vertex remains a required SQL/parser input with no default value.
547    pub fn default_params(&self) -> GraphAlgorithmParams {
548        match self.algorithm {
549            GraphAlgorithm::PageRank => GraphAlgorithmParams::PageRank(GraphPageRankParams::default()),
550            GraphAlgorithm::PersonalizedPageRank => {
551                GraphAlgorithmParams::PersonalizedPageRank(GraphPersonalizedPageRankParams::default())
552            },
553            GraphAlgorithm::Bfs => GraphAlgorithmParams::Bfs(Box::new(GraphBfsParams::new(0, None))),
554            GraphAlgorithm::Louvain => GraphAlgorithmParams::Louvain(GraphLouvainParams::default()),
555            GraphAlgorithm::EigenvectorCentrality => {
556                GraphAlgorithmParams::EigenvectorCentrality(GraphEigenvectorCentralityParams::default())
557            },
558            GraphAlgorithm::KatzCentrality => {
559                GraphAlgorithmParams::KatzCentrality(GraphKatzCentralityParams::default())
560            },
561            GraphAlgorithm::Hits => GraphAlgorithmParams::Hits(GraphHitsParams::default()),
562            GraphAlgorithm::BetweennessCentrality => {
563                GraphAlgorithmParams::BetweennessCentrality(GraphBetweennessCentralityParams::default())
564            },
565            GraphAlgorithm::EdgeBetweennessCentrality => {
566                GraphAlgorithmParams::EdgeBetweennessCentrality(GraphEdgeBetweennessCentralityParams::default())
567            },
568            GraphAlgorithm::Sssp => {
569                GraphAlgorithmParams::Sssp(GraphSsspParams { source_vertex: GraphSsspSource::I64(0), cutoff: None })
570            },
571            GraphAlgorithm::DegreesAll => GraphAlgorithmParams::DegreesAll(GraphDegreesAllParams),
572            GraphAlgorithm::InDegreesAll => GraphAlgorithmParams::InDegreesAll(GraphInDegreesAllParams),
573            GraphAlgorithm::OutDegreesAll => GraphAlgorithmParams::OutDegreesAll(GraphOutDegreesAllParams),
574            GraphAlgorithm::WeaklyConnectedComponents => {
575                GraphAlgorithmParams::WeaklyConnectedComponents(GraphWccParams)
576            },
577            GraphAlgorithm::StronglyConnectedComponents => {
578                GraphAlgorithmParams::StronglyConnectedComponents(GraphSccParams)
579            },
580            GraphAlgorithm::TriangleCountAll => GraphAlgorithmParams::TriangleCountAll(GraphTriangleCountAllParams),
581            GraphAlgorithm::CoreNumber => GraphAlgorithmParams::CoreNumber(GraphCoreNumberParams::default()),
582            GraphAlgorithm::KCore => GraphAlgorithmParams::KCore(GraphKCoreParams::default()),
583            GraphAlgorithm::MinimumSpanningTree => GraphAlgorithmParams::MinimumSpanningTree(GraphMstParams),
584            GraphAlgorithm::Leiden => GraphAlgorithmParams::Leiden(GraphLeidenParams::default()),
585            GraphAlgorithm::Ecg => GraphAlgorithmParams::Ecg(GraphEcgParams::default()),
586            GraphAlgorithm::SpectralModularityMaximization => {
587                GraphAlgorithmParams::SpectralModularityMaximization(GraphSpectralClusteringParams::default())
588            },
589            GraphAlgorithm::ForceAtlas2 => GraphAlgorithmParams::ForceAtlas2(GraphForceAtlas2Params::default()),
590            GraphAlgorithm::Jaccard | GraphAlgorithm::Sorensen | GraphAlgorithm::Overlap | GraphAlgorithm::Cosine => {
591                GraphAlgorithmParams::Similarity(GraphSimilarityParams::default())
592            },
593        }
594    }
595
596    /// Result schema for an algorithm parameter payload.
597    ///
598    /// This preserves native-owned parameter-sensitive schema semantics. SQL
599    /// adapters may still apply a final user-facing overlay for modes that are
600    /// not part of the native IR.
601    pub fn result_schema_for_params(&self, params: &GraphAlgorithmParams) -> SchemaRef {
602        assert!(params.supports_algorithm(self.algorithm), "graph algorithm and parameter variant must match");
603        if let GraphAlgorithmParams::Bfs(params) = params
604            && params.path_output.is_some()
605        {
606            return Arc::new(Schema::new(vec![
607                Field::new("path_index", DataType::Int64, false),
608                Field::new("source", DataType::Int64, false),
609                Field::new("target", DataType::Int64, false),
610                Field::new("vertex", DataType::Int64, false),
611                Field::new("distance", DataType::Int64, false),
612            ]));
613        }
614        self.base_result_schema()
615    }
616}
617
618/// Source-of-truth list of supported cuGraph operations.
619///
620/// Order is preserved by [`GraphAlgorithm::all`] and is the order in which
621/// the SQL surface iterates algorithms when registering UDTFs.
622pub const GRAPH_OPERATION_REGISTRY: &[GraphOperationDefinition] = &[
623    GraphOperationDefinition {
624        algorithm: GraphAlgorithm::PageRank,
625        name: "pagerank",
626        layout_requirement: GraphLayoutRequirement::Transposed,
627        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
628    },
629    GraphOperationDefinition {
630        algorithm: GraphAlgorithm::Bfs,
631        name: "bfs",
632        layout_requirement: GraphLayoutRequirement::Forward,
633        empty_input_policy: EmptyGraphInputPolicy::BFS,
634    },
635    GraphOperationDefinition {
636        algorithm: GraphAlgorithm::Louvain,
637        name: "louvain",
638        layout_requirement: GraphLayoutRequirement::Forward,
639        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
640    },
641    GraphOperationDefinition {
642        algorithm: GraphAlgorithm::EigenvectorCentrality,
643        name: "eigenvector_centrality",
644        layout_requirement: GraphLayoutRequirement::Transposed,
645        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
646    },
647    GraphOperationDefinition {
648        algorithm: GraphAlgorithm::KatzCentrality,
649        name: "katz_centrality",
650        layout_requirement: GraphLayoutRequirement::Transposed,
651        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
652    },
653    GraphOperationDefinition {
654        algorithm: GraphAlgorithm::Hits,
655        name: "hits",
656        layout_requirement: GraphLayoutRequirement::Transposed,
657        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
658    },
659    GraphOperationDefinition {
660        algorithm: GraphAlgorithm::BetweennessCentrality,
661        name: "betweenness_centrality",
662        layout_requirement: GraphLayoutRequirement::Any,
663        empty_input_policy: EmptyGraphInputPolicy::VALIDATE_SELECTORS_THEN_RETURN_EMPTY,
664    },
665    GraphOperationDefinition {
666        algorithm: GraphAlgorithm::EdgeBetweennessCentrality,
667        name: "edge_betweenness_centrality",
668        layout_requirement: GraphLayoutRequirement::Any,
669        empty_input_policy: EmptyGraphInputPolicy::VALIDATE_SELECTORS_THEN_RETURN_EMPTY,
670    },
671    GraphOperationDefinition {
672        algorithm: GraphAlgorithm::Sssp,
673        name: "sssp",
674        layout_requirement: GraphLayoutRequirement::Forward,
675        empty_input_policy: EmptyGraphInputPolicy::REQUIRE_GRAPH,
676    },
677    GraphOperationDefinition {
678        algorithm: GraphAlgorithm::DegreesAll,
679        name: "degrees_all",
680        layout_requirement: GraphLayoutRequirement::Transposed,
681        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
682    },
683    GraphOperationDefinition {
684        algorithm: GraphAlgorithm::InDegreesAll,
685        name: "in_degrees_all",
686        layout_requirement: GraphLayoutRequirement::Transposed,
687        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
688    },
689    GraphOperationDefinition {
690        algorithm: GraphAlgorithm::OutDegreesAll,
691        name: "out_degrees_all",
692        layout_requirement: GraphLayoutRequirement::Any,
693        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
694    },
695    GraphOperationDefinition {
696        algorithm: GraphAlgorithm::WeaklyConnectedComponents,
697        name: "weakly_connected_components",
698        layout_requirement: GraphLayoutRequirement::Any,
699        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
700    },
701    GraphOperationDefinition {
702        algorithm: GraphAlgorithm::StronglyConnectedComponents,
703        name: "strongly_connected_components",
704        layout_requirement: GraphLayoutRequirement::Any,
705        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
706    },
707    GraphOperationDefinition {
708        algorithm: GraphAlgorithm::TriangleCountAll,
709        name: "triangle_count_all",
710        layout_requirement: GraphLayoutRequirement::Any,
711        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
712    },
713    GraphOperationDefinition {
714        algorithm: GraphAlgorithm::CoreNumber,
715        name: "core_number",
716        layout_requirement: GraphLayoutRequirement::Any,
717        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
718    },
719    GraphOperationDefinition {
720        algorithm: GraphAlgorithm::KCore,
721        name: "k_core",
722        layout_requirement: GraphLayoutRequirement::Any,
723        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
724    },
725    GraphOperationDefinition {
726        algorithm: GraphAlgorithm::MinimumSpanningTree,
727        name: "minimum_spanning_tree",
728        layout_requirement: GraphLayoutRequirement::Any,
729        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
730    },
731    GraphOperationDefinition {
732        algorithm: GraphAlgorithm::PersonalizedPageRank,
733        name: "personalized_pagerank",
734        layout_requirement: GraphLayoutRequirement::Transposed,
735        empty_input_policy: EmptyGraphInputPolicy::REQUIRE_GRAPH_AND_PERSONALIZATION,
736    },
737    GraphOperationDefinition {
738        algorithm: GraphAlgorithm::Leiden,
739        name: "leiden",
740        layout_requirement: GraphLayoutRequirement::Forward,
741        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
742    },
743    GraphOperationDefinition {
744        algorithm: GraphAlgorithm::Ecg,
745        name: "ecg",
746        layout_requirement: GraphLayoutRequirement::Forward,
747        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
748    },
749    GraphOperationDefinition {
750        algorithm: GraphAlgorithm::SpectralModularityMaximization,
751        name: "spectral_modularity_maximization",
752        layout_requirement: GraphLayoutRequirement::Forward,
753        empty_input_policy: EmptyGraphInputPolicy::REQUIRE_GRAPH,
754    },
755    GraphOperationDefinition {
756        algorithm: GraphAlgorithm::ForceAtlas2,
757        name: "force_atlas2",
758        layout_requirement: GraphLayoutRequirement::Any,
759        empty_input_policy: EmptyGraphInputPolicy::RETURN_EMPTY,
760    },
761    GraphOperationDefinition {
762        algorithm: GraphAlgorithm::Jaccard,
763        name: "jaccard",
764        layout_requirement: GraphLayoutRequirement::Any,
765        empty_input_policy: EmptyGraphInputPolicy::SIMILARITY,
766    },
767    GraphOperationDefinition {
768        algorithm: GraphAlgorithm::Sorensen,
769        name: "sorensen",
770        layout_requirement: GraphLayoutRequirement::Any,
771        empty_input_policy: EmptyGraphInputPolicy::SIMILARITY,
772    },
773    GraphOperationDefinition {
774        algorithm: GraphAlgorithm::Overlap,
775        name: "overlap",
776        layout_requirement: GraphLayoutRequirement::Any,
777        empty_input_policy: EmptyGraphInputPolicy::SIMILARITY,
778    },
779    GraphOperationDefinition {
780        algorithm: GraphAlgorithm::Cosine,
781        name: "cosine",
782        layout_requirement: GraphLayoutRequirement::Any,
783        empty_input_policy: EmptyGraphInputPolicy::SIMILARITY,
784    },
785];
786
787/// Edge-list column bindings consumed by a graph algorithm.
788///
789/// `weight` and `edge_id` are optional. When `weight` is present,
790/// duplicate-edge normalization follows the selected
791/// [`GraphConstructionPolicy`] and [`crate::plan::EdgeWeightCombiner`] so conflicting
792/// weights are deterministic. When `edge_id` is present, the column is carried
793/// through graph construction as the stable user-visible edge id used by
794/// edge-id predicates.
795#[derive(Debug, Clone, PartialEq, Eq)]
796pub struct GraphEdgeColumnBindings {
797    /// Source-vertex column name in the edge-list input.
798    pub source: String,
799    /// Destination-vertex column name in the edge-list input.
800    pub destination: String,
801    /// Optional edge-weight column name.
802    pub weight: Option<String>,
803    /// Optional stable edge-id column name.
804    pub edge_id: Option<String>,
805}
806
807impl GraphEdgeColumnBindings {
808    /// Create edge-list column bindings.
809    pub fn new(source: impl Into<String>, destination: impl Into<String>, weight: Option<impl Into<String>>) -> Self {
810        Self { source: source.into(), destination: destination.into(), weight: weight.map(Into::into), edge_id: None }
811    }
812
813    /// Attach a stable edge-id column binding.
814    pub fn with_edge_id(mut self, edge_id: impl Into<String>) -> Self {
815        self.edge_id = Some(edge_id.into());
816        self
817    }
818}
819
820/// Graph construction options shared by cuGraph algorithms.
821///
822/// Defaults match Python cuGraph: directed graph construction, vertex
823/// renumbering enabled, and Python-compatible edge-list normalization. Changing
824/// `directed` affects whether reverse edges are inserted by the
825/// Python-compatible policy.
826#[derive(Debug, Clone, PartialEq, Eq)]
827pub struct GraphConstructionOptions {
828    /// Whether graph construction treats edges as directed.
829    pub directed: bool,
830    /// Whether cuGraph may renumber vertices internally.
831    pub renumber: bool,
832    /// Edge-list normalization policy used before graph construction.
833    pub policy: GraphConstructionPolicy,
834}
835
836impl Default for GraphConstructionOptions {
837    fn default() -> Self {
838        Self { directed: true, renumber: true, policy: GraphConstructionPolicy::PythonCugraph }
839    }
840}
841
842/// Graph construction policy understood by the native IR.
843///
844/// Mirrors `cugraph::cudf_interop::GraphConstructionPolicy`. See
845/// `algeon_datafusion::CugraphGraphConstructionPolicy` for the SQL-level
846/// semantics and trade-offs between the two variants.
847#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
848pub enum GraphConstructionPolicy {
849    /// Normalize edge lists to match Python cuGraph semantics.
850    PythonCugraph,
851    /// Pass edge lists directly to libcugraph-compatible construction.
852    RawLibcugraph,
853}
854
855impl GraphConstructionPolicy {
856    /// Stable lowercase construction-policy code.
857    pub const fn as_str(self) -> &'static str {
858        match self {
859            Self::PythonCugraph => "python_cugraph",
860            Self::RawLibcugraph => "raw_libcugraph",
861        }
862    }
863}
864
865impl fmt::Display for GraphConstructionPolicy {
866    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
867        f.write_str(self.as_str())
868    }
869}
query_planning/plan/graph_algorithm/definition.rs

query_planning/plan/graph_algorithm/
definition.rs
