snark-tool 0.4.0

snark-tool library contains structures and algorithm for (mainly) cubic graph analysis
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

use crate::service::graph_traversal::bfs::BfsOfGraph;
use crate::service::graph_traversal::dfs::DfsOfGraph;
use crate::tests::test_data::test_data;

#[test]
fn should_traverse_using_bfs() {
    let graph = test_data::get_petersen_graph();

    let mut bfs = BfsOfGraph::new(&graph, 0);

    let mut vertices = vec![];
    while let Some(next) = bfs.next() {
        vertices.push(next.index());
    }

    let right_order = vec![0, 4, 6, 8, 2, 5, 1, 7, 3, 9];
    assert_eq!(vertices, right_order);
}

#[test]
fn should_reconstruct_path_using_bfs() {
    let graph = test_data::get_falcon_graph();
    let source = 5;
    let target = 6;
    let mut bfs = BfsOfGraph::new(&graph, 5);

    while let Some(next) = bfs.next() {
        if next.index() == target {
            break;
        }
    }
    let visited = bfs.visited_vertex(target);
    assert_eq!(visited.is_some(), true);

    let mut visited = visited.unwrap();
    let mut path = vec![];
    path.push(visited.index());
    loop {
        let before = visited.discovered_from();
        path.push(before);
        if before == source {
            break;
        }
        visited = bfs.visited_vertex(before).unwrap();
    }
    let path_check = vec![6, 7, 3, 5];
    assert_eq!(path, path_check);
}

#[test]
fn should_traverse_using_bfs_discovery_order() {
    let graph = test_data::get_petersen_graph();

    let mut bfs = BfsOfGraph::new(&graph, 0);

    let mut vertices = vec![];
    while let Some(next) = bfs.next() {
        vertices.push(next.index());
    }

    let right_order = vec![0, 4, 6, 8, 2, 5, 1, 7, 3, 9];
    assert_eq!(vertices, right_order);
    assert_eq!(bfs.discovery_order(), &right_order);

    bfs.back();
    let right_order = vec![0, 4, 6, 8, 2, 5, 1, 7, 3];
    assert_eq!(bfs.discovery_order(), &right_order);

    bfs.back();
    bfs.back();
    let right_order = vec![0, 4, 6, 8, 2, 5, 1];
    assert_eq!(bfs.discovery_order(), &right_order);

    bfs.next();
    bfs.next();
    bfs.next();
    let right_order = vec![0, 4, 6, 8, 2, 5, 1, 7, 3, 9];
    assert_eq!(bfs.discovery_order(), &right_order);

    bfs.back();
    bfs.back();
    bfs.back();
    bfs.back();
    bfs.back();
    bfs.back();
    let right_order = vec![0, 4, 6, 8];
    assert_eq!(bfs.discovery_order(), &right_order);

    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    bfs.next();
    let right_order = vec![0, 4, 6, 8, 2, 5, 1, 7, 3, 9];
    assert_eq!(bfs.discovery_order(), &right_order);
}

#[test]
fn should_traverse_using_dfs() {
    let graph = test_data::get_petersen_graph();
    let mut dfs = DfsOfGraph::new(&graph, 0);

    let mut vertices = vec![];
    while let Some(next) = dfs.next() {
        vertices.push(next.index());
    }

    let right_order = vec![0, 8, 9, 2, 7, 6, 1, 5, 4, 3];
    assert_eq!(vertices, right_order);
}