1 #![cfg(feature = "quickcheck")]
2 #[macro_use]
3 extern crate quickcheck;
4 extern crate petgraph;
5 extern crate rand;
6 #[macro_use]
7 extern crate defmac;
8
9 extern crate itertools;
10 extern crate odds;
11
12 mod utils;
13
14 use utils::Small;
15
16 use odds::prelude::*;
17 use std::collections::HashSet;
18 use std::hash::Hash;
19
20 use itertools::assert_equal;
21 use itertools::cloned;
22 use rand::Rng;
23
24 use petgraph::algo::{
25 bellman_ford, condensation, dijkstra, is_cyclic_directed, is_cyclic_undirected, is_isomorphic,
26 is_isomorphic_matching, kosaraju_scc, min_spanning_tree, tarjan_scc, toposort,
27 };
28 use petgraph::data::FromElements;
29 use petgraph::dot::{Config, Dot};
30 use petgraph::graph::{edge_index, node_index, IndexType};
31 use petgraph::graphmap::NodeTrait;
32 use petgraph::prelude::*;
33 use petgraph::visit::{EdgeRef, IntoEdgeReferences, IntoNodeReferences, NodeIndexable};
34 use petgraph::visit::{Reversed, Topo};
35 use petgraph::EdgeType;
36
mst_graph<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) -> Graph<N, E, Undirected, Ix> where Ty: EdgeType, Ix: IndexType, N: Clone, E: Clone + PartialOrd,37 fn mst_graph<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) -> Graph<N, E, Undirected, Ix>
38 where
39 Ty: EdgeType,
40 Ix: IndexType,
41 N: Clone,
42 E: Clone + PartialOrd,
43 {
44 Graph::from_elements(min_spanning_tree(&g))
45 }
46
47 use std::fmt;
48
49 quickcheck! {
50 fn mst_directed(g: Small<Graph<(), u32>>) -> bool {
51 // filter out isolated nodes
52 let no_singles = g.filter_map(
53 |nx, w| g.neighbors_undirected(nx).next().map(|_| w),
54 |_, w| Some(w));
55 for i in no_singles.node_indices() {
56 assert!(no_singles.neighbors_undirected(i).count() > 0);
57 }
58 assert_eq!(no_singles.edge_count(), g.edge_count());
59 let mst = mst_graph(&no_singles);
60 assert!(!is_cyclic_undirected(&mst));
61 true
62 }
63 }
64
65 quickcheck! {
66 fn mst_undirected(g: Graph<(), u32, Undirected>) -> bool {
67 // filter out isolated nodes
68 let no_singles = g.filter_map(
69 |nx, w| g.neighbors_undirected(nx).next().map(|_| w),
70 |_, w| Some(w));
71 for i in no_singles.node_indices() {
72 assert!(no_singles.neighbors_undirected(i).count() > 0);
73 }
74 assert_eq!(no_singles.edge_count(), g.edge_count());
75 let mst = mst_graph(&no_singles);
76 assert!(!is_cyclic_undirected(&mst));
77 true
78 }
79 }
80
81 quickcheck! {
82 fn reverse_undirected(g: Small<UnGraph<(), ()>>) -> bool {
83 let mut h = (*g).clone();
84 h.reverse();
85 is_isomorphic(&g, &h)
86 }
87 }
88
assert_graph_consistent<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>) where Ty: EdgeType, Ix: IndexType,89 fn assert_graph_consistent<N, E, Ty, Ix>(g: &Graph<N, E, Ty, Ix>)
90 where
91 Ty: EdgeType,
92 Ix: IndexType,
93 {
94 assert_eq!(g.node_count(), g.node_indices().count());
95 assert_eq!(g.edge_count(), g.edge_indices().count());
96 for edge in g.raw_edges() {
97 assert!(
98 g.find_edge(edge.source(), edge.target()).is_some(),
99 "Edge not in graph! {:?} to {:?}",
100 edge.source(),
101 edge.target()
102 );
103 }
104 }
105
106 #[test]
reverse_directed()107 fn reverse_directed() {
108 fn prop<Ty: EdgeType>(mut g: Graph<(), (), Ty>) -> bool {
109 let node_outdegrees = g
110 .node_indices()
111 .map(|i| g.neighbors_directed(i, Outgoing).count())
112 .collect::<Vec<_>>();
113 let node_indegrees = g
114 .node_indices()
115 .map(|i| g.neighbors_directed(i, Incoming).count())
116 .collect::<Vec<_>>();
117
118 g.reverse();
119 let new_outdegrees = g
120 .node_indices()
121 .map(|i| g.neighbors_directed(i, Outgoing).count())
122 .collect::<Vec<_>>();
123 let new_indegrees = g
124 .node_indices()
125 .map(|i| g.neighbors_directed(i, Incoming).count())
126 .collect::<Vec<_>>();
127 assert_eq!(node_outdegrees, new_indegrees);
128 assert_eq!(node_indegrees, new_outdegrees);
129 assert_graph_consistent(&g);
130 true
131 }
132 quickcheck::quickcheck(prop as fn(Graph<_, _, Directed>) -> bool);
133 }
134
135 #[test]
graph_retain_nodes()136 fn graph_retain_nodes() {
137 fn prop<Ty: EdgeType>(mut g: Graph<i32, i32, Ty>) -> bool {
138 // Remove all negative nodes, these should be randomly spread
139 let og = g.clone();
140 let nodes = g.node_count();
141 let num_negs = g.raw_nodes().iter().filter(|n| n.weight < 0).count();
142 let mut removed = 0;
143 g.retain_nodes(|g, i| {
144 let keep = g[i] >= 0;
145 if !keep {
146 removed += 1;
147 }
148 keep
149 });
150 let num_negs_post = g.raw_nodes().iter().filter(|n| n.weight < 0).count();
151 let num_pos_post = g.raw_nodes().iter().filter(|n| n.weight >= 0).count();
152 assert_eq!(num_negs_post, 0);
153 assert_eq!(removed, num_negs);
154 assert_eq!(num_negs + g.node_count(), nodes);
155 assert_eq!(num_pos_post, g.node_count());
156
157 // check against filter_map
158 let filtered = og.filter_map(
159 |_, w| if *w >= 0 { Some(*w) } else { None },
160 |_, w| Some(*w),
161 );
162 assert_eq!(g.node_count(), filtered.node_count());
163 /*
164 println!("Iso of graph with nodes={}, edges={}",
165 g.node_count(), g.edge_count());
166 */
167 assert!(is_isomorphic_matching(
168 &filtered,
169 &g,
170 PartialEq::eq,
171 PartialEq::eq
172 ));
173
174 true
175 }
176 quickcheck::quickcheck(prop as fn(Graph<_, _, Directed>) -> bool);
177 quickcheck::quickcheck(prop as fn(Graph<_, _, Undirected>) -> bool);
178 }
179
180 #[test]
graph_retain_edges()181 fn graph_retain_edges() {
182 fn prop<Ty: EdgeType>(mut g: Graph<(), i32, Ty>) -> bool {
183 // Remove all negative edges, these should be randomly spread
184 let og = g.clone();
185 let edges = g.edge_count();
186 let num_negs = g.raw_edges().iter().filter(|n| n.weight < 0).count();
187 let mut removed = 0;
188 g.retain_edges(|g, i| {
189 let keep = g[i] >= 0;
190 if !keep {
191 removed += 1;
192 }
193 keep
194 });
195 let num_negs_post = g.raw_edges().iter().filter(|n| n.weight < 0).count();
196 let num_pos_post = g.raw_edges().iter().filter(|n| n.weight >= 0).count();
197 assert_eq!(num_negs_post, 0);
198 assert_eq!(removed, num_negs);
199 assert_eq!(num_negs + g.edge_count(), edges);
200 assert_eq!(num_pos_post, g.edge_count());
201 if og.edge_count() < 30 {
202 // check against filter_map
203 let filtered = og.filter_map(
204 |_, w| Some(*w),
205 |_, w| if *w >= 0 { Some(*w) } else { None },
206 );
207 assert_eq!(g.node_count(), filtered.node_count());
208 assert!(is_isomorphic(&filtered, &g));
209 }
210 true
211 }
212 quickcheck::quickcheck(prop as fn(Graph<_, _, Directed>) -> bool);
213 quickcheck::quickcheck(prop as fn(Graph<_, _, Undirected>) -> bool);
214 }
215
216 #[test]
stable_graph_retain_edges()217 fn stable_graph_retain_edges() {
218 fn prop<Ty: EdgeType>(mut g: StableGraph<(), i32, Ty>) -> bool {
219 // Remove all negative edges, these should be randomly spread
220 let og = g.clone();
221 let edges = g.edge_count();
222 let num_negs = g.edge_references().filter(|n| *n.weight() < 0).count();
223 let mut removed = 0;
224 g.retain_edges(|g, i| {
225 let keep = g[i] >= 0;
226 if !keep {
227 removed += 1;
228 }
229 keep
230 });
231 let num_negs_post = g.edge_references().filter(|n| *n.weight() < 0).count();
232 let num_pos_post = g.edge_references().filter(|n| *n.weight() >= 0).count();
233 assert_eq!(num_negs_post, 0);
234 assert_eq!(removed, num_negs);
235 assert_eq!(num_negs + g.edge_count(), edges);
236 assert_eq!(num_pos_post, g.edge_count());
237 if og.edge_count() < 30 {
238 // check against filter_map
239 let filtered = og.filter_map(
240 |_, w| Some(*w),
241 |_, w| if *w >= 0 { Some(*w) } else { None },
242 );
243 assert_eq!(g.node_count(), filtered.node_count());
244 }
245 true
246 }
247 quickcheck::quickcheck(prop as fn(StableGraph<_, _, Directed>) -> bool);
248 quickcheck::quickcheck(prop as fn(StableGraph<_, _, Undirected>) -> bool);
249 }
250
251 #[test]
isomorphism_1()252 fn isomorphism_1() {
253 // using small weights so that duplicates are likely
254 fn prop<Ty: EdgeType>(g: Small<Graph<i8, i8, Ty>>) -> bool {
255 let mut rng = rand::thread_rng();
256 // several trials of different isomorphisms of the same graph
257 // mapping of node indices
258 let mut map = g.node_indices().collect::<Vec<_>>();
259 let mut ng = Graph::<_, _, Ty>::with_capacity(g.node_count(), g.edge_count());
260 for _ in 0..1 {
261 rng.shuffle(&mut map);
262 ng.clear();
263
264 for _ in g.node_indices() {
265 ng.add_node(0);
266 }
267 // Assign node weights
268 for i in g.node_indices() {
269 ng[map[i.index()]] = g[i];
270 }
271 // Add edges
272 for i in g.edge_indices() {
273 let (s, t) = g.edge_endpoints(i).unwrap();
274 ng.add_edge(map[s.index()], map[t.index()], g[i]);
275 }
276 if g.node_count() < 20 && g.edge_count() < 50 {
277 assert!(is_isomorphic(&g, &ng));
278 }
279 assert!(is_isomorphic_matching(
280 &g,
281 &ng,
282 PartialEq::eq,
283 PartialEq::eq
284 ));
285 }
286 true
287 }
288 quickcheck::quickcheck(prop::<Undirected> as fn(_) -> bool);
289 quickcheck::quickcheck(prop::<Directed> as fn(_) -> bool);
290 }
291
292 #[test]
isomorphism_modify()293 fn isomorphism_modify() {
294 // using small weights so that duplicates are likely
295 fn prop<Ty: EdgeType>(g: Small<Graph<i16, i8, Ty>>, node: u8, edge: u8) -> bool {
296 println!("graph {:#?}", g);
297 let mut ng = (*g).clone();
298 let i = node_index(node as usize);
299 let j = edge_index(edge as usize);
300 if i.index() < g.node_count() {
301 ng[i] = (g[i] == 0) as i16;
302 }
303 if j.index() < g.edge_count() {
304 ng[j] = (g[j] == 0) as i8;
305 }
306 if i.index() < g.node_count() || j.index() < g.edge_count() {
307 assert!(!is_isomorphic_matching(
308 &g,
309 &ng,
310 PartialEq::eq,
311 PartialEq::eq
312 ));
313 } else {
314 assert!(is_isomorphic_matching(
315 &g,
316 &ng,
317 PartialEq::eq,
318 PartialEq::eq
319 ));
320 }
321 true
322 }
323 quickcheck::quickcheck(prop::<Undirected> as fn(_, _, _) -> bool);
324 quickcheck::quickcheck(prop::<Directed> as fn(_, _, _) -> bool);
325 }
326
327 #[test]
graph_remove_edge()328 fn graph_remove_edge() {
329 fn prop<Ty: EdgeType>(mut g: Graph<(), (), Ty>, a: u8, b: u8) -> bool {
330 let a = node_index(a as usize);
331 let b = node_index(b as usize);
332 let edge = g.find_edge(a, b);
333 if !g.is_directed() {
334 assert_eq!(edge.is_some(), g.find_edge(b, a).is_some());
335 }
336 if let Some(ex) = edge {
337 assert!(g.remove_edge(ex).is_some());
338 }
339 assert_graph_consistent(&g);
340 assert!(g.find_edge(a, b).is_none());
341 assert!(g.neighbors(a).find(|x| *x == b).is_none());
342 if !g.is_directed() {
343 assert!(g.neighbors(b).find(|x| *x == a).is_none());
344 }
345 true
346 }
347 quickcheck::quickcheck(prop as fn(Graph<_, _, Undirected>, _, _) -> bool);
348 quickcheck::quickcheck(prop as fn(Graph<_, _, Directed>, _, _) -> bool);
349 }
350
351 #[cfg(feature = "stable_graph")]
352 #[test]
stable_graph_remove_edge()353 fn stable_graph_remove_edge() {
354 fn prop<Ty: EdgeType>(mut g: StableGraph<(), (), Ty>, a: u8, b: u8) -> bool {
355 let a = node_index(a as usize);
356 let b = node_index(b as usize);
357 let edge = g.find_edge(a, b);
358 if !g.is_directed() {
359 assert_eq!(edge.is_some(), g.find_edge(b, a).is_some());
360 }
361 if let Some(ex) = edge {
362 assert!(g.remove_edge(ex).is_some());
363 }
364 //assert_graph_consistent(&g);
365 assert!(g.find_edge(a, b).is_none());
366 assert!(g.neighbors(a).find(|x| *x == b).is_none());
367 if !g.is_directed() {
368 assert!(g.find_edge(b, a).is_none());
369 assert!(g.neighbors(b).find(|x| *x == a).is_none());
370 }
371 true
372 }
373 quickcheck::quickcheck(prop as fn(StableGraph<_, _, Undirected>, _, _) -> bool);
374 quickcheck::quickcheck(prop as fn(StableGraph<_, _, Directed>, _, _) -> bool);
375 }
376
377 #[cfg(feature = "stable_graph")]
378 #[test]
stable_graph_add_remove_edges()379 fn stable_graph_add_remove_edges() {
380 fn prop<Ty: EdgeType>(mut g: StableGraph<(), (), Ty>, edges: Vec<(u8, u8)>) -> bool {
381 for &(a, b) in &edges {
382 let a = node_index(a as usize);
383 let b = node_index(b as usize);
384 let edge = g.find_edge(a, b);
385
386 if edge.is_none() && g.contains_node(a) && g.contains_node(b) {
387 let _index = g.add_edge(a, b, ());
388 continue;
389 }
390
391 if !g.is_directed() {
392 assert_eq!(edge.is_some(), g.find_edge(b, a).is_some());
393 }
394 if let Some(ex) = edge {
395 assert!(g.remove_edge(ex).is_some());
396 }
397 //assert_graph_consistent(&g);
398 assert!(
399 g.find_edge(a, b).is_none(),
400 "failed to remove edge {:?} from graph {:?}",
401 (a, b),
402 g
403 );
404 assert!(g.neighbors(a).find(|x| *x == b).is_none());
405 if !g.is_directed() {
406 assert!(g.find_edge(b, a).is_none());
407 assert!(g.neighbors(b).find(|x| *x == a).is_none());
408 }
409 }
410 true
411 }
412 quickcheck::quickcheck(prop as fn(StableGraph<_, _, Undirected>, _) -> bool);
413 quickcheck::quickcheck(prop as fn(StableGraph<_, _, Directed>, _) -> bool);
414 }
415
assert_graphmap_consistent<N, E, Ty>(g: &GraphMap<N, E, Ty>) where Ty: EdgeType, N: NodeTrait + fmt::Debug,416 fn assert_graphmap_consistent<N, E, Ty>(g: &GraphMap<N, E, Ty>)
417 where
418 Ty: EdgeType,
419 N: NodeTrait + fmt::Debug,
420 {
421 for (a, b, _weight) in g.all_edges() {
422 assert!(
423 g.contains_edge(a, b),
424 "Edge not in graph! {:?} to {:?}",
425 a,
426 b
427 );
428 assert!(
429 g.neighbors(a).find(|x| *x == b).is_some(),
430 "Edge {:?} not in neighbor list for {:?}",
431 (a, b),
432 a
433 );
434 if !g.is_directed() {
435 assert!(
436 g.neighbors(b).find(|x| *x == a).is_some(),
437 "Edge {:?} not in neighbor list for {:?}",
438 (b, a),
439 b
440 );
441 }
442 }
443 }
444
445 #[test]
graphmap_remove()446 fn graphmap_remove() {
447 fn prop<Ty: EdgeType>(mut g: GraphMap<i8, (), Ty>, a: i8, b: i8) -> bool {
448 //if g.edge_count() > 20 { return true; }
449 assert_graphmap_consistent(&g);
450 let contains = g.contains_edge(a, b);
451 if !g.is_directed() {
452 assert_eq!(contains, g.contains_edge(b, a));
453 }
454 assert_eq!(g.remove_edge(a, b).is_some(), contains);
455 assert!(!g.contains_edge(a, b) && g.neighbors(a).find(|x| *x == b).is_none());
456 //(g.is_directed() || g.neighbors(b).find(|x| *x == a).is_none()));
457 assert!(g.remove_edge(a, b).is_none());
458 assert_graphmap_consistent(&g);
459 true
460 }
461 quickcheck::quickcheck(prop as fn(DiGraphMap<_, _>, _, _) -> bool);
462 quickcheck::quickcheck(prop as fn(UnGraphMap<_, _>, _, _) -> bool);
463 }
464
465 #[test]
graphmap_add_remove()466 fn graphmap_add_remove() {
467 fn prop(mut g: UnGraphMap<i8, ()>, a: i8, b: i8) -> bool {
468 assert_eq!(g.contains_edge(a, b), g.add_edge(a, b, ()).is_some());
469 g.remove_edge(a, b);
470 !g.contains_edge(a, b)
471 && g.neighbors(a).find(|x| *x == b).is_none()
472 && g.neighbors(b).find(|x| *x == a).is_none()
473 }
474 quickcheck::quickcheck(prop as fn(_, _, _) -> bool);
475 }
476
sort_sccs<T: Ord>(v: &mut [Vec<T>])477 fn sort_sccs<T: Ord>(v: &mut [Vec<T>]) {
478 for scc in &mut *v {
479 scc.sort();
480 }
481 v.sort();
482 }
483
484 quickcheck! {
485 fn graph_sccs(g: Graph<(), ()>) -> bool {
486 let mut sccs = kosaraju_scc(&g);
487 let mut tsccs = tarjan_scc(&g);
488 sort_sccs(&mut sccs);
489 sort_sccs(&mut tsccs);
490 if sccs != tsccs {
491 println!("{:?}",
492 Dot::with_config(&g, &[Config::EdgeNoLabel,
493 Config::NodeIndexLabel]));
494 println!("Sccs {:?}", sccs);
495 println!("Sccs (Tarjan) {:?}", tsccs);
496 return false;
497 }
498 true
499 }
500 }
501
502 quickcheck! {
503 fn kosaraju_scc_is_topo_sort(g: Graph<(), ()>) -> bool {
504 let tsccs = kosaraju_scc(&g);
505 let firsts = vec(tsccs.iter().rev().map(|v| v[0]));
506 subset_is_topo_order(&g, &firsts)
507 }
508 }
509
510 quickcheck! {
511 fn tarjan_scc_is_topo_sort(g: Graph<(), ()>) -> bool {
512 let tsccs = tarjan_scc(&g);
513 let firsts = vec(tsccs.iter().rev().map(|v| v[0]));
514 subset_is_topo_order(&g, &firsts)
515 }
516 }
517
518 quickcheck! {
519 // Reversed edges gives the same sccs (when sorted)
520 fn graph_reverse_sccs(g: Graph<(), ()>) -> bool {
521 let mut sccs = kosaraju_scc(&g);
522 let mut tsccs = kosaraju_scc(Reversed(&g));
523 sort_sccs(&mut sccs);
524 sort_sccs(&mut tsccs);
525 if sccs != tsccs {
526 println!("{:?}",
527 Dot::with_config(&g, &[Config::EdgeNoLabel,
528 Config::NodeIndexLabel]));
529 println!("Sccs {:?}", sccs);
530 println!("Sccs (Reversed) {:?}", tsccs);
531 return false;
532 }
533 true
534 }
535 }
536
537 quickcheck! {
538 // Reversed edges gives the same sccs (when sorted)
539 fn graphmap_reverse_sccs(g: DiGraphMap<u16, ()>) -> bool {
540 let mut sccs = kosaraju_scc(&g);
541 let mut tsccs = kosaraju_scc(Reversed(&g));
542 sort_sccs(&mut sccs);
543 sort_sccs(&mut tsccs);
544 if sccs != tsccs {
545 println!("{:?}",
546 Dot::with_config(&g, &[Config::EdgeNoLabel,
547 Config::NodeIndexLabel]));
548 println!("Sccs {:?}", sccs);
549 println!("Sccs (Reversed) {:?}", tsccs);
550 return false;
551 }
552 true
553 }
554 }
555
556 #[test]
graph_condensation_acyclic()557 fn graph_condensation_acyclic() {
558 fn prop(g: Graph<(), ()>) -> bool {
559 !is_cyclic_directed(&condensation(g, /* make_acyclic */ true))
560 }
561 quickcheck::quickcheck(prop as fn(_) -> bool);
562 }
563
564 #[derive(Debug, Clone)]
565 struct DAG<N: Default + Clone + Send + 'static>(Graph<N, ()>);
566
567 impl<N: Default + Clone + Send + 'static> quickcheck::Arbitrary for DAG<N> {
arbitrary<G: quickcheck::Gen>(g: &mut G) -> Self568 fn arbitrary<G: quickcheck::Gen>(g: &mut G) -> Self {
569 let nodes = usize::arbitrary(g);
570 if nodes == 0 {
571 return DAG(Graph::with_capacity(0, 0));
572 }
573 let split = g.gen_range(0., 1.);
574 let max_width = f64::sqrt(nodes as f64) as usize;
575 let tall = (max_width as f64 * split) as usize;
576 let fat = max_width - tall;
577
578 let edge_prob = 1. - (1. - g.gen_range(0., 1.)) * (1. - g.gen_range(0., 1.));
579 let edges = ((nodes as f64).powi(2) * edge_prob) as usize;
580 let mut gr = Graph::with_capacity(nodes, edges);
581 let mut nodes = 0;
582 for _ in 0..tall {
583 let cur_nodes = g.gen_range(0, fat);
584 for _ in 0..cur_nodes {
585 gr.add_node(N::default());
586 }
587 for j in 0..nodes {
588 for k in 0..cur_nodes {
589 if g.gen_range(0., 1.) < edge_prob {
590 gr.add_edge(NodeIndex::new(j), NodeIndex::new(k + nodes), ());
591 }
592 }
593 }
594 nodes += cur_nodes;
595 }
596 DAG(gr)
597 }
598
599 // shrink the graph by splitting it in two by a very
600 // simple algorithm, just even and odd node indices
shrink(&self) -> Box<dyn Iterator<Item = Self>>601 fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
602 let self_ = self.clone();
603 Box::new((0..2).filter_map(move |x| {
604 let gr = self_.0.filter_map(
605 |i, w| {
606 if i.index() % 2 == x {
607 Some(w.clone())
608 } else {
609 None
610 }
611 },
612 |_, w| Some(w.clone()),
613 );
614 // make sure we shrink
615 if gr.node_count() < self_.0.node_count() {
616 Some(DAG(gr))
617 } else {
618 None
619 }
620 }))
621 }
622 }
623
is_topo_order<N>(gr: &Graph<N, (), Directed>, order: &[NodeIndex]) -> bool624 fn is_topo_order<N>(gr: &Graph<N, (), Directed>, order: &[NodeIndex]) -> bool {
625 if gr.node_count() != order.len() {
626 println!(
627 "Graph ({}) and count ({}) had different amount of nodes.",
628 gr.node_count(),
629 order.len()
630 );
631 return false;
632 }
633 // check all the edges of the graph
634 for edge in gr.raw_edges() {
635 let a = edge.source();
636 let b = edge.target();
637 let ai = order.find(&a).unwrap();
638 let bi = order.find(&b).unwrap();
639 if ai >= bi {
640 println!("{:?} > {:?} ", a, b);
641 return false;
642 }
643 }
644 true
645 }
646
subset_is_topo_order<N>(gr: &Graph<N, (), Directed>, order: &[NodeIndex]) -> bool647 fn subset_is_topo_order<N>(gr: &Graph<N, (), Directed>, order: &[NodeIndex]) -> bool {
648 if gr.node_count() < order.len() {
649 println!(
650 "Graph (len={}) had less nodes than order (len={})",
651 gr.node_count(),
652 order.len()
653 );
654 return false;
655 }
656 // check all the edges of the graph
657 for edge in gr.raw_edges() {
658 let a = edge.source();
659 let b = edge.target();
660 if a == b {
661 continue;
662 }
663 // skip those that are not in the subset
664 let ai = match order.find(&a) {
665 Some(i) => i,
666 None => continue,
667 };
668 let bi = match order.find(&b) {
669 Some(i) => i,
670 None => continue,
671 };
672 if ai >= bi {
673 println!("{:?} > {:?} ", a, b);
674 return false;
675 }
676 }
677 true
678 }
679
680 #[test]
full_topo()681 fn full_topo() {
682 fn prop(DAG(gr): DAG<()>) -> bool {
683 let order = toposort(&gr, None).unwrap();
684 is_topo_order(&gr, &order)
685 }
686 quickcheck::quickcheck(prop as fn(_) -> bool);
687 }
688
689 #[test]
full_topo_generic()690 fn full_topo_generic() {
691 fn prop_generic(DAG(mut gr): DAG<usize>) -> bool {
692 assert!(!is_cyclic_directed(&gr));
693 let mut index = 0;
694 let mut topo = Topo::new(&gr);
695 while let Some(nx) = topo.next(&gr) {
696 gr[nx] = index;
697 index += 1;
698 }
699
700 let mut order = Vec::new();
701 index = 0;
702 let mut topo = Topo::new(&gr);
703 while let Some(nx) = topo.next(&gr) {
704 order.push(nx);
705 assert_eq!(gr[nx], index);
706 index += 1;
707 }
708 if !is_topo_order(&gr, &order) {
709 println!("{:?}", gr);
710 return false;
711 }
712
713 {
714 order.clear();
715 let mut topo = Topo::new(&gr);
716 while let Some(nx) = topo.next(&gr) {
717 order.push(nx);
718 }
719 if !is_topo_order(&gr, &order) {
720 println!("{:?}", gr);
721 return false;
722 }
723 }
724 true
725 }
726 quickcheck::quickcheck(prop_generic as fn(_) -> bool);
727 }
728
729 quickcheck! {
730 // checks that the distances computed by dijkstra satisfy the triangle
731 // inequality.
732 fn dijkstra_triangle_ineq(g: Graph<u32, u32>, node: usize) -> bool {
733 if g.node_count() == 0 {
734 return true;
735 }
736 let v = node_index(node % g.node_count());
737 let distances = dijkstra(&g, v, None, |e| *e.weight());
738 for v2 in distances.keys() {
739 let dv2 = distances[v2];
740 // triangle inequality:
741 // d(v,u) <= d(v,v2) + w(v2,u)
742 for edge in g.edges(*v2) {
743 let u = edge.target();
744 let w = edge.weight();
745 if distances.contains_key(&u) && distances[&u] > dv2 + w {
746 return false;
747 }
748 }
749 }
750 true
751 }
752 }
753
set<I>(iter: I) -> HashSet<I::Item> where I: IntoIterator, I::Item: Hash + Eq,754 fn set<I>(iter: I) -> HashSet<I::Item>
755 where
756 I: IntoIterator,
757 I::Item: Hash + Eq,
758 {
759 iter.into_iter().collect()
760 }
761
762 quickcheck! {
763 fn dfs_visit(gr: Graph<(), ()>, node: usize) -> bool {
764 use petgraph::visit::{Visitable, VisitMap};
765 use petgraph::visit::DfsEvent::*;
766 use petgraph::visit::{Time, depth_first_search};
767 if gr.node_count() == 0 {
768 return true;
769 }
770 let start_node = node_index(node % gr.node_count());
771
772 let invalid_time = Time(!0);
773 let mut discover_time = vec![invalid_time; gr.node_count()];
774 let mut finish_time = vec![invalid_time; gr.node_count()];
775 let mut has_tree_edge = gr.visit_map();
776 let mut edges = HashSet::new();
777 depth_first_search(&gr, Some(start_node).into_iter().chain(gr.node_indices()),
778 |evt| {
779 match evt {
780 Discover(n, t) => discover_time[n.index()] = t,
781 Finish(n, t) => finish_time[n.index()] = t,
782 TreeEdge(u, v) => {
783 // v is an ancestor of u
784 assert!(has_tree_edge.visit(v), "Two tree edges to {:?}!", v);
785 assert!(discover_time[v.index()] == invalid_time);
786 assert!(discover_time[u.index()] != invalid_time);
787 assert!(finish_time[u.index()] == invalid_time);
788 edges.insert((u, v));
789 }
790 BackEdge(u, v) => {
791 // u is an ancestor of v
792 assert!(discover_time[v.index()] != invalid_time);
793 assert!(finish_time[v.index()] == invalid_time);
794 edges.insert((u, v));
795 }
796 CrossForwardEdge(u, v) => {
797 edges.insert((u, v));
798 }
799 }
800 });
801 assert!(discover_time.iter().all(|x| *x != invalid_time));
802 assert!(finish_time.iter().all(|x| *x != invalid_time));
803 assert_eq!(edges.len(), gr.edge_count());
804 assert_eq!(edges, set(gr.edge_references().map(|e| (e.source(), e.target()))));
805 true
806 }
807 }
808
809 quickcheck! {
810 fn test_bellman_ford(gr: Graph<(), f32>) -> bool {
811 let mut gr = gr;
812 for elt in gr.edge_weights_mut() {
813 *elt = elt.abs();
814 }
815 if gr.node_count() == 0 {
816 return true;
817 }
818 for (i, start) in gr.node_indices().enumerate() {
819 if i >= 10 { break; } // testing all is too slow
820 bellman_ford(&gr, start).unwrap();
821 }
822 true
823 }
824 }
825
826 quickcheck! {
827 fn test_bellman_ford_undir(gr: Graph<(), f32, Undirected>) -> bool {
828 let mut gr = gr;
829 for elt in gr.edge_weights_mut() {
830 *elt = elt.abs();
831 }
832 if gr.node_count() == 0 {
833 return true;
834 }
835 for (i, start) in gr.node_indices().enumerate() {
836 if i >= 10 { break; } // testing all is too slow
837 bellman_ford(&gr, start).unwrap();
838 }
839 true
840 }
841 }
842
843 defmac!(iter_eq a, b => a.eq(b));
844 defmac!(nodes_eq ref a, ref b => a.node_references().eq(b.node_references()));
845 defmac!(edgew_eq ref a, ref b => a.edge_references().eq(b.edge_references()));
846 defmac!(edges_eq ref a, ref b =>
847 iter_eq!(
848 a.edge_references().map(|e| (e.source(), e.target())),
849 b.edge_references().map(|e| (e.source(), e.target()))));
850
851 quickcheck! {
852 fn test_di_from(gr1: DiGraph<i32, i32>) -> () {
853 let sgr = StableGraph::from(gr1.clone());
854 let gr2 = Graph::from(sgr);
855
856 assert!(nodes_eq!(gr1, gr2));
857 assert!(edgew_eq!(gr1, gr2));
858 assert!(edges_eq!(gr1, gr2));
859 }
860 fn test_un_from(gr1: UnGraph<i32, i32>) -> () {
861 let sgr = StableGraph::from(gr1.clone());
862 let gr2 = Graph::from(sgr);
863
864 assert!(nodes_eq!(gr1, gr2));
865 assert!(edgew_eq!(gr1, gr2));
866 assert!(edges_eq!(gr1, gr2));
867 }
868
869 fn test_graph_from_stable_graph(gr1: StableDiGraph<usize, usize>) -> () {
870 let mut gr1 = gr1;
871 let gr2 = Graph::from(gr1.clone());
872
873 // renumber the stablegraph nodes and put the new index in the
874 // associated data
875 let mut index = 0;
876 for i in 0..gr1.node_bound() {
877 let ni = node_index(i);
878 if gr1.contains_node(ni) {
879 gr1[ni] = index;
880 index += 1;
881 }
882 }
883 if let Some(edge_bound) = gr1.edge_references().next_back()
884 .map(|ed| ed.id().index() + 1)
885 {
886 index = 0;
887 for i in 0..edge_bound {
888 let ni = edge_index(i);
889 if gr1.edge_weight(ni).is_some() {
890 gr1[ni] = index;
891 index += 1;
892 }
893 }
894 }
895
896 assert_equal(
897 // Remap the stablegraph to compact indices
898 gr1.edge_references().map(|ed| (edge_index(*ed.weight()), gr1[ed.source()], gr1[ed.target()])),
899 gr2.edge_references().map(|ed| (ed.id(), ed.source().index(), ed.target().index()))
900 );
901 }
902
903 fn stable_di_graph_map_id(gr1: StableDiGraph<usize, usize>) -> () {
904 let gr2 = gr1.map(|_, &nw| nw, |_, &ew| ew);
905 assert!(nodes_eq!(gr1, gr2));
906 assert!(edgew_eq!(gr1, gr2));
907 assert!(edges_eq!(gr1, gr2));
908 }
909
910 fn stable_un_graph_map_id(gr1: StableUnGraph<usize, usize>) -> () {
911 let gr2 = gr1.map(|_, &nw| nw, |_, &ew| ew);
912 assert!(nodes_eq!(gr1, gr2));
913 assert!(edgew_eq!(gr1, gr2));
914 assert!(edges_eq!(gr1, gr2));
915 }
916
917 fn stable_di_graph_filter_map_id(gr1: StableDiGraph<usize, usize>) -> () {
918 let gr2 = gr1.filter_map(|_, &nw| Some(nw), |_, &ew| Some(ew));
919 assert!(nodes_eq!(gr1, gr2));
920 assert!(edgew_eq!(gr1, gr2));
921 assert!(edges_eq!(gr1, gr2));
922 }
923
924 fn test_stable_un_graph_filter_map_id(gr1: StableUnGraph<usize, usize>) -> () {
925 let gr2 = gr1.filter_map(|_, &nw| Some(nw), |_, &ew| Some(ew));
926 assert!(nodes_eq!(gr1, gr2));
927 assert!(edgew_eq!(gr1, gr2));
928 assert!(edges_eq!(gr1, gr2));
929 }
930
931 fn stable_di_graph_filter_map_remove(gr1: Small<StableDiGraph<i32, i32>>,
932 nodes: Vec<usize>,
933 edges: Vec<usize>) -> ()
934 {
935 let gr2 = gr1.filter_map(|ix, &nw| {
936 if !nodes.contains(&ix.index()) { Some(nw) } else { None }
937 },
938 |ix, &ew| {
939 if !edges.contains(&ix.index()) { Some(ew) } else { None }
940 });
941 let check_nodes = &set(gr1.node_indices()) - &set(cloned(&nodes).map(node_index));
942 let mut check_edges = &set(gr1.edge_indices()) - &set(cloned(&edges).map(edge_index));
943 // remove all edges with endpoint in removed nodes
944 for edge in gr1.edge_references() {
945 if nodes.contains(&edge.source().index()) ||
946 nodes.contains(&edge.target().index()) {
947 check_edges.remove(&edge.id());
948 }
949 }
950 // assert maintained
951 for i in check_nodes {
952 assert_eq!(gr1[i], gr2[i]);
953 }
954 for i in check_edges {
955 assert_eq!(gr1[i], gr2[i]);
956 assert_eq!(gr1.edge_endpoints(i), gr2.edge_endpoints(i));
957 }
958
959 // assert removals
960 for i in nodes {
961 assert!(gr2.node_weight(node_index(i)).is_none());
962 }
963 for i in edges {
964 assert!(gr2.edge_weight(edge_index(i)).is_none());
965 }
966 }
967 }
968