Function rs_graph::mst::worstout

pub fn worstout<'a, 'b, G, W, F>(g: &'a G, weights: F) -> Vec<G::Edge<'a>>where
    G: IndexGraph,
    W: Copy + Ord,
    F: Fn(G::Edge<'a>) -> 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::*};
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 tree = worstout(&graph, |e| weights[graph.edge_id(e)]);

// check the results
let mut sum = 0;
for &e in &tree { sum += weights[graph.edge_id(e)]; }
assert_eq!(sum, 38);

let mut tree = tree.into_iter()
     .map(|e| graph.enodes(e))
     .map(|(u,v)| (graph.node_id(u), graph.node_id(v)))
     .map(|(u,v)| if u > v { (v,u) } else { (u,v) })
     .collect::<Vec<_>>();
tree.sort();

assert_eq!(tree, vec![(a,d), (a,h), (b,c), (c,f), (c,h), (d,e), (e,i), (f,g), (h,j)]);