Function petgraph::algo::bellman_ford::find_negative_cycle
source · pub fn find_negative_cycle<G>(g: G, source: G::NodeId) -> Option<Vec<G::NodeId>>where
G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable + Visitable,
G::EdgeWeight: FloatMeasure,
Expand description
[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 NodeId
s.
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())
);