tawasuyu/hifas

1//! `router` — ruteo de presupuesto por el grafo (T9b, §C).
2//!
3//! Cierre de arco honesto: el Laplaciano lineal que en el MVP era un **detector
4//! con falso-positivo** (`H¹ = β₁`) reaparece aquí como un **ruteador de
5//! presupuesto legítimo**. Misma máquina, problema correcto — no detectar
6//! conflictos post-hoc, sino repartir derechos proactivamente sobre el grafo.
7//!
8//! - **Presupuesto** = una 0-cocadena `b` sobre los vértices, con `Σ b_i ≤ S`.
9//! - **Rebalanceo** = un flujo (1-cocadena) que mueve presupuesto por las aristas
10//!   **conservando el total** (`Σ b` invariante ⟹ el certificado se preserva).
11//! - **El Laplaciano rutea**: `diffuse` suaviza el presupuesto (paso de calor,
12//!   reduce la varianza); `rebalance_to` localiza el flujo mínimo que repone a
13//!   una réplica seca desde vecinos con excedente — edge-local, no consenso global.
14//!
15//! Para presupuesto **escalar** basta el Laplaciano de grafo ordinario. El
16//! Laplaciano de haces (Hansen–Ghrist) solo hace falta si los presupuestos son
17//! vectoriales (multi-recurso) — ver TODO en `diffuse` y §H de `T9.md`.
18
19use crate::escrow::Budget;
20use crate::nerve::Nerve;
21
22/// Rutea un presupuesto mutable sobre el grafo del nervio.
23pub struct BudgetRouter<'a> {
24    nerve: &'a Nerve,
25    budget: &'a mut Budget,
26}
27
28impl<'a> BudgetRouter<'a> {
29    /// Envuelve un nervio y un presupuesto para rutearlo.
30    pub fn new(nerve: &'a Nerve, budget: &'a mut Budget) -> Self {
31        Self { nerve, budget }
32    }
33
34    /// Total de presupuesto `Σ b` (la cantidad conservada; el certificado de §B).
35    pub fn total(&self) -> i64 {
36        self.budget.per_replica.iter().sum()
37    }
38
39    /// Flujo **mínimo** que repone `deficit` a la réplica `r` tomándolo de sus
40    /// vecinas con excedente. Devuelve los movimientos `(desde, hacia, monto)`.
41    /// Conserva `Σ b` (solo mueve) y solo toca aristas **adyacentes a `r`**.
42    ///
43    /// Si las vecinas directas no alcanzan, cubre lo posible (el resto quedaría
44    /// para un rebalanceo multi-salto o `diffuse` previo).
45    pub fn rebalance_to(&mut self, r: usize, deficit: i64) -> Vec<(usize, usize, i64)> {
46        let mut moves = Vec::new();
47        let mut need = deficit.max(0);
48        for j in self.nerve.neighbors(r) {
49            if need == 0 {
50                break;
51            }
52            let avail = self.budget.per_replica[j].max(0);
53            let amount = avail.min(need);
54            if amount > 0 {
55                self.budget.per_replica[j] -= amount;
56                self.budget.per_replica[r] += amount;
57                moves.push((j, r, amount));
58                need -= amount;
59            }
60        }
61        moves
62    }
63
64    /// Un paso de difusión de Laplaciano que **suaviza** el presupuesto
65    /// conservando `Σ b`. Por cada arista mueve la mitad (entera) de la diferencia
66    /// del extremo alto al bajo: un promediado por pares que nunca aumenta la
67    /// varianza y mantiene los presupuestos no negativos.
68    ///
69    /// TODO(multi-recurso): para presupuestos vectoriales, sustituir este paso
70    /// escalar por el Laplaciano de haces (§C, §H de `T9.md`).
71    pub fn diffuse(&mut self) {
72        for (a, b) in self.nerve.edges() {
73            let d = self.budget.per_replica[a] - self.budget.per_replica[b];
74            let m = d / 2; // trunca hacia cero; mueve del alto al bajo en ambos signos
75            self.budget.per_replica[a] -= m;
76            self.budget.per_replica[b] += m;
77        }
78    }
79}
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84    use proptest::prelude::*;
85
86    fn suma(b: &Budget) -> i64 {
87        b.per_replica.iter().sum()
88    }
89
90    /// Σ b² es un proxy de la varianza cuando `Σ b` está fijo: menor Σ b² ⟺ menor
91    /// varianza. Lo usamos para comprobar que `diffuse` no la aumenta.
92    fn suma_de_cuadrados(b: &Budget) -> i128 {
93        b.per_replica.iter().map(|&x| (x as i128) * (x as i128)).sum()
94    }
95
96    #[test]
97    fn rebalanceo_conserva_el_total_y_repone() {
98        // Camino 0—1—2; la réplica 1 está seca y pide 8.
99        let nerve = Nerve::from_edges(3, &[(0, 1), (1, 2)]);
100        let mut budget = Budget::new(vec![5, 0, 5]);
101        let antes = suma(&budget);
102
103        let moves = BudgetRouter::new(&nerve, &mut budget).rebalance_to(1, 8);
104        assert_eq!(suma(&budget), antes, "el rebalanceo conserva Σ b");
105        assert_eq!(budget.remaining(1), 8, "la réplica seca queda repuesta");
106        // Solo movió desde vecinas de 1 (0 y 2), nunca desde una no vecina.
107        for (from, to, _) in &moves {
108            assert_eq!(*to, 1);
109            assert!(nerve.neighbors(1).contains(from), "movió desde una no vecina");
110        }
111    }
112
113    #[test]
114    fn rebalanceo_solo_toca_vecinas() {
115        // Estrella: centro 0 con hojas 1,2,3. La hoja 3 NO es vecina de 1.
116        let nerve = Nerve::from_edges(4, &[(0, 1), (0, 2), (0, 3)]);
117        let mut budget = Budget::new(vec![10, 0, 0, 0]);
118        let moves = BudgetRouter::new(&nerve, &mut budget).rebalance_to(1, 5);
119        // La única vecina de 1 es 0; el flujo viene solo de ahí.
120        for (from, _, _) in &moves {
121            assert_eq!(*from, 0, "una hoja no puede reponer a otra hoja directamente");
122        }
123        assert_eq!(budget.remaining(1), 5);
124        assert_eq!(budget.remaining(0), 5);
125    }
126
127    #[test]
128    fn diffuse_no_aumenta_varianza_y_conserva_total() {
129        let nerve = Nerve::from_edges(4, &[(0, 1), (1, 2), (2, 3), (3, 0)]);
130        let mut budget = Budget::new(vec![100, 0, 0, 0]);
131        let antes_sum = suma(&budget);
132        let antes_var = suma_de_cuadrados(&budget);
133
134        BudgetRouter::new(&nerve, &mut budget).diffuse();
135        assert_eq!(suma(&budget), antes_sum, "diffuse conserva Σ b");
136        assert!(suma_de_cuadrados(&budget) <= antes_var, "diffuse no aumenta la varianza");
137        assert!(budget.per_replica.iter().all(|&b| b >= 0), "sigue no negativo");
138    }
139
140    fn nerve_y_budget() -> impl Strategy<Value = (usize, Vec<(usize, usize)>, Vec<i64>)> {
141        (2usize..=6).prop_flat_map(|n| {
142            let arista = (0..n, 0..n).prop_filter("sin lazos", |(a, b)| a != b);
143            let edges = prop::collection::vec(arista, 0..10);
144            let presupuestos = prop::collection::vec(0i64..100, n);
145            (Just(n), edges, presupuestos)
146        })
147    }
148
149    proptest! {
150        /// Conservación e idempotencia del certificado: ni `rebalance_to` ni
151        /// `diffuse` cambian `Σ b`, y `diffuse` nunca aumenta la varianza.
152        #[test]
153        fn ruteo_conserva_total((n, edges, pres) in nerve_y_budget(), objetivo in 0usize..6) {
154            let nerve = Nerve::from_edges(n, &edges);
155            let mut budget = Budget::new(pres);
156            let total = budget.per_replica.iter().sum::<i64>();
157
158            let r = objetivo % n;
159            let moves = BudgetRouter::new(&nerve, &mut budget).rebalance_to(r, 30);
160            prop_assert_eq!(budget.per_replica.iter().sum::<i64>(), total, "rebalance conserva");
161            // Localización: todo movimiento entra a r desde una vecina suya.
162            for (from, to, amount) in &moves {
163                prop_assert_eq!(*to, r);
164                prop_assert!(*amount > 0);
165                prop_assert!(nerve.neighbors(r).contains(from));
166            }
167
168            let var_antes = suma_de_cuadrados(&budget);
169            BudgetRouter::new(&nerve, &mut budget).diffuse();
170            prop_assert_eq!(budget.per_replica.iter().sum::<i64>(), total, "diffuse conserva");
171            prop_assert!(suma_de_cuadrados(&budget) <= var_antes, "diffuse no aumenta varianza");
172            prop_assert!(budget.per_replica.iter().all(|&b| b >= 0));
173        }
174    }
175}