graphforge_core/
algorithms.rs

1//! Typed registry and stable logical result schemas for analyst algorithms.
2//!
3//! Algorithm execution belongs to `graphforge-exec`; this module is intentionally
4//! dependency-light so the Rust API and every binding share one vocabulary.
5
6use std::{fmt, str::FromStr};
7
8use crate::GfError;
9
10/// Analyst-intent API surface that owns an algorithm.
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
12pub enum AlgorithmVerb {
13    /// Node scoring.
14    Rank,
15    /// Community assignment and decomposition.
16    Cluster,
17    /// Pairwise similarity.
18    Similar,
19    /// Paths, traversal, reachability, and flow.
20    Paths,
21    /// Graph-level and structural analysis.
22    Analyze,
23}
24
25impl AlgorithmVerb {
26    /// Public method name.
27    #[must_use]
28    pub const fn as_str(self) -> &'static str {
29        match self {
30            Self::Rank => "rank",
31            Self::Cluster => "cluster",
32            Self::Similar => "similar",
33            Self::Paths => "paths",
34            Self::Analyze => "analyze",
35        }
36    }
37}
38
39macro_rules! algorithm_enum {
40    (
41        $name:ident, $default:ident, $verb:expr,
42        { $($variant:ident => $wire:literal),+ $(,)? }
43        $(, aliases { $($alias:literal => $alias_variant:ident),+ $(,)? })?
44    ) => {
45        #[doc = concat!("Typed `by=` values for `", stringify!($name), "`.")]
46        #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
47        pub enum $name {
48            $(
49                #[doc = concat!("`", $wire, "`.")]
50                $variant,
51            )+
52        }
53
54        impl $name {
55            /// Every canonical value in deterministic catalog order.
56            pub const ALL: &'static [Self] = &[$(Self::$variant),+];
57
58            /// Canonical public `by=` value.
59            #[must_use]
60            pub const fn as_str(self) -> &'static str {
61                match self { $(Self::$variant => $wire),+ }
62            }
63
64            /// Owning analyst verb.
65            #[must_use]
66            pub const fn verb(self) -> AlgorithmVerb { $verb }
67        }
68
69        impl fmt::Display for $name {
70            fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
71                formatter.write_str(self.as_str())
72            }
73        }
74
75        impl FromStr for $name {
76            type Err = GfError;
77
78            fn from_str(value: &str) -> Result<Self, Self::Err> {
79                match value {
80                    $($wire => Ok(Self::$variant),)+
81                    $($($alias => Ok(Self::$alias_variant),)+)?
82                    _ => Err(unknown_algorithm($verb, value)),
83                }
84            }
85        }
86
87        impl Default for $name {
88            fn default() -> Self { Self::$default }
89        }
90    };
91}
92
93algorithm_enum!(RankAlgorithm, PageRank, AlgorithmVerb::Rank, {
94    PageRank => "pagerank",
95    Betweenness => "betweenness",
96    Closeness => "closeness",
97    HarmonicCloseness => "harmonic_closeness",
98    Degree => "degree",
99    Eigenvector => "eigenvector",
100    ArticleRank => "article_rank",
101    HitsHub => "hits_hub",
102    HitsAuthority => "hits_authority",
103    Celf => "celf",
104    ClusteringCoefficient => "clustering_coefficient",
105    Triangles => "triangles",
106    KCore => "k_core",
107    PreferentialAttachment => "preferential_attachment",
108    AdamicAdar => "adamic_adar",
109    CommonNeighbors => "common_neighbors",
110    ResourceAllocation => "resource_allocation",
111    TotalNeighbors => "total_neighbors",
112}, aliases {
113    "local_clustering_coefficient" => ClusteringCoefficient,
114});
115
116algorithm_enum!(ClusterAlgorithm, Louvain, AlgorithmVerb::Cluster, {
117    Louvain => "louvain",
118    Leiden => "leiden",
119    LabelPropagation => "label_propagation",
120    SpeakerListener => "speaker_listener",
121    GirvanNewman => "girvan_newman",
122    ModularityOptimization => "modularity_optimization",
123    FastGreedy => "fastgreedy",
124    InfoMap => "infomap",
125    LeadingEigenvector => "leading_eigenvector",
126    Walktrap => "walktrap",
127    Spinglass => "spinglass",
128    Hdbscan => "hdbscan",
129    KMeans => "k_means",
130    ApproximateMaxKCut => "approximate_max_k_cut",
131    Components => "components",
132    StronglyConnected => "strongly_connected",
133    Biconnected => "biconnected",
134    KCoreDecomposition => "k_core_decomposition",
135});
136
137impl ClusterAlgorithm {
138    /// Whether this algorithm consumes edge orientation.
139    #[must_use]
140    pub const fn respects_direction(self) -> bool {
141        match self {
142            Self::InfoMap
143            | Self::LeadingEigenvector
144            | Self::Walktrap
145            | Self::Components
146            | Self::StronglyConnected => true,
147            Self::Louvain
148            | Self::Leiden
149            | Self::LabelPropagation
150            | Self::SpeakerListener
151            | Self::GirvanNewman
152            | Self::ModularityOptimization
153            | Self::FastGreedy
154            | Self::Spinglass
155            | Self::Hdbscan
156            | Self::KMeans
157            | Self::ApproximateMaxKCut
158            | Self::Biconnected
159            | Self::KCoreDecomposition => false,
160        }
161    }
162}
163
164algorithm_enum!(SimilarAlgorithm, NodeSimilarity, AlgorithmVerb::Similar, {
165    NodeSimilarity => "node_similarity",
166    Knn => "knn",
167    FilteredKnn => "filtered_knn",
168    FilteredNodeSimilarity => "filtered_node_similarity",
169    Cosine => "cosine",
170});
171
172algorithm_enum!(PathAlgorithm, Bfs, AlgorithmVerb::Paths, {
173    Bfs => "bfs",
174    Dijkstra => "dijkstra",
175    DijkstraAllPairs => "dijkstra_all_pairs",
176    AStar => "astar",
177    BellmanFord => "bellman_ford",
178    FloydWarshall => "floyd_warshall",
179    DeltaStepping => "delta_stepping",
180    Yens => "yens",
181    MaxFlow => "max_flow",
182    MaxFlowEdges => "max_flow_edges",
183    MinCut => "min_cut",
184    MinCutEdges => "min_cut_edges",
185    MinCostMaxFlow => "min_cost_max_flow",
186    MinCostMaxFlowEdges => "min_cost_max_flow_edges",
187    GomoryHuTree => "gomory_hu_tree",
188    MinSteinerTree => "min_steiner_tree",
189    PrizeCollectingSteinerTree => "prize_collecting_steiner_tree",
190    Dfs => "dfs",
191    RandomWalk => "random_walk",
192    TransitiveClosure => "transitive_closure",
193});
194
195algorithm_enum!(AnalyzeAlgorithm, IsDag, AlgorithmVerb::Analyze, {
196    MinimumSpanningTree => "minimum_spanning_tree",
197    MaximumSpanningTree => "maximum_spanning_tree",
198    MinimumKSpanningTree => "minimum_k_spanning_tree",
199    TopologicalSort => "topological_sort",
200    IsDag => "is_dag",
201    FindCycles => "find_cycles",
202    DagLongestPath => "dag_longest_path",
203    DagLongestPathWeighted => "dag_longest_path_weighted",
204    NodeColoring => "node_coloring",
205    EdgeColoring => "edge_coloring",
206    ChromaticNumber => "chromatic_number",
207    K1Coloring => "k1_coloring",
208    MaxWeightMatching => "max_weight_matching",
209    MaxCardinalityMatching => "max_cardinality_matching",
210    MaxBipartiteMatching => "max_bipartite_matching",
211    EulerCircuit => "euler_circuit",
212    EulerPath => "euler_path",
213    HasEulerCircuit => "has_euler_circuit",
214    HasEulerPath => "has_euler_path",
215    IsPlanar => "is_planar",
216    ArticulationPoints => "articulation_points",
217    Bridges => "bridges",
218    TriangleCount => "triangle_count",
219    Conductance => "conductance",
220    Modularity => "modularity",
221    Transitivity => "transitivity",
222    TriadCensus => "triad_census",
223    DyadCensus => "dyad_census",
224    CountAutomorphisms => "count_automorphisms",
225    Node2Vec => "node2vec",
226    GraphSage => "graphsage",
227    FastRandomProjection => "fast_random_projection",
228    HashGnn => "hashgnn",
229});
230
231/// A typed algorithm from any analyst verb.
232#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
233pub enum Algorithm {
234    /// Rank algorithm.
235    Rank(RankAlgorithm),
236    /// Cluster algorithm.
237    Cluster(ClusterAlgorithm),
238    /// Similarity algorithm.
239    Similar(SimilarAlgorithm),
240    /// Path algorithm.
241    Paths(PathAlgorithm),
242    /// Analysis algorithm.
243    Analyze(AnalyzeAlgorithm),
244}
245
246/// Language-independent type in an algorithm result schema.
247#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
248pub enum AlgorithmFieldType {
249    /// Arrow `FixedSizeBinary(16)` public UUID identity.
250    Uuid,
251    /// Arrow `List<FixedSizeBinary(16)>` UUID sequence.
252    UuidList,
253    /// Arrow `List<Float32>` embedding.
254    Float32List,
255    /// Arrow `Utf8`.
256    Utf8,
257    /// Arrow `Boolean`.
258    Boolean,
259    /// Arrow `UInt64`.
260    UInt64,
261    /// Arrow `Int64`.
262    Int64,
263    /// Arrow `Float64`.
264    Float64,
265}
266
267/// Required field in a stable logical result schema.
268#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
269pub struct AlgorithmField {
270    /// Stable public column name.
271    pub name: &'static str,
272    /// Logical Arrow type.
273    pub data_type: AlgorithmFieldType,
274    /// Whether the field accepts nulls.
275    pub nullable: bool,
276}
277
278const fn field(
279    name: &'static str,
280    data_type: AlgorithmFieldType,
281    nullable: bool,
282) -> AlgorithmField {
283    AlgorithmField {
284        name,
285        data_type,
286        nullable,
287    }
288}
289
290/// Stable logical schema required from an algorithm implementation.
291#[derive(Debug, Clone, Copy, PartialEq, Eq)]
292pub struct AlgorithmResultSchema {
293    /// Required fields in public output order.
294    pub fields: &'static [AlgorithmField],
295    /// Node properties follow the required fields for node-oriented verbs.
296    pub includes_node_properties: bool,
297}
298
299const fn schema(fields: &'static [AlgorithmField]) -> AlgorithmResultSchema {
300    AlgorithmResultSchema {
301        fields,
302        includes_node_properties: false,
303    }
304}
305
306const fn node_schema(fields: &'static [AlgorithmField]) -> AlgorithmResultSchema {
307    AlgorithmResultSchema {
308        fields,
309        includes_node_properties: true,
310    }
311}
312
313const NODE_SCORE: &[AlgorithmField] = &[
314    field("node_uuid", AlgorithmFieldType::Uuid, false),
315    field("score", AlgorithmFieldType::Float64, false),
316];
317const NODE_COMMUNITY: &[AlgorithmField] = &[
318    field("node_uuid", AlgorithmFieldType::Uuid, false),
319    field("community_id", AlgorithmFieldType::Int64, false),
320];
321const SIMILARITY: &[AlgorithmField] = &[
322    field("node1_uuid", AlgorithmFieldType::Uuid, false),
323    field("node2_uuid", AlgorithmFieldType::Uuid, false),
324    field("similarity", AlgorithmFieldType::Float64, false),
325];
326const PATH: &[AlgorithmField] = &[
327    field("source_uuid", AlgorithmFieldType::Uuid, false),
328    field("target_uuid", AlgorithmFieldType::Uuid, false),
329    field("cost", AlgorithmFieldType::Float64, false),
330    field("path", AlgorithmFieldType::UuidList, false),
331];
332const RANKED_PATH: &[AlgorithmField] = &[
333    field("source_uuid", AlgorithmFieldType::Uuid, false),
334    field("target_uuid", AlgorithmFieldType::Uuid, false),
335    field("rank", AlgorithmFieldType::UInt64, false),
336    field("cost", AlgorithmFieldType::Float64, false),
337    field("path", AlgorithmFieldType::UuidList, false),
338];
339const FLOW: &[AlgorithmField] = &[
340    field("source_uuid", AlgorithmFieldType::Uuid, false),
341    field("sink_uuid", AlgorithmFieldType::Uuid, false),
342    field("flow", AlgorithmFieldType::Float64, false),
343];
344const FLOW_EDGES: &[AlgorithmField] = &[
345    field("edge_uuid", AlgorithmFieldType::Uuid, false),
346    field("source_uuid", AlgorithmFieldType::Uuid, false),
347    field("target_uuid", AlgorithmFieldType::Uuid, false),
348    field("flow", AlgorithmFieldType::Float64, false),
349];
350const COSTED_FLOW: &[AlgorithmField] = &[
351    field("source_uuid", AlgorithmFieldType::Uuid, false),
352    field("sink_uuid", AlgorithmFieldType::Uuid, false),
353    field("flow", AlgorithmFieldType::Float64, false),
354    field("cost", AlgorithmFieldType::Float64, false),
355];
356const COSTED_FLOW_EDGES: &[AlgorithmField] = &[
357    field("edge_uuid", AlgorithmFieldType::Uuid, false),
358    field("source_uuid", AlgorithmFieldType::Uuid, false),
359    field("target_uuid", AlgorithmFieldType::Uuid, false),
360    field("flow", AlgorithmFieldType::Float64, false),
361    field("unit_cost", AlgorithmFieldType::Float64, false),
362    field("flow_cost", AlgorithmFieldType::Float64, false),
363];
364const MIN_CUT: &[AlgorithmField] = &[
365    field("source_uuid", AlgorithmFieldType::Uuid, false),
366    field("sink_uuid", AlgorithmFieldType::Uuid, false),
367    field("cut_value", AlgorithmFieldType::Float64, false),
368];
369const MIN_CUT_EDGES: &[AlgorithmField] = &[
370    field("edge_uuid", AlgorithmFieldType::Uuid, false),
371    field("source_uuid", AlgorithmFieldType::Uuid, false),
372    field("target_uuid", AlgorithmFieldType::Uuid, false),
373    field("capacity", AlgorithmFieldType::Float64, false),
374];
375const CUT: &[AlgorithmField] = &[
376    field("source_uuid", AlgorithmFieldType::Uuid, false),
377    field("target_uuid", AlgorithmFieldType::Uuid, false),
378    field("cut_value", AlgorithmFieldType::Float64, false),
379];
380const EDGE_LIST: &[AlgorithmField] = &[
381    field("edge_uuid", AlgorithmFieldType::Uuid, false),
382    field("source_uuid", AlgorithmFieldType::Uuid, false),
383    field("target_uuid", AlgorithmFieldType::Uuid, false),
384    field("weight", AlgorithmFieldType::Float64, true),
385];
386const STEINER_EDGE_LIST: &[AlgorithmField] = &[
387    field("edge_uuid", AlgorithmFieldType::Uuid, false),
388    field("source_uuid", AlgorithmFieldType::Uuid, false),
389    field("target_uuid", AlgorithmFieldType::Uuid, false),
390    field("weight", AlgorithmFieldType::Float64, false),
391];
392const UNWEIGHTED_EDGE_LIST: &[AlgorithmField] = &[
393    field("edge_uuid", AlgorithmFieldType::Uuid, false),
394    field("source_uuid", AlgorithmFieldType::Uuid, false),
395    field("target_uuid", AlgorithmFieldType::Uuid, false),
396];
397const K_EDGE_LIST: &[AlgorithmField] = &[
398    field("tree_id", AlgorithmFieldType::UInt64, false),
399    field("edge_uuid", AlgorithmFieldType::Uuid, false),
400    field("source_uuid", AlgorithmFieldType::Uuid, false),
401    field("target_uuid", AlgorithmFieldType::Uuid, false),
402    field("weight", AlgorithmFieldType::Float64, false),
403];
404const TRAVERSAL: &[AlgorithmField] = &[
405    field("node_uuid", AlgorithmFieldType::Uuid, false),
406    field("depth", AlgorithmFieldType::UInt64, false),
407    field("order", AlgorithmFieldType::UInt64, false),
408];
409const WALK: &[AlgorithmField] = &[
410    field("start_uuid", AlgorithmFieldType::Uuid, false),
411    field("walk", AlgorithmFieldType::UuidList, false),
412];
413const PAIR: &[AlgorithmField] = &[
414    field("source_uuid", AlgorithmFieldType::Uuid, false),
415    field("target_uuid", AlgorithmFieldType::Uuid, false),
416];
417const NODE_ORDER: &[AlgorithmField] = &[
418    field("node_uuid", AlgorithmFieldType::Uuid, false),
419    field("order", AlgorithmFieldType::UInt64, false),
420];
421const NODE: &[AlgorithmField] = &[field("node_uuid", AlgorithmFieldType::Uuid, false)];
422const NODE_COLOR: &[AlgorithmField] = &[
423    field("node_uuid", AlgorithmFieldType::Uuid, false),
424    field("color", AlgorithmFieldType::UInt64, false),
425];
426const EDGE_COLOR: &[AlgorithmField] = &[
427    field("edge_uuid", AlgorithmFieldType::Uuid, false),
428    field("color", AlgorithmFieldType::UInt64, false),
429];
430const EULER_TRAIL: &[AlgorithmField] = &[
431    field("node_path", AlgorithmFieldType::UuidList, false),
432    field("edge_path", AlgorithmFieldType::UuidList, false),
433];
434const CYCLE: &[AlgorithmField] = &[field("cycle", AlgorithmFieldType::UuidList, false)];
435const COST_PATH: &[AlgorithmField] = &[
436    field("cost", AlgorithmFieldType::Float64, false),
437    field("path", AlgorithmFieldType::UuidList, false),
438];
439const IS_DAG: &[AlgorithmField] = &[field("is_dag", AlgorithmFieldType::Boolean, false)];
440const HAS_EULER_CIRCUIT: &[AlgorithmField] = &[field(
441    "has_euler_circuit",
442    AlgorithmFieldType::Boolean,
443    false,
444)];
445const HAS_EULER_PATH: &[AlgorithmField] =
446    &[field("has_euler_path", AlgorithmFieldType::Boolean, false)];
447const IS_PLANAR: &[AlgorithmField] = &[field("is_planar", AlgorithmFieldType::Boolean, false)];
448const CHROMATIC_NUMBER: &[AlgorithmField] =
449    &[field("chromatic_number", AlgorithmFieldType::UInt64, false)];
450const TRIANGLE_COUNT: &[AlgorithmField] =
451    &[field("triangle_count", AlgorithmFieldType::UInt64, false)];
452const AUTOMORPHISM_COUNT: &[AlgorithmField] = &[field("count", AlgorithmFieldType::UInt64, false)];
453const CONDUCTANCE: &[AlgorithmField] = &[
454    field("partition_id", AlgorithmFieldType::Utf8, false),
455    field("conductance", AlgorithmFieldType::Float64, false),
456];
457const MODULARITY: &[AlgorithmField] = &[field("modularity", AlgorithmFieldType::Float64, false)];
458const TRANSITIVITY: &[AlgorithmField] =
459    &[field("transitivity", AlgorithmFieldType::Float64, false)];
460const TRIAD_CENSUS: &[AlgorithmField] = &[
461    field("triad_type", AlgorithmFieldType::Utf8, false),
462    field("count", AlgorithmFieldType::UInt64, false),
463];
464const DYAD_CENSUS: &[AlgorithmField] = &[
465    field("dyad_type", AlgorithmFieldType::Utf8, false),
466    field("count", AlgorithmFieldType::UInt64, false),
467];
468const EMBEDDING: &[AlgorithmField] = &[
469    field("node_uuid", AlgorithmFieldType::Uuid, false),
470    field("embedding", AlgorithmFieldType::Float32List, false),
471];
472
473impl Algorithm {
474    /// Parse a public `by=` value in the namespace of its verb.
475    pub fn parse(verb: AlgorithmVerb, value: &str) -> Result<Self, GfError> {
476        match verb {
477            AlgorithmVerb::Rank => value.parse().map(Self::Rank),
478            AlgorithmVerb::Cluster => value.parse().map(Self::Cluster),
479            AlgorithmVerb::Similar => value.parse().map(Self::Similar),
480            AlgorithmVerb::Paths => value.parse().map(Self::Paths),
481            AlgorithmVerb::Analyze => value.parse().map(Self::Analyze),
482        }
483    }
484
485    /// Owning public verb.
486    #[must_use]
487    pub const fn verb(self) -> AlgorithmVerb {
488        match self {
489            Self::Rank(_) => AlgorithmVerb::Rank,
490            Self::Cluster(_) => AlgorithmVerb::Cluster,
491            Self::Similar(_) => AlgorithmVerb::Similar,
492            Self::Paths(_) => AlgorithmVerb::Paths,
493            Self::Analyze(_) => AlgorithmVerb::Analyze,
494        }
495    }
496
497    /// Canonical public `by=` value.
498    #[must_use]
499    pub const fn as_str(self) -> &'static str {
500        match self {
501            Self::Rank(value) => value.as_str(),
502            Self::Cluster(value) => value.as_str(),
503            Self::Similar(value) => value.as_str(),
504            Self::Paths(value) => value.as_str(),
505            Self::Analyze(value) => value.as_str(),
506        }
507    }
508
509    /// Stable logical result schema required from every language surface.
510    #[must_use]
511    pub const fn result_schema(self) -> AlgorithmResultSchema {
512        match self {
513            Self::Rank(_) => node_schema(NODE_SCORE),
514            Self::Cluster(_) => node_schema(NODE_COMMUNITY),
515            Self::Similar(_) => schema(SIMILARITY),
516            Self::Paths(value) => path_schema(value),
517            Self::Analyze(value) => analyze_schema(value),
518        }
519    }
520}
521
522const fn path_schema(value: PathAlgorithm) -> AlgorithmResultSchema {
523    match value {
524        PathAlgorithm::Yens => schema(RANKED_PATH),
525        PathAlgorithm::MaxFlow => schema(FLOW),
526        PathAlgorithm::MaxFlowEdges => schema(FLOW_EDGES),
527        PathAlgorithm::MinCut => schema(MIN_CUT),
528        PathAlgorithm::MinCutEdges => schema(MIN_CUT_EDGES),
529        PathAlgorithm::MinCostMaxFlow => schema(COSTED_FLOW),
530        PathAlgorithm::MinCostMaxFlowEdges => schema(COSTED_FLOW_EDGES),
531        PathAlgorithm::GomoryHuTree => schema(CUT),
532        PathAlgorithm::MinSteinerTree | PathAlgorithm::PrizeCollectingSteinerTree => {
533            schema(STEINER_EDGE_LIST)
534        }
535        PathAlgorithm::Dfs => schema(TRAVERSAL),
536        PathAlgorithm::RandomWalk => schema(WALK),
537        PathAlgorithm::TransitiveClosure => schema(PAIR),
538        _ => schema(PATH),
539    }
540}
541
542const fn analyze_schema(value: AnalyzeAlgorithm) -> AlgorithmResultSchema {
543    match value {
544        AnalyzeAlgorithm::MinimumKSpanningTree => schema(K_EDGE_LIST),
545        AnalyzeAlgorithm::MinimumSpanningTree
546        | AnalyzeAlgorithm::MaximumSpanningTree
547        | AnalyzeAlgorithm::MaxWeightMatching => schema(EDGE_LIST),
548        AnalyzeAlgorithm::MaxCardinalityMatching
549        | AnalyzeAlgorithm::MaxBipartiteMatching
550        | AnalyzeAlgorithm::Bridges => schema(UNWEIGHTED_EDGE_LIST),
551        AnalyzeAlgorithm::TopologicalSort => schema(NODE_ORDER),
552        AnalyzeAlgorithm::ArticulationPoints => schema(NODE),
553        AnalyzeAlgorithm::IsDag => schema(IS_DAG),
554        AnalyzeAlgorithm::FindCycles => schema(CYCLE),
555        AnalyzeAlgorithm::DagLongestPath | AnalyzeAlgorithm::DagLongestPathWeighted => {
556            schema(COST_PATH)
557        }
558        AnalyzeAlgorithm::NodeColoring | AnalyzeAlgorithm::K1Coloring => schema(NODE_COLOR),
559        AnalyzeAlgorithm::EdgeColoring => schema(EDGE_COLOR),
560        AnalyzeAlgorithm::ChromaticNumber => schema(CHROMATIC_NUMBER),
561        AnalyzeAlgorithm::EulerCircuit | AnalyzeAlgorithm::EulerPath => schema(EULER_TRAIL),
562        AnalyzeAlgorithm::HasEulerCircuit => schema(HAS_EULER_CIRCUIT),
563        AnalyzeAlgorithm::HasEulerPath => schema(HAS_EULER_PATH),
564        AnalyzeAlgorithm::IsPlanar => schema(IS_PLANAR),
565        AnalyzeAlgorithm::TriangleCount => schema(TRIANGLE_COUNT),
566        AnalyzeAlgorithm::Conductance => schema(CONDUCTANCE),
567        AnalyzeAlgorithm::Modularity => schema(MODULARITY),
568        AnalyzeAlgorithm::Transitivity => schema(TRANSITIVITY),
569        AnalyzeAlgorithm::TriadCensus => schema(TRIAD_CENSUS),
570        AnalyzeAlgorithm::DyadCensus => schema(DYAD_CENSUS),
571        AnalyzeAlgorithm::CountAutomorphisms => schema(AUTOMORPHISM_COUNT),
572        AnalyzeAlgorithm::Node2Vec
573        | AnalyzeAlgorithm::GraphSage
574        | AnalyzeAlgorithm::FastRandomProjection
575        | AnalyzeAlgorithm::HashGnn => schema(EMBEDDING),
576    }
577}
578
579fn unknown_algorithm(verb: AlgorithmVerb, value: &str) -> GfError {
580    GfError::Validation(format!(
581        "unknown {} algorithm `{value}`; use a catalogued `by=` value",
582        verb.as_str()
583    ))
584}
585
586#[cfg(test)]
587mod tests {
588    use std::collections::HashSet;
589
590    use super::*;
591
592    #[test]
593    fn every_catalog_is_unique_and_round_trips() {
594        let rank = RankAlgorithm::ALL
595            .iter()
596            .map(|value| value.as_str())
597            .collect::<Vec<_>>();
598        let cluster = ClusterAlgorithm::ALL
599            .iter()
600            .map(|value| value.as_str())
601            .collect::<Vec<_>>();
602        let similar = SimilarAlgorithm::ALL
603            .iter()
604            .map(|value| value.as_str())
605            .collect::<Vec<_>>();
606        let paths = PathAlgorithm::ALL
607            .iter()
608            .map(|value| value.as_str())
609            .collect::<Vec<_>>();
610        let analyze = AnalyzeAlgorithm::ALL
611            .iter()
612            .map(|value| value.as_str())
613            .collect::<Vec<_>>();
614        let catalogs: &[(&[&str], AlgorithmVerb)] = &[
615            (&rank, AlgorithmVerb::Rank),
616            (&cluster, AlgorithmVerb::Cluster),
617            (&similar, AlgorithmVerb::Similar),
618            (&paths, AlgorithmVerb::Paths),
619            (&analyze, AlgorithmVerb::Analyze),
620        ];
621
622        for (names, verb) in catalogs {
623            let unique: HashSet<_> = names.iter().copied().collect();
624            assert_eq!(unique.len(), names.len(), "duplicate in {}", verb.as_str());
625            for name in *names {
626                let parsed = Algorithm::parse(*verb, name).expect("catalog entry must parse");
627                assert_eq!(parsed.as_str(), *name);
628                assert_eq!(parsed.verb(), *verb);
629                assert!(!parsed.result_schema().fields.is_empty());
630            }
631        }
632    }
633
634    #[test]
635    fn rank_alias_has_one_canonical_owner() {
636        let alias: RankAlgorithm = "local_clustering_coefficient".parse().unwrap();
637        assert_eq!(alias, RankAlgorithm::ClusteringCoefficient);
638        assert_eq!(alias.as_str(), "clustering_coefficient");
639        assert!(
640            !RankAlgorithm::ALL
641                .iter()
642                .any(|value| value.as_str() == "local_clustering_coefficient")
643        );
644    }
645
646    #[test]
647    fn invalid_name_is_a_stable_validation_error() {
648        let error = Algorithm::parse(AlgorithmVerb::Similar, "pagerank").unwrap_err();
649        assert!(matches!(error, GfError::Validation(_)));
650        assert_eq!(
651            error.to_string(),
652            "validation error: unknown similar algorithm `pagerank`; use a catalogued `by=` value"
653        );
654    }
655
656    #[test]
657    fn vertical_proof_schemas_are_stable_and_uuid_only() {
658        let cases = [
659            (
660                Algorithm::Rank(RankAlgorithm::Degree),
661                &["node_uuid", "score"][..],
662            ),
663            (
664                Algorithm::Cluster(ClusterAlgorithm::Components),
665                &["node_uuid", "community_id"],
666            ),
667            (
668                Algorithm::Similar(SimilarAlgorithm::NodeSimilarity),
669                &["node1_uuid", "node2_uuid", "similarity"],
670            ),
671            (
672                Algorithm::Paths(PathAlgorithm::Bfs),
673                &["source_uuid", "target_uuid", "cost", "path"],
674            ),
675            (Algorithm::Analyze(AnalyzeAlgorithm::IsDag), &["is_dag"]),
676        ];
677        for (algorithm, names) in cases {
678            let fields = algorithm.result_schema().fields;
679            assert_eq!(
680                fields.iter().map(|field| field.name).collect::<Vec<_>>(),
681                names
682            );
683            assert!(fields.iter().all(|field| {
684                ![
685                    "node_id",
686                    "edge_id",
687                    "src_id",
688                    "dst_id",
689                    "source_id",
690                    "target_id",
691                ]
692                .contains(&field.name)
693            }));
694        }
695    }
696
697    #[test]
698    fn max_cardinality_matching_has_an_unweighted_edge_schema() {
699        let fields = Algorithm::Analyze(AnalyzeAlgorithm::MaxCardinalityMatching)
700            .result_schema()
701            .fields;
702
703        assert_eq!(
704            fields
705                .iter()
706                .map(|field| (field.name, field.data_type, field.nullable))
707                .collect::<Vec<_>>(),
708            [
709                ("edge_uuid", AlgorithmFieldType::Uuid, false),
710                ("source_uuid", AlgorithmFieldType::Uuid, false),
711                ("target_uuid", AlgorithmFieldType::Uuid, false),
712            ]
713        );
714    }
715
716    #[test]
717    fn max_bipartite_matching_has_an_unweighted_edge_schema() {
718        let fields = Algorithm::Analyze(AnalyzeAlgorithm::MaxBipartiteMatching)
719            .result_schema()
720            .fields;
721
722        assert_eq!(
723            fields
724                .iter()
725                .map(|field| (field.name, field.data_type, field.nullable))
726                .collect::<Vec<_>>(),
727            [
728                ("edge_uuid", AlgorithmFieldType::Uuid, false),
729                ("source_uuid", AlgorithmFieldType::Uuid, false),
730                ("target_uuid", AlgorithmFieldType::Uuid, false),
731            ]
732        );
733    }
734
735    #[test]
736    fn max_flow_catalog_values_have_separate_stable_schemas() {
737        let scalar: PathAlgorithm = "max_flow".parse().unwrap();
738        let edges: PathAlgorithm = "max_flow_edges".parse().unwrap();
739
740        assert_eq!(scalar, PathAlgorithm::MaxFlow);
741        assert_eq!(scalar.as_str(), "max_flow");
742        assert_eq!(edges, PathAlgorithm::MaxFlowEdges);
743        assert_eq!(edges.as_str(), "max_flow_edges");
744        assert_eq!(
745            Algorithm::Paths(scalar)
746                .result_schema()
747                .fields
748                .iter()
749                .map(|field| (field.name, field.data_type, field.nullable))
750                .collect::<Vec<_>>(),
751            [
752                ("source_uuid", AlgorithmFieldType::Uuid, false),
753                ("sink_uuid", AlgorithmFieldType::Uuid, false),
754                ("flow", AlgorithmFieldType::Float64, false),
755            ]
756        );
757        assert_eq!(
758            Algorithm::Paths(edges)
759                .result_schema()
760                .fields
761                .iter()
762                .map(|field| (field.name, field.data_type, field.nullable))
763                .collect::<Vec<_>>(),
764            [
765                ("edge_uuid", AlgorithmFieldType::Uuid, false),
766                ("source_uuid", AlgorithmFieldType::Uuid, false),
767                ("target_uuid", AlgorithmFieldType::Uuid, false),
768                ("flow", AlgorithmFieldType::Float64, false),
769            ]
770        );
771    }
772
773    #[test]
774    fn min_cost_flow_catalog_values_have_separate_stable_schemas() {
775        let scalar: PathAlgorithm = "min_cost_max_flow".parse().unwrap();
776        let edges: PathAlgorithm = "min_cost_max_flow_edges".parse().unwrap();
777        assert_eq!(scalar, PathAlgorithm::MinCostMaxFlow);
778        assert_eq!(edges, PathAlgorithm::MinCostMaxFlowEdges);
779        assert_eq!(
780            Algorithm::Paths(scalar)
781                .result_schema()
782                .fields
783                .iter()
784                .map(|field| field.name)
785                .collect::<Vec<_>>(),
786            ["source_uuid", "sink_uuid", "flow", "cost"]
787        );
788        assert_eq!(
789            Algorithm::Paths(edges)
790                .result_schema()
791                .fields
792                .iter()
793                .map(|field| field.name)
794                .collect::<Vec<_>>(),
795            [
796                "edge_uuid",
797                "source_uuid",
798                "target_uuid",
799                "flow",
800                "unit_cost",
801                "flow_cost",
802            ]
803        );
804        assert!(
805            Algorithm::Paths(edges)
806                .result_schema()
807                .fields
808                .iter()
809                .all(|field| !field.nullable)
810        );
811    }
812
813    #[test]
814    fn min_cut_catalog_values_have_distinct_stable_uuid_schemas() {
815        let scalar: PathAlgorithm = "min_cut".parse().unwrap();
816        let edges: PathAlgorithm = "min_cut_edges".parse().unwrap();
817
818        assert_eq!(scalar, PathAlgorithm::MinCut);
819        assert_eq!(scalar.as_str(), "min_cut");
820        assert_eq!(scalar.to_string(), "min_cut");
821        assert_eq!(edges, PathAlgorithm::MinCutEdges);
822        assert_eq!(edges.as_str(), "min_cut_edges");
823        assert_eq!(edges.to_string(), "min_cut_edges");
824
825        let scalar_schema = Algorithm::Paths(scalar).result_schema();
826        assert_eq!(
827            scalar_schema
828                .fields
829                .iter()
830                .map(|field| (field.name, field.data_type, field.nullable))
831                .collect::<Vec<_>>(),
832            [
833                ("source_uuid", AlgorithmFieldType::Uuid, false),
834                ("sink_uuid", AlgorithmFieldType::Uuid, false),
835                ("cut_value", AlgorithmFieldType::Float64, false),
836            ]
837        );
838
839        let edge_schema = Algorithm::Paths(edges).result_schema();
840        assert_eq!(
841            edge_schema
842                .fields
843                .iter()
844                .map(|field| (field.name, field.data_type, field.nullable))
845                .collect::<Vec<_>>(),
846            [
847                ("edge_uuid", AlgorithmFieldType::Uuid, false),
848                ("source_uuid", AlgorithmFieldType::Uuid, false),
849                ("target_uuid", AlgorithmFieldType::Uuid, false),
850                ("capacity", AlgorithmFieldType::Float64, false),
851            ]
852        );
853        assert_ne!(scalar_schema, edge_schema);
854        assert!(scalar_schema.fields.iter().all(|field| {
855            !["node_id", "edge_id", "source_id", "sink_id", "target_id"].contains(&field.name)
856        }));
857        assert!(edge_schema.fields.iter().all(|field| {
858            !["node_id", "edge_id", "source_id", "sink_id", "target_id"].contains(&field.name)
859        }));
860    }
861
862    #[test]
863    fn euler_constructions_share_aligned_non_null_identity_schema() {
864        for algorithm in [AnalyzeAlgorithm::EulerCircuit, AnalyzeAlgorithm::EulerPath] {
865            assert_eq!(
866                Algorithm::Analyze(algorithm)
867                    .result_schema()
868                    .fields
869                    .iter()
870                    .map(|field| (field.name, field.data_type, field.nullable))
871                    .collect::<Vec<_>>(),
872                [
873                    ("node_path", AlgorithmFieldType::UuidList, false),
874                    ("edge_path", AlgorithmFieldType::UuidList, false),
875                ]
876            );
877        }
878    }
879
880    #[test]
881    fn steiner_algorithms_share_dedicated_non_null_weighted_edge_schema() {
882        let ordinary_edge_list =
883            Algorithm::Analyze(AnalyzeAlgorithm::MinimumSpanningTree).result_schema();
884        assert_eq!(
885            ordinary_edge_list
886                .fields
887                .iter()
888                .map(|field| (field.name, field.data_type, field.nullable))
889                .collect::<Vec<_>>(),
890            [
891                ("edge_uuid", AlgorithmFieldType::Uuid, false),
892                ("source_uuid", AlgorithmFieldType::Uuid, false),
893                ("target_uuid", AlgorithmFieldType::Uuid, false),
894                ("weight", AlgorithmFieldType::Float64, true),
895            ]
896        );
897        assert!(!ordinary_edge_list.includes_node_properties);
898        for algorithm in [
899            PathAlgorithm::MinSteinerTree,
900            PathAlgorithm::PrizeCollectingSteinerTree,
901        ] {
902            let steiner = Algorithm::Paths(algorithm).result_schema();
903            assert_eq!(
904                steiner
905                    .fields
906                    .iter()
907                    .map(|field| (field.name, field.data_type, field.nullable))
908                    .collect::<Vec<_>>(),
909                [
910                    ("edge_uuid", AlgorithmFieldType::Uuid, false),
911                    ("source_uuid", AlgorithmFieldType::Uuid, false),
912                    ("target_uuid", AlgorithmFieldType::Uuid, false),
913                    ("weight", AlgorithmFieldType::Float64, false),
914                ]
915            );
916            assert!(!steiner.includes_node_properties);
917            assert_ne!(steiner, ordinary_edge_list);
918        }
919    }
920}
graphforge_core/algorithms.rs

graphforge_core/
algorithms.rs
