Function bevy_internal::utils::petgraph::algo::bellman_ford::find_negative_cycle

pub fn find_negative_cycle<G>(
    g: G,
    source: <G as GraphBase>::NodeId
) -> Option<Vec<<G as GraphBase>::NodeId>>
where
    G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable + Visitable,
    <G as Data>::EdgeWeight: FloatMeasure,

[Generic] Find the path of a negative cycle reachable from node source.

Using the find_negative_cycle; will search the Graph for negative cycles using Bellman–Ford algorithm. If no negative cycle is found the function will return None.

If a negative cycle is found from source, return one vec with a path of NodeIds.

The time complexity of this algorithm should be the same as the Bellman-Ford (O(|V|·|E|)).

Example

use petgraph::Graph;
use petgraph::algo::find_negative_cycle;
use petgraph::prelude::*;

let graph_with_neg_cycle = Graph::<(), f32, Directed>::from_edges(&[
        (0, 1, 1.),
        (0, 2, 1.),
        (0, 3, 1.),
        (1, 3, 1.),
        (2, 1, 1.),
        (3, 2, -3.),
]);

let path = find_negative_cycle(&graph_with_neg_cycle, NodeIndex::new(0));
assert_eq!(
    path,
    Some([NodeIndex::new(1), NodeIndex::new(3), NodeIndex::new(2)].to_vec())
);