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::dijkstra;
11 
12 #[bench]
dijkstra_bench(bench: &mut Bencher)13 fn dijkstra_bench(bench: &mut Bencher) {
14     static NODE_COUNT: usize = 10_000;
15     let mut g = Graph::new_undirected();
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 distance = (i + 3) % 10;
25             g.add_edge(n1, n2, distance);
26         }
27     }
28 
29     bench.iter(|| {
30         let _scores = dijkstra(&g, nodes[0], None, |e| *e.weight());
31     });
32 }
33