Conversation
…adjacency details
TKanX
added
enhancement ✨
10 tasks
Contributor
There was a problem hiding this comment.
Pull request overview
This PR optimizes the ring perception algorithm by eliminating expensive bond lookups during cycle detection. The optimization introduces a bond-aware adjacency list (adjacency_with_bonds) that pre-caches bond identifiers, transforming a critical O(E) lookup into O(1), and adds workspace reuse to avoid repeated allocations during BFS traversal.
Key Changes:
- Introduced
NeighborBondstruct bundling neighbor ID, bond ID, and bond order for direct access - Added
adjacency_with_bondsfield toAnnotatedMoleculewith synchronized initialization - Implemented
RingSearchWorkspaceto reuse BFS buffers across all ring searches
Reviewed changes
Copilot reviewed 3 out of 3 changed files in this pull request and generated 2 comments.
| File | Description |
|---|---|
src/perception/model.rs |
Adds NeighborBond struct and adjacency_with_bonds field; updates AnnotatedMolecule::new to populate both adjacency representations; adds unit tests verifying the new adjacency structure |
src/perception/rings.rs |
Introduces RingSearchWorkspace for buffer reuse; refactors shortest_path_bfs to use cached bond IDs from adjacency_with_bonds; updates enumerate_cycle_candidates to accept and reuse workspace; adds test for fused ring systems |
docs/02_perception.md |
Documents the optimization approach in the ring detection section |
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
TKanX
deleted the
feature/15-accelerate-ring-perception-with-bond-aware-adjacency
branch
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
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:
Significantly optimizes the ring perception algorithm by pre-calculating and caching bond identifiers within the adjacency list. Previously, the cycle detection logic performed a linear search (
O(E)) to find the bond connecting two atoms during every step of the graph traversal. By introducing aNeighborBondstruct and anadjacency_with_bondscache inAnnotatedMolecule, this lookup becomesO(1). Additionally, the BFS traversal now reuses scratch memory (RingSearchWorkspace) to eliminate repeated allocations.Changes:
Optimized Graph Representation:
NeighborBondstruct to bundle neighbor ID, bond ID, and bond order.adjacency_with_bondstoAnnotatedMolecule, pre-populated during initialization.AnnotatedMolecule::newto build this enhanced adjacency list efficiently.Accelerated Cycle Detection:
shortest_path_bfsto use the cachedbond_idfromadjacency_with_bondsdirectly, removing the expensiveO(E)bond lookup loop.RingSearchWorkspaceto reusequeue,visited, andparentbuffers across all BFS runs, drastically reducing heap allocations.enumerate_cycle_candidatesto utilize the new workspace.Verified Correctness:
adjacency_with_bondspopulation.