🚀 Arbitrage Cycle Detector (Rust)

This project implements a profitable cycle detector for weighted directed graphs (e.g., currency arbitrage), using:

• Compressed Sparse Row (CSR) graph representation for compact and cache-friendly storage.

• SPFA (Shortest Path Faster Algorithm) variant with hop cap to detect negative cycles efficiently.

• Streaming updates via async ingestion pipeline to simulate live rate changes.

• Clean, well-structured code that passes formatting and linting checks.

🧩 Features

Component	Description
CSR Builder	Converts edge lists into a compressed sparse row format for efficient traversal.
SPFA Cycle Detection	Detects profitable cycles (negative log-sum loops) with optional hop limit.
Async Updates Ingest	Receives edge/rate updates and applies them to shared graph state.
Numeric Kernel	Handles rate transformations with clamping, quantization, and epsilon gating.
Data Layout (AoS ↔ SoA)	Demonstrates memory layout performance differences via benchmarks.

📂 Project Structure

src/
├── lib.rs                  # Core logic: CSR, SPFA, numeric kernel, data structs
├── bin/
│   ├── async_pipeline.rs   # Async update ingestion + cycle recheck demo
│   ├── bench_aos.rs        # AoS benchmark
│   ├── bench_soa.rs        # SoA benchmark
│   └── cycle_finder.rs     # Build graph + detect profitable cycle

🛠️ Build & Run

Prerequisites

• Rust 1.75+
• Cargo package manager

Buid

cargo build --release

1. Run Arbitrage Detector

cargo run --release --bin cycle_finder

2. Run AoS/SoA Benchmarks

cargo run --release --bin bench_aos
cargo run --release --bin bench_soa

3. Run Unit Tests

cargo test

4. Run Async Update Simulation

cargo run --release --bin async_pipeline

🧠 Design Notes

• CSR Graph Format: Nodes and edges are stored compactly in arrays (offsets, targets, weights) to improve memory locality and speed up SPFA traversal.

• SPFA with Hop Cap: Similar to Bellman–Ford but uses a queue and hop limit to avoid infinite loops. Detects negative cycles (i.e., profitable cycles in log-space).

• Profitability Criterion: Rates are transformed with w(u,v) = -ln(rate). A cycle is profitable if the sum of weights (logs) < 0 → product of rates > 1.

• Async Update Pipeline: Uses tokio::sync::mpsc with a bounded channel to ingest updates, apply them to the graph, and trigger recalculation periodically.

• Performance & Safety:
  • Bounded channels provide backpressure.
  • Locking (RwLock) is kept minimal.
  • Arithmetic kernels are clamped, quantized, and epsilon-filtered for stability.
  • All code passes:

  cargo fmt --check
  cargo clippy -- -D warnings

🧪 Example Output

Cycle found: Cycle { nodes: [2, 0, 1], ... }
Product: 0.5500, log_sum: -0.5978