feat(graph): add CSR graph algorithms (PageRank, community, path, similarity)#46
Merged
Conversation
…ilarity) Pure-Rust zero-dependency module (src/graph/algo/) compiled in behind the existing `graph` feature — no Cargo.toml change, no petgraph. Closes the Neo4j/GDS algorithm gap flagged in issue #45 Axis C. - CsrGraph: directed weighted CSR snapshot with dangling-node detection - pagerank: weighted power iteration with dangling-node redistribution - community: connected components (union-find) + label propagation - path: Dijkstra weighted shortest path (distance = -ln(weight)) - similarity: Jaccard, common neighbors, Adamic-Adar, link prediction smart_recall's graph boost (W_GRAPH) now ranks the top-100 candidates by true PageRank over their induced subgraph, replacing the approximate degree-centrality neighbor-weight sum. The SQLite (recall.rs) and PostgreSQL (pg.rs) recall paths share pagerank_default, permanently removing the cross-backend boost-logic drift. All algorithms validated by hand-computed unit tests (diamond PageRank, jaccard 1/3, adamic-adar 1/ln(2), two-hop-beats-direct Dijkstra) plus criterion benchmarks (PageRank 1000 nodes: ~4.9us). 570 tests pass, clippy/fmt/rustdoc clean.
docs/benchmarks/graph.md captures the 2026-06-26 criterion measurements (PageRank 1000 nodes: 4.87us, connected components 9.50us, Dijkstra 41us, CSR build 727us) as the v1.0.0 baseline for issue #45 Axis A / ROADMAP #3. README Benchmarks section now links to it and lists the new algorithm benchmark groups.
edge_cost now clamps weight to [SHORTEST_PATH_W_MIN, 1.0]. A contract-violating weight > 1.0 previously produced -ln(w) < 0, a negative edge cost that breaks Dijkstra's non-negative-edge assumption and silently returns wrong shortest paths. It is now treated as maximal strength (cost 0). Adds a regression test asserting no negative distances.
recall_graph_boost asserted only len()==2 despite a comment claiming the boost was applied. Now also asserts the dangling sink outranks its source: with hint=None and identical base scores the score difference is purely the graph boost, so this is the one test exercising its ranking effect. Normalizes the contract-violating weight 2.0 to 1.0.
epicsagas
added a commit
that referenced
this pull request
Jun 26, 2026
) Resolves RUSTSEC-2026-0185 in quinn-proto, the advisory that was failing the audit CI gate on every PR (#44, #46). quinn-proto reaches the lockfile via the reqwest 0.12 tree but is not activated under any feature/target combination (cargo tree -i reports nothing to print), so this is a lockfile-only patch. Verified: cargo audit now reports 0 vulnerabilities (exit 0); cargo test --all-features green.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Summary
Closes the Neo4j/GDS algorithm gap flagged in #45 (Axis C — algorithmic depth). Adds a pure-Rust, zero-dependency graph algorithm module (
src/graph/algo/) behind the existinggraphfeature — noCargo.tomlchange, nopetgraph.Algorithms
algo/csr.rsCsrGraph— directed weighted CSR snapshot, dangling-node detectionalgo/pagerank.rsalgo/community.rsalgo/path.rsdistance = -ln(weight))algo/similarity.rsrecall integration + drift removal
smart_recall's graph boost (W_GRAPH = 0.10) now ranks the top-100 candidates by true PageRank over their induced subgraph, replacing the former neighbor-weight-sum (an approximate degree centrality). The SQLite (recall.rs) and PostgreSQL (pg.rs) recall paths share the samepagerank_defaultfree function, permanently removing the cross-backend boost-logic drift (pg.rshad duplicated the boost SQL).New
store::edges_amongserves the induced-subgraph query.Verification
cargo test --all-features); +87 new algorithm/regression testscargo clippy --all-features -- -D warnings— cleancargo fmt --all -- --check— cleanRUSTDOCFLAGS=\"-D warnings\" cargo doc --all-features— cleaneval graphPASS (12 scenarios incl. 2 PageRank, avg_recall 1.0)Benchmarks (2026-06-26 baseline)
Full numbers + interpretation in docs/benchmarks/graph.md. Highlights (criterion median):
PageRank at ~5 µs / 1000 nodes justifies recomputing it on every
smart_recallcall — no result cache needed.Scope
Addresses #45 Axis C (algorithmic depth) and contributes to Axis A (benchmark baselines). The remaining axes (scale ceiling, recall-quality harness, concurrency proof, consumer integration) stay open.
Refs #45.