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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
use petgraph::algo::dsatur_coloring;
use petgraph::{Graph, Undirected};
#[test]
fn dsatur_coloring_cycle6() {
let mut graph: Graph<(), (), Undirected> = Graph::new_undirected();
let a = graph.add_node(());
let d = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
graph.extend_with_edges([(a, b), (b, c), (c, d), (d, e), (e, f), (f, e)]);
let (coloring, nb_colors) = dsatur_coloring(&graph);
assert_eq!(nb_colors, 2);
assert_eq!(coloring.len(), 6);
}
#[test]
fn dsatur_coloring_bipartite() {
let mut graph: Graph<(), (), Undirected> = Graph::new_undirected();
let a = graph.add_node(());
let d = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
let g = graph.add_node(());
let h = graph.add_node(());
let i = graph.add_node(());
let j = graph.add_node(());
let k = graph.add_node(());
let l = graph.add_node(());
graph.extend_with_edges([
(a, b),
(a, g),
(a, l),
(b, d),
(b, h),
(b, k),
(c, d),
(c, k),
(d, l),
(e, f),
(e, j),
(f, i),
(f, l),
(g, h),
(g, j),
(g, k),
(h, i),
(i, j),
(i, k),
]);
let (_, nb_colors) = dsatur_coloring(&graph);
assert_eq!(nb_colors, 2);
}
|
