graph_api_benches/
traversal.rs

1use crate::generators::{GraphSize, generate_social_graph, generate_test_graph};
2
3use criterion::{BenchmarkGroup, Throughput, measurement::WallTime};
4use graph_api_lib::{EdgeSearch, Graph, VertexReference};
5use graph_api_test::{Edge, EdgeExt, Person, Vertex, VertexExt};
6
7/// Run all traversal operation benchmarks
8pub fn run_benchmarks<G: Graph<Vertex = Vertex, Edge = Edge>>(
9    group: &mut BenchmarkGroup<WallTime>,
10    setup: impl Fn() -> G + Clone,
11) {
12    bench_traversal_outgoing(group, setup.clone());
13    bench_traversal_incoming(group, setup.clone());
14    bench_traversal_filtered(group, setup.clone());
15    bench_traversal_complex(group, setup.clone());
16    bench_traversal_deep(group, setup.clone());
17}
18
19/// Benchmark basic outgoing traversal
20fn bench_traversal_outgoing<G: Graph<Vertex = Vertex, Edge = Edge>>(
21    group: &mut BenchmarkGroup<WallTime>,
22    setup: impl Fn() -> G + Clone,
23) {
24    group.throughput(Throughput::Elements(1));
25    group.bench_function("traversal_outgoing", |b| {
26        // Setup: Create graph with test data
27        let mut graph = setup();
28        let refs = generate_test_graph(&mut graph);
29
30        b.iter(|| {
31            graph
32                .walk()
33                .vertices_by_id(vec![refs.bryn])
34                .edges(EdgeSearch::scan().outgoing())
35                .head()
36                .collect::<Vec<_>>()
37        })
38    });
39}
40
41/// Benchmark incoming traversal
42fn bench_traversal_incoming<G: Graph<Vertex = Vertex, Edge = Edge>>(
43    group: &mut BenchmarkGroup<WallTime>,
44    setup: impl Fn() -> G + Clone,
45) {
46    group.throughput(Throughput::Elements(1));
47    group.bench_function("traversal_incoming", |b| {
48        // Setup: Create graph with test data
49        let mut graph = setup();
50        let refs = generate_test_graph(&mut graph);
51
52        b.iter(|| {
53            graph
54                .walk()
55                .vertices_by_id(vec![refs.bryn])
56                .edges(EdgeSearch::scan().incoming())
57                .head()
58                .collect::<Vec<_>>()
59        })
60    });
61}
62
63/// Benchmark filtered traversal
64fn bench_traversal_filtered<G: Graph<Vertex = Vertex, Edge = Edge>>(
65    group: &mut BenchmarkGroup<WallTime>,
66    setup: impl Fn() -> G + Clone,
67) {
68    group.throughput(Throughput::Elements(1));
69    group.bench_function("traversal_filtered", |b| {
70        // Setup: Create graph with test data
71        let mut graph = setup();
72        let refs = generate_test_graph(&mut graph);
73
74        b.iter(|| {
75            graph
76                .walk()
77                .vertices_by_id(vec![refs.bryn])
78                .filter_by_person(|_, _| true)
79                .edges(EdgeSearch::scan().outgoing())
80                .filter_by_knows(|_, _| true)
81                .head()
82                .collect::<Vec<_>>()
83        })
84    });
85}
86
87/// Benchmark complex traversal combining multiple operations
88fn bench_traversal_complex<G: Graph<Vertex = Vertex, Edge = Edge>>(
89    group: &mut BenchmarkGroup<WallTime>,
90    setup: impl Fn() -> G + Clone,
91) {
92    group.throughput(Throughput::Elements(1));
93    group.bench_function("traversal_complex", |b| {
94        // Setup: Create graph with test data
95        let mut graph = setup();
96        let refs = generate_test_graph(&mut graph);
97
98        b.iter(|| {
99            graph
100                .walk()
101                .vertices_by_id(vec![refs.bryn])
102                .filter_by_person(|v, _| v.age() > 40)
103                .push_context(|v, _ctx| v.project::<Person<_>>().unwrap().age())
104                .edges(EdgeSearch::scan().outgoing())
105                .take(5)
106                .head()
107                .collect::<Vec<_>>()
108        })
109    });
110}
111
112/// Benchmark deep traversal (multiple hops)
113fn bench_traversal_deep<G: Graph<Vertex = Vertex, Edge = Edge>>(
114    group: &mut BenchmarkGroup<WallTime>,
115    setup: impl Fn() -> G + Clone,
116) {
117    group.throughput(Throughput::Elements(1));
118    group.bench_function("traversal_deep", |b| {
119        // Setup: Create a bigger graph for this test
120        let mut graph = setup();
121        let vertex_ids = generate_social_graph(&mut graph, GraphSize::Small, 42);
122        let start_id = vertex_ids[0]; // Start with the first vertex
123
124        b.iter(|| {
125            // Friends of friends (2 hops)
126            graph
127                .walk()
128                .vertices_by_id(vec![start_id])
129                .edges(EdgeSearch::scan().outgoing())
130                .head()
131                .edges(EdgeSearch::scan().outgoing())
132                .head()
133                .collect::<Vec<_>>()
134        })
135    });
136}
graph_api_benches/traversal.rs

graph_api_benches/
traversal.rs
