graph_api_test/
fuzz.rs

1use graph_api_lib::Graph;
2use graph_api_lib::{EdgeReference, EdgeSearch};
3use proptest::prelude::*;
4use std::collections::HashSet;
5
6#[derive(Debug, Clone)]
7pub enum GraphOperation {
8    AddVertex(u32),
9    RemoveVertex(usize),
10    AddEdge(usize, usize),
11    RemoveEdge(usize),
12}
13
14prop_compose! {
15    pub fn arb_graph_operation()(
16        op_type in 0..4u8,
17        vertex_weight in any::<u32>(),
18        index in any::<usize>(),
19        from_idx in any::<usize>(),
20        to_idx in any::<usize>(),
21    ) -> GraphOperation {
22        match op_type {
23            0 => GraphOperation::AddVertex(vertex_weight),
24            1 => GraphOperation::RemoveVertex(index),
25            2 => GraphOperation::AddEdge(from_idx, to_idx),
26            _ => GraphOperation::RemoveEdge(index),
27        }
28    }
29}
30
31pub fn test_fuzz(
32    mut graph: impl Graph<Vertex = u32, Edge = ()>,
33    operations: Vec<GraphOperation>,
34) -> bool {
35    let mut vertex_ids = HashSet::new();
36    let mut edge_ids = HashSet::new();
37
38    for op in operations {
39        match op {
40            GraphOperation::AddVertex(weight) => {
41                let id = graph.add_vertex(weight);
42                vertex_ids.insert(id);
43            }
44            GraphOperation::RemoveVertex(idx) => {
45                if let Some(id) = vertex_ids.iter().nth(idx % (vertex_ids.len() + 1)).cloned() {
46                    //println!("Removing vertex: {:?}", id);
47                    // First find all edges connected to this vertex
48                    let connected_edges: HashSet<_> = edge_ids
49                        .iter()
50                        .filter(|&&edge_id| {
51                            let edge = graph.edge(edge_id).unwrap();
52                            let head = edge.head();
53                            let tail = edge.tail();
54                            head == id || tail == id
55                        })
56                        .cloned()
57                        .collect();
58
59                    // Remove the vertex
60                    graph.remove_vertex(id);
61                    vertex_ids.remove(&id);
62
63                    // Remove all connected edges from our tracking set
64                    edge_ids = &edge_ids - &connected_edges;
65                }
66            }
67            GraphOperation::AddEdge(from_idx, to_idx) => {
68                let vertices: Vec<_> = vertex_ids.iter().collect();
69                if vertices.len() >= 2 {
70                    let from = vertices[from_idx % vertices.len()];
71                    let to = vertices[to_idx % vertices.len()];
72                    let edge_id = graph.add_edge(*from, *to, ());
73                    edge_ids.insert(edge_id);
74                }
75            }
76            GraphOperation::RemoveEdge(idx) => {
77                if let Some(id) = edge_ids.iter().nth(idx % (edge_ids.len() + 1)).cloned() {
78                    //println!("Removing edge {:?}", id);
79                    graph.remove_edge(id);
80                    edge_ids.remove(&id);
81                }
82            }
83        }
84
85        // Validate no dangling edges
86        for edge_id in &edge_ids {
87            let edge = graph.edge(*edge_id).expect("Edge must exist");
88            assert!(vertex_ids.contains(&edge.head()));
89            assert!(vertex_ids.contains(&edge.tail()));
90        }
91
92        // Validate we can't walk to deleted elements
93        for start in &vertex_ids {
94            let reachable: HashSet<_> = graph
95                .walk()
96                .vertices_by_id([*start])
97                .edges(EdgeSearch::scan().outgoing())
98                .head()
99                .collect();
100
101            assert!(reachable.is_subset(&vertex_ids));
102        }
103    }
104    true
105}
graph_api_test/fuzz.rs

graph_api_test/
fuzz.rs
