1 #![feature(test)]
2 
3 extern crate petgraph;
4 extern crate test;
5 
6 use test::Bencher;
7 
8 use petgraph::algo;
9 use petgraph::matrix_graph::{node_index, MatrixGraph};
10 use petgraph::{Directed, EdgeType, Incoming, Outgoing};
11 
12 #[bench]
add_100_nodes(b: &mut test::Bencher)13 fn add_100_nodes(b: &mut test::Bencher) {
14     b.iter(|| {
15         let mut g = MatrixGraph::<(), ()>::with_capacity(100);
16 
17         for _ in 0..100 {
18             let _ = g.add_node(());
19         }
20     });
21 }
22 
23 #[bench]
add_100_edges_to_self(b: &mut test::Bencher)24 fn add_100_edges_to_self(b: &mut test::Bencher) {
25     let mut g = MatrixGraph::<(), ()>::with_capacity(100);
26     let nodes: Vec<_> = (0..100).map(|_| g.add_node(())).collect();
27     let g = g;
28 
29     b.iter(|| {
30         let mut g = g.clone();
31 
32         for &node in nodes.iter() {
33             g.add_edge(node, node, ());
34         }
35     });
36 }
37 
38 #[bench]
add_5_edges_for_each_of_100_nodes(b: &mut test::Bencher)39 fn add_5_edges_for_each_of_100_nodes(b: &mut test::Bencher) {
40     let mut g = MatrixGraph::<(), ()>::with_capacity(100);
41     let nodes: Vec<_> = (0..100).map(|_| g.add_node(())).collect();
42     let g = g;
43 
44     let edges_to_add: Vec<_> = nodes
45         .iter()
46         .enumerate()
47         .flat_map(|(i, &node)| {
48             let edges: Vec<_> = (0..5)
49                 .map(|j| (i + j + 1) % nodes.len())
50                 .map(|j| (node, nodes[j]))
51                 .collect();
52 
53             edges
54         })
55         .collect();
56 
57     b.iter(|| {
58         let mut g = g.clone();
59 
60         for &(source, target) in edges_to_add.iter() {
61             g.add_edge(source, target, ());
62         }
63     });
64 }
65 
66 #[bench]
add_edges_from_root(bench: &mut test::Bencher)67 fn add_edges_from_root(bench: &mut test::Bencher) {
68     bench.iter(|| {
69         let mut gr = MatrixGraph::new();
70         let a = gr.add_node(());
71 
72         for _ in 0..100 {
73             let b = gr.add_node(());
74             gr.add_edge(a, b, ());
75         }
76     });
77 }
78 
79 #[bench]
add_adjacent_edges(bench: &mut test::Bencher)80 fn add_adjacent_edges(bench: &mut test::Bencher) {
81     bench.iter(|| {
82         let mut gr = MatrixGraph::new();
83         let mut prev = None;
84         for _ in 0..100 {
85             let b = gr.add_node(());
86 
87             if let Some(a) = prev {
88                 gr.add_edge(a, b, ());
89             }
90 
91             prev = Some(b);
92         }
93     });
94 }
95 
96 /// An almost full set
97 const FULL: &str = "
98  1 1 1 1 1 1 1 1 1 1
99  1 1 1 1 1 1 1 1 1 1
100  1 1 1 1 1 1 1 1 1 1
101  1 1 1 1 1 1 1 1 1 1
102  1 1 1 1 1 1 1 1 1 1
103  1 1 1 1 1 1 1 1 1 1
104  1 1 1 1 1 1 1 1 1 1
105  1 1 1 1 1 1 1 1 1 1
106  1 1 1 1 0 1 1 1 0 1
107  1 1 1 1 1 1 1 1 1 1
108 ";
109 
110 const BIGGER: &str = "
111  0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
112  0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
113  0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
114  0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
115  0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
116  0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
117  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
118  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
119  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
120  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
121  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
122  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
123  0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
124  0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
125  0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
126  0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
127  0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
128  0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
129  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
130  0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
131  0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
132  1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0
133  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
134  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
135  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
136  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
137  0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
138  0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0
139  1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0
140  0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0
141  0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0
142  0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1
143  0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0
144  0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 0
145  0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1
146  0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0
147  0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1
148  0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 1
149  0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1
150  0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0
151 ";
152 
153 /// Parse a text adjacency matrix format into a directed graph
parse_matrix<Ty: EdgeType>(s: &str) -> MatrixGraph<(), (), Ty>154 fn parse_matrix<Ty: EdgeType>(s: &str) -> MatrixGraph<(), (), Ty> {
155     let mut gr = MatrixGraph::default();
156     let s = s.trim();
157     let lines = s.lines().filter(|l| !l.is_empty());
158     for (row, line) in lines.enumerate() {
159         for (col, word) in line.split(' ').filter(|s| !s.is_empty()).enumerate() {
160             let has_edge = word.parse::<i32>().unwrap();
161             assert!(has_edge == 0 || has_edge == 1);
162             if has_edge == 0 {
163                 continue;
164             }
165             while col >= gr.node_count() || row >= gr.node_count() {
166                 gr.add_node(());
167             }
168             gr.add_edge(node_index(row), node_index(col), ());
169         }
170     }
171     gr
172 }
173 
174 #[bench]
full_edges_out(bench: &mut Bencher)175 fn full_edges_out(bench: &mut Bencher) {
176     let a = parse_matrix::<Directed>(FULL);
177     bench.iter(|| a.edges_directed(node_index(1), Outgoing).count())
178 }
179 
180 #[bench]
full_edges_in(bench: &mut Bencher)181 fn full_edges_in(bench: &mut Bencher) {
182     let a = parse_matrix::<Directed>(FULL);
183     bench.iter(|| a.edges_directed(node_index(1), Incoming).count())
184 }
185 
186 #[bench]
full_neighbors_out(bench: &mut Bencher)187 fn full_neighbors_out(bench: &mut Bencher) {
188     let a = parse_matrix::<Directed>(FULL);
189     bench.iter(|| a.neighbors_directed(node_index(1), Outgoing).count())
190 }
191 
192 #[bench]
full_neighbors_in(bench: &mut Bencher)193 fn full_neighbors_in(bench: &mut Bencher) {
194     let a = parse_matrix::<Directed>(FULL);
195 
196     bench.iter(|| a.neighbors_directed(node_index(1), Incoming).count())
197 }
198 
199 #[bench]
full_kosaraju_sccs(bench: &mut Bencher)200 fn full_kosaraju_sccs(bench: &mut Bencher) {
201     let a = parse_matrix::<Directed>(FULL);
202     bench.iter(|| algo::kosaraju_scc(&a));
203 }
204 
205 #[bench]
full_tarjan_sccs(bench: &mut Bencher)206 fn full_tarjan_sccs(bench: &mut Bencher) {
207     let a = parse_matrix::<Directed>(FULL);
208     bench.iter(|| algo::tarjan_scc(&a));
209 }
210 
211 #[bench]
bigger_edges_out(bench: &mut Bencher)212 fn bigger_edges_out(bench: &mut Bencher) {
213     let a = parse_matrix::<Directed>(BIGGER);
214     bench.iter(|| a.edges_directed(node_index(1), Outgoing).count())
215 }
216 
217 #[bench]
bigger_edges_in(bench: &mut Bencher)218 fn bigger_edges_in(bench: &mut Bencher) {
219     let a = parse_matrix::<Directed>(BIGGER);
220     bench.iter(|| a.edges_directed(node_index(1), Incoming).count())
221 }
222 
223 #[bench]
bigger_neighbors_out(bench: &mut Bencher)224 fn bigger_neighbors_out(bench: &mut Bencher) {
225     let a = parse_matrix::<Directed>(BIGGER);
226     bench.iter(|| a.neighbors_directed(node_index(1), Outgoing).count())
227 }
228 
229 #[bench]
bigger_neighbors_in(bench: &mut Bencher)230 fn bigger_neighbors_in(bench: &mut Bencher) {
231     let a = parse_matrix::<Directed>(BIGGER);
232 
233     bench.iter(|| a.neighbors_directed(node_index(1), Incoming).count())
234 }
235 
236 #[bench]
bigger_kosaraju_sccs(bench: &mut Bencher)237 fn bigger_kosaraju_sccs(bench: &mut Bencher) {
238     let a = parse_matrix::<Directed>(BIGGER);
239     bench.iter(|| algo::kosaraju_scc(&a));
240 }
241 
242 #[bench]
bigger_tarjan_sccs(bench: &mut Bencher)243 fn bigger_tarjan_sccs(bench: &mut Bencher) {
244     let a = parse_matrix::<Directed>(BIGGER);
245     bench.iter(|| algo::tarjan_scc(&a));
246 }
247