graphalgs 0.2.0

Graph algorithms based on the Rust 'petgraph' library.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#![allow(unused_imports)]
use criterion::measurement::WallTime;
use criterion::BenchmarkGroup;
use criterion::{black_box, criterion_group, criterion_main, Criterion};
use graphalgs::adj_matrix::unweighted;
use graphalgs::elementary_circuits::elementary_circuits;
use graphalgs::generate::{random_digraph, random_ungraph};
use graphalgs::shortest_path::{apd, floyd_warshall, seidel, shortest_distances};
use petgraph::{Directed, Graph};

#[allow(unused_must_use)]
fn run(graph: &Graph<(), f32, Directed, usize>) {
    seidel(graph);
}

fn bench_seidel(c: &mut Criterion) {
    let n = 100;
    let graph = Graph::<(), f32, Directed, usize>::from_edges(
        random_ungraph(n, n * (n - 1) / 2)
            .unwrap()
            .into_iter()
            .map(|edge| (edge.0, edge.1, 1.0)),
    );
    c.bench_function("Seidel", |b| {
        b.iter(|| {
            run(&graph);
            black_box(())
        })
    });
}

fn elementary_circuits_helper(
    group: &mut BenchmarkGroup<WallTime>,
    name: &str,
    nodes: usize,
    nedges: usize,
) {
    group.bench_function(name, |b| {
        b.iter(|| {
            let graph: Graph<(), (), Directed, usize> =
                Graph::from_edges(random_digraph(nodes, nedges).unwrap());
            let output = elementary_circuits(&graph);
            black_box(output)
        })
    });
}

fn bench_elementary_circuits(c: &mut Criterion) {
    let mut group = c.benchmark_group("ElementaryCircuits");
    group.sample_size(10);
    elementary_circuits_helper(&mut group, "ManyNodes", 10000, 5000);
    let n = 14;
    elementary_circuits_helper(&mut group, "FewNodes", n, n * n / 2);
    group.finish();
}

criterion_group!(benches, bench_seidel, bench_elementary_circuits);
criterion_main!(benches);