1 #![feature(test)]
2
3 extern crate petgraph;
4 extern crate test;
5
6 use petgraph::prelude::*;
7 use std::cmp::{max, min};
8 use test::Bencher;
9
10 use petgraph::algo::{bellman_ford, find_negative_cycle};
11
12 #[bench]
bellman_ford_bench(bench: &mut Bencher)13 fn bellman_ford_bench(bench: &mut Bencher) {
14 static NODE_COUNT: usize = 100;
15 let mut g = Graph::new();
16 let nodes: Vec<NodeIndex<_>> = (0..NODE_COUNT).map(|i| g.add_node(i)).collect();
17 for i in 0..NODE_COUNT {
18 let n1 = nodes[i];
19 let neighbour_count = i % 8 + 3;
20 let j_from = max(0, i as i32 - neighbour_count as i32 / 2) as usize;
21 let j_to = min(NODE_COUNT, j_from + neighbour_count);
22 for j in j_from..j_to {
23 let n2 = nodes[j];
24 let mut distance: f64 = ((i + 3) % 10) as f64;
25 if n1 != n2 {
26 distance -= 1.0
27 }
28 g.add_edge(n1, n2, distance);
29 }
30 }
31
32 bench.iter(|| {
33 let _scores = bellman_ford(&g, nodes[0]);
34 });
35 }
36
37 #[bench]
find_negative_cycle_bench(bench: &mut Bencher)38 fn find_negative_cycle_bench(bench: &mut Bencher) {
39 static NODE_COUNT: usize = 100;
40 let mut g = Graph::new();
41 let nodes: Vec<NodeIndex<_>> = (0..NODE_COUNT).map(|i| g.add_node(i)).collect();
42 for i in 0..NODE_COUNT {
43 let n1 = nodes[i];
44 let neighbour_count = i % 8 + 3;
45 let j_from = max(0, i as i32 - neighbour_count as i32 / 2) as usize;
46 let j_to = min(NODE_COUNT, j_from + neighbour_count);
47 for j in j_from..j_to {
48 let n2 = nodes[j];
49 let mut distance: f64 = ((i + 3) % 10) as f64;
50 if n1 != n2 {
51 distance -= 1.0
52 }
53 g.add_edge(n1, n2, distance);
54 }
55 }
56
57 bench.iter(|| {
58 let _scores = find_negative_cycle(&g, nodes[0]);
59 });
60 }
61