1 #![cfg(feature = "graphmap")]
2 extern crate petgraph;
3
4 use std::collections::HashSet;
5 use std::fmt;
6
7 use petgraph::prelude::*;
8 use petgraph::visit::{ Walker, };
9
10 use petgraph::algo::{ dijkstra, };
11
12 use petgraph::dot::{Dot, Config};
13
14 #[test]
simple()15 fn simple() {
16 //let root = TypedArena::<Node<_>>::new();
17 let mut gr = UnGraphMap::new();
18 //let node = |&: name: &'static str| Ptr(root.alloc(Node(name.to_string())));
19 let a = gr.add_node("A");
20 let b = gr.add_node("B");
21 let c = gr.add_node("C");
22 let d = gr.add_node("D");
23 let e = gr.add_node("E");
24 let f = gr.add_node("F");
25 gr.add_edge(a, b, 7);
26 gr.add_edge(a, c, 9);
27 gr.add_edge(a, d, 14);
28 gr.add_edge(b, c, 10);
29 gr.add_edge(c, d, 2);
30 gr.add_edge(d, e, 9);
31 gr.add_edge(b, f, 15);
32 gr.add_edge(c, f, 11);
33
34 assert!(gr.add_edge(e, f, 5).is_none());
35
36 // duplicate edges
37 assert_eq!(gr.add_edge(f, b, 16), Some(15));
38 assert_eq!(gr.add_edge(f, e, 6), Some(5));
39 println!("{:?}", gr);
40 println!("{}", Dot::with_config(&gr, &[]));
41
42 assert_eq!(gr.node_count(), 6);
43 assert_eq!(gr.edge_count(), 9);
44
45 // check updated edge weight
46 assert_eq!(gr.edge_weight(e, f), Some(&6));
47 let scores = dijkstra(&gr, a, None, |e| *e.weight());
48 let mut scores: Vec<_> = scores.into_iter().collect();
49 scores.sort();
50 assert_eq!(scores,
51 vec![("A", 0), ("B", 7), ("C", 9), ("D", 11), ("E", 20), ("F", 20)]);
52 }
53
54 #[test]
remov()55 fn remov()
56 {
57 let mut g = UnGraphMap::new();
58 g.add_node(1);
59 g.add_node(2);
60 g.add_edge(1, 2, -1);
61
62 assert_eq!(g.edge_weight(1, 2), Some(&-1));
63 assert_eq!(g.edge_weight(2, 1), Some(&-1));
64 assert_eq!(g.neighbors(1).count(), 1);
65
66 let noexist = g.remove_edge(2, 3);
67 assert_eq!(noexist, None);
68
69 let exist = g.remove_edge(2, 1);
70 assert_eq!(exist, Some(-1));
71 assert_eq!(g.edge_count(), 0);
72 assert_eq!(g.edge_weight(1, 2), None);
73 assert_eq!(g.edge_weight(2, 1), None);
74 assert_eq!(g.neighbors(1).count(), 0);
75 }
76
77 #[test]
remove_directed()78 fn remove_directed()
79 {
80 let mut g = GraphMap::<_, _, Directed>::with_capacity(0, 0);
81 g.add_edge(1, 2, -1);
82 println!("{:?}", g);
83
84 assert_eq!(g.edge_weight(1, 2), Some(&-1));
85 assert_eq!(g.edge_weight(2, 1), None);
86 assert_eq!(g.neighbors(1).count(), 1);
87
88 let noexist = g.remove_edge(2, 3);
89 assert_eq!(noexist, None);
90
91 let exist = g.remove_edge(2, 1);
92 assert_eq!(exist, None);
93 let exist = g.remove_edge(1, 2);
94 assert_eq!(exist, Some(-1));
95 println!("{:?}", g);
96 assert_eq!(g.edge_count(), 0);
97 assert_eq!(g.edge_weight(1, 2), None);
98 assert_eq!(g.edge_weight(2, 1), None);
99 assert_eq!(g.neighbors(1).count(), 0);
100 }
101
102 #[test]
dfs()103 fn dfs() {
104 let mut gr = UnGraphMap::default();
105 let h = gr.add_node("H");
106 let i = gr.add_node("I");
107 let j = gr.add_node("J");
108 let k = gr.add_node("K");
109 // Z is disconnected.
110 let z = gr.add_node("Z");
111 gr.add_edge(h, i, 1.);
112 gr.add_edge(h, j, 3.);
113 gr.add_edge(i, j, 1.);
114 gr.add_edge(i, k, 2.);
115
116 println!("{:?}", gr);
117
118 {
119 let mut cnt = 0;
120 let mut dfs = Dfs::new(&gr, h);
121 while let Some(_) = dfs.next(&gr) { cnt += 1; }
122 assert_eq!(cnt, 4);
123 }
124 {
125 let mut cnt = 0;
126 let mut dfs = Dfs::new(&gr, z);
127 while let Some(_) = dfs.next(&gr) { cnt += 1; }
128 assert_eq!(cnt, 1);
129 }
130
131 assert_eq!(Dfs::new(&gr, h).iter(&gr).count(), 4);
132 assert_eq!(Dfs::new(&gr, i).iter(&gr).count(), 4);
133 assert_eq!(Dfs::new(&gr, z).iter(&gr).count(), 1);
134 }
135
136 #[test]
edge_iterator()137 fn edge_iterator() {
138 let mut gr = UnGraphMap::new();
139 let h = gr.add_node("H");
140 let i = gr.add_node("I");
141 let j = gr.add_node("J");
142 let k = gr.add_node("K");
143 gr.add_edge(h, i, 1);
144 gr.add_edge(h, j, 2);
145 gr.add_edge(i, j, 3);
146 gr.add_edge(i, k, 4);
147
148 let real_edges: HashSet<_> = gr.all_edges().map(|(a, b, &w)| (a, b, w)).collect();
149 let expected_edges: HashSet<_> = vec![
150 ("H", "I", 1),
151 ("H", "J", 2),
152 ("I", "J", 3),
153 ("I", "K", 4)
154 ].into_iter().collect();
155
156 assert_eq!(real_edges, expected_edges);
157 }
158
159 #[test]
from_edges()160 fn from_edges() {
161 let gr = GraphMap::<_, _, Undirected>::from_edges(&[
162 ("a", "b", 1),
163 ("a", "c", 2),
164 ("c", "d", 3),
165 ]);
166 assert_eq!(gr.node_count(), 4);
167 assert_eq!(gr.edge_count(), 3);
168 assert_eq!(gr[("a", "c")], 2);
169
170 let gr = GraphMap::<_, (), Undirected>::from_edges(&[
171 (0, 1), (0, 2), (0, 3),
172 (1, 2), (1, 3),
173 (2, 3),
174 ]);
175 assert_eq!(gr.node_count(), 4);
176 assert_eq!(gr.edge_count(), 6);
177 assert_eq!(gr.neighbors(0).count(), 3);
178 assert_eq!(gr.neighbors(1).count(), 3);
179 assert_eq!(gr.neighbors(2).count(), 3);
180 assert_eq!(gr.neighbors(3).count(), 3);
181
182 println!("{:?}", Dot::with_config(&gr, &[Config::EdgeNoLabel]));
183 }
184
185
186 #[test]
graphmap_directed()187 fn graphmap_directed() {
188 //let root = TypedArena::<Node<_>>::new();
189 let mut gr = DiGraphMap::<_, ()>::with_capacity(0, 0);
190 //let node = |&: name: &'static str| Ptr(root.alloc(Node(name.to_string())));
191 let a = gr.add_node("A");
192 let b = gr.add_node("B");
193 let c = gr.add_node("C");
194 let d = gr.add_node("D");
195 let e = gr.add_node("E");
196 let edges = [
197 (a, b),
198 (a, c),
199 (a, d),
200 (b, c),
201 (c, d),
202 (d, e),
203 (b, b),
204 ];
205 gr.extend(&edges);
206
207 // Add reverse edges -- ok!
208 assert!(gr.add_edge(e, d, ()).is_none());
209 // duplicate edge - no
210 assert!(!gr.add_edge(a, b, ()).is_none());
211
212 // duplicate self loop - no
213 assert!(!gr.add_edge(b, b, ()).is_none());
214 println!("{:#?}", gr);
215 }
216
assert_sccs_eq<N>(mut res: Vec<Vec<N>>, mut answer: Vec<Vec<N>>) where N: Ord + fmt::Debug,217 fn assert_sccs_eq<N>(mut res: Vec<Vec<N>>, mut answer: Vec<Vec<N>>)
218 where N: Ord + fmt::Debug,
219 {
220 // normalize the result and compare with the answer.
221 for scc in &mut res {
222 scc.sort();
223 }
224 res.sort();
225 for scc in &mut answer {
226 scc.sort();
227 }
228 answer.sort();
229 assert_eq!(res, answer);
230 }
231
232 #[test]
scc()233 fn scc() {
234 let gr: GraphMap<_, u32, Directed> = GraphMap::from_edges(&[
235 (6, 0, 0),
236 (0, 3, 1),
237 (3, 6, 2),
238 (8, 6, 3),
239 (8, 2, 4),
240 (2, 5, 5),
241 (5, 8, 6),
242 (7, 5, 7),
243 (1, 7, 8),
244 (7, 4, 9),
245 (4, 1, 10)]);
246
247 assert_sccs_eq(petgraph::algo::kosaraju_scc(&gr), vec![
248 vec![0, 3, 6],
249 vec![1, 4, 7],
250 vec![2, 5, 8],
251 ]);
252 }
253
254 #[test]
test_into_graph()255 fn test_into_graph() {
256 let gr: GraphMap<_, u32, Directed> = GraphMap::from_edges(&[
257 (6, 0, 0),
258 (0, 3, 1),
259 (3, 6, 2),
260 (8, 6, 3),
261 (8, 2, 4),
262 (2, 5, 5),
263 (5, 8, 6),
264 (7, 5, 7),
265 (1, 7, 8),
266 (7, 4, 9),
267 (4, 1, 10)]);
268
269 let graph: Graph<_, _, _> = gr.clone().into_graph();
270 println!("{}", Dot::new(&gr));
271 println!("{}", Dot::new(&graph));
272
273 // node weigths in `graph` are node identifiers in `gr`.
274 for edge in graph.edge_references() {
275 let a = edge.source();
276 let b = edge.target();
277 let aw = graph[a];
278 let bw = graph[b];
279 assert_eq!(&gr[(aw, bw)], edge.weight());
280 }
281 }
282
283 #[test]
test_all_edges_mut()284 fn test_all_edges_mut() {
285 // graph with edge weights equal to in+out
286 let mut graph: GraphMap<_, u32, Directed> = GraphMap::from_edges(&[
287 (0, 1, 1),
288 (1, 2, 3),
289 (2, 0, 2),
290 ]);
291
292 // change it so edge weight is equal to 2 * (in+out)
293 for (start, end, weight) in graph.all_edges_mut() {
294 *weight = (start + end) * 2;
295 }
296
297 // test it
298 for (start, end, weight) in graph.all_edges() {
299 assert_eq!((start + end) * 2, *weight);
300 }
301 }