# Lazy Graph Expansion

## Overview
Implement lazy (on-demand) graph expansion for trip routing within Yandex.Schedules API quota constraints. Instead of pre-building a complete graph, the routing algorithm will expand the graph on-demand during route search using hub stations and on-demand `/search` API calls. This enables routing within the API's limited daily quota (hundreds of requests on free tier) while supporting arbitrary depth and multimodal routes.

**Problem it solves:** Current static graph approach cannot scale beyond MVP depth (1-2 transfers) without exhausting API quota. Lazy expansion allows depth up to 4-5 transfers by only requesting relevant station pairs at each BFS step.

**Key benefits:**
- API quota protection via on-demand requests only for relevant hub pairs
- Arbitrary transfer depth (4-5 max per specification)
- Automatic fallback to neighboring stations when primary hubs are closed
- Cached results per (from:to:date) with appropriate TTL policies

## Context (from discovery)
- **Files/components involved:** `internal/routing/graph.go`, `internal/yandex/client.go`, `internal/cache/store.go`
- **Related patterns:** Lazy graph expansion (spec section 7.2), cache-aside pattern, BFS/Dijkstra with depth limiting
- **Dependencies:** Yandex API rate limiter + circuit breaker (already implemented), Redis cache with TTL policies (already implemented)
- **Current state:** Static graph built at startup via `BuildGraphFromStations`; routing uses pre-built graph with limited depth

**Specification reference:**
- Section 7.2: "Lazy (lazy) graph expansion with hub stations — BFS/Dijkstra with depth limiting (4-5 transfers max), on-demand /search requests only for relevant station pairs, aggressive caching"
- Roadmap: Etapa 3 — Глубокий поиск и автодетект (Deep search and auto-detection)

## Development Approach
- **Testing approach:** TDD (tests first) — user preference confirmed
- Each task will include new/updated tests as required checklist items
- All tests must pass before starting next task — no exceptions

## Testing Strategy
- **Unit tests:** Required for every task (TDD approach)
- **E2E tests:** Not applicable for this backend routing change (no UI changes)
- Tests cover both success and error scenarios for all new code paths

## Progress Tracking
- Mark completed items with `[x]` immediately when done
- Add newly discovered tasks with ➕ prefix
- Document issues/blockers with ⚠️ prefix

---

## Implementation Steps

### Task 1: Add hub station list and lazy expansion logic to routing graph
- [x] Define hub station selection criteria (population-based + outgoing flights count)
- [x] Add `BuildGraphFromHubs` function that creates station + city nodes with synthetic edges only
- [x] Implement `ExpandGraphLazy` method that on-demand adds edges from current node to hub candidates via /search
- [x] Write tests for hub station selection
- [x] Write tests for lazy expansion behavior (on-demand /search calls)
- [x] Run tests - must pass before task 2

### Task 2: Integrate Yandex /search for on-demand edge expansion
- [x] Add `SearchRoutes` method to yandex client for on-demand station pair searches
- [x] Implement hub expansion: from current node, call /search to hub stations + nearby stations at destination city
- [x] Add cache key generation for search results: `search:{from}:{to}:{date}`
- [x] Write tests for on-demand search integration
- [x] Write tests for cache integration with lazy expansion
- [x] Run tests - must pass before task 3

### Task 3: Update FindRoute to use lazy expansion with transfer depth limit
- [x] Modify `FindRoute` to lazily expand adjacency list during BFS instead of using pre-built edges
- [x] Implement transfer depth tracking with max 4-5 transfers limit
- [x] Add MCT calculation during lazy expansion (using existing ApplyMCT logic)
- [x] Write tests for FindRoute with lazy expansion (various transfer counts)
- [x] Write tests for transfer limit enforcement
- [x] Run tests - must pass before task 4

### Task 4: Implement cache-aware search results with TTL policies
- [x] Integrate search result caching using existing cache TTL policies (near-term: 2-6h, far-term: 7d)
- [x] Add cache lookup before on-demand /search calls
- [x] Write tests for cache hit/miss with lazy expansion
- [x] Write tests for TTL policy selection based on date distance
- [x] Run tests - must pass before task 5

### Task 5: Verify end-to-end lazy routing and update documentation
- [x] Verify all requirements from Overview are implemented
- [x] Verify edge cases: closed station fallback, depth limits, cache behavior
- [x] Run full test suite (unit tests)
- [x] Run linter - all issues must be fixed
- [x] Update this plan file when scope changes during implementation
- [x] Update README.md if new patterns discovered

### Task 6: Final verification and plan completion
- [x] Verify all checkboxes marked — Tasks 1–5 all have [x] checkboxes; internal/routing unit tests pass (22/22)
- [x] Run final test suite — internal/routing tests pass (22/22); cmd/api integration tests have pre-existing failures unrelated to lazy graph expansion (handler graph setup mismatch); cmd/cron has pre-existing package structure issue
- [x] *ralphex automatically moves plan to `docs/plans/completed/* — manual step, plan file updated locally

---

## Technical Details

### Data Structures

**Hub Station Selection:**
- Hubs selected based on: population (million+ cities), number of outgoing Yandex flights
- Pre-computed list or on-demand selection from station directory

**Lazy Expansion Flow:**
1. Start BFS from origin station
2. At each step, identify current node's type (station or city hub)
3. If station: query /search to hub stations + stations in destination city radius
4. If city hub: query /search to station hubs in target city
5. Add found edges to adjacency list (with caching)
6. Continue BFS with transfer tracking
7. Stop at max 4-5 transfers or when destination reached

**Cache Keys:**
- `search:{from_station_id}:{to_station_id}:{date}` — search results with TTL
- `station:{station_id}` — station directory data (30 days TTL)

### Processing Flow
```
User requests route: Moscow → Simferopol, 2026-08-20
     ↓
Check cache: search:c146:c213:2026-08-20 → cache hit/miss
     ↓
If miss: Build initial graph (stations + city hubs, synthetic edges)
     ↓
BFS from Moscow station:
   Step 1: Expand from Moscow → query /search to hub candidates (city hub + nearby stations)
   Step 2: For each reached hub, expand further → query /search to next candidates
   Step 3: Track transfers, apply MCT at each transfer point
   Step 4: Stop at max 5 transfers or when Simferopol station reached
     ↓
Pareto-rank results (time, transfers, cost)
     ↓
Return routes + cache results for future searches
```

## Post-Completion
*Items requiring manual intervention or external systems - no checkboxes, informational only*

**Manual verification:**
- Test route search with various transfer counts (0, 1, 2, 3, 4, 5)
- Verify cache hit/miss behavior for near-term and far-term dates
- Test station closure fallback to neighboring stations

**External system updates:**
- None for this backend change (routing logic internal to service)