1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
use itertools::Itertools;
use pathfinding::prelude::*;
#[test]
fn grid_lines() {
let mut g = Grid::new(2, 2);
g.fill();
let weighted_edges = g
.edges()
.map(|((x1, y1), (x2, y2))| ((x1, y1), (x2, y2), y1.min(y2)))
.collect::<Vec<_>>();
assert_eq!(weighted_edges.len(), 4);
let mst = kruskal(&weighted_edges).sorted().collect_vec();
assert_eq!(
mst,
vec![
(&(0, 0), &(0, 1), 0),
(&(0, 0), &(1, 0), 0),
(&(1, 0), &(1, 1), 0)
]
);
}
#[test]
fn wikipedia() {
// Example from https://en.wikipedia.org/wiki/Kruskal's_algorithm
let edges = vec![
('a', 'b', 3),
('a', 'e', 1),
('b', 'c', 5),
('b', 'e', 4),
('c', 'd', 2),
('c', 'e', 6),
('d', 'e', 7),
];
assert_eq!(
kruskal(&edges).collect::<Vec<_>>(),
vec![
(&'a', &'e', 1),
(&'c', &'d', 2),
(&'a', &'b', 3),
(&'b', &'c', 5)
]
);
}
|
