Struct MaxParametricSolver 

pub struct MaxParametricSolver<'a, V, R, P>
where
    R: Copy + PartialOrd + Add<Output = R> + Sub<Output = R> + Mul<Output = R> + Div<Output = R> + Neg<Output = R> + Inv<Output = R>,
    V: Eq + Hash + Clone,
    P: ParametricAPI<V, R>,
{ /* private fields */ }

Maximum parametric shortest path solver.

$$ d_j(\lambda) = \min_{k} \big( d_k(\lambda) + \text{cost}(k, j, \lambda) \big) $$

Finds the minimum ratio cycle in a directed graph using Howard’s algorithm for negative cycle detection.

Implementations

impl<'a, V, R, P> MaxParametricSolver<'a, V, R, P>

where R: Copy + PartialOrd + Zero + One + Add<Output = R> + Sub<Output = R> + Mul<Output = R> + Div<Output = R> + Neg<Output = R> + Inv<Output = R>, V: Eq + Hash + Clone, P: ParametricAPI<V, R>,

pub fn new(gra: &'a DiGraph<V, R>, omega: P) -> Self

pub fn run( &mut self, dist: &mut [R], ratio: &mut R, ) -> Vec<EdgeReference<'a, R>>

The function run finds the minimum ratio and corresponding cycle in a given graph.

$$ r^* = \min_{C \in \text{cycles}} \frac{\sum_{(u,v) \in C} w_{uv}}{|C|} $$

Arguments:

• dist: dist is a mutable reference to a slice of type R. It represents a distance matrix or array, where R is the type of the elements in the matrix.
• ratio: The ratio parameter is a mutable reference to a value of type R. It represents the current ratio value that is being used in the algorithm. The algorithm will update this value if it finds a smaller ratio during its execution.

Returns:

a vector of EdgeReference<R>.

Example

use petgraph::graph::DiGraph;
use petgraph::prelude::*;
use num::rational::Ratio;
use netoptim_rs::parametric::{MaxParametricSolver, ParametricAPI};
use petgraph::graph::EdgeReference;

struct TestParametricAPI;

impl ParametricAPI<(), Ratio<i32>> for TestParametricAPI {
    fn distance(&self, ratio: &Ratio<i32>, edge: &EdgeReference<Ratio<i32>>) -> Ratio<i32> {
        *edge.weight() - *ratio
    }

    fn zero_cancel(&self, cycle: &[EdgeReference<Ratio<i32>>]) -> Ratio<i32> {
        let mut sum_a = Ratio::new(0, 1);
        let mut sum_b = Ratio::new(0, 1);
        for edge in cycle {
            sum_a += *edge.weight();
            sum_b += Ratio::new(1, 1);
        }
        sum_a / sum_b
    }
}

let digraph = DiGraph::<(), Ratio<i32>>::from_edges(&[
    (0, 1, Ratio::new(1, 1)),
    (1, 2, Ratio::new(1, 1)),
    (2, 0, Ratio::new(-3, 1)),
]);

let mut solver = MaxParametricSolver::new(&digraph, TestParametricAPI);
let mut dist = [Ratio::new(0, 1), Ratio::new(0, 1), Ratio::new(0, 1)];
let mut ratio = Ratio::new(0, 1);

let cycle = solver.run(&mut dist, &mut ratio);
assert!(!cycle.is_empty());
assert_eq!(ratio, Ratio::new(-1, 3));

Trait Implementations

impl<'a, V, R, P> Debug for MaxParametricSolver<'a, V, R, P>

where R: Copy + PartialOrd + Add<Output = R> + Sub<Output = R> + Mul<Output = R> + Div<Output = R> + Neg<Output = R> + Inv<Output = R> + Debug, V: Eq + Hash + Clone + Debug, P: ParametricAPI<V, R> + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.