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    BfsDepth => "bfs_depth",
194    DijkstraCost => "dijkstra_cost",
195});
196
197algorithm_enum!(AnalyzeAlgorithm, IsDag, AlgorithmVerb::Analyze, {
198    MinimumSpanningTree => "minimum_spanning_tree",
199    MaximumSpanningTree => "maximum_spanning_tree",
200    MinimumKSpanningTree => "minimum_k_spanning_tree",
201    TopologicalSort => "topological_sort",
202    IsDag => "is_dag",
203    FindCycles => "find_cycles",
204    DagLongestPath => "dag_longest_path",
205    DagLongestPathWeighted => "dag_longest_path_weighted",
206    NodeColoring => "node_coloring",
207    EdgeColoring => "edge_coloring",
208    ChromaticNumber => "chromatic_number",
209    K1Coloring => "k1_coloring",
210    MaxWeightMatching => "max_weight_matching",
211    MaxCardinalityMatching => "max_cardinality_matching",
212    MaxBipartiteMatching => "max_bipartite_matching",
213    EulerCircuit => "euler_circuit",
214    EulerPath => "euler_path",
215    HasEulerCircuit => "has_euler_circuit",
216    HasEulerPath => "has_euler_path",
217    IsPlanar => "is_planar",
218    ArticulationPoints => "articulation_points",
219    Bridges => "bridges",
220    TriangleCount => "triangle_count",
221    Conductance => "conductance",
222    Modularity => "modularity",
223    Transitivity => "transitivity",
224    TriadCensus => "triad_census",
225    DyadCensus => "dyad_census",
226    CountAutomorphisms => "count_automorphisms",
227    Node2Vec => "node2vec",
228    GraphSage => "graphsage",
229    FastRandomProjection => "fast_random_projection",
230    HashGnn => "hashgnn",
231});
232
233/// A typed algorithm from any analyst verb.
234#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
235pub enum Algorithm {
236    /// Rank algorithm.
237    Rank(RankAlgorithm),
238    /// Cluster algorithm.
239    Cluster(ClusterAlgorithm),
240    /// Similarity algorithm.
241    Similar(SimilarAlgorithm),
242    /// Path algorithm.
243    Paths(PathAlgorithm),
244    /// Analysis algorithm.
245    Analyze(AnalyzeAlgorithm),
246}
247
248/// Language-independent type in an algorithm result schema.
249#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
250pub enum AlgorithmFieldType {
251    /// Arrow `FixedSizeBinary(16)` public UUID identity.
252    Uuid,
253    /// Arrow `List<FixedSizeBinary(16)>` UUID sequence.
254    UuidList,
255    /// Arrow `List<Float32>` embedding.
256    Float32List,
257    /// Arrow `Utf8`.
258    Utf8,
259    /// Arrow `Boolean`.
260    Boolean,
261    /// Arrow `UInt64`.
262    UInt64,
263    /// Arrow `Int64`.
264    Int64,
265    /// Arrow `Float64`.
266    Float64,
267}
268
269/// Required field in a stable logical result schema.
270#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
271pub struct AlgorithmField {
272    /// Stable public column name.
273    pub name: &'static str,
274    /// Logical Arrow type.
275    pub data_type: AlgorithmFieldType,
276    /// Whether the field accepts nulls.
277    pub nullable: bool,
278}
279
280const fn field(
281    name: &'static str,
282    data_type: AlgorithmFieldType,
283    nullable: bool,
284) -> AlgorithmField {
285    AlgorithmField {
286        name,
287        data_type,
288        nullable,
289    }
290}
291
292/// Stable logical schema required from an algorithm implementation.
293#[derive(Debug, Clone, Copy, PartialEq, Eq)]
294pub struct AlgorithmResultSchema {
295    /// Required fields in public output order.
296    pub fields: &'static [AlgorithmField],
297    /// Node properties follow the required fields for node-oriented verbs.
298    pub includes_node_properties: bool,
299}
300
301const fn schema(fields: &'static [AlgorithmField]) -> AlgorithmResultSchema {
302    AlgorithmResultSchema {
303        fields,
304        includes_node_properties: false,
305    }
306}
307
308const fn node_schema(fields: &'static [AlgorithmField]) -> AlgorithmResultSchema {
309    AlgorithmResultSchema {
310        fields,
311        includes_node_properties: true,
312    }
313}
314
315const NODE_SCORE: &[AlgorithmField] = &[
316    field("node_uuid", AlgorithmFieldType::Uuid, false),
317    field("score", AlgorithmFieldType::Float64, false),
318];
319const NODE_COMMUNITY: &[AlgorithmField] = &[
320    field("node_uuid", AlgorithmFieldType::Uuid, false),
321    field("community_id", AlgorithmFieldType::Int64, false),
322];
323const SIMILARITY: &[AlgorithmField] = &[
324    field("node1_uuid", AlgorithmFieldType::Uuid, false),
325    field("node2_uuid", AlgorithmFieldType::Uuid, false),
326    field("similarity", AlgorithmFieldType::Float64, false),
327];
328const PATH: &[AlgorithmField] = &[
329    field("source_uuid", AlgorithmFieldType::Uuid, false),
330    field("target_uuid", AlgorithmFieldType::Uuid, false),
331    field("cost", AlgorithmFieldType::Float64, false),
332    field("path", AlgorithmFieldType::UuidList, false),
333];
334const PATH_COST: &[AlgorithmField] = &[
335    field("source_uuid", AlgorithmFieldType::Uuid, false),
336    field("target_uuid", AlgorithmFieldType::Uuid, false),
337    field("cost", AlgorithmFieldType::Float64, false),
338];
339const RANKED_PATH: &[AlgorithmField] = &[
340    field("source_uuid", AlgorithmFieldType::Uuid, false),
341    field("target_uuid", AlgorithmFieldType::Uuid, false),
342    field("rank", AlgorithmFieldType::UInt64, false),
343    field("cost", AlgorithmFieldType::Float64, false),
344    field("path", AlgorithmFieldType::UuidList, false),
345];
346const FLOW: &[AlgorithmField] = &[
347    field("source_uuid", AlgorithmFieldType::Uuid, false),
348    field("sink_uuid", AlgorithmFieldType::Uuid, false),
349    field("flow", AlgorithmFieldType::Float64, false),
350];
351const FLOW_EDGES: &[AlgorithmField] = &[
352    field("edge_uuid", AlgorithmFieldType::Uuid, false),
353    field("source_uuid", AlgorithmFieldType::Uuid, false),
354    field("target_uuid", AlgorithmFieldType::Uuid, false),
355    field("flow", AlgorithmFieldType::Float64, false),
356];
357const COSTED_FLOW: &[AlgorithmField] = &[
358    field("source_uuid", AlgorithmFieldType::Uuid, false),
359    field("sink_uuid", AlgorithmFieldType::Uuid, false),
360    field("flow", AlgorithmFieldType::Float64, false),
361    field("cost", AlgorithmFieldType::Float64, false),
362];
363const COSTED_FLOW_EDGES: &[AlgorithmField] = &[
364    field("edge_uuid", AlgorithmFieldType::Uuid, false),
365    field("source_uuid", AlgorithmFieldType::Uuid, false),
366    field("target_uuid", AlgorithmFieldType::Uuid, false),
367    field("flow", AlgorithmFieldType::Float64, false),
368    field("unit_cost", AlgorithmFieldType::Float64, false),
369    field("flow_cost", AlgorithmFieldType::Float64, false),
370];
371const MIN_CUT: &[AlgorithmField] = &[
372    field("source_uuid", AlgorithmFieldType::Uuid, false),
373    field("sink_uuid", AlgorithmFieldType::Uuid, false),
374    field("cut_value", AlgorithmFieldType::Float64, false),
375];
376const MIN_CUT_EDGES: &[AlgorithmField] = &[
377    field("edge_uuid", AlgorithmFieldType::Uuid, false),
378    field("source_uuid", AlgorithmFieldType::Uuid, false),
379    field("target_uuid", AlgorithmFieldType::Uuid, false),
380    field("capacity", AlgorithmFieldType::Float64, false),
381];
382const CUT: &[AlgorithmField] = &[
383    field("source_uuid", AlgorithmFieldType::Uuid, false),
384    field("target_uuid", AlgorithmFieldType::Uuid, false),
385    field("cut_value", AlgorithmFieldType::Float64, false),
386];
387const EDGE_LIST: &[AlgorithmField] = &[
388    field("edge_uuid", AlgorithmFieldType::Uuid, false),
389    field("source_uuid", AlgorithmFieldType::Uuid, false),
390    field("target_uuid", AlgorithmFieldType::Uuid, false),
391    field("weight", AlgorithmFieldType::Float64, true),
392];
393const STEINER_EDGE_LIST: &[AlgorithmField] = &[
394    field("edge_uuid", AlgorithmFieldType::Uuid, false),
395    field("source_uuid", AlgorithmFieldType::Uuid, false),
396    field("target_uuid", AlgorithmFieldType::Uuid, false),
397    field("weight", AlgorithmFieldType::Float64, false),
398];
399const UNWEIGHTED_EDGE_LIST: &[AlgorithmField] = &[
400    field("edge_uuid", AlgorithmFieldType::Uuid, false),
401    field("source_uuid", AlgorithmFieldType::Uuid, false),
402    field("target_uuid", AlgorithmFieldType::Uuid, false),
403];
404const K_EDGE_LIST: &[AlgorithmField] = &[
405    field("tree_id", AlgorithmFieldType::UInt64, false),
406    field("edge_uuid", AlgorithmFieldType::Uuid, false),
407    field("source_uuid", AlgorithmFieldType::Uuid, false),
408    field("target_uuid", AlgorithmFieldType::Uuid, false),
409    field("weight", AlgorithmFieldType::Float64, false),
410];
411const TRAVERSAL: &[AlgorithmField] = &[
412    field("node_uuid", AlgorithmFieldType::Uuid, false),
413    field("depth", AlgorithmFieldType::UInt64, false),
414    field("order", AlgorithmFieldType::UInt64, false),
415];
416const WALK: &[AlgorithmField] = &[
417    field("start_uuid", AlgorithmFieldType::Uuid, false),
418    field("walk", AlgorithmFieldType::UuidList, false),
419];
420const PAIR: &[AlgorithmField] = &[
421    field("source_uuid", AlgorithmFieldType::Uuid, false),
422    field("target_uuid", AlgorithmFieldType::Uuid, false),
423];
424const NODE_ORDER: &[AlgorithmField] = &[
425    field("node_uuid", AlgorithmFieldType::Uuid, false),
426    field("order", AlgorithmFieldType::UInt64, false),
427];
428const NODE: &[AlgorithmField] = &[field("node_uuid", AlgorithmFieldType::Uuid, false)];
429const NODE_COLOR: &[AlgorithmField] = &[
430    field("node_uuid", AlgorithmFieldType::Uuid, false),
431    field("color", AlgorithmFieldType::UInt64, false),
432];
433const EDGE_COLOR: &[AlgorithmField] = &[
434    field("edge_uuid", AlgorithmFieldType::Uuid, false),
435    field("color", AlgorithmFieldType::UInt64, false),
436];
437const EULER_TRAIL: &[AlgorithmField] = &[
438    field("node_path", AlgorithmFieldType::UuidList, false),
439    field("edge_path", AlgorithmFieldType::UuidList, false),
440];
441const CYCLE: &[AlgorithmField] = &[field("cycle", AlgorithmFieldType::UuidList, false)];
442const COST_PATH: &[AlgorithmField] = &[
443    field("cost", AlgorithmFieldType::Float64, false),
444    field("path", AlgorithmFieldType::UuidList, false),
445];
446const IS_DAG: &[AlgorithmField] = &[field("is_dag", AlgorithmFieldType::Boolean, false)];
447const HAS_EULER_CIRCUIT: &[AlgorithmField] = &[field(
448    "has_euler_circuit",
449    AlgorithmFieldType::Boolean,
450    false,
451)];
452const HAS_EULER_PATH: &[AlgorithmField] =
453    &[field("has_euler_path", AlgorithmFieldType::Boolean, false)];
454const IS_PLANAR: &[AlgorithmField] = &[field("is_planar", AlgorithmFieldType::Boolean, false)];
455const CHROMATIC_NUMBER: &[AlgorithmField] =
456    &[field("chromatic_number", AlgorithmFieldType::UInt64, false)];
457const TRIANGLE_COUNT: &[AlgorithmField] =
458    &[field("triangle_count", AlgorithmFieldType::UInt64, false)];
459const AUTOMORPHISM_COUNT: &[AlgorithmField] = &[field("count", AlgorithmFieldType::UInt64, false)];
460const CONDUCTANCE: &[AlgorithmField] = &[
461    field("partition_id", AlgorithmFieldType::Utf8, false),
462    field("conductance", AlgorithmFieldType::Float64, false),
463];
464const MODULARITY: &[AlgorithmField] = &[field("modularity", AlgorithmFieldType::Float64, false)];
465const TRANSITIVITY: &[AlgorithmField] =
466    &[field("transitivity", AlgorithmFieldType::Float64, false)];
467const TRIAD_CENSUS: &[AlgorithmField] = &[
468    field("triad_type", AlgorithmFieldType::Utf8, false),
469    field("count", AlgorithmFieldType::UInt64, false),
470];
471const DYAD_CENSUS: &[AlgorithmField] = &[
472    field("dyad_type", AlgorithmFieldType::Utf8, false),
473    field("count", AlgorithmFieldType::UInt64, false),
474];
475const EMBEDDING: &[AlgorithmField] = &[
476    field("node_uuid", AlgorithmFieldType::Uuid, false),
477    field("embedding", AlgorithmFieldType::Float32List, false),
478];
479
480impl Algorithm {
481    /// Parse a public `by=` value in the namespace of its verb.
482    pub fn parse(verb: AlgorithmVerb, value: &str) -> Result<Self, GfError> {
483        match verb {
484            AlgorithmVerb::Rank => value.parse().map(Self::Rank),
485            AlgorithmVerb::Cluster => value.parse().map(Self::Cluster),
486            AlgorithmVerb::Similar => value.parse().map(Self::Similar),
487            AlgorithmVerb::Paths => value.parse().map(Self::Paths),
488            AlgorithmVerb::Analyze => value.parse().map(Self::Analyze),
489        }
490    }
491
492    /// Owning public verb.
493    #[must_use]
494    pub const fn verb(self) -> AlgorithmVerb {
495        match self {
496            Self::Rank(_) => AlgorithmVerb::Rank,
497            Self::Cluster(_) => AlgorithmVerb::Cluster,
498            Self::Similar(_) => AlgorithmVerb::Similar,
499            Self::Paths(_) => AlgorithmVerb::Paths,
500            Self::Analyze(_) => AlgorithmVerb::Analyze,
501        }
502    }
503
504    /// Canonical public `by=` value.
505    #[must_use]
506    pub const fn as_str(self) -> &'static str {
507        match self {
508            Self::Rank(value) => value.as_str(),
509            Self::Cluster(value) => value.as_str(),
510            Self::Similar(value) => value.as_str(),
511            Self::Paths(value) => value.as_str(),
512            Self::Analyze(value) => value.as_str(),
513        }
514    }
515
516    /// Stable logical result schema required from every language surface.
517    #[must_use]
518    pub const fn result_schema(self) -> AlgorithmResultSchema {
519        match self {
520            Self::Rank(_) => node_schema(NODE_SCORE),
521            Self::Cluster(_) => node_schema(NODE_COMMUNITY),
522            Self::Similar(_) => schema(SIMILARITY),
523            Self::Paths(value) => path_schema(value),
524            Self::Analyze(value) => analyze_schema(value),
525        }
526    }
527}
528
529const fn path_schema(value: PathAlgorithm) -> AlgorithmResultSchema {
530    match value {
531        PathAlgorithm::Yens => schema(RANKED_PATH),
532        PathAlgorithm::MaxFlow => schema(FLOW),
533        PathAlgorithm::MaxFlowEdges => schema(FLOW_EDGES),
534        PathAlgorithm::MinCut => schema(MIN_CUT),
535        PathAlgorithm::MinCutEdges => schema(MIN_CUT_EDGES),
536        PathAlgorithm::MinCostMaxFlow => schema(COSTED_FLOW),
537        PathAlgorithm::MinCostMaxFlowEdges => schema(COSTED_FLOW_EDGES),
538        PathAlgorithm::GomoryHuTree => schema(CUT),
539        PathAlgorithm::MinSteinerTree | PathAlgorithm::PrizeCollectingSteinerTree => {
540            schema(STEINER_EDGE_LIST)
541        }
542        PathAlgorithm::Dfs => schema(TRAVERSAL),
543        PathAlgorithm::RandomWalk => schema(WALK),
544        PathAlgorithm::TransitiveClosure => schema(PAIR),
545        PathAlgorithm::BfsDepth | PathAlgorithm::DijkstraCost => schema(PATH_COST),
546        _ => schema(PATH),
547    }
548}
549
550const fn analyze_schema(value: AnalyzeAlgorithm) -> AlgorithmResultSchema {
551    match value {
552        AnalyzeAlgorithm::MinimumKSpanningTree => schema(K_EDGE_LIST),
553        AnalyzeAlgorithm::MinimumSpanningTree
554        | AnalyzeAlgorithm::MaximumSpanningTree
555        | AnalyzeAlgorithm::MaxWeightMatching => schema(EDGE_LIST),
556        AnalyzeAlgorithm::MaxCardinalityMatching
557        | AnalyzeAlgorithm::MaxBipartiteMatching
558        | AnalyzeAlgorithm::Bridges => schema(UNWEIGHTED_EDGE_LIST),
559        AnalyzeAlgorithm::TopologicalSort => schema(NODE_ORDER),
560        AnalyzeAlgorithm::ArticulationPoints => schema(NODE),
561        AnalyzeAlgorithm::IsDag => schema(IS_DAG),
562        AnalyzeAlgorithm::FindCycles => schema(CYCLE),
563        AnalyzeAlgorithm::DagLongestPath | AnalyzeAlgorithm::DagLongestPathWeighted => {
564            schema(COST_PATH)
565        }
566        AnalyzeAlgorithm::NodeColoring | AnalyzeAlgorithm::K1Coloring => schema(NODE_COLOR),
567        AnalyzeAlgorithm::EdgeColoring => schema(EDGE_COLOR),
568        AnalyzeAlgorithm::ChromaticNumber => schema(CHROMATIC_NUMBER),
569        AnalyzeAlgorithm::EulerCircuit | AnalyzeAlgorithm::EulerPath => schema(EULER_TRAIL),
570        AnalyzeAlgorithm::HasEulerCircuit => schema(HAS_EULER_CIRCUIT),
571        AnalyzeAlgorithm::HasEulerPath => schema(HAS_EULER_PATH),
572        AnalyzeAlgorithm::IsPlanar => schema(IS_PLANAR),
573        AnalyzeAlgorithm::TriangleCount => schema(TRIANGLE_COUNT),
574        AnalyzeAlgorithm::Conductance => schema(CONDUCTANCE),
575        AnalyzeAlgorithm::Modularity => schema(MODULARITY),
576        AnalyzeAlgorithm::Transitivity => schema(TRANSITIVITY),
577        AnalyzeAlgorithm::TriadCensus => schema(TRIAD_CENSUS),
578        AnalyzeAlgorithm::DyadCensus => schema(DYAD_CENSUS),
579        AnalyzeAlgorithm::CountAutomorphisms => schema(AUTOMORPHISM_COUNT),
580        AnalyzeAlgorithm::Node2Vec
581        | AnalyzeAlgorithm::GraphSage
582        | AnalyzeAlgorithm::FastRandomProjection
583        | AnalyzeAlgorithm::HashGnn => schema(EMBEDDING),
584    }
585}
586
587fn unknown_algorithm(verb: AlgorithmVerb, value: &str) -> GfError {
588    GfError::Validation(format!(
589        "unknown {} algorithm `{value}`; use a catalogued `by=` value",
590        verb.as_str()
591    ))
592}
593
594#[cfg(test)]
595mod tests {
596    use std::collections::HashSet;
597
598    use super::*;
599
600    #[test]
601    fn every_catalog_is_unique_and_round_trips() {
602        let rank = RankAlgorithm::ALL
603            .iter()
604            .map(|value| value.as_str())
605            .collect::<Vec<_>>();
606        let cluster = ClusterAlgorithm::ALL
607            .iter()
608            .map(|value| value.as_str())
609            .collect::<Vec<_>>();
610        let similar = SimilarAlgorithm::ALL
611            .iter()
612            .map(|value| value.as_str())
613            .collect::<Vec<_>>();
614        let paths = PathAlgorithm::ALL
615            .iter()
616            .map(|value| value.as_str())
617            .collect::<Vec<_>>();
618        let analyze = AnalyzeAlgorithm::ALL
619            .iter()
620            .map(|value| value.as_str())
621            .collect::<Vec<_>>();
622        let catalogs: &[(&[&str], AlgorithmVerb)] = &[
623            (&rank, AlgorithmVerb::Rank),
624            (&cluster, AlgorithmVerb::Cluster),
625            (&similar, AlgorithmVerb::Similar),
626            (&paths, AlgorithmVerb::Paths),
627            (&analyze, AlgorithmVerb::Analyze),
628        ];
629
630        for (names, verb) in catalogs {
631            let unique: HashSet<_> = names.iter().copied().collect();
632            assert_eq!(unique.len(), names.len(), "duplicate in {}", verb.as_str());
633            for name in *names {
634                let parsed = Algorithm::parse(*verb, name).expect("catalog entry must parse");
635                assert_eq!(parsed.as_str(), *name);
636                assert_eq!(parsed.verb(), *verb);
637                assert!(!parsed.result_schema().fields.is_empty());
638            }
639        }
640    }
641
642    #[test]
643    fn concrete_catalog_accessors_display_and_direction_policy_are_total() {
644        for value in RankAlgorithm::ALL {
645            assert_eq!(value.verb(), AlgorithmVerb::Rank);
646            assert_eq!(value.to_string(), value.as_str());
647        }
648        for value in SimilarAlgorithm::ALL {
649            assert_eq!(value.verb(), AlgorithmVerb::Similar);
650            assert_eq!(value.to_string(), value.as_str());
651        }
652        for value in PathAlgorithm::ALL {
653            assert_eq!(value.verb(), AlgorithmVerb::Paths);
654            assert_eq!(value.to_string(), value.as_str());
655        }
656        for value in AnalyzeAlgorithm::ALL {
657            assert_eq!(value.verb(), AlgorithmVerb::Analyze);
658            assert_eq!(value.to_string(), value.as_str());
659        }
660        for value in ClusterAlgorithm::ALL {
661            assert_eq!(value.verb(), AlgorithmVerb::Cluster);
662            assert_eq!(value.to_string(), value.as_str());
663        }
664        assert!(ClusterAlgorithm::InfoMap.respects_direction());
665        assert!(ClusterAlgorithm::StronglyConnected.respects_direction());
666        assert!(!ClusterAlgorithm::Louvain.respects_direction());
667        assert!(!ClusterAlgorithm::Hdbscan.respects_direction());
668    }
669
670    #[test]
671    fn rank_alias_has_one_canonical_owner() {
672        let alias: RankAlgorithm = "local_clustering_coefficient".parse().unwrap();
673        assert_eq!(alias, RankAlgorithm::ClusteringCoefficient);
674        assert_eq!(alias.as_str(), "clustering_coefficient");
675        assert!(
676            !RankAlgorithm::ALL
677                .iter()
678                .any(|value| value.as_str() == "local_clustering_coefficient")
679        );
680    }
681
682    #[test]
683    fn invalid_name_is_a_stable_validation_error() {
684        let error = Algorithm::parse(AlgorithmVerb::Similar, "pagerank").unwrap_err();
685        assert!(matches!(error, GfError::Validation(_)));
686        assert_eq!(
687            error.to_string(),
688            "validation error: unknown similar algorithm `pagerank`; use a catalogued `by=` value"
689        );
690    }
691
692    #[test]
693    fn vertical_proof_schemas_are_stable_and_uuid_only() {
694        let cases = [
695            (
696                Algorithm::Rank(RankAlgorithm::Degree),
697                &["node_uuid", "score"][..],
698            ),
699            (
700                Algorithm::Cluster(ClusterAlgorithm::Components),
701                &["node_uuid", "community_id"],
702            ),
703            (
704                Algorithm::Similar(SimilarAlgorithm::NodeSimilarity),
705                &["node1_uuid", "node2_uuid", "similarity"],
706            ),
707            (
708                Algorithm::Paths(PathAlgorithm::Bfs),
709                &["source_uuid", "target_uuid", "cost", "path"],
710            ),
711            (Algorithm::Analyze(AnalyzeAlgorithm::IsDag), &["is_dag"]),
712        ];
713        for (algorithm, names) in cases {
714            let fields = algorithm.result_schema().fields;
715            assert_eq!(
716                fields.iter().map(|field| field.name).collect::<Vec<_>>(),
717                names
718            );
719            assert!(fields.iter().all(|field| {
720                ![
721                    "node_id",
722                    "edge_id",
723                    "src_id",
724                    "dst_id",
725                    "source_id",
726                    "target_id",
727                ]
728                .contains(&field.name)
729            }));
730        }
731    }
732
733    #[test]
734    fn max_cardinality_matching_has_an_unweighted_edge_schema() {
735        let fields = Algorithm::Analyze(AnalyzeAlgorithm::MaxCardinalityMatching)
736            .result_schema()
737            .fields;
738
739        assert_eq!(
740            fields
741                .iter()
742                .map(|field| (field.name, field.data_type, field.nullable))
743                .collect::<Vec<_>>(),
744            [
745                ("edge_uuid", AlgorithmFieldType::Uuid, false),
746                ("source_uuid", AlgorithmFieldType::Uuid, false),
747                ("target_uuid", AlgorithmFieldType::Uuid, false),
748            ]
749        );
750    }
751
752    #[test]
753    fn max_bipartite_matching_has_an_unweighted_edge_schema() {
754        let fields = Algorithm::Analyze(AnalyzeAlgorithm::MaxBipartiteMatching)
755            .result_schema()
756            .fields;
757
758        assert_eq!(
759            fields
760                .iter()
761                .map(|field| (field.name, field.data_type, field.nullable))
762                .collect::<Vec<_>>(),
763            [
764                ("edge_uuid", AlgorithmFieldType::Uuid, false),
765                ("source_uuid", AlgorithmFieldType::Uuid, false),
766                ("target_uuid", AlgorithmFieldType::Uuid, false),
767            ]
768        );
769    }
770
771    #[test]
772    fn max_flow_catalog_values_have_separate_stable_schemas() {
773        let scalar: PathAlgorithm = "max_flow".parse().unwrap();
774        let edges: PathAlgorithm = "max_flow_edges".parse().unwrap();
775
776        assert_eq!(scalar, PathAlgorithm::MaxFlow);
777        assert_eq!(scalar.as_str(), "max_flow");
778        assert_eq!(edges, PathAlgorithm::MaxFlowEdges);
779        assert_eq!(edges.as_str(), "max_flow_edges");
780        assert_eq!(
781            Algorithm::Paths(scalar)
782                .result_schema()
783                .fields
784                .iter()
785                .map(|field| (field.name, field.data_type, field.nullable))
786                .collect::<Vec<_>>(),
787            [
788                ("source_uuid", AlgorithmFieldType::Uuid, false),
789                ("sink_uuid", AlgorithmFieldType::Uuid, false),
790                ("flow", AlgorithmFieldType::Float64, false),
791            ]
792        );
793        assert_eq!(
794            Algorithm::Paths(edges)
795                .result_schema()
796                .fields
797                .iter()
798                .map(|field| (field.name, field.data_type, field.nullable))
799                .collect::<Vec<_>>(),
800            [
801                ("edge_uuid", AlgorithmFieldType::Uuid, false),
802                ("source_uuid", AlgorithmFieldType::Uuid, false),
803                ("target_uuid", AlgorithmFieldType::Uuid, false),
804                ("flow", AlgorithmFieldType::Float64, false),
805            ]
806        );
807    }
808
809    #[test]
810    fn min_cost_flow_catalog_values_have_separate_stable_schemas() {
811        let scalar: PathAlgorithm = "min_cost_max_flow".parse().unwrap();
812        let edges: PathAlgorithm = "min_cost_max_flow_edges".parse().unwrap();
813        assert_eq!(scalar, PathAlgorithm::MinCostMaxFlow);
814        assert_eq!(edges, PathAlgorithm::MinCostMaxFlowEdges);
815        assert_eq!(
816            Algorithm::Paths(scalar)
817                .result_schema()
818                .fields
819                .iter()
820                .map(|field| field.name)
821                .collect::<Vec<_>>(),
822            ["source_uuid", "sink_uuid", "flow", "cost"]
823        );
824        assert_eq!(
825            Algorithm::Paths(edges)
826                .result_schema()
827                .fields
828                .iter()
829                .map(|field| field.name)
830                .collect::<Vec<_>>(),
831            [
832                "edge_uuid",
833                "source_uuid",
834                "target_uuid",
835                "flow",
836                "unit_cost",
837                "flow_cost",
838            ]
839        );
840        assert!(
841            Algorithm::Paths(edges)
842                .result_schema()
843                .fields
844                .iter()
845                .all(|field| !field.nullable)
846        );
847    }
848
849    #[test]
850    fn min_cut_catalog_values_have_distinct_stable_uuid_schemas() {
851        let scalar: PathAlgorithm = "min_cut".parse().unwrap();
852        let edges: PathAlgorithm = "min_cut_edges".parse().unwrap();
853
854        assert_eq!(scalar, PathAlgorithm::MinCut);
855        assert_eq!(scalar.as_str(), "min_cut");
856        assert_eq!(scalar.to_string(), "min_cut");
857        assert_eq!(edges, PathAlgorithm::MinCutEdges);
858        assert_eq!(edges.as_str(), "min_cut_edges");
859        assert_eq!(edges.to_string(), "min_cut_edges");
860
861        let scalar_schema = Algorithm::Paths(scalar).result_schema();
862        assert_eq!(
863            scalar_schema
864                .fields
865                .iter()
866                .map(|field| (field.name, field.data_type, field.nullable))
867                .collect::<Vec<_>>(),
868            [
869                ("source_uuid", AlgorithmFieldType::Uuid, false),
870                ("sink_uuid", AlgorithmFieldType::Uuid, false),
871                ("cut_value", AlgorithmFieldType::Float64, false),
872            ]
873        );
874
875        let edge_schema = Algorithm::Paths(edges).result_schema();
876        assert_eq!(
877            edge_schema
878                .fields
879                .iter()
880                .map(|field| (field.name, field.data_type, field.nullable))
881                .collect::<Vec<_>>(),
882            [
883                ("edge_uuid", AlgorithmFieldType::Uuid, false),
884                ("source_uuid", AlgorithmFieldType::Uuid, false),
885                ("target_uuid", AlgorithmFieldType::Uuid, false),
886                ("capacity", AlgorithmFieldType::Float64, false),
887            ]
888        );
889        assert_ne!(scalar_schema, edge_schema);
890        assert!(scalar_schema.fields.iter().all(|field| {
891            !["node_id", "edge_id", "source_id", "sink_id", "target_id"].contains(&field.name)
892        }));
893        assert!(edge_schema.fields.iter().all(|field| {
894            !["node_id", "edge_id", "source_id", "sink_id", "target_id"].contains(&field.name)
895        }));
896    }
897
898    #[test]
899    fn euler_constructions_share_aligned_non_null_identity_schema() {
900        for algorithm in [AnalyzeAlgorithm::EulerCircuit, AnalyzeAlgorithm::EulerPath] {
901            assert_eq!(
902                Algorithm::Analyze(algorithm)
903                    .result_schema()
904                    .fields
905                    .iter()
906                    .map(|field| (field.name, field.data_type, field.nullable))
907                    .collect::<Vec<_>>(),
908                [
909                    ("node_path", AlgorithmFieldType::UuidList, false),
910                    ("edge_path", AlgorithmFieldType::UuidList, false),
911                ]
912            );
913        }
914    }
915
916    #[test]
917    fn steiner_algorithms_share_dedicated_non_null_weighted_edge_schema() {
918        let ordinary_edge_list =
919            Algorithm::Analyze(AnalyzeAlgorithm::MinimumSpanningTree).result_schema();
920        assert_eq!(
921            ordinary_edge_list
922                .fields
923                .iter()
924                .map(|field| (field.name, field.data_type, field.nullable))
925                .collect::<Vec<_>>(),
926            [
927                ("edge_uuid", AlgorithmFieldType::Uuid, false),
928                ("source_uuid", AlgorithmFieldType::Uuid, false),
929                ("target_uuid", AlgorithmFieldType::Uuid, false),
930                ("weight", AlgorithmFieldType::Float64, true),
931            ]
932        );
933        assert!(!ordinary_edge_list.includes_node_properties);
934        for algorithm in [
935            PathAlgorithm::MinSteinerTree,
936            PathAlgorithm::PrizeCollectingSteinerTree,
937        ] {
938            let steiner = Algorithm::Paths(algorithm).result_schema();
939            assert_eq!(
940                steiner
941                    .fields
942                    .iter()
943                    .map(|field| (field.name, field.data_type, field.nullable))
944                    .collect::<Vec<_>>(),
945                [
946                    ("edge_uuid", AlgorithmFieldType::Uuid, false),
947                    ("source_uuid", AlgorithmFieldType::Uuid, false),
948                    ("target_uuid", AlgorithmFieldType::Uuid, false),
949                    ("weight", AlgorithmFieldType::Float64, false),
950                ]
951            );
952            assert!(!steiner.includes_node_properties);
953            assert_ne!(steiner, ordinary_edge_list);
954        }
955    }
956}
graphforge_core/algorithms.rs

graphforge_core/
algorithms.rs
