Crate oxicuda_graphalg 

oxicuda-graphalg — Classical Graph Algorithms for OxiCUDA.

Architecture

oxicuda-graphalg
├── repr/            — Graph representations (AdjacencyList, AdjacencyMatrix,
│                      EdgeList, CSR, WeightedGraph)
├── traversal/       — BFS, DFS (iterative + post-order), IDDFS, bidirectional BFS
├── topological/     — Kahn's algorithm and DFS-based topological sort
├── shortest_path/   — Dijkstra, Bellman-Ford, SPFA, Floyd-Warshall, Johnson,
│                      A*, Yen K-shortest, bidirectional Dijkstra
├── mst/             — Prim, Kruskal, Borůvka, Union-Find
├── max_flow/        — Edmonds-Karp, Dinic, push-relabel, min-cut
├── matching/        — Hopcroft-Karp bipartite, Hungarian (Munkres) assignment,
│                      simplified blossom for general unweighted matching
├── flow/            — Gomory-Hu cut tree (Gusfield), Stoer-Wagner global min cut
├── path/            — Suurballe vertex-disjoint shortest path pair
├── connectivity/    — Tarjan / Kosaraju / Gabow SCC, bridges, articulation
│                      points, biconnected components
├── centrality/      — Degree, betweenness (Brandes), closeness, eigenvector,
│                      PageRank, Katz
├── community/       — Louvain, label propagation, Girvan-Newman
├── arborescence/    — Chu-Liu-Edmonds minimum spanning arborescence
├── isomorphism/     — VF2 subgraph isomorphism
├── coloring/        — Greedy, DSATUR, Welsh-Powell
├── tsp/             — Christofides approximation, nearest-neighbor, 2-opt
├── eulerian/        — Hierholzer's Eulerian circuit
├── hamiltonian/     — Held-Karp DP exact TSP
├── dynamic/         — Streaming dynamic graph (incremental PageRank, incremental SCC)
└── metrics/         — Diameter, radius, density, clustering coefficient, transitivity

All algorithms are implemented in pure Rust with no external graph libraries. Random sampling uses the workspace LcgRng (MMIX LCG with bit-32 boolean trick).

Re-exports

pub use error::GraphalgError;

pub use error::GraphalgResult;

pub use handle::GraphalgHandle;

pub use handle::LcgRng;

pub use handle::SmVersion;

Modules

arborescence

Minimum spanning arborescence.

centrality

Centrality measures.

clique

Clique enumeration and maximum clique algorithms.

coloring

Graph coloring.

community

Community detection algorithms.

connectivity

Connectivity: strongly-connected components, bridges, articulation points, biconnected.

dynamic

Streaming dynamic-graph algorithms.

error

Error types for oxicuda-graphalg.

eulerian

Eulerian circuit construction.

flow

Cut-structure algorithms built on max-flow / min-cut.

hamiltonian

Hamiltonian-path / cycle algorithms.

handle

Handle and RNG primitives for oxicuda-graphalg.

isomorphism

Subgraph isomorphism / graph isomorphism.

matching

Graph matching algorithms.

max_flow

Max flow / min cut algorithms.

metrics

Graph metrics: diameter, radius, density, clustering coefficient.

min_cost_flow

Min-cost max-flow algorithms.

mst

Minimum spanning tree algorithms.

path

Disjoint-path algorithms.

ptx_kernels

GPU PTX kernels for graph algorithm operations.

repr

Graph representations: adjacency list, adjacency matrix, edge list, CSR, weighted graph.

separation

Graph separators.

shortest_path

Shortest path algorithms.

topological

Topological sort algorithms (Kahn, DFS-based).

traversal

Graph traversal: BFS, DFS (recursive + iterative), IDDFS, bidirectional BFS.

tsp

Traveling Salesperson approximations/heuristics.