Function graphalgs::metrics::weighted_center
source · pub fn weighted_center<G, F, K>(graph: G, edge_cost: F) -> Vec<G::NodeId>where
G: IntoEdgeReferences + IntoNodeIdentifiers + NodeIndexable + NodeCount,
F: FnMut(G::EdgeRef) -> K,
K: FloatMeasure,
Expand description
Center of a weighted graph.
Calculate the central nodes 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 center()
function.
Arguments
graph
: weighted graph.edge_cost
: closure that returns weight of a particular edge.
Returns
- A vector of indices of central vertices.
vec![]
: if the graph contains a negative cycle.
use graphalgs::metrics::weighted_center;
use petgraph::Graph;
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), (3, 0, 3.0),
]);
assert_eq!(weighted_center(&graph, |edge| *edge.weight()), vec![1.into()]);
// Negative cycle.
let graph = Graph::<(), f32>::from_edges(&[
(0, 1, 2.0), (1, 2, 2.0), (2, 0, -10.0)
]);
assert_eq!(weighted_center(&graph, |edge| *edge.weight()), vec![]);