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 concrete_catalog_accessors_display_and_direction_policy_are_total() {
636        for value in RankAlgorithm::ALL {
637            assert_eq!(value.verb(), AlgorithmVerb::Rank);
638            assert_eq!(value.to_string(), value.as_str());
639        }
640        for value in SimilarAlgorithm::ALL {
641            assert_eq!(value.verb(), AlgorithmVerb::Similar);
642            assert_eq!(value.to_string(), value.as_str());
643        }
644        for value in PathAlgorithm::ALL {
645            assert_eq!(value.verb(), AlgorithmVerb::Paths);
646            assert_eq!(value.to_string(), value.as_str());
647        }
648        for value in AnalyzeAlgorithm::ALL {
649            assert_eq!(value.verb(), AlgorithmVerb::Analyze);
650            assert_eq!(value.to_string(), value.as_str());
651        }
652        for value in ClusterAlgorithm::ALL {
653            assert_eq!(value.verb(), AlgorithmVerb::Cluster);
654            assert_eq!(value.to_string(), value.as_str());
655        }
656        assert!(ClusterAlgorithm::InfoMap.respects_direction());
657        assert!(ClusterAlgorithm::StronglyConnected.respects_direction());
658        assert!(!ClusterAlgorithm::Louvain.respects_direction());
659        assert!(!ClusterAlgorithm::Hdbscan.respects_direction());
660    }
661
662    #[test]
663    fn rank_alias_has_one_canonical_owner() {
664        let alias: RankAlgorithm = "local_clustering_coefficient".parse().unwrap();
665        assert_eq!(alias, RankAlgorithm::ClusteringCoefficient);
666        assert_eq!(alias.as_str(), "clustering_coefficient");
667        assert!(
668            !RankAlgorithm::ALL
669                .iter()
670                .any(|value| value.as_str() == "local_clustering_coefficient")
671        );
672    }
673
674    #[test]
675    fn invalid_name_is_a_stable_validation_error() {
676        let error = Algorithm::parse(AlgorithmVerb::Similar, "pagerank").unwrap_err();
677        assert!(matches!(error, GfError::Validation(_)));
678        assert_eq!(
679            error.to_string(),
680            "validation error: unknown similar algorithm `pagerank`; use a catalogued `by=` value"
681        );
682    }
683
684    #[test]
685    fn vertical_proof_schemas_are_stable_and_uuid_only() {
686        let cases = [
687            (
688                Algorithm::Rank(RankAlgorithm::Degree),
689                &["node_uuid", "score"][..],
690            ),
691            (
692                Algorithm::Cluster(ClusterAlgorithm::Components),
693                &["node_uuid", "community_id"],
694            ),
695            (
696                Algorithm::Similar(SimilarAlgorithm::NodeSimilarity),
697                &["node1_uuid", "node2_uuid", "similarity"],
698            ),
699            (
700                Algorithm::Paths(PathAlgorithm::Bfs),
701                &["source_uuid", "target_uuid", "cost", "path"],
702            ),
703            (Algorithm::Analyze(AnalyzeAlgorithm::IsDag), &["is_dag"]),
704        ];
705        for (algorithm, names) in cases {
706            let fields = algorithm.result_schema().fields;
707            assert_eq!(
708                fields.iter().map(|field| field.name).collect::<Vec<_>>(),
709                names
710            );
711            assert!(fields.iter().all(|field| {
712                ![
713                    "node_id",
714                    "edge_id",
715                    "src_id",
716                    "dst_id",
717                    "source_id",
718                    "target_id",
719                ]
720                .contains(&field.name)
721            }));
722        }
723    }
724
725    #[test]
726    fn max_cardinality_matching_has_an_unweighted_edge_schema() {
727        let fields = Algorithm::Analyze(AnalyzeAlgorithm::MaxCardinalityMatching)
728            .result_schema()
729            .fields;
730
731        assert_eq!(
732            fields
733                .iter()
734                .map(|field| (field.name, field.data_type, field.nullable))
735                .collect::<Vec<_>>(),
736            [
737                ("edge_uuid", AlgorithmFieldType::Uuid, false),
738                ("source_uuid", AlgorithmFieldType::Uuid, false),
739                ("target_uuid", AlgorithmFieldType::Uuid, false),
740            ]
741        );
742    }
743
744    #[test]
745    fn max_bipartite_matching_has_an_unweighted_edge_schema() {
746        let fields = Algorithm::Analyze(AnalyzeAlgorithm::MaxBipartiteMatching)
747            .result_schema()
748            .fields;
749
750        assert_eq!(
751            fields
752                .iter()
753                .map(|field| (field.name, field.data_type, field.nullable))
754                .collect::<Vec<_>>(),
755            [
756                ("edge_uuid", AlgorithmFieldType::Uuid, false),
757                ("source_uuid", AlgorithmFieldType::Uuid, false),
758                ("target_uuid", AlgorithmFieldType::Uuid, false),
759            ]
760        );
761    }
762
763    #[test]
764    fn max_flow_catalog_values_have_separate_stable_schemas() {
765        let scalar: PathAlgorithm = "max_flow".parse().unwrap();
766        let edges: PathAlgorithm = "max_flow_edges".parse().unwrap();
767
768        assert_eq!(scalar, PathAlgorithm::MaxFlow);
769        assert_eq!(scalar.as_str(), "max_flow");
770        assert_eq!(edges, PathAlgorithm::MaxFlowEdges);
771        assert_eq!(edges.as_str(), "max_flow_edges");
772        assert_eq!(
773            Algorithm::Paths(scalar)
774                .result_schema()
775                .fields
776                .iter()
777                .map(|field| (field.name, field.data_type, field.nullable))
778                .collect::<Vec<_>>(),
779            [
780                ("source_uuid", AlgorithmFieldType::Uuid, false),
781                ("sink_uuid", AlgorithmFieldType::Uuid, false),
782                ("flow", AlgorithmFieldType::Float64, false),
783            ]
784        );
785        assert_eq!(
786            Algorithm::Paths(edges)
787                .result_schema()
788                .fields
789                .iter()
790                .map(|field| (field.name, field.data_type, field.nullable))
791                .collect::<Vec<_>>(),
792            [
793                ("edge_uuid", AlgorithmFieldType::Uuid, false),
794                ("source_uuid", AlgorithmFieldType::Uuid, false),
795                ("target_uuid", AlgorithmFieldType::Uuid, false),
796                ("flow", AlgorithmFieldType::Float64, false),
797            ]
798        );
799    }
800
801    #[test]
802    fn min_cost_flow_catalog_values_have_separate_stable_schemas() {
803        let scalar: PathAlgorithm = "min_cost_max_flow".parse().unwrap();
804        let edges: PathAlgorithm = "min_cost_max_flow_edges".parse().unwrap();
805        assert_eq!(scalar, PathAlgorithm::MinCostMaxFlow);
806        assert_eq!(edges, PathAlgorithm::MinCostMaxFlowEdges);
807        assert_eq!(
808            Algorithm::Paths(scalar)
809                .result_schema()
810                .fields
811                .iter()
812                .map(|field| field.name)
813                .collect::<Vec<_>>(),
814            ["source_uuid", "sink_uuid", "flow", "cost"]
815        );
816        assert_eq!(
817            Algorithm::Paths(edges)
818                .result_schema()
819                .fields
820                .iter()
821                .map(|field| field.name)
822                .collect::<Vec<_>>(),
823            [
824                "edge_uuid",
825                "source_uuid",
826                "target_uuid",
827                "flow",
828                "unit_cost",
829                "flow_cost",
830            ]
831        );
832        assert!(
833            Algorithm::Paths(edges)
834                .result_schema()
835                .fields
836                .iter()
837                .all(|field| !field.nullable)
838        );
839    }
840
841    #[test]
842    fn min_cut_catalog_values_have_distinct_stable_uuid_schemas() {
843        let scalar: PathAlgorithm = "min_cut".parse().unwrap();
844        let edges: PathAlgorithm = "min_cut_edges".parse().unwrap();
845
846        assert_eq!(scalar, PathAlgorithm::MinCut);
847        assert_eq!(scalar.as_str(), "min_cut");
848        assert_eq!(scalar.to_string(), "min_cut");
849        assert_eq!(edges, PathAlgorithm::MinCutEdges);
850        assert_eq!(edges.as_str(), "min_cut_edges");
851        assert_eq!(edges.to_string(), "min_cut_edges");
852
853        let scalar_schema = Algorithm::Paths(scalar).result_schema();
854        assert_eq!(
855            scalar_schema
856                .fields
857                .iter()
858                .map(|field| (field.name, field.data_type, field.nullable))
859                .collect::<Vec<_>>(),
860            [
861                ("source_uuid", AlgorithmFieldType::Uuid, false),
862                ("sink_uuid", AlgorithmFieldType::Uuid, false),
863                ("cut_value", AlgorithmFieldType::Float64, false),
864            ]
865        );
866
867        let edge_schema = Algorithm::Paths(edges).result_schema();
868        assert_eq!(
869            edge_schema
870                .fields
871                .iter()
872                .map(|field| (field.name, field.data_type, field.nullable))
873                .collect::<Vec<_>>(),
874            [
875                ("edge_uuid", AlgorithmFieldType::Uuid, false),
876                ("source_uuid", AlgorithmFieldType::Uuid, false),
877                ("target_uuid", AlgorithmFieldType::Uuid, false),
878                ("capacity", AlgorithmFieldType::Float64, false),
879            ]
880        );
881        assert_ne!(scalar_schema, edge_schema);
882        assert!(scalar_schema.fields.iter().all(|field| {
883            !["node_id", "edge_id", "source_id", "sink_id", "target_id"].contains(&field.name)
884        }));
885        assert!(edge_schema.fields.iter().all(|field| {
886            !["node_id", "edge_id", "source_id", "sink_id", "target_id"].contains(&field.name)
887        }));
888    }
889
890    #[test]
891    fn euler_constructions_share_aligned_non_null_identity_schema() {
892        for algorithm in [AnalyzeAlgorithm::EulerCircuit, AnalyzeAlgorithm::EulerPath] {
893            assert_eq!(
894                Algorithm::Analyze(algorithm)
895                    .result_schema()
896                    .fields
897                    .iter()
898                    .map(|field| (field.name, field.data_type, field.nullable))
899                    .collect::<Vec<_>>(),
900                [
901                    ("node_path", AlgorithmFieldType::UuidList, false),
902                    ("edge_path", AlgorithmFieldType::UuidList, false),
903                ]
904            );
905        }
906    }
907
908    #[test]
909    fn steiner_algorithms_share_dedicated_non_null_weighted_edge_schema() {
910        let ordinary_edge_list =
911            Algorithm::Analyze(AnalyzeAlgorithm::MinimumSpanningTree).result_schema();
912        assert_eq!(
913            ordinary_edge_list
914                .fields
915                .iter()
916                .map(|field| (field.name, field.data_type, field.nullable))
917                .collect::<Vec<_>>(),
918            [
919                ("edge_uuid", AlgorithmFieldType::Uuid, false),
920                ("source_uuid", AlgorithmFieldType::Uuid, false),
921                ("target_uuid", AlgorithmFieldType::Uuid, false),
922                ("weight", AlgorithmFieldType::Float64, true),
923            ]
924        );
925        assert!(!ordinary_edge_list.includes_node_properties);
926        for algorithm in [
927            PathAlgorithm::MinSteinerTree,
928            PathAlgorithm::PrizeCollectingSteinerTree,
929        ] {
930            let steiner = Algorithm::Paths(algorithm).result_schema();
931            assert_eq!(
932                steiner
933                    .fields
934                    .iter()
935                    .map(|field| (field.name, field.data_type, field.nullable))
936                    .collect::<Vec<_>>(),
937                [
938                    ("edge_uuid", AlgorithmFieldType::Uuid, false),
939                    ("source_uuid", AlgorithmFieldType::Uuid, false),
940                    ("target_uuid", AlgorithmFieldType::Uuid, false),
941                    ("weight", AlgorithmFieldType::Float64, false),
942                ]
943            );
944            assert!(!steiner.includes_node_properties);
945            assert_ne!(steiner, ordinary_edge_list);
946        }
947    }
948}
graphforge_core/algorithms.rs

graphforge_core/
algorithms.rs
