graph_api_test/
fuzz.rs

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

graph_api_test/
fuzz.rs
