Description:

This task focuses on reworking ring perception to remove O(n³)-like behavior on large or dense graphs while keeping ring semantics unchanged. The current implementation scans the full bond list inside each BFS, and runs one BFS per bond, causing high overhead. We will introduce bond-aware adjacency, reuse traversal buffers, and optionally switch to a spanning-tree/non-tree-edge basis selection to minimize searches. The goal is to preserve the existing SSSR-style minimal cycle basis and annotations, but deliver markedly better throughput and memory behavior on large biomolecular and materials systems.

Tasks:

• Phase 1: Data Structure Preparation

  • In perception::model (or alongside), add an adjacency variant that stores neighbor atom ID, bond ID, and bond order together (e.g., adjacency_with_bond).
  • Populate this structure during AnnotatedMolecule::new, ensuring bond IDs stay stable and ordering remains deterministic.

• Phase 2: BFS Fast Path

  • Update rings::shortest_path_bfs to consume the bond-aware adjacency and drop the bonds.iter().find(...) scan.
  • Introduce reusable buffers for visited, parent, and the queue to avoid per-bond allocations.
  • Keep the current observable outputs (ring membership, smallest ring size) identical.

• Phase 3: Candidate Generation Optimization (Optional but preferred)

  • Replace the “one BFS per bond” candidate search with a spanning-tree + non-tree-edge path enumeration to cap BFS calls at the cyclomatic number.
  • Maintain the existing Gaussian-elimination minimal basis selection logic and output ordering guarantees.