netoptim_rs/
parametric.rs

1// use std::collections::HashMap;
2// use std::cmp::Ordering;
3use std::hash::Hash;
4use std::ops::Add;
5use std::ops::Div;
6use std::ops::Mul;
7use std::ops::Neg;
8use std::ops::Sub;
9
10use petgraph::graph::{DiGraph, EdgeReference};
11// use petgraph::prelude::*;
12// use petgraph::visit::EdgeRef;
13// use petgraph::visit::IntoNodeIdentifiers;
14// use petgraph::Direction;
15
16// use num::traits::Float;
17use num::traits::Inv;
18use num::traits::One;
19use num::traits::Zero;
20
21use crate::neg_cycle::NegCycleFinder;
22
23/// The `ParametricAPI` trait defines two methods: `distance` and `zero_cancel`.
24pub trait ParametricAPI<E, R>
25where
26    R: Copy + PartialOrd,
27    E: Clone,
28{
29    fn distance(&self, ratio: &R, edge: &EdgeReference<R>) -> R;
30    fn zero_cancel(&self, cycle: &[EdgeReference<R>]) -> R;
31}
32
33/// The `MaxParametricSolver` struct is a generic type that takes in parameters `V`, `R`, and `P` and
34/// contains a `NegCycleFinder` and `omega` of type `P`.
35///
36/// Properties:
37///
38/// * `ncf`: NegCycleFinder is a struct that is used to find negative cycles in a graph. It takes three
39///             type parameters: 'a, V, and R. 'a represents the lifetime of the struct, V represents the type of
40///             the vertices in the graph, and R represents the type of the weights or
41/// * `omega`: The `omega` property is of type `P`, which is a generic type parameter that implements
42///             the `ParametricAPI` trait. This trait is not defined in the code snippet you provided, so it is
43///             likely defined elsewhere in the codebase.
44#[derive(Debug)]
45pub struct MaxParametricSolver<'a, V, R, P>
46where
47    R: Copy
48        + PartialOrd
49        + Add<Output = R>
50        + Sub<Output = R>
51        + Mul<Output = R>
52        + Div<Output = R>
53        + Neg<Output = R>
54        + Inv<Output = R>,
55    V: Eq + Hash + Clone,
56    P: ParametricAPI<V, R>,
57{
58    ncf: NegCycleFinder<'a, V, R>,
59    omega: P,
60}
61
62impl<'a, V, R, P> MaxParametricSolver<'a, V, R, P>
63where
64    R: Copy
65        + PartialOrd
66        + Zero
67        + One
68        + Add<Output = R>
69        + Sub<Output = R>
70        + Mul<Output = R>
71        + Div<Output = R>
72        + Neg<Output = R>
73        + Inv<Output = R>,
74    V: Eq + Hash + Clone,
75    P: ParametricAPI<V, R>,
76{
77    /// The function creates a new instance of a struct with a given directed graph and a value.
78    ///
79    /// Arguments:
80    ///
81    /// * `grph`: The `grph` parameter is a reference to a directed graph (`DiGraph`) with vertices of
82    ///             type `V` and edges of type `R`.
83    /// * `omega`: The `omega` parameter is of type `P`. It represents some value or parameter that is
84    ///             used in the implementation of the `new` function. The specific meaning or purpose of `omega`
85    ///             would depend on the context and the code that uses this function.
86    ///
87    /// Returns:
88    ///
89    /// The `new` function is returning an instance of the struct that it is defined in.
90    pub fn new(grph: &'a DiGraph<V, R>, omega: P) -> Self {
91        Self {
92            ncf: NegCycleFinder::new(grph),
93            omega,
94        }
95    }
96
97    /// The function `run` finds the minimum ratio and corresponding cycle in a given graph.
98    ///
99    /// Arguments:
100    ///
101    /// * `dist`: `dist` is a mutable reference to a slice of type `R`. It represents a distance matrix
102    ///             or array, where `R` is the type of the elements in the matrix.
103    /// * `ratio`: The `ratio` parameter is a mutable reference to a value of type `R`. It represents
104    ///             the current ratio value that is being used in the algorithm. The algorithm will update this
105    ///             value if it finds a smaller ratio during its execution.
106    ///
107    /// Returns:
108    ///
109    /// a vector of `EdgeReference<R>`.
110    pub fn run(&mut self, dist: &mut [R], ratio: &mut R) -> Vec<EdgeReference<R>> {
111        let mut r_min = *ratio;
112        let mut c_min = Vec::<EdgeReference<R>>::new();
113        let mut cycle = Vec::<EdgeReference<R>>::new();
114        loop {
115            if let Some(ci) = self.ncf.howard(dist, |e| self.omega.distance(ratio, &e)) {
116                let ri = self.omega.zero_cancel(&ci);
117                if r_min > ri {
118                    r_min = ri;
119                    c_min = ci;
120                }
121            }
122            if r_min >= *ratio {
123                break;
124            }
125            cycle.clone_from(&c_min);
126            *ratio = r_min;
127        }
128        cycle
129    }
130}
netoptim_rs/parametric.rs

netoptim_rs/
parametric.rs
