Function rs_graph::mst::prim

pub fn prim<'a, G, W, F>(g: &'a G, weights: F) -> Vec<G::Edge> where
    G: IndexGraph<'a>,
    G::Node: Hash,
    W: NumAssign + Ord + Copy,
    F: Fn(G::Edge) -> W, 

Run Prim's algorithm to solve the Minimum Spanning Tree problem on a graph.

• g is the undirected graph weights the edge weights

If the graph is not connected, the returned vector only spans one component. This can easily be verifyed by checking the size of the returned vector.

Example

use rs_graph::{Net, traits::*, EdgeVec};
use rs_graph::mst::prim;
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 = prim(&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)]);