Expand description
Substrate-agnostic graph algorithms over storage-agnostic topology traits.
oxgraph-algo contains algorithms whose semantics generalize across
ordinary binary graphs and hypergraphs. BFS binds only to capability traits
from oxgraph-topology; PageRank additionally uses ordinary-graph and
hypergraph vocabulary traits from oxgraph-graph and oxgraph-hyper while
still avoiding concrete storage and Arrow/property dependencies. The same
compiled algorithms run on oxgraph-csr::CsrGraph,
oxgraph-hyper-bcsr::BcsrHypergraph, and any future view that exposes the
required capabilities.
The default APIs are allocation-free: callers provide reusable scratch
storage for traversal state. Allocating convenience wrappers are available
behind the alloc feature. Standard-library optimized generic wrappers are
available behind the std feature.
Each variant ships in two directions. Forward entry points expand through
ElementSuccessors; reverse entry
points expand through
ElementPredecessors. Both
directions reuse the same storage policies, so a single
BfsEpochScratch / [BfsWorkspace] serves either traversal direction.
§BFS tiers
| Feature | Forward API | Reverse API | Topology requirement | Performance |
|---|---|---|---|---|
| none | breadth_first_search_with_scratch | reverse_breadth_first_search_with_scratch | dense ElementIndex + direction trait | O(b) setup, O(n + m) traversal, no allocation |
| none | breadth_first_search_with_epoch_scratch | reverse_breadth_first_search_with_epoch_scratch | dense ElementIndex + direction trait | amortized O(1) setup, O(n + m) traversal, no allocation |
alloc | [breadth_first_search] | [reverse_breadth_first_search] | dense ElementIndex + direction trait | O(b) setup, O(n + m) traversal, owned storage |
alloc | [breadth_first_search_with_workspace] | [reverse_breadth_first_search_with_workspace] | dense ElementIndex + direction trait | amortized O(1) setup, O(n + m) traversal, reusable owned storage |
alloc | [breadth_first_search_generic] | [reverse_breadth_first_search_generic] | arbitrary element IDs | O((n + m) log n) traversal with BTreeSet membership |
std | [breadth_first_search_generic_hash] | [reverse_breadth_first_search_generic_hash] | arbitrary element IDs | expected O(n + m) traversal with HashSet membership |
Forward BFS follows
ElementSuccessors; reverse BFS
follows
ElementPredecessors. Both
traverse element-to-element directly without materializing intermediate
relation IDs.
b is graph.element_bound(), n is the number of elements yielded, and
m is the number of expansion-target entries inspected.
Re-exports§
pub use bfs::BfsBounds;pub use bfs::BfsEpochScratch;pub use bfs::BfsError;pub use bfs::BfsVisitor;pub use bfs::BreadthFirstSearchEpochScratch;pub use bfs::BreadthFirstSearchScratch;pub use bfs::ReverseBreadthFirstSearchEpochScratch;pub use bfs::ReverseBreadthFirstSearchScratch;pub use bfs::breadth_first_search_bounded;pub use bfs::breadth_first_search_bounded_both;pub use bfs::breadth_first_search_with_epoch_scratch;pub use bfs::breadth_first_search_with_scratch;pub use bfs::reverse_breadth_first_search_bounded;pub use bfs::reverse_breadth_first_search_with_epoch_scratch;pub use bfs::reverse_breadth_first_search_with_scratch;pub use pagerank::HyperWeighted;pub use pagerank::HypergraphOutgoingDistribution;pub use pagerank::HypergraphPageRankScratch;pub use pagerank::IntoPageRankScalar;pub use pagerank::OutgoingDistribution;pub use pagerank::PageRankConfig;pub use pagerank::PageRankError;pub use pagerank::PageRankReport;pub use pagerank::PageRankScalar;pub use pagerank::PageRankScratch;pub use pagerank::Uniform;pub use pagerank::Weighted;pub use pagerank::pagerank_graph_with_scratch;pub use pagerank::pagerank_hypergraph_with_scratch;