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
121
122
123
124
125
126
127
128
129
|
use tracing::debug;
use crate::graph::implementation::*;
type TestGraph = Graph<&'static str, &'static str>;
fn create_graph() -> TestGraph {
let mut graph = Graph::new();
// Create a simple graph
//
// F
// |
// V
// A --> B --> C
// | ^
// v |
// D --> E
let a = graph.add_node("A");
let b = graph.add_node("B");
let c = graph.add_node("C");
let d = graph.add_node("D");
let e = graph.add_node("E");
let f = graph.add_node("F");
graph.add_edge(a, b, "AB");
graph.add_edge(b, c, "BC");
graph.add_edge(b, d, "BD");
graph.add_edge(d, e, "DE");
graph.add_edge(e, c, "EC");
graph.add_edge(f, b, "FB");
return graph;
}
#[test]
fn each_node() {
let graph = create_graph();
let expected = ["A", "B", "C", "D", "E", "F"];
graph.each_node(|idx, node| {
assert_eq!(&expected[idx.0], graph.node_data(idx));
assert_eq!(expected[idx.0], node.data);
true
});
}
#[test]
fn each_edge() {
let graph = create_graph();
let expected = ["AB", "BC", "BD", "DE", "EC", "FB"];
graph.each_edge(|idx, edge| {
assert_eq!(expected[idx.0], edge.data);
true
});
}
fn test_adjacent_edges<N: PartialEq + Debug, E: PartialEq + Debug>(
graph: &Graph<N, E>,
start_index: NodeIndex,
start_data: N,
expected_incoming: &[(E, N)],
expected_outgoing: &[(E, N)],
) {
assert!(graph.node_data(start_index) == &start_data);
let mut counter = 0;
for (edge_index, edge) in graph.incoming_edges(start_index) {
assert!(counter < expected_incoming.len());
debug!(
"counter={:?} expected={:?} edge_index={:?} edge={:?}",
counter, expected_incoming[counter], edge_index, edge
);
match &expected_incoming[counter] {
(e, n) => {
assert!(e == &edge.data);
assert!(n == graph.node_data(edge.source()));
assert!(start_index == edge.target);
}
}
counter += 1;
}
assert_eq!(counter, expected_incoming.len());
let mut counter = 0;
for (edge_index, edge) in graph.outgoing_edges(start_index) {
assert!(counter < expected_outgoing.len());
debug!(
"counter={:?} expected={:?} edge_index={:?} edge={:?}",
counter, expected_outgoing[counter], edge_index, edge
);
match &expected_outgoing[counter] {
(e, n) => {
assert!(e == &edge.data);
assert!(start_index == edge.source);
assert!(n == graph.node_data(edge.target));
}
}
counter += 1;
}
assert_eq!(counter, expected_outgoing.len());
}
#[test]
fn each_adjacent_from_a() {
let graph = create_graph();
test_adjacent_edges(&graph, NodeIndex(0), "A", &[], &[("AB", "B")]);
}
#[test]
fn each_adjacent_from_b() {
let graph = create_graph();
test_adjacent_edges(&graph, NodeIndex(1), "B", &[("FB", "F"), ("AB", "A")], &[
("BD", "D"),
("BC", "C"),
]);
}
#[test]
fn each_adjacent_from_c() {
let graph = create_graph();
test_adjacent_edges(&graph, NodeIndex(2), "C", &[("EC", "E"), ("BC", "B")], &[]);
}
#[test]
fn each_adjacent_from_d() {
let graph = create_graph();
test_adjacent_edges(&graph, NodeIndex(3), "D", &[("BD", "B")], &[("DE", "E")]);
}
|
