Function petgraph::algo::bellman_ford::find_negative_cycle [−][src]
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()) );