oxgraph-algo 0.1.0

Substrate-agnostic graph algorithms over oxgraph-topology traits.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

//! 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`](oxgraph_topology::ElementSuccessors); reverse entry
//! points expand through
//! [`ElementPredecessors`](oxgraph_topology::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`](oxgraph_topology::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`](oxgraph_topology::ElementIndex) + direction trait | amortized `O(1)` setup, `O(n + m)` traversal, no allocation |
//! | `alloc` | [`breadth_first_search`] | [`reverse_breadth_first_search`] | dense [`ElementIndex`](oxgraph_topology::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`](oxgraph_topology::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`](oxgraph_topology::ElementSuccessors); reverse BFS
//! follows
//! [`ElementPredecessors`](oxgraph_topology::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.
#![no_std]

#[cfg(kani)]
extern crate kani;

#[cfg(feature = "alloc")]
extern crate alloc;

#[cfg(feature = "std")]
extern crate std;

pub mod bfs;
pub mod pagerank;

pub use bfs::{
    BfsEpochScratch, BfsError, BreadthFirstSearchEpochScratch, BreadthFirstSearchScratch,
    ReverseBreadthFirstSearchEpochScratch, ReverseBreadthFirstSearchScratch,
    breadth_first_search_with_epoch_scratch, breadth_first_search_with_scratch,
    reverse_breadth_first_search_with_epoch_scratch, reverse_breadth_first_search_with_scratch,
};
#[cfg(feature = "alloc")]
pub use bfs::{
    BfsWorkspace, BreadthFirstSearch, BreadthFirstSearchWorkspace, GenericBreadthFirstSearch,
    GenericReverseBreadthFirstSearch, ReverseBreadthFirstSearch,
    ReverseBreadthFirstSearchWorkspace, breadth_first_search, breadth_first_search_generic,
    breadth_first_search_with_workspace, reverse_breadth_first_search,
    reverse_breadth_first_search_generic, reverse_breadth_first_search_with_workspace,
};
#[cfg(feature = "std")]
pub use bfs::{
    HashBreadthFirstSearch, HashReverseBreadthFirstSearch, breadth_first_search_generic_hash,
    reverse_breadth_first_search_generic_hash,
};
pub use pagerank::{
    HyperWeighted, HypergraphOutgoingDistribution, HypergraphPageRankScratch, IntoPageRankScalar,
    OutgoingDistribution, PageRankConfig, PageRankError, PageRankReport, PageRankScalar,
    PageRankScratch, Uniform, Weighted, pagerank_graph_with_scratch,
    pagerank_hypergraph_with_scratch,
};
#[cfg(feature = "alloc")]
pub use pagerank::{
    HypergraphPageRankWorkspace, PageRankWorkspace, pagerank_graph, pagerank_graph_with_workspace,
    pagerank_hypergraph, pagerank_hypergraph_with_workspace,
};