luka 0.4.0

Library for working with graphs
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

use luka::{Graph, utils, Vertex};
use luka::algorithms;
use luka::algorithms::{VisitorBFS, VisitorBFSAction};
use luka::error::GraphError;

#[test]
fn integration_test_bfs_algorithm() {
    use crate::utils;

    let mut graph = Graph::new(100);
    graph.add_edge(1, 2, 0.0).unwrap();
    graph.add_edge(2, 3, 0.0).unwrap();
    graph.add_edge(2, 4, 0.0).unwrap();
    graph.add_edge(2, 5, 0.0).unwrap();
    graph.add_edge(4, 8, 0.0).unwrap();
    graph.add_edge(8, 17, 0.0).unwrap();

    let start = graph.get_vertex(1).unwrap();
    let target = graph.get_vertex(5).unwrap();
    let parents = algorithms::bfs(&graph, &start).unwrap();

    let path = utils::find_path(&graph, &target, &parents).unwrap().unwrap();
    let mut ids = vec![];
    for vertex in path {
        ids.push(vertex.id());
    }
    assert_eq!(ids, vec![1, 2, 5]);

    let target = graph.get_vertex(17).unwrap();
    let path = utils::find_path(&graph, &target, &parents).unwrap().unwrap();
    let mut ids = vec![];
    for vertex in path {
        ids.push(vertex.id());
    }
    assert_eq!(ids, vec![1, 2, 4, 8, 17]);
}

#[test]
#[should_panic]
fn integration_test_bfs_algorithm_panic() {
    let mut graph = Graph::new(100);
    graph.add_edge(1, 2, 0.0).unwrap();
    let start = graph.get_vertex(122).unwrap();
    algorithms::bfs(&graph, &start).unwrap();
}

#[test]
fn integration_test_bfs_with_visitor_algorithm() {
    struct CustomVisitor {
        visiting_order: Vec<usize>
    }

    impl <T> VisitorBFS<T> for CustomVisitor {
        fn queue_extract_event(&mut self, vertex: &Vertex<T>) -> Result<VisitorBFSAction, GraphError> {
            self.visiting_order.push(vertex.id());
            Ok(VisitorBFSAction::Nothing)
        }
    }

    let mut graph = Graph::new(100);
    graph.add_edge(1, 2, 0.0).unwrap();
    graph.add_edge(2, 3, 0.0).unwrap();
    graph.add_edge(2, 4, 0.0).unwrap();
    graph.add_edge(2, 5, 0.0).unwrap();
    graph.add_edge(4, 8, 0.0).unwrap();
    graph.add_edge(8, 17, 0.0).unwrap();

    let mut visitor = CustomVisitor{ visiting_order: vec![] };
    let start = graph.get_vertex(1).unwrap();
    algorithms::bfs_with_visitor(&graph, &start, &mut visitor).unwrap();

    assert_eq!(vec![1, 2, 3, 4, 5, 8, 17], visitor.visiting_order);
}