[−][src]Function rs_graph::mst::worstout
pub fn worstout<'a, 'b, G, W, F>(g: &'a G, weights: F) -> Vec<G::Edge> where
G: IndexGraph<'a>,
W: Copy + Ord,
F: Fn(G::Edge) -> W,
Run Worst-Out-Greedy algorithm to solve the Minimum Spanning Tree problem on a graph.
g
is the undirected graphweights
the edge weights
The algorithm actually solved a minimum spanning forest problem in the graph. This can easily be verified by checking the size of the returned vector.
Example
use rs_graph::{Net, traits::*, EdgeVec}; use rs_graph::mst::worstout; use rs_graph::string::{Data, from_ascii}; let Data { graph, weights, nodes } = from_ascii::<Net>(r" ------9----- / \ ---a---9-- --2--b / |\ \ / |\ 4 5 \ c 4 6 / | -7- |\ | \ d---1--e- \ 8 --2--f-3-g \ | \ \| /| | 4 | -9---h---9- | | \ 3 / \ 9 / \ | -10-- -8-- | 9 \ |/ \|/ -i------18------j ").unwrap(); let a = nodes[&'a']; let b = nodes[&'b']; let c = nodes[&'c']; let d = nodes[&'d']; let e = nodes[&'e']; let f = nodes[&'f']; let g = nodes[&'g']; let h = nodes[&'h']; let i = nodes[&'i']; let j = nodes[&'j']; // run the algorithm let weights = EdgeVec::new_from_vec(&graph, weights); let tree = worstout(&graph, |e| weights[e]); // check the results let mut sum = 0; for &e in &tree { sum += weights[e]; } assert_eq!(sum, 38); let mut tree = tree.into_iter() .map(|e| graph.enodes(e)) .map(|(u,v)| if graph.node_id(u) > graph.node_id(v) { (v,u) } else { (u,v) }) .collect::<Vec<_>>(); tree.sort_by_key(|&(u,v)| (graph.node_id(u), graph.node_id(v))); assert_eq!(tree, vec![(a,d), (a,h), (b,c), (c,f), (c,h), (d,e), (e,i), (f,g), (h,j)]);