Function graphalgs::metrics::weighted_eccentricity
source · pub fn weighted_eccentricity<G>(
graph: G,
start: G::NodeId
) -> Option<G::EdgeWeight>where
G: NodeCount + IntoNodeIdentifiers + IntoEdges + NodeIndexable,
G::EdgeWeight: FloatMeasure,
Expand description
Weighted eccentricity.
Calculate the distance to the node farthest from start
, given the edge weights.
The function is based on the Bellman-Ford algorithm
and has a time complexity of O(|V|*|E|). So if edge weight is not important it is better to use eccentricity()
function.
Arguments
graph
: weighted graph.start
: node whose eccentricity is to be calculated.
Returns
Some(G::EdgeWeight)
: the eccentricity.None
: if graph contains negative cycle.
Examples
use graphalgs::metrics::weighted_eccentricity;
use petgraph::Graph;
let inf = f32::INFINITY;
let graph = Graph::<(), f32>::from_edges(&[
(0, 1, 2.0), (1, 2, 10.0), (1, 3, -5.0),
(3, 2, 2.0), (2, 3, 20.0),
]);
assert_eq!(weighted_eccentricity(&graph, 0.into()), Some(2.0));
assert_eq!(weighted_eccentricity(&graph, 1.into()), Some(inf));
assert_eq!(weighted_eccentricity(&graph, 2.into()), Some(inf));
assert_eq!(weighted_eccentricity(&graph, 3.into()), Some(inf));
// Negative cycle.
let graph = Graph::<(), f32>::from_edges(&[
(0, 1, 2.0), (1, 2, 2.0), (2, 0, -10.0)
]);
assert_eq!(weighted_eccentricity(&graph, 0.into()), None);
assert_eq!(weighted_eccentricity(&graph, 1.into()), None);
assert_eq!(weighted_eccentricity(&graph, 2.into()), None);