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.

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(grph: &'a DiGraph<V, R>, omega: P) -> Self

The function creates a new instance of a struct with a given directed graph and a value.

Arguments:

• grph: The grph parameter is a reference to a directed graph (DiGraph) with vertices of type V and edges of type R.
• omega: The omega parameter is of type P. It represents some value or parameter that is used in the implementation of the new function. The specific meaning or purpose of omega would depend on the context and the code that uses this function.

Returns:

The new function is returning an instance of the struct that it is defined in.

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.

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.