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 graph weights 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)]);