lling-llang 0.1.0

# Phase 1: Foundation Algorithms

**Branch**: `feature/shortest-distance`
**Base Commit**: `c013a29` (master)
**Started**: 2025-12-27

## Overview

Phase 1 implements the core shortest-distance algorithms required by all subsequent phases.
These are foundational algorithms from Mohri's work on weighted automata.

### Components

1. **Queue Disciplines**: Different traversal strategies for shortest-distance
   - `FifoQueue`: General-purpose, k-closed semirings
   - `TopologicalQueue`: Acyclic graphs, O(|Q| + |E|)
   - `ShortestFirstQueue`: Dijkstra-style, tropical semiring

2. **Gen-Single-Source Shortest-Distance**: Generalized relaxation algorithm
   - Parameterized by queue discipline
   - Complexity varies by queue choice and graph structure

3. **Gen-All-Pairs Shortest-Distance**: Floyd-Warshall generalization
   - For complete semirings
   - Complexity: Θ(|Q|³(T⊕ + T⊗ + T*))

---

## 1.1 Queue Disciplines

**Date**: 2025-12-27
**Status**: COMPLETED

### Hypothesis

Queue discipline selection significantly impacts shortest-distance performance:

| Queue Type | Best For | Expected Complexity |
|------------|----------|---------------------|
| TopologicalQueue | Acyclic graphs | O(|Q| + |E|) |
| ShortestFirstQueue | Tropical semiring | O(|E| + |Q| log |Q|) |
| FifoQueue | General k-closed | O(|Q|² + |Q||E|) worst case |

### Design

```rust
/// Trait for queue disciplines in shortest-distance algorithms.
pub trait ShortestDistanceQueue<W: Semiring> {
    fn with_capacity(capacity: usize) -> Self;
    fn insert(&mut self, state: StateId, distance: &W);
    fn pop(&mut self) -> Option<StateId>;
    fn update(&mut self, state: StateId, distance: &W);
    fn is_empty(&self) -> bool;
    fn len(&self) -> usize;
    fn contains(&self, state: StateId) -> bool;
    fn clear(&mut self);
}
```

### Implementation

**Files created**:
- `src/algorithms/mod.rs` (~45 lines)
- `src/algorithms/queue.rs` (~794 lines)

**Key implementations**:
- `FifoQueue`: VecDeque-based, O(1) insert/pop, O(n) contains
- `TopologicalQueue`: Topological order traversal with FIFO fallback
- `ShortestFirstQueue`: BinaryHeap-based priority queue, O(log n) operations
- `AutoQueue`: Automatic queue selection based on graph properties

---

## 1.2 Gen-Single-Source Shortest-Distance

**Date**: 2025-12-27
**Status**: COMPLETED

### Hypothesis

Generalized single-source shortest-distance computes minimum weight from start state
to all reachable states. Performance depends on queue discipline:

- **Acyclic + TopologicalQueue**: O(|Q| + (T⊕ + T⊗)|E|)
- **Tropical + ShortestFirstQueue**: O(|E| + |Q| log |Q|)
- **General + FifoQueue**: O(C·|E|) where C is path length bound

### Implementation

**Files created**:
- `src/algorithms/shortest_distance.rs` (~670 lines)

**Key functions**:
- `single_source_shortest_distance()` - Main API with config
- `single_source_shortest_distance_with_queue()` - Low-level with explicit queue
- `reverse_shortest_distance()` - Distances to final states
- `shortest_distance_to_final()` - Total weight to any final state

---

## 1.3 Gen-All-Pairs Shortest-Distance

**Date**: 2025-12-27
**Status**: COMPLETED

### Hypothesis

All-pairs shortest distance computes minimum weight between every pair of states.
Floyd-Warshall generalization for complete semirings.

**Complexity**: Θ(|Q|³(T⊕ + T⊗ + T*))
**Space**: Θ(|Q|²)

### Implementation

**Key function**:
- `all_pairs_shortest_distance()` - Floyd-Warshall generalization

**Requires**: `StarSemiring` for cycle handling via star() operation.

---

## Benchmark Results

**Date**: 2025-12-27
**Configuration**: CPU governor=performance, taskset -c 0-3, 100 samples, 3s warmup

### Single-Source Shortest Distance

#### Linear WFST (chain: 0 → 1 → 2 → ... → n)

| Size | Auto (FifoQueue) | Topological | ShortestFirst |
|------|------------------|-------------|---------------|
| 10 | 360 ns | 362 ns | 527 ns |
| 50 | 1.38 µs | 1.45 µs | 2.55 µs |
| 100 | 2.80 µs | 2.78 µs | 4.84 µs |
| 200 | 5.69 µs | 5.63 µs | 9.83 µs |

**Observation**: FIFO and Topological queues perform similarly for linear chains.
ShortestFirst has ~1.7x overhead due to BinaryHeap operations.

#### Diamond WFST (branching factor 3)

| Size | Auto (FifoQueue) | Topological |
|------|------------------|-------------|
| 10 | 538 ns | 491 ns |
| 50 | 2.08 µs | 2.07 µs |
| 100 | 3.73 µs | 3.75 µs |
| 200 | 7.51 µs | 7.62 µs |

**Observation**: TopologicalQueue shows slight advantage at small sizes.
Both scale linearly with graph size, confirming O(|Q| + |E|) complexity.

### All-Pairs Shortest Distance

| Size | Linear | Diamond (branching 3) |
|------|--------|----------------------|
| 5 | 347 ns | 383 ns |
| 10 | 1.49 µs | 1.51 µs |
| 20 | 7.26 µs | 7.40 µs |
| 30 | 19.39 µs | 19.47 µs |

**Observation**: Confirms O(n³) scaling. 30³/10³ = 27x theoretical, actual ~13x
(due to constant factors and cache effects at larger sizes).

### Queue Discipline Comparison (Diamond, 50 positions, varying branching)

| Branching | FifoQueue | TopologicalQueue | ShortestFirstQueue |
|-----------|-----------|------------------|-------------------|
| 2 | 1.75 µs | 1.69 µs | 2.56 µs |
| 4 | 2.17 µs | 2.21 µs | 2.86 µs |
| 8 | 3.43 µs | 3.40 µs | 3.47 µs |

**Observation**: As edge density increases, all queues converge in performance.
TopologicalQueue has slight advantage at low density; ShortestFirst overhead
becomes negligible at high density.

### Analysis Summary

1. **TopologicalQueue** is optimal for acyclic graphs (slight advantage at small sizes)
2. **FifoQueue** is a reliable general-purpose choice
3. **ShortestFirstQueue** has heap overhead (~1.5-1.7x) that diminishes with density
4. All algorithms show expected complexity scaling
5. **Recommendation**: Use `ShortestDistanceConfig::acyclic()` for known acyclic graphs

### Result: ACCEPTED

All implementations show expected algorithmic complexity and reasonable constant factors.
The queue discipline selection API allows users to optimize for their specific use case.

---