netoptim_rs/
network_oracle.rs

1use crate::neg_cycle::NegCycleFinder;
2use num::traits::ToPrimitive;
3use petgraph::graph::{DiGraph, EdgeReference};
4
5pub type Cut<X> = (X, f64);
6
7/// Newtype wrapper around `Vec<f64>` so we can implement `Neg` and `Sum`
8/// (orphan rules prevent direct impls on `Vec<f64>`).
9#[derive(Clone, Debug, PartialEq)]
10pub struct GradVec(pub Vec<f64>);
11
12impl std::ops::Neg for GradVec {
13    type Output = GradVec;
14    fn neg(self) -> GradVec {
15        GradVec(self.0.into_iter().map(|x| -x).collect())
16    }
17}
18
19impl std::iter::Sum<GradVec> for GradVec {
20    fn sum<I>(iter: I) -> Self
21    where
22        I: Iterator<Item = GradVec>,
23    {
24        let mut result = Vec::new();
25        for v in iter {
26            if result.is_empty() {
27                result = v.0;
28            } else {
29                for (i, val) in v.0.iter().enumerate() {
30                    result[i] += val;
31                }
32            }
33        }
34        GradVec(result)
35    }
36}
37
38pub trait OracleFn<D> {
39    type X: Clone;
40
41    fn eval(&self, edge: &EdgeReference<D>, x: &Self::X) -> D;
42    fn grad(&self, edge: &EdgeReference<D>, x: &Self::X) -> Self::X;
43    fn update(&mut self, _gamma: &D) {}
44}
45
46pub struct NetworkOracle<'a, V, D, F>
47where
48    D: std::cmp::PartialOrd,
49{
50    #[allow(dead_code)]
51    gra: &'a DiGraph<V, D>,
52    potential: Vec<D>,
53    ncf: NegCycleFinder<'a, V, D>,
54    oracle: F,
55}
56
57impl<'a, V, D, F> NetworkOracle<'a, V, D, F>
58where
59    D: std::ops::Add<Output = D> + std::cmp::PartialOrd + Copy + 'a,
60    F: OracleFn<D>,
61{
62    pub fn new(gra: &'a DiGraph<V, D>, potential: Vec<D>, oracle: F) -> Self {
63        let ncf = NegCycleFinder::new(gra);
64        NetworkOracle {
65            gra,
66            potential,
67            ncf,
68            oracle,
69        }
70    }
71
72    pub fn update(&mut self, gamma: &D) {
73        self.oracle.update(gamma);
74    }
75
76    pub fn assess_feas(&mut self, x: &F::X) -> Option<Cut<F::X>>
77    where
78        F::X: std::ops::Neg<Output = F::X>,
79        F::X: std::iter::Sum<F::X>,
80        D: ToPrimitive,
81    {
82        let get_weight = |edge: EdgeReference<D>| self.oracle.eval(&edge, x);
83
84        if let Some(cycle) = self.ncf.howard(&mut self.potential, get_weight) {
85            let f: f64 = -cycle
86                .iter()
87                .map(|edge| self.oracle.eval(edge, x))
88                .filter_map(|d| d.to_f64())
89                .sum::<f64>();
90            let g: F::X = -cycle
91                .iter()
92                .map(|edge| self.oracle.grad(edge, x))
93                .sum::<F::X>();
94            return Some((g, f));
95        }
96        None
97    }
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103    use num::rational::Ratio;
104
105    struct TestOracle;
106
107    impl OracleFn<Ratio<i32>> for TestOracle {
108        type X = Ratio<i32>;
109
110        fn eval(&self, edge: &EdgeReference<Ratio<i32>>, x: &Ratio<i32>) -> Ratio<i32> {
111            *edge.weight() - *x
112        }
113
114        fn grad(&self, _edge: &EdgeReference<Ratio<i32>>, _x: &Ratio<i32>) -> Ratio<i32> {
115            Ratio::new(-1, 1)
116        }
117    }
118
119    #[test]
120    fn test_network_oracle_feasible() {
121        let digraph = DiGraph::<(), Ratio<i32>>::from_edges([
122            (0, 1, Ratio::new(1, 1)),
123            (1, 2, Ratio::new(1, 1)),
124        ]);
125        let potential = vec![Ratio::new(0, 1), Ratio::new(0, 1), Ratio::new(0, 1)];
126        let mut oracle = NetworkOracle::new(&digraph, potential, TestOracle);
127        let x = Ratio::new(0, 1);
128        let result = oracle.assess_feas(&x);
129        assert!(result.is_none());
130    }
131
132    #[test]
133    fn test_network_oracle_infeasible() {
134        let digraph = DiGraph::<(), Ratio<i32>>::from_edges([
135            (0, 1, Ratio::new(1, 1)),
136            (1, 2, Ratio::new(1, 1)),
137            (2, 0, Ratio::new(-3, 1)),
138        ]);
139        let potential = vec![Ratio::new(0, 1), Ratio::new(0, 1), Ratio::new(0, 1)];
140        let mut oracle = NetworkOracle::new(&digraph, potential, TestOracle);
141        let x = Ratio::new(0, 1);
142        let result = oracle.assess_feas(&x);
143        assert!(result.is_some());
144    }
145}
netoptim_rs/network_oracle.rs

netoptim_rs/
network_oracle.rs
