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]
remov()64 fn remov() {
65     let mut g = UnGraphMap::new();
66     g.add_node(1);
67     g.add_node(2);
68     g.add_edge(1, 2, -1);
69 
70     assert_eq!(g.edge_weight(1, 2), Some(&-1));
71     assert_eq!(g.edge_weight(2, 1), Some(&-1));
72     assert_eq!(g.neighbors(1).count(), 1);
73 
74     let noexist = g.remove_edge(2, 3);
75     assert_eq!(noexist, None);
76 
77     let exist = g.remove_edge(2, 1);
78     assert_eq!(exist, Some(-1));
79     assert_eq!(g.edge_count(), 0);
80     assert_eq!(g.edge_weight(1, 2), None);
81     assert_eq!(g.edge_weight(2, 1), None);
82     assert_eq!(g.neighbors(1).count(), 0);
83 }
84 
85 #[test]
remove_directed()86 fn remove_directed() {
87     let mut g = GraphMap::<_, _, Directed>::with_capacity(0, 0);
88     g.add_edge(1, 2, -1);
89     println!("{:?}", g);
90 
91     assert_eq!(g.edge_weight(1, 2), Some(&-1));
92     assert_eq!(g.edge_weight(2, 1), None);
93     assert_eq!(g.neighbors(1).count(), 1);
94 
95     let noexist = g.remove_edge(2, 3);
96     assert_eq!(noexist, None);
97 
98     let exist = g.remove_edge(2, 1);
99     assert_eq!(exist, None);
100     let exist = g.remove_edge(1, 2);
101     assert_eq!(exist, Some(-1));
102     println!("{:?}", g);
103     assert_eq!(g.edge_count(), 0);
104     assert_eq!(g.edge_weight(1, 2), None);
105     assert_eq!(g.edge_weight(2, 1), None);
106     assert_eq!(g.neighbors(1).count(), 0);
107 }
108 
109 #[test]
dfs()110 fn dfs() {
111     let mut gr = UnGraphMap::default();
112     let h = gr.add_node("H");
113     let i = gr.add_node("I");
114     let j = gr.add_node("J");
115     let k = gr.add_node("K");
116     // Z is disconnected.
117     let z = gr.add_node("Z");
118     gr.add_edge(h, i, 1.);
119     gr.add_edge(h, j, 3.);
120     gr.add_edge(i, j, 1.);
121     gr.add_edge(i, k, 2.);
122 
123     println!("{:?}", gr);
124 
125     {
126         let mut cnt = 0;
127         let mut dfs = Dfs::new(&gr, h);
128         while let Some(_) = dfs.next(&gr) {
129             cnt += 1;
130         }
131         assert_eq!(cnt, 4);
132     }
133     {
134         let mut cnt = 0;
135         let mut dfs = Dfs::new(&gr, z);
136         while let Some(_) = dfs.next(&gr) {
137             cnt += 1;
138         }
139         assert_eq!(cnt, 1);
140     }
141 
142     assert_eq!(Dfs::new(&gr, h).iter(&gr).count(), 4);
143     assert_eq!(Dfs::new(&gr, i).iter(&gr).count(), 4);
144     assert_eq!(Dfs::new(&gr, z).iter(&gr).count(), 1);
145 }
146 
147 #[test]
edge_iterator()148 fn edge_iterator() {
149     let mut gr = UnGraphMap::new();
150     let h = gr.add_node("H");
151     let i = gr.add_node("I");
152     let j = gr.add_node("J");
153     let k = gr.add_node("K");
154     gr.add_edge(h, i, 1);
155     gr.add_edge(h, j, 2);
156     gr.add_edge(i, j, 3);
157     gr.add_edge(i, k, 4);
158 
159     let real_edges: HashSet<_> = gr.all_edges().map(|(a, b, &w)| (a, b, w)).collect();
160     let expected_edges: HashSet<_> =
161         vec![("H", "I", 1), ("H", "J", 2), ("I", "J", 3), ("I", "K", 4)]
162             .into_iter()
163             .collect();
164 
165     assert_eq!(real_edges, expected_edges);
166 }
167 
168 #[test]
from_edges()169 fn from_edges() {
170     let gr =
171         GraphMap::<_, _, Undirected>::from_edges(&[("a", "b", 1), ("a", "c", 2), ("c", "d", 3)]);
172     assert_eq!(gr.node_count(), 4);
173     assert_eq!(gr.edge_count(), 3);
174     assert_eq!(gr[("a", "c")], 2);
175 
176     let gr = GraphMap::<_, (), Undirected>::from_edges(&[
177         (0, 1),
178         (0, 2),
179         (0, 3),
180         (1, 2),
181         (1, 3),
182         (2, 3),
183     ]);
184     assert_eq!(gr.node_count(), 4);
185     assert_eq!(gr.edge_count(), 6);
186     assert_eq!(gr.neighbors(0).count(), 3);
187     assert_eq!(gr.neighbors(1).count(), 3);
188     assert_eq!(gr.neighbors(2).count(), 3);
189     assert_eq!(gr.neighbors(3).count(), 3);
190 
191     println!("{:?}", Dot::with_config(&gr, &[Config::EdgeNoLabel]));
192 }
193 
194 #[test]
graphmap_directed()195 fn graphmap_directed() {
196     //let root = TypedArena::<Node<_>>::new();
197     let mut gr = DiGraphMap::<_, ()>::with_capacity(0, 0);
198     //let node = |&: name: &'static str| Ptr(root.alloc(Node(name.to_string())));
199     let a = gr.add_node("A");
200     let b = gr.add_node("B");
201     let c = gr.add_node("C");
202     let d = gr.add_node("D");
203     let e = gr.add_node("E");
204     let edges = [(a, b), (a, c), (a, d), (b, c), (c, d), (d, e), (b, b)];
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
219     N: Ord + fmt::Debug,
220 {
221     // normalize the result and compare with the answer.
222     for scc in &mut res {
223         scc.sort();
224     }
225     res.sort();
226     for scc in &mut answer {
227         scc.sort();
228     }
229     answer.sort();
230     assert_eq!(res, answer);
231 }
232 
233 #[test]
scc()234 fn scc() {
235     let gr: GraphMap<_, u32, Directed> = GraphMap::from_edges(&[
236         (6, 0, 0),
237         (0, 3, 1),
238         (3, 6, 2),
239         (8, 6, 3),
240         (8, 2, 4),
241         (2, 5, 5),
242         (5, 8, 6),
243         (7, 5, 7),
244         (1, 7, 8),
245         (7, 4, 9),
246         (4, 1, 10),
247     ]);
248 
249     assert_sccs_eq(
250         petgraph::algo::kosaraju_scc(&gr),
251         vec![vec![0, 3, 6], vec![1, 4, 7], vec![2, 5, 8]],
252     );
253 }
254 
255 #[test]
test_into_graph()256 fn test_into_graph() {
257     let gr: GraphMap<_, u32, Directed> = GraphMap::from_edges(&[
258         (6, 0, 0),
259         (0, 3, 1),
260         (3, 6, 2),
261         (8, 6, 3),
262         (8, 2, 4),
263         (2, 5, 5),
264         (5, 8, 6),
265         (7, 5, 7),
266         (1, 7, 8),
267         (7, 4, 9),
268         (4, 1, 10),
269     ]);
270 
271     let graph: Graph<_, _, _> = gr.clone().into_graph();
272     println!("{}", Dot::new(&gr));
273     println!("{}", Dot::new(&graph));
274 
275     // node weigths in `graph` are node identifiers in `gr`.
276     for edge in graph.edge_references() {
277         let a = edge.source();
278         let b = edge.target();
279         let aw = graph[a];
280         let bw = graph[b];
281         assert_eq!(&gr[(aw, bw)], edge.weight());
282     }
283 }
284 
285 #[test]
test_all_edges_mut()286 fn test_all_edges_mut() {
287     // graph with edge weights equal to in+out
288     let mut graph: GraphMap<_, u32, Directed> =
289         GraphMap::from_edges(&[(0, 1, 1), (1, 2, 3), (2, 0, 2)]);
290 
291     // change it so edge weight is equal to 2 * (in+out)
292     for (start, end, weight) in graph.all_edges_mut() {
293         *weight = (start + end) * 2;
294     }
295 
296     // test it
297     for (start, end, weight) in graph.all_edges() {
298         assert_eq!((start + end) * 2, *weight);
299     }
300 }
301 
302 #[test]
neighbors_incoming_includes_self_loops()303 fn neighbors_incoming_includes_self_loops() {
304     let mut graph = DiGraphMap::new();
305 
306     graph.add_node(());
307     graph.add_edge((), (), ());
308 
309     let mut neighbors = graph.neighbors_directed((), Incoming);
310     assert_eq!(neighbors.next(), Some(()));
311     assert_eq!(neighbors.next(), None);
312 }
313 
314 #[test]
undirected_neighbors_includes_self_loops()315 fn undirected_neighbors_includes_self_loops() {
316     let mut graph = UnGraphMap::new();
317 
318     graph.add_node(());
319     graph.add_edge((), (), ());
320 
321     let mut neighbors = graph.neighbors(());
322     assert_eq!(neighbors.next(), Some(()));
323     assert_eq!(neighbors.next(), None);
324 }
325 
326 #[test]
self_loops_can_be_removed()327 fn self_loops_can_be_removed() {
328     let mut graph = DiGraphMap::new();
329 
330     graph.add_node(());
331     graph.add_edge((), (), ());
332 
333     graph.remove_edge((), ());
334 
335     assert_eq!(graph.neighbors_directed((), Outgoing).next(), None);
336     assert_eq!(graph.neighbors_directed((), Incoming).next(), None);
337 }
338