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