Function rs_graph::mst::worstout

pub fn worstout<'a, 'b, G, W>(
    g: &'a G, 
    weights: &EdgeSlice<'a, 'b, G, W>
) -> Vec<G::Edge> where
    G: IndexGraph<'a>,
    W: Copy + Ord, 

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, Builder, EdgeVec};
use rs_graph::mst::worstout;

let mut g = Net::new();
let mut weights: Vec<usize> = vec![];

let nodes = g.add_nodes(10);
for &(u,v,w) in [(0,1,4), (0,2,1), (0,3,4),
                 (1,2,5), (1,4,9), (1,5,9), (1,7,7),
                 (2,3,3), (2,7,9),
                 (3,7,10), (3,9,18),
                 (4,5,2), (4,6,4), (4,8,6),
                 (5,6,2), (5,7,8),
                 (6,7,9), (6,8,3), (6,9,9),
                 (7,9,8),
                 (8,9,9)].iter()
{
    g.add_edge(nodes[u], nodes[v]);
    weights.push(w);
}
let weights = EdgeVec::from_vec(&g, weights);

// run the algorithm
let tree = worstout(&g, &weights.as_slice());

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