Function metric_closure

pub fn metric_closure<G, F, E>(
    graph: G,
    weight_fn: F,
) -> Result<Option<StableGraph<G::NodeId, (f64, Vec<usize>), Undirected>>, E>
where
    G: NodeIndexable + EdgeIndexable + Sync + EdgeCount + NodeCount + Visitable + IntoNodeReferences + IntoEdges + GraphProp<EdgeType = Undirected>,
    G::NodeId: Eq + Hash + NodeRef + Send,
    G::EdgeId: Eq + Hash + Send,
    G::NodeWeight: Clone,
    F: FnMut(G::EdgeRef) -> Result<f64, E>,

Return the metric closure of a graph

The metric closure of a graph is the complete graph in which each edge is weighted by the shortest path distance between the nodes in the graph.

Arguments: graph: The input graph to compute the metric closure for weight_fn: A callable weight function that will be passed an edge reference for each edge in the graph and it is expected to return a Result<f64> which if it doesn’t error represents the weight of that edge. default_weight: A blind callable that returns a default weight to use for edges added to the output

Returns a StableGraph with the input graph node ids for node weights and edge weights with a tuple of the numeric weight (found via weight_fn) and the path. The output will be None if graph is disconnected.

Example

use std::convert::Infallible;

use rustworkx_core::petgraph::Graph;
use rustworkx_core::petgraph::Undirected;
use rustworkx_core::petgraph::graph::EdgeReference;
use rustworkx_core::petgraph::visit::{IntoEdgeReferences, EdgeRef};

use rustworkx_core::steiner_tree::metric_closure;

let input_graph = Graph::<(), u8, Undirected>::from_edges(&[
    (0, 1, 10),
    (1, 2, 10),
    (2, 3, 10),
    (3, 4, 10),
    (4, 5, 10),
    (1, 6, 1),
    (6, 4, 1),
]);

let weight_fn = |e: EdgeReference<u8>| -> Result<f64, Infallible> {
   Ok(*e.weight() as f64)
};

let closure = metric_closure(&input_graph, weight_fn).unwrap().unwrap();
let mut output_edge_list: Vec<(usize, usize, (f64, Vec<usize>))> = closure.edge_references().map(|edge| (edge.source().index(), edge.target().index(), edge.weight().clone())).collect();
let mut expected_edges: Vec<(usize, usize, (f64, Vec<usize>))> = vec![
    (0, 1, (10.0, vec![0, 1])),
    (0, 2, (20.0, vec![0, 1, 2])),
    (0, 3, (22.0, vec![0, 1, 6, 4, 3])),
    (0, 4, (12.0, vec![0, 1, 6, 4])),
    (0, 5, (22.0, vec![0, 1, 6, 4, 5])),
    (0, 6, (11.0, vec![0, 1, 6])),
    (1, 2, (10.0, vec![1, 2])),
    (1, 3, (12.0, vec![1, 6, 4, 3])),
    (1, 4, (2.0, vec![1, 6, 4])),
    (1, 5, (12.0, vec![1, 6, 4, 5])),
    (1, 6, (1.0, vec![1, 6])),
    (2, 3, (10.0, vec![2, 3])),
    (2, 4, (12.0, vec![2, 1, 6, 4])),
    (2, 5, (22.0, vec![2, 1, 6, 4, 5])),
    (2, 6, (11.0, vec![2, 1, 6])),
    (3, 4, (10.0, vec![3, 4])),
    (3, 5, (20.0, vec![3, 4, 5])),
    (3, 6, (11.0, vec![3, 4, 6])),
    (4, 5, (10.0, vec![4, 5])),
    (4, 6, (1.0, vec![4, 6])),
    (5, 6, (11.0, vec![5, 4, 6])),
];
output_edge_list.sort_by_key(|x| [x.0, x.1]);
expected_edges.sort_by_key(|x| [x.0, x.1]);
assert_eq!(output_edge_list, expected_edges);