Function graphalgs::metrics::weighted_diameter

pub fn weighted_diameter<G, F, K>(graph: G, edge_cost: F) -> Option<K>where
    G: IntoEdgeReferences + IntoNodeIdentifiers + NodeIndexable + NodeCount,
    F: FnMut(G::EdgeRef) -> K,
    K: FloatMeasure,

Weighted graph diameter.

Calculate the diameter of the graph given the edge weights. The function is based on the Floyd–Warshall algorithm and has a time complexity of O(|V|^3). So if edge weights is not important it is better to use diameter() function.

Arguments

• graph: weighted graph.
• edge_cost: closure that returns weight of a particular edge.

Returns

• Some: the diameter of the graph.
• None: if the graph contains a negative cycle or has no vertices.

Examples

use graphalgs::metrics::weighted_diameter;
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_diameter(&graph, |edge| *edge.weight()), 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_diameter(&graph, |edge| *edge.weight()), None);