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::{Config, Dot};
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!(
51 scores,
52 vec![
53 ("A", 0),
54 ("B", 7),
55 ("C", 9),
56 ("D", 11),
57 ("E", 20),
58 ("F", 20)
59 ]
60 );
61 }
62
63 #[test]
edges_directed()64 fn edges_directed() {
65 let mut gr = DiGraphMap::new();
66 let a = gr.add_node("A");
67 let b = gr.add_node("B");
68 let c = gr.add_node("C");
69 let d = gr.add_node("D");
70 let e = gr.add_node("E");
71 let f = gr.add_node("F");
72 gr.add_edge(a, b, 7);
73 gr.add_edge(a, c, 9);
74 gr.add_edge(a, d, 14);
75 gr.add_edge(b, c, 10);
76 gr.add_edge(c, d, 2);
77 gr.add_edge(d, e, 9);
78 gr.add_edge(b, f, 15);
79 gr.add_edge(c, f, 11);
80
81 let mut edges_out = gr.edges_directed(c, Direction::Outgoing);
82 assert_eq!(edges_out.next(), Some((c, d, &2)));
83 assert_eq!(edges_out.next(), Some((c, f, &11)));
84 assert_eq!(edges_out.next(), None);
85
86 let mut edges_in = gr.edges_directed(c, Direction::Incoming);
87 assert_eq!(edges_in.next(), Some((a, c, &9)));
88 assert_eq!(edges_in.next(), Some((b, c, &10)));
89 assert_eq!(edges_in.next(), None);
90 }
91
92 #[test]
remov()93 fn remov() {
94 let mut g = UnGraphMap::new();
95 g.add_node(1);
96 g.add_node(2);
97 g.add_edge(1, 2, -1);
98
99 assert_eq!(g.edge_weight(1, 2), Some(&-1));
100 assert_eq!(g.edge_weight(2, 1), Some(&-1));
101 assert_eq!(g.neighbors(1).count(), 1);
102
103 let noexist = g.remove_edge(2, 3);
104 assert_eq!(noexist, None);
105
106 let exist = g.remove_edge(2, 1);
107 assert_eq!(exist, Some(-1));
108 assert_eq!(g.edge_count(), 0);
109 assert_eq!(g.edge_weight(1, 2), None);
110 assert_eq!(g.edge_weight(2, 1), None);
111 assert_eq!(g.neighbors(1).count(), 0);
112 }
113
114 #[test]
remove_node()115 fn remove_node() {
116 // From #431
117 let mut graph = petgraph::graphmap::DiGraphMap::<u32, ()>::new();
118 graph.add_edge(1, 2, ());
119 graph.remove_node(2);
120
121 let neighbors: Vec<u32> = graph.neighbors(1).collect();
122 assert_eq!(neighbors, []);
123
124 let edges: Vec<(u32, u32, _)> = graph.all_edges().collect();
125 assert_eq!(edges, []);
126 }
127
128 #[test]
remove_directed()129 fn remove_directed() {
130 let mut g = GraphMap::<_, _, Directed>::with_capacity(0, 0);
131 g.add_edge(1, 2, -1);
132 println!("{:?}", g);
133
134 assert_eq!(g.edge_weight(1, 2), Some(&-1));
135 assert_eq!(g.edge_weight(2, 1), None);
136 assert_eq!(g.neighbors(1).count(), 1);
137
138 let noexist = g.remove_edge(2, 3);
139 assert_eq!(noexist, None);
140
141 let exist = g.remove_edge(2, 1);
142 assert_eq!(exist, None);
143 let exist = g.remove_edge(1, 2);
144 assert_eq!(exist, Some(-1));
145 println!("{:?}", g);
146 assert_eq!(g.edge_count(), 0);
147 assert_eq!(g.edge_weight(1, 2), None);
148 assert_eq!(g.edge_weight(2, 1), None);
149 assert_eq!(g.neighbors(1).count(), 0);
150 }
151
152 #[test]
dfs()153 fn dfs() {
154 let mut gr = UnGraphMap::default();
155 let h = gr.add_node("H");
156 let i = gr.add_node("I");
157 let j = gr.add_node("J");
158 let k = gr.add_node("K");
159 // Z is disconnected.
160 let z = gr.add_node("Z");
161 gr.add_edge(h, i, 1.);
162 gr.add_edge(h, j, 3.);
163 gr.add_edge(i, j, 1.);
164 gr.add_edge(i, k, 2.);
165
166 println!("{:?}", gr);
167
168 {
169 let mut cnt = 0;
170 let mut dfs = Dfs::new(&gr, h);
171 while dfs.next(&gr).is_some() {
172 cnt += 1;
173 }
174 assert_eq!(cnt, 4);
175 }
176 {
177 let mut cnt = 0;
178 let mut dfs = Dfs::new(&gr, z);
179 while dfs.next(&gr).is_some() {
180 cnt += 1;
181 }
182 assert_eq!(cnt, 1);
183 }
184
185 assert_eq!(Dfs::new(&gr, h).iter(&gr).count(), 4);
186 assert_eq!(Dfs::new(&gr, i).iter(&gr).count(), 4);
187 assert_eq!(Dfs::new(&gr, z).iter(&gr).count(), 1);
188 }
189
190 #[test]
edge_iterator()191 fn edge_iterator() {
192 let mut gr = UnGraphMap::new();
193 let h = gr.add_node("H");
194 let i = gr.add_node("I");
195 let j = gr.add_node("J");
196 let k = gr.add_node("K");
197 gr.add_edge(h, i, 1);
198 gr.add_edge(h, j, 2);
199 gr.add_edge(i, j, 3);
200 gr.add_edge(i, k, 4);
201
202 let real_edges: HashSet<_> = gr.all_edges().map(|(a, b, &w)| (a, b, w)).collect();
203 let expected_edges: HashSet<_> =
204 vec![("H", "I", 1), ("H", "J", 2), ("I", "J", 3), ("I", "K", 4)]
205 .into_iter()
206 .collect();
207
208 assert_eq!(real_edges, expected_edges);
209 }
210
211 #[test]
from_edges()212 fn from_edges() {
213 let gr =
214 GraphMap::<_, _, Undirected>::from_edges(&[("a", "b", 1), ("a", "c", 2), ("c", "d", 3)]);
215 assert_eq!(gr.node_count(), 4);
216 assert_eq!(gr.edge_count(), 3);
217 assert_eq!(gr[("a", "c")], 2);
218
219 let gr = GraphMap::<_, (), Undirected>::from_edges(&[
220 (0, 1),
221 (0, 2),
222 (0, 3),
223 (1, 2),
224 (1, 3),
225 (2, 3),
226 ]);
227 assert_eq!(gr.node_count(), 4);
228 assert_eq!(gr.edge_count(), 6);
229 assert_eq!(gr.neighbors(0).count(), 3);
230 assert_eq!(gr.neighbors(1).count(), 3);
231 assert_eq!(gr.neighbors(2).count(), 3);
232 assert_eq!(gr.neighbors(3).count(), 3);
233
234 println!("{:?}", Dot::with_config(&gr, &[Config::EdgeNoLabel]));
235 }
236
237 #[test]
graphmap_directed()238 fn graphmap_directed() {
239 //let root = TypedArena::<Node<_>>::new();
240 let mut gr = DiGraphMap::<_, ()>::with_capacity(0, 0);
241 //let node = |&: name: &'static str| Ptr(root.alloc(Node(name.to_string())));
242 let a = gr.add_node("A");
243 let b = gr.add_node("B");
244 let c = gr.add_node("C");
245 let d = gr.add_node("D");
246 let e = gr.add_node("E");
247 let edges = [(a, b), (a, c), (a, d), (b, c), (c, d), (d, e), (b, b)];
248 gr.extend(&edges);
249
250 // Add reverse edges -- ok!
251 assert!(gr.add_edge(e, d, ()).is_none());
252 // duplicate edge - no
253 assert!(gr.add_edge(a, b, ()).is_some());
254
255 // duplicate self loop - no
256 assert!(gr.add_edge(b, b, ()).is_some());
257 println!("{:#?}", gr);
258 }
259
assert_sccs_eq<N>(mut res: Vec<Vec<N>>, mut answer: Vec<Vec<N>>) where N: Ord + fmt::Debug,260 fn assert_sccs_eq<N>(mut res: Vec<Vec<N>>, mut answer: Vec<Vec<N>>)
261 where
262 N: Ord + fmt::Debug,
263 {
264 // normalize the result and compare with the answer.
265 for scc in &mut res {
266 scc.sort();
267 }
268 res.sort();
269 for scc in &mut answer {
270 scc.sort();
271 }
272 answer.sort();
273 assert_eq!(res, answer);
274 }
275
276 #[test]
scc()277 fn scc() {
278 let gr: GraphMap<_, u32, Directed> = GraphMap::from_edges(&[
279 (6, 0, 0),
280 (0, 3, 1),
281 (3, 6, 2),
282 (8, 6, 3),
283 (8, 2, 4),
284 (2, 5, 5),
285 (5, 8, 6),
286 (7, 5, 7),
287 (1, 7, 8),
288 (7, 4, 9),
289 (4, 1, 10),
290 ]);
291
292 assert_sccs_eq(
293 petgraph::algo::kosaraju_scc(&gr),
294 vec![vec![0, 3, 6], vec![1, 4, 7], vec![2, 5, 8]],
295 );
296 }
297
298 #[test]
test_into_graph()299 fn test_into_graph() {
300 let gr: GraphMap<_, u32, Directed> = GraphMap::from_edges(&[
301 (6, 0, 0),
302 (0, 3, 1),
303 (3, 6, 2),
304 (8, 6, 3),
305 (8, 2, 4),
306 (2, 5, 5),
307 (5, 8, 6),
308 (7, 5, 7),
309 (1, 7, 8),
310 (7, 4, 9),
311 (4, 1, 10),
312 ]);
313
314 let graph: Graph<_, _, _> = gr.clone().into_graph();
315 println!("{}", Dot::new(&gr));
316 println!("{}", Dot::new(&graph));
317
318 // node weigths in `graph` are node identifiers in `gr`.
319 for edge in graph.edge_references() {
320 let a = edge.source();
321 let b = edge.target();
322 let aw = graph[a];
323 let bw = graph[b];
324 assert_eq!(&gr[(aw, bw)], edge.weight());
325 }
326 }
327
328 #[test]
test_from_graph()329 fn test_from_graph() {
330 let mut gr: Graph<u32, u32, Directed> = Graph::new();
331 let node_a = gr.add_node(12);
332 let node_b = gr.add_node(13);
333 let node_c = gr.add_node(14);
334 gr.add_edge(node_a, node_b, 1000);
335 gr.add_edge(node_b, node_c, 999);
336 gr.add_edge(node_c, node_a, 1111);
337 gr.add_node(42);
338 let gr = gr;
339
340 let graph: GraphMap<u32, u32, Directed> = GraphMap::from_graph(gr.clone());
341 println!("{}", Dot::new(&gr));
342 println!("{}", Dot::new(&graph));
343
344 assert!(petgraph::algo::is_isomorphic(&gr, &graph));
345 assert_eq!(graph[(12, 13)], 1000);
346 }
347
348 #[test]
test_all_edges_mut()349 fn test_all_edges_mut() {
350 // graph with edge weights equal to in+out
351 let mut graph: GraphMap<_, u32, Directed> =
352 GraphMap::from_edges(&[(0, 1, 1), (1, 2, 3), (2, 0, 2)]);
353
354 // change it so edge weight is equal to 2 * (in+out)
355 for (start, end, weight) in graph.all_edges_mut() {
356 *weight = (start + end) * 2;
357 }
358
359 // test it
360 for (start, end, weight) in graph.all_edges() {
361 assert_eq!((start + end) * 2, *weight);
362 }
363 }
364
365 #[test]
neighbors_incoming_includes_self_loops()366 fn neighbors_incoming_includes_self_loops() {
367 let mut graph = DiGraphMap::new();
368
369 graph.add_node(());
370 graph.add_edge((), (), ());
371
372 let mut neighbors = graph.neighbors_directed((), Incoming);
373 assert_eq!(neighbors.next(), Some(()));
374 assert_eq!(neighbors.next(), None);
375 }
376
377 #[test]
undirected_neighbors_includes_self_loops()378 fn undirected_neighbors_includes_self_loops() {
379 let mut graph = UnGraphMap::new();
380
381 graph.add_node(());
382 graph.add_edge((), (), ());
383
384 let mut neighbors = graph.neighbors(());
385 assert_eq!(neighbors.next(), Some(()));
386 assert_eq!(neighbors.next(), None);
387 }
388
389 #[test]
self_loops_can_be_removed()390 fn self_loops_can_be_removed() {
391 let mut graph = DiGraphMap::new();
392
393 graph.add_node(());
394 graph.add_edge((), (), ());
395
396 graph.remove_edge((), ());
397
398 assert_eq!(graph.neighbors_directed((), Outgoing).next(), None);
399 assert_eq!(graph.neighbors_directed((), Incoming).next(), None);
400 }
401
402 #[test]
403 #[cfg(feature = "rayon")]
test_parallel_iterator()404 fn test_parallel_iterator() {
405 use rayon::prelude::*;
406 let mut gr: DiGraphMap<u32, u32> = DiGraphMap::new();
407
408 for i in 0..1000 {
409 gr.add_node(i);
410 }
411
412 let serial_sum: u32 = gr.nodes().sum();
413 let parallel_sum: u32 = gr.par_nodes().sum();
414 assert_eq!(serial_sum, parallel_sum);
415
416 gr.par_nodes()
417 .enumerate()
418 .for_each(|(i, n)| assert_eq!(i as u32, n));
419
420 for i in 0..1000 {
421 gr.add_edge(i / 2, i, i + i / 2);
422 }
423
424 let serial_sum: u32 = gr.all_edges().map(|(.., &e)| e).sum();
425 let parallel_sum: u32 = gr.par_all_edges().map(|(.., &e)| e).sum();
426 assert_eq!(serial_sum, parallel_sum);
427
428 gr.par_all_edges_mut().for_each(|(n1, n2, e)| *e -= n1 + n2);
429 gr.all_edges().for_each(|(.., &e)| assert_eq!(e, 0));
430 }
431
432 #[test]
test_alternative_hasher()433 fn test_alternative_hasher() {
434 let mut gr: GraphMap<&str, u32, Directed, fxhash::FxBuildHasher> = GraphMap::new();
435 gr.add_node("abc");
436 gr.add_node("def");
437 gr.add_node("ghi");
438
439 gr.add_edge("abc", "def", 1);
440
441 assert!(gr.contains_edge("abc", "def"));
442 assert!(!gr.contains_edge("abc", "ghi"));
443 }
444