1 #![feature(test)]
2 
3 extern crate petgraph;
4 extern crate test;
5 
6 use test::Bencher;
7 
8 #[allow(dead_code)]
9 mod common;
10 use common::*;
11 
12 use petgraph::algo::{greedy_matching, maximum_matching};
13 use petgraph::graph::UnGraph;
14 
huge() -> UnGraph<(), ()>15 fn huge() -> UnGraph<(), ()> {
16     static NODE_COUNT: u32 = 1_000;
17 
18     let mut edges = Vec::new();
19 
20     for i in 0..NODE_COUNT {
21         for j in i..NODE_COUNT {
22             if i % 3 == 0 && j % 2 == 0 {
23                 edges.push((i, j));
24             }
25         }
26     }
27 
28     // 999 nodes, 83500 edges
29     UnGraph::from_edges(&edges)
30 }
31 
32 #[bench]
greedy_matching_bipartite(bench: &mut Bencher)33 fn greedy_matching_bipartite(bench: &mut Bencher) {
34     let g = ungraph().bipartite();
35     bench.iter(|| greedy_matching(&g));
36 }
37 
38 #[bench]
greedy_matching_full(bench: &mut Bencher)39 fn greedy_matching_full(bench: &mut Bencher) {
40     let g = ungraph().full_a();
41     bench.iter(|| greedy_matching(&g));
42 }
43 
44 #[bench]
greedy_matching_bigger(bench: &mut Bencher)45 fn greedy_matching_bigger(bench: &mut Bencher) {
46     let g = ungraph().bigger();
47     bench.iter(|| greedy_matching(&g));
48 }
49 
50 #[bench]
greedy_matching_huge(bench: &mut Bencher)51 fn greedy_matching_huge(bench: &mut Bencher) {
52     let g = huge();
53     bench.iter(|| greedy_matching(&g));
54 }
55 
56 #[bench]
maximum_matching_bipartite(bench: &mut Bencher)57 fn maximum_matching_bipartite(bench: &mut Bencher) {
58     let g = ungraph().bipartite();
59     bench.iter(|| maximum_matching(&g));
60 }
61 
62 #[bench]
maximum_matching_full(bench: &mut Bencher)63 fn maximum_matching_full(bench: &mut Bencher) {
64     let g = ungraph().full_a();
65     bench.iter(|| maximum_matching(&g));
66 }
67 
68 #[bench]
maximum_matching_bigger(bench: &mut Bencher)69 fn maximum_matching_bigger(bench: &mut Bencher) {
70     let g = ungraph().bigger();
71     bench.iter(|| maximum_matching(&g));
72 }
73 
74 #[bench]
maximum_matching_huge(bench: &mut Bencher)75 fn maximum_matching_huge(bench: &mut Bencher) {
76     let g = huge();
77     bench.iter(|| maximum_matching(&g));
78 }
79