petgraph 0.8.3

Graph data structure library. Provides graph types and graph algorithms.
Documentation 
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);
}