]>
git.proxmox.com Git - rustc.git/blob - src/librustc_data_structures/graph/tests.rs
1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
14 type TestNode
= Node
<&'
static str>;
15 type TestEdge
= Edge
<&'
static str>;
16 type TestGraph
= Graph
<&'
static str, &'
static str>;
18 fn create_graph() -> TestGraph
{
19 let mut graph
= Graph
::new();
21 // Create a simple graph
28 let a
= graph
.add_node("A");
29 let b
= graph
.add_node("B");
30 let c
= graph
.add_node("C");
31 let d
= graph
.add_node("D");
32 let e
= graph
.add_node("E");
33 let f
= graph
.add_node("F");
35 graph
.add_edge(a
, b
, "AB");
36 graph
.add_edge(b
, c
, "BC");
37 graph
.add_edge(b
, d
, "BD");
38 graph
.add_edge(d
, e
, "DE");
39 graph
.add_edge(e
, c
, "EC");
40 graph
.add_edge(f
, b
, "FB");
47 let graph
= create_graph();
48 let expected
= ["A", "B", "C", "D", "E", "F"];
49 graph
.each_node(|idx
, node
| {
50 assert_eq
!(&expected
[idx
.0], graph
.node_data(idx
));
51 assert_eq
!(expected
[idx
.0], node
.data
);
58 let graph
= create_graph();
59 let expected
= ["AB", "BC", "BD", "DE", "EC", "FB"];
60 graph
.each_edge(|idx
, edge
| {
61 assert_eq
!(&expected
[idx
.0], graph
.edge_data(idx
));
62 assert_eq
!(expected
[idx
.0], edge
.data
);
67 fn test_adjacent_edges
<N
: PartialEq
+ Debug
, E
: PartialEq
+ Debug
>(graph
: &Graph
<N
, E
>,
68 start_index
: NodeIndex
,
70 expected_incoming
: &[(E
, N
)],
71 expected_outgoing
: &[(E
, N
)]) {
72 assert
!(graph
.node_data(start_index
) == &start_data
);
75 for (edge_index
, edge
) in graph
.incoming_edges(start_index
) {
76 assert
!(graph
.edge_data(edge_index
) == &edge
.data
);
77 assert
!(counter
< expected_incoming
.len());
78 debug
!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
80 expected_incoming
[counter
],
83 match expected_incoming
[counter
] {
85 assert
!(e
== &edge
.data
);
86 assert
!(n
== graph
.node_data(edge
.source()));
87 assert
!(start_index
== edge
.target
);
92 assert_eq
!(counter
, expected_incoming
.len());
95 for (edge_index
, edge
) in graph
.outgoing_edges(start_index
) {
96 assert
!(graph
.edge_data(edge_index
) == &edge
.data
);
97 assert
!(counter
< expected_outgoing
.len());
98 debug
!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
100 expected_outgoing
[counter
],
103 match expected_outgoing
[counter
] {
105 assert
!(e
== &edge
.data
);
106 assert
!(start_index
== edge
.source
);
107 assert
!(n
== graph
.node_data(edge
.target
));
112 assert_eq
!(counter
, expected_outgoing
.len());
116 fn each_adjacent_from_a() {
117 let graph
= create_graph();
118 test_adjacent_edges(&graph
, NodeIndex(0), "A", &[], &[("AB", "B")]);
122 fn each_adjacent_from_b() {
123 let graph
= create_graph();
124 test_adjacent_edges(&graph
,
127 &[("FB", "F"), ("AB", "A")],
128 &[("BD", "D"), ("BC", "C")]);
132 fn each_adjacent_from_c() {
133 let graph
= create_graph();
134 test_adjacent_edges(&graph
, NodeIndex(2), "C", &[("EC", "E"), ("BC", "B")], &[]);
138 fn each_adjacent_from_d() {
139 let graph
= create_graph();
140 test_adjacent_edges(&graph
, NodeIndex(3), "D", &[("BD", "B")], &[("DE", "E")]);