1 use petgraph::{algo::min_spanning_tree, dot::Dot, graph::UnGraph, Graph};
2
3 #[test]
mst()4 fn mst() {
5 use petgraph::data::FromElements;
6
7 let mut gr = Graph::<_, _>::new();
8 let a = gr.add_node("A");
9 let b = gr.add_node("B");
10 let c = gr.add_node("C");
11 let d = gr.add_node("D");
12 let e = gr.add_node("E");
13 let f = gr.add_node("F");
14 let g = gr.add_node("G");
15 gr.add_edge(a, b, 7.);
16 gr.add_edge(a, d, 5.);
17 gr.add_edge(d, b, 9.);
18 gr.add_edge(b, c, 8.);
19 gr.add_edge(b, e, 7.);
20 gr.add_edge(c, e, 5.);
21 gr.add_edge(d, e, 15.);
22 gr.add_edge(d, f, 6.);
23 gr.add_edge(f, e, 8.);
24 gr.add_edge(f, g, 11.);
25 gr.add_edge(e, g, 9.);
26
27 // add a disjoint part
28 let h = gr.add_node("H");
29 let i = gr.add_node("I");
30 let j = gr.add_node("J");
31 gr.add_edge(h, i, 1.);
32 gr.add_edge(h, j, 3.);
33 gr.add_edge(i, j, 1.);
34
35 println!("{}", Dot::new(&gr));
36
37 let mst = UnGraph::from_elements(min_spanning_tree(&gr));
38
39 println!("{}", Dot::new(&mst));
40 println!("{:?}", Dot::new(&mst));
41 println!("MST is:\n{:#?}", mst);
42 assert!(mst.node_count() == gr.node_count());
43 // |E| = |N| - 2 because there are two disconnected components.
44 assert!(mst.edge_count() == gr.node_count() - 2);
45
46 // check the exact edges are there
47 assert!(mst.find_edge(a, b).is_some());
48 assert!(mst.find_edge(a, d).is_some());
49 assert!(mst.find_edge(b, e).is_some());
50 assert!(mst.find_edge(e, c).is_some());
51 assert!(mst.find_edge(e, g).is_some());
52 assert!(mst.find_edge(d, f).is_some());
53
54 assert!(mst.find_edge(h, i).is_some());
55 assert!(mst.find_edge(i, j).is_some());
56
57 assert!(mst.find_edge(d, b).is_none());
58 assert!(mst.find_edge(b, c).is_none());
59 }
60