Struct NegCycleFinder

Source

pub struct NegCycleFinder<'a, V, D> {
    pub digraph: &'a DiGraph<V, D>,
    pub pred: HashMap<NodeIndex, (NodeIndex, EdgeReference<'a, D>)>,
}

Expand description

The NegCycleFinder struct is used to find negative cycles in a directed graph.

Properties:

digraph: The digraph property is a reference to a directed graph (DiGraph) that the NegCycleFinder is operating on. It is annotated with a lifetime 'a, indicating that the reference is valid for a certain scope.
pred: The pred property is a HashMap that maps a NodeIndex to a tuple containing the previous node index and an EdgeReference. This is used to keep track of the predecessor node and the edge that leads to that node during the process of finding negative cycles in a directed graph

Fields§

§digraph: &'a DiGraph<V, D>§pred: HashMap<NodeIndex, (NodeIndex, EdgeReference<'a, D>)>

Implementations§

Source §

impl<'a, V, D> NegCycleFinder<'a, V, D>
where D: Add<Output = D> + PartialOrd + Copy,

Source

pub fn new(digraph: &'a DiGraph<V, D>) -> Self

The new function creates a new NegCycleFinder object with an empty predecessor map.

Arguments:

digraph: A reference to a directed graph (DiGraph) that the NegCycleFinder will operate on.

Returns:

The new function is returning an instance of the NegCycleFinder<V, D> struct. Creates a new NegCycleFinder<V, D>.

Source

pub fn find_cycle(&self) -> Option<NodeIndex>

The find_cycle function in Rust returns the first node in a cycle found in a directed graph.

Returns:

The function find_cycle returns an Option<NodeIndex>.

Source

pub fn relax<F>(&mut self, dist: &mut [D], get_weight: F) -> bool
where F: Fn(EdgeReference<'_, D>) -> D,

The relax function updates the distances between nodes in a graph based on the weights of the edges, and returns a boolean indicating whether any distances were changed.

Arguments:

dist: dist is a mutable reference to a slice of type D. It represents the distances from a source node to each node in a graph.
get_weight: The get_weight parameter is a closure that takes an EdgeReference<D> as input and returns a value of type D. This closure is used to calculate the weight of each edge in the graph. The EdgeReference<D> represents a reference to an edge in the graph, and

Returns:

a boolean value.

Source

pub fn howard<F>( &mut self, dist: &mut [D], get_weight: F, ) -> Option<Vec<EdgeReference<'a, D>>>
where F: Fn(EdgeReference<'_, D>) -> D,

The howard function implements Howard’s algorithm for finding negative cycles in a directed graph.

Arguments:

dist: dist is a mutable reference to an array of type D. This array is used to store the distances from the source vertex to each vertex in the graph. The algorithm will update the distances during the execution.
get_weight: get_weight is a closure that takes an EdgeReference<D> and returns the weight of that edge. The howard function uses this closure to get the weight of each edge in the graph.

Returns:

The howard function returns an Option<Vec<EdgeReference<'a, D>>>. Howard’s algorithm for finding negative cycles

§Examples

use petgraph::prelude::*;
use netoptim_rs::neg_cycle::NegCycleFinder;
let digraph = DiGraph::<(), i32>::from_edges([
    (0, 1, 1),
    (0, 2, 1),
    (0, 3, 1),
    (1, 3, 1),
    (2, 1, 1),
    (3, 2, -3),
]);
let mut ncf = NegCycleFinder::new(&digraph);
let mut dist = [0, 0, 0, 0];
let result = ncf.howard(&mut dist, |e| { *e.weight()});
assert!(result.is_some());