Expand description
§Geometric traits
Rust crate providing algebraic and graph algorithms, and basic structs, designed with a trait-first, correctness-focused approach. It supports no_std environments and offers optional alloc support for algorithms requiring dynamic memory allocation. See CONTRIBUTING.md for the design philosophy and how to contribute.
§Available Algorithms
The table below lists the main algorithm entrypoints currently exported from geometric_traits::traits::algorithms. All listed algorithms require the alloc feature. RandomizedDAG additionally requires either std or hashbrown. Full citations live in the API docs, and the fuzz harnesses are under fuzz/fuzz_targets.
| Algorithm | Trait | Complexity | Reference |
|---|---|---|---|
| Bipartite Maximum Matching | HopcroftKarp | O(E√V) | Hopcroft & Karp (1973) |
| General Maximum Matching | Blossom | O(V²E) | Edmonds (1965) |
| General Min-Cost Perfect Matching | BlossomV | O(V²E) believed | Kolmogorov (2009) |
| General Maximum Matching | Gabow1976 | O(V³) | Gabow (1976) |
| General Maximum Matching | MicaliVazirani | O(E√V) | Micali & Vazirani (1980) |
| Linear Assignment (Dense LAPJV) | LAPJV | O(n³) | Jonker & Volgenant (1987) |
| Linear Assignment (Sparse + Padding) | SparseLAPJV | O(n³) | Jonker & Volgenant (1987) |
| Linear Assignment (Sparse Core) | LAPMOD | O(n³) | Volgenant (1996) |
| Rectangular Assignment (Diagonal Cost Extension) | Jaqaman | O((L+R)³) | Jaqaman et al. (2008) |
| Rectangular Assignment (Crouse LAPJV) | Crouse | O(min(n,m)²·max(n,m)) | Crouse (2016) |
| Topological Sorting | Kahn | O(V+E) | Kahn (1962) |
| Elementary Circuit Enumeration | Johnson | O((V+E)(C+1)) | Johnson (1975) |
| All-Pairs Shortest Paths (Weighted) | FloydWarshall | O(V³) | Floyd (1962), Warshall (1962) |
| All-Pairs Shortest Paths (Non-Negative Weighted) | PairwiseDijkstra | O(V·(V+E)·log V) | Dijkstra (1959) |
| All-Pairs Shortest Paths (Unweighted) | PairwiseBFS | O(V·(V+E)) | Moore (1959) |
| Diameter (Exact, Undirected Unweighted) | Diameter | worst-case O(V·(V+E)) | Crescenzi et al. (2013) |
| Strongly Connected Components | Tarjan | O(V+E) | Tarjan (1972) |
| Maximum s-t Flow / Minimum Cut | Dinic | O(V²E) | Dinitz (1970) |
| Maximum s-t Flow / Minimum Cut | EdmondsKarp | O(VE²) | Edmonds & Karp (1972) |
| Feedback Arc Set (Greedy Heuristic) | EadesLinSmyth | O(V+E+cV), c = tangled-core size | Eades, Lin & Smyth (1993) |
| Biconnected Components / Articulation Points / Bridges | BiconnectedComponents | O(V+E) | Hopcroft & Tarjan (1973) |
| Cycle Detection (DFS) | CycleDetection | O(V+E) | DFS back-edge detection |
| Connected Components (Undirected) | ConnectedComponents | O(V+E) | Linear-time graph traversal |
| Minimum Spanning Forest (Kruskal) | Kruskal | O(E log E) | Kruskal (1956) |
| Minimum Spanning Forest (Prim) | Prim | O(E log V) | Prim (1957) |
| Minimum Spanning Forest (Boruvka) | Boruvka | O(E log V) | Borůvka (1926), transl. Nešetřil et al. (2001) |
| Bipartite Detection / 2-Coloring | BipartiteDetection | O(V+E) | BFS 2-coloring |
| Tree / Forest Detection | TreeDetection | O(V+E) | Component and edge-count predicates |
| Planarity Testing / Embedding | PlanarityDetection | O(V+E) | Boyer & Myrvold (2004) |
| Outerplanarity Testing | OuterplanarityDetection | O(V+E) | Boyer (2012) |
| K_{2,3} Homeomorph Detection | K23HomeomorphDetection | O(V+E) | Boyer (2012) |
| K_{3,3} Homeomorph Detection | K33HomeomorphDetection | O(V+E) | Boyer (2012) |
| Canonical Labeling (Labeled Simple Graphs) | CanonicalLabeling | worst-case exponential backtracking | Junttila & Kaski (2007) |
| Subgraph Isomorphism | Vf2 | worst-case exponential backtracking | Cordella et al. (2004) |
| Community Detection | Louvain | O(V+E) per level | Blondel et al. (2008) |
| Community Detection | Leiden | O(L·E), L = iterations | Traag et al. (2019) |
| Root Node Extraction | RootNodes | O(V+E) | Graph primitive |
| Sink Node Extraction | SinkNodes | O(V+E) | Graph primitive |
| Singleton Node Extraction | SingletonNodes | O(V+E) | Graph primitive |
| Simple Path Detection | SimplePath | O(V+E) | Graph property check |
| Information Content Propagation | InformationContent | O(V+E) | Resnik (1995) |
| Resnik Semantic Similarity | Resnik | O(R·(V+E)) per query | Resnik (1995) |
| Lin Semantic Similarity | Lin | O(R·(V+E)) per query | Lin (1998) |
| Wu-Palmer Semantic Similarity | WuPalmer | O(V+E) per query | Wu & Palmer (1994) |
| Line Graph | LineGraph | O(∑deg²) | Whitney (1932) |
| Labeled Line Graph | LabeledLineGraph | O(∑deg²) | Labeled variant for MCES / RASCAL |
| Modular Product | ModularProduct | O(|P|²) | Barrow & Burstall (1976) |
| Maximum Clique Enumeration | MaximumClique | O(3^(n/3)) worst case | Tomita & Seki (2003); Prosser (2012) |
| Delta-Y Exchange Detection | DeltaYExchange | O(V+E) | Delta-Y / Y-Delta detector for MCES filtering |
| Balanced Network Flow | Kocay | O(K·(V+E)) | Kocay & Stone (1995) |
| Minimum-Cost Maximum Balanced Flow | MinimumCostBalancedFlow | hybrid exact (tree DP, bipartite min-cost flow, Blossom-V fallback) | Kocay & Stone (1995); Kolmogorov (2009) |
| Stationary Distribution (Dense GTH) | Gth | O(n³) | Grassmann et al. (1985) |
| Eigenvalue Decomposition | Jacobi | O(n³) | Jacobi (1846) |
| Classical MDS | ClassicalMds | O(n³) | Torgerson (1952) |
| Force-Directed Layout | ForceAtlas2 | O(I·(V²+E)) exact, O(I·(V log V+E)) Barnes-Hut | Jacomy et al. (2014) |
| Fast-Multipole Multilevel Layout (TMAP) | Fmme | O(L·I·(V log V + E)), L = coarsening levels | Probst & Reymond (2020) |
| Random DAG Generation | RandomizedDAG | O(V² log V) | Utility generator (needs std or hashbrown) |
CanonicalLabeling returns a canonical order, a certificate and search statistics. Setting CanonicalLabelingOptions::collect_automorphism_generators to true also returns generators of the full label-preserving automorphism group, where generator[v] is the image of original dense vertex v. The generator vector is empty when collection is disabled or the graph is asymmetric, excludes the identity and need not be minimal.
PermutationGroup computes with such generators without enumerating the group. It builds a stabilizer chain by deterministic Schreier–Sims (Sims, 1970) and answers order, contains and orbit, and smallest_image returns the lexicographically smallest image of a set together with a group element reaching it, by a backtrack over the chain after Linton (2004) that is exponential only in the worst case.
§Node Ordering Primitives
The crate also exports reusable graph-level node ordering and node scoring building blocks from geometric_traits::traits::algorithms.
| Primitive | Kind | Complexity | Reference |
|---|---|---|---|
| DegeneracySorter | smallest-last node ordering | O(V+E) | Matula & Beck (1983) |
| LayeredLabelPropagationSorter | multiresolution node ordering | O(|Γ| · U · (V+E) + |Γ|² · V log V) | Boldi et al. (2011) |
| CoreNumberScorer | k-core / shell score | O(V+E) | Batagelj & Zaveršnik (2003) |
| DegreeScorer | node score | O(V+E) | Graph primitive |
| SecondOrderDegreeScorer | node score | O(V+E) | Degree-of-neighbors score |
| TriangleCountScorer | node score | O(|V̂| · d_cover²) | Exact triangle count |
| SquareCountScorer | node score | O(|V̂| · d_cover² · d_graph) | Exact 4-cycle count |
| LocalClusteringCoefficientScorer | node score | O(|V̂| · d_cover² + V+E) | Matches NetworkX clustering() |
| SquareClusteringCoefficientScorer | node score | O(V · d_graph³) | Matches NetworkX square_clustering() |
| PageRankScorer | centrality score | O(iterations · (V+E)) | Brin & Page (1998); NetworkX-aligned |
| PowerIterationEigenvectorCentralityScorer | centrality score | O(iterations · (V+E)) | Shifted power iteration; NetworkX-aligned |
| KatzCentralityScorer | centrality score | O(iterations · (V+E)) | Katz (1953); NetworkX-aligned |
| BetweennessCentralityScorer | centrality score | O(V · (V+E)) | Brandes (2001) |
| ClosenessCentralityScorer | centrality score | O(V · (V+E)) | Freeman (1979) |
| DescendingLexicographicScoreSorter | two-key node ordering | O(V log V) plus scorer cost | Lexicographic two-key sorter |
§Undirected Graph Generators
Standalone functions for generating undirected graphs, all returning SymmetricCSR2D<CSR2D<usize, usize, usize>>. All require the alloc feature. Random generators additionally take a seed: u64 parameter.
§Deterministic Generators
| Generator | Function | Parameters |
|---|---|---|
| Complete Graph K_n | complete_graph(n) | n = vertices |
| Cycle C_n | cycle_graph(n) | n = vertices |
| Path P_n | path_graph(n) | n = vertices |
| Star S_n | star_graph(n) | n = leaves |
| Grid G_{r×c} | grid_graph(rows, cols) | rows, cols |
| Hexagonal / Honeycomb Lattice | hexagonal_lattice_graph(rows, cols) | rows, cols = hexagon rows, cols |
| Triangular Lattice | triangular_lattice_graph(rows, cols) | rows, cols = vertex-grid rows, cols |
| Torus T_{r×c} | torus_graph(rows, cols) | rows, cols |
| Hypercube Q_d | hypercube_graph(d) | d = dimension |
| Barbell B(k, p) | barbell_graph(clique_size, path_len) | clique_size, path_len |
| Crown Cr_n | crown_graph(n) | n = vertices per side |
| Wheel W_n | wheel_graph(n) | n = rim vertices |
| Complete Bipartite K_{m,n} | complete_bipartite_graph(m, n) | m, n = partition sizes |
| Petersen | petersen_graph() | - |
| Turán T(n, r) | turan_graph(n, r) | n = vertices, r = partitions |
| Windmill Wd(k, n) | windmill_graph(num_cliques, clique_size) | num_cliques, clique_size |
| Friendship F_n | friendship_graph(n) | n = triangles = windmill_graph(n, 3) |
§Random Generators
Random generators require std or hashbrown in addition to alloc when they use a HashSet internally.
| Generator | Function | Parameters | Reference |
|---|---|---|---|
| Erdős-Rényi G(n, m) | erdos_renyi_gnm(seed, n, m) | n = vertices, m = edges | Erdős & Rényi (1959) |
| Erdős-Rényi G(n, p) | erdos_renyi_gnp(seed, n, p) | n = vertices, p = edge probability | Gilbert (1959); geometric skip: Batagelj & Brandes (2005) |
| Barabási-Albert | barabasi_albert(seed, n, m) | n = vertices, m = edges/step; initial clique size = m + 1 | Barabási & Albert (1999) |
| Watts-Strogatz | watts_strogatz(seed, n, k, beta) | n = vertices, k = neighbours, β = rewiring prob. | Watts & Strogatz (1998) |
| Random Regular | random_regular_graph(seed, n, k) -> Result<_, _> | n = vertices, k = degree | Configuration model; Wormald (1999) |
| Stochastic Block Model | stochastic_block_model(seed, sizes, p_intra, p_inter) | community sizes, within-community p, between-community p | Holland, Laskey & Leinhardt (1983) |
| Configuration Model | configuration_model(seed, degrees) | degree sequence | Molloy & Reed (1995) |
| Chung-Lu | chung_lu(seed, weights) | weight vector | Chung & Lu (2002) |
| Random Geometric | random_geometric_graph(seed, n, radius) | n = vertices, r = connection radius | Gilbert (1961); Penrose (2003) |
§Graph & Set Similarity Metrics
Standalone free functions and a GraphSimilarities trait for comparing graphs or sets by their overlap. The trait provides edge-based, vertex-based, and combined similarity methods via default implementations. Any type that reports matched counts and graph sizes gets all metrics for free. These do not require the alloc feature.
| Metric | Function | Formula | Range | Reference |
|---|---|---|---|---|
| Jaccard / Tanimoto | tanimoto_similarity | |A∩B| / |A∪B| | [0, 1] | Jaccard (1901) |
| Dice / Sorensen | dice_similarity | 2|A∩B| / (|A|+|B|) | [0, 1] | Dice (1945); Sørensen (1948) |
| Overlap / Szymkiewicz-Simpson | overlap_similarity | |A∩B| / min(|A|,|B|) | [0, 1] | Szymkiewicz (1934); Simpson (1943) |
| Cosine | cosine_similarity | |A∩B| / sqrt(|A||B|) | [0, 1] | Salton & McGill (1983) |
| Tversky | tversky_similarity | |A∩B| / (|A∩B| + α|A\B| + β|B\A|) | [0, 1] | Tversky (1977) |
| Kulczynski (2nd) | kulczynski_similarity | 0.5(|A∩B|/|A| + |A∩B|/|B|) | [0, 1] | Kulczyński (1927) |
| Braun-Blanquet | braun_blanquet_similarity | |A∩B| / max(|A|,|B|) | [0, 1] | Braun-Blanquet (1932) |
| Sokal-Sneath (1st) | sokal_sneath_similarity | |A∩B| / (|A∩B| + 2|AΔB|) | [0, 1] | Sokal & Sneath (1963) |
| McConnaughey | mcconnaughey_similarity | (|A∩B|² - |A\B||B\A|) / (|A||B|) | [-1, 1] | McConnaughey (1964) |
| Johnson | johnson_similarity | (E_c+V_c)² / ((V₁+E₁)(V₂+E₂)) | [0, 1] | Raymond et al. (2002) |
Modules§
- errors
- Submodule defining common errors for the graph crate.
- impls
- Implementations of traits for standard library types.
- naive_
structs - Submodule providing naively implemented data structures for graphs.
- prelude
- Prelude module for the graph crate.
- test_
utils - Testing utilities for constructing type instances from raw bytes and replaying fuzz corpus or crash files, and shared invariant-checking functions used by both fuzz targets and regression tests.
- traits
- Submodule defining the graph-related traits.