oxicuda_graphalg/lib.rs
1//! `oxicuda-graphalg` — Classical Graph Algorithms for OxiCUDA.
2//!
3//! # Architecture
4//!
5//! ```text
6//! oxicuda-graphalg
7//! ├── repr/ — Graph representations (AdjacencyList, AdjacencyMatrix,
8//! │ EdgeList, CSR, WeightedGraph)
9//! ├── traversal/ — BFS, DFS (iterative + post-order), IDDFS, bidirectional BFS
10//! ├── topological/ — Kahn's algorithm and DFS-based topological sort
11//! ├── shortest_path/ — Dijkstra, Bellman-Ford, SPFA, Floyd-Warshall, Johnson,
12//! │ A*, Yen K-shortest, bidirectional Dijkstra
13//! ├── mst/ — Prim, Kruskal, Borůvka, Union-Find
14//! ├── max_flow/ — Edmonds-Karp, Dinic, push-relabel, min-cut
15//! ├── matching/ — Hopcroft-Karp bipartite, Hungarian (Munkres) assignment,
16//! │ simplified blossom for general unweighted matching
17//! ├── flow/ — Gomory-Hu cut tree (Gusfield), Stoer-Wagner global min cut
18//! ├── path/ — Suurballe vertex-disjoint shortest path pair
19//! ├── connectivity/ — Tarjan / Kosaraju / Gabow SCC, bridges, articulation
20//! │ points, biconnected components
21//! ├── centrality/ — Degree, betweenness (Brandes), closeness, eigenvector,
22//! │ PageRank, Katz
23//! ├── community/ — Louvain, label propagation, Girvan-Newman
24//! ├── arborescence/ — Chu-Liu-Edmonds minimum spanning arborescence
25//! ├── isomorphism/ — VF2 subgraph isomorphism
26//! ├── coloring/ — Greedy, DSATUR, Welsh-Powell
27//! ├── tsp/ — Christofides approximation, nearest-neighbor, 2-opt
28//! ├── eulerian/ — Hierholzer's Eulerian circuit
29//! ├── hamiltonian/ — Held-Karp DP exact TSP
30//! ├── dynamic/ — Streaming dynamic graph (incremental PageRank, incremental SCC)
31//! └── metrics/ — Diameter, radius, density, clustering coefficient, transitivity
32//! ```
33//!
34//! All algorithms are implemented in pure Rust with no external graph libraries.
35//! Random sampling uses the workspace `LcgRng` (MMIX LCG with bit-32 boolean trick).
36
37#![forbid(unsafe_code)]
38#![allow(clippy::needless_range_loop)]
39#![allow(clippy::needless_borrows_for_generic_args)]
40#![allow(clippy::useless_vec)]
41#![allow(clippy::collapsible_if)]
42#![allow(clippy::while_let_loop)]
43#![allow(clippy::if_same_then_else)]
44#![allow(clippy::identity_op)]
45#![allow(clippy::erasing_op)]
46#![allow(clippy::manual_range_contains)]
47#![allow(clippy::needless_late_init)]
48#![allow(clippy::single_match)]
49#![allow(clippy::redundant_closure)]
50
51pub mod arborescence;
52pub mod centrality;
53pub mod clique;
54pub mod coloring;
55pub mod community;
56pub mod connectivity;
57pub mod dynamic;
58pub mod error;
59pub mod eulerian;
60pub mod flow;
61pub mod hamiltonian;
62pub mod handle;
63pub mod isomorphism;
64pub mod matching;
65pub mod max_flow;
66pub mod metrics;
67pub mod min_cost_flow;
68pub mod mst;
69pub mod path;
70pub mod ptx_kernels;
71pub mod repr;
72pub mod separation;
73pub mod shortest_path;
74pub mod topological;
75pub mod traversal;
76pub mod tsp;
77
78pub use error::{GraphalgError, GraphalgResult};
79pub use handle::{GraphalgHandle, LcgRng, SmVersion};
80
81#[cfg(test)]
82mod e2e_tests;