oxgraph_algo/
lib.rs

1//! Substrate-agnostic graph algorithms over storage-agnostic topology traits.
2//!
3//! `oxgraph-algo` contains algorithms whose semantics generalize across
4//! ordinary binary graphs and hypergraphs. BFS binds only to capability traits
5//! from `oxgraph-topology`; `PageRank` additionally uses ordinary-graph and
6//! hypergraph vocabulary traits from `oxgraph-graph` and `oxgraph-hyper` while
7//! still avoiding concrete storage and Arrow/property dependencies. The same
8//! compiled algorithms run on `oxgraph-csr::CsrGraph`,
9//! `oxgraph-hyper-bcsr::BcsrHypergraph`, and any future view that exposes the
10//! required capabilities.
11//!
12//! The default APIs are allocation-free: callers provide reusable scratch
13//! storage for traversal state. Allocating convenience wrappers are available
14//! behind the `alloc` feature. Standard-library optimized generic wrappers are
15//! available behind the `std` feature.
16//!
17//! Each variant ships in two directions. Forward entry points expand through
18//! [`ElementSuccessors`](oxgraph_topology::ElementSuccessors); reverse entry
19//! points expand through
20//! [`ElementPredecessors`](oxgraph_topology::ElementPredecessors). Both
21//! directions reuse the same storage policies, so a single
22//! [`BfsEpochScratch`] / [`BfsWorkspace`] serves either traversal direction.
23//!
24//! # BFS tiers
25//!
26//! | Feature | Forward API | Reverse API | Topology requirement | Performance |
27//! | --- | --- | --- | --- | --- |
28//! | none | [`breadth_first_search_with_scratch`] | [`reverse_breadth_first_search_with_scratch`] | dense [`ElementIndex`](oxgraph_topology::ElementIndex) + direction trait | `O(b)` setup, `O(n + m)` traversal, no allocation |
29//! | none | [`breadth_first_search_with_epoch_scratch`] | [`reverse_breadth_first_search_with_epoch_scratch`] | dense [`ElementIndex`](oxgraph_topology::ElementIndex) + direction trait | amortized `O(1)` setup, `O(n + m)` traversal, no allocation |
30//! | `alloc` | [`breadth_first_search`] | [`reverse_breadth_first_search`] | dense [`ElementIndex`](oxgraph_topology::ElementIndex) + direction trait | `O(b)` setup, `O(n + m)` traversal, owned storage |
31//! | `alloc` | [`breadth_first_search_with_workspace`] | [`reverse_breadth_first_search_with_workspace`] | dense [`ElementIndex`](oxgraph_topology::ElementIndex) + direction trait | amortized `O(1)` setup, `O(n + m)` traversal, reusable owned storage |
32//! | `alloc` | [`breadth_first_search_generic`] | [`reverse_breadth_first_search_generic`] | arbitrary element IDs | `O((n + m) log n)` traversal with `BTreeSet` membership |
33//! | `std` | [`breadth_first_search_generic_hash`] | [`reverse_breadth_first_search_generic_hash`] | arbitrary element IDs | expected `O(n + m)` traversal with `HashSet` membership |
34//!
35//! Forward BFS follows
36//! [`ElementSuccessors`](oxgraph_topology::ElementSuccessors); reverse BFS
37//! follows
38//! [`ElementPredecessors`](oxgraph_topology::ElementPredecessors). Both
39//! traverse element-to-element directly without materializing intermediate
40//! relation IDs.
41//!
42//! `b` is `graph.element_bound()`, `n` is the number of elements yielded, and
43//! `m` is the number of expansion-target entries inspected.
44#![no_std]
45
46#[cfg(kani)]
47extern crate kani;
48
49#[cfg(feature = "alloc")]
50extern crate alloc;
51
52#[cfg(feature = "std")]
53extern crate std;
54
55pub mod bfs;
56pub mod pagerank;
57
58#[cfg(feature = "alloc")]
59pub mod components;
60#[cfg(feature = "alloc")]
61pub mod longest_path_dag;
62#[cfg(feature = "alloc")]
63pub mod scc;
64#[cfg(feature = "alloc")]
65pub mod sssp;
66#[cfg(feature = "alloc")]
67pub mod toposort;
68
69pub use bfs::{
70    BfsBounds, BfsEpochScratch, BfsError, BfsVisitor, BreadthFirstSearchEpochScratch,
71    BreadthFirstSearchScratch, ReverseBreadthFirstSearchEpochScratch,
72    ReverseBreadthFirstSearchScratch, breadth_first_search_bounded,
73    breadth_first_search_bounded_both, breadth_first_search_with_epoch_scratch,
74    breadth_first_search_with_scratch, reverse_breadth_first_search_bounded,
75    reverse_breadth_first_search_with_epoch_scratch, reverse_breadth_first_search_with_scratch,
76};
77#[cfg(feature = "alloc")]
78pub use bfs::{
79    BfsWorkspace, BreadthFirstSearch, BreadthFirstSearchWorkspace, GenericBreadthFirstSearch,
80    GenericReverseBreadthFirstSearch, ReverseBreadthFirstSearch,
81    ReverseBreadthFirstSearchWorkspace, breadth_first_search, breadth_first_search_generic,
82    breadth_first_search_with_workspace, reverse_breadth_first_search,
83    reverse_breadth_first_search_generic, reverse_breadth_first_search_with_workspace,
84};
85#[cfg(feature = "std")]
86pub use bfs::{
87    HashBreadthFirstSearch, HashReverseBreadthFirstSearch, breadth_first_search_generic_hash,
88    reverse_breadth_first_search_generic_hash,
89};
90#[cfg(feature = "alloc")]
91pub use components::connected_components;
92#[cfg(feature = "alloc")]
93pub use longest_path_dag::{LongestPathError, longest_path_dag};
94pub use pagerank::{
95    HyperWeighted, HypergraphOutgoingDistribution, HypergraphPageRankScratch, IntoPageRankScalar,
96    OutgoingDistribution, PageRankConfig, PageRankError, PageRankReport, PageRankScalar,
97    PageRankScratch, Uniform, Weighted, pagerank_graph_with_scratch,
98    pagerank_hypergraph_with_scratch,
99};
100#[cfg(feature = "alloc")]
101pub use pagerank::{
102    HypergraphPageRankWorkspace, PageRankWorkspace, pagerank_graph, pagerank_graph_with_workspace,
103    pagerank_hypergraph, pagerank_hypergraph_with_workspace,
104};
105#[cfg(feature = "alloc")]
106pub use scc::strongly_connected_components;
107#[cfg(feature = "alloc")]
108pub use sssp::shortest_path_lengths;
109#[cfg(feature = "alloc")]
110pub use toposort::{ToposortError, topological_sort};
oxgraph_algo/lib.rs

oxgraph_algo/
lib.rs
