harness_space/
graph.rs

1//! Graph implementation with support for both directed and undirected graphs.
2//!
3//! This module provides a flexible graph data structure that can represent both directed
4//! and undirected graphs through a type parameter. The implementation supports basic
5//! set operations and is designed to work with the topology traits defined in the
6//! definitions module.
7
8use std::{collections::HashSet, hash::Hash, marker::PhantomData};
9
10use crate::set::Collection;
11
12/// Private module to implement the sealed trait pattern.
13/// This prevents other crates from implementing DirectedType.
14mod sealed {
15  pub trait Sealed {}
16}
17
18/// A trait to distinguish between directed and undirected graphs.
19///
20/// This trait is sealed and can only be implemented by the `Directed` and
21/// `Undirected` types provided in this module.
22pub trait DirectedType: sealed::Sealed {}
23
24/// Type marker for undirected graphs.
25#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
26pub struct Undirected;
27impl sealed::Sealed for Undirected {}
28impl DirectedType for Undirected {}
29
30/// Type marker for directed graphs.
31#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
32pub struct Directed;
33impl sealed::Sealed for Directed {}
34impl DirectedType for Directed {}
35
36/// Represents a point in a graph, which can be either a vertex or a point on an edge.
37///
38/// # Type Parameters
39/// * `V` - The type of vertex identifiers
40#[derive(Debug, Clone, PartialEq, Eq, Hash)]
41pub enum VertexOrEdge<V> {
42  /// A vertex in the graph
43  Vertex(V),
44  /// An edge between two vertices
45  Edge(V, V),
46}
47
48/// A graph data structure supporting both directed and undirected graphs.
49///
50/// # Type Parameters
51/// * `V` - The type of vertex identifiers
52/// * `D` - The directedness type (`Directed` or `Undirected`)
53///
54/// # Examples
55/// ```
56/// use std::collections::HashSet;
57/// # use harness_space::graph::{Graph, Undirected};
58///
59/// let mut vertices = HashSet::new();
60/// vertices.insert(1);
61/// vertices.insert(2);
62///
63/// let mut edges = HashSet::new();
64/// edges.insert((1, 2));
65///
66/// let graph = Graph::<usize, Undirected>::new(vertices, edges);
67/// ```
68#[derive(Debug, Clone)]
69pub struct Graph<V, D: DirectedType> {
70  /// The set of vertices in the graph
71  vertices: HashSet<V>,
72  /// The set of edges in the graph
73  edges:    HashSet<(V, V)>,
74  /// Phantom data to carry the directedness type
75  d:        PhantomData<D>,
76}
77
78impl<V: PartialOrd + Eq + Hash> Graph<V, Undirected> {
79  /// Creates a new graph with the given vertices and edges.
80  ///
81  /// For undirected graphs, edges are normalized so that the smaller vertex
82  /// (by `PartialOrd`) is always first in the pair.
83  ///
84  /// # Arguments
85  /// * `vertices` - The set of vertices in the graph
86  /// * `edges` - The set of edges in the graph
87  ///
88  /// # Panics
89  /// * If any edge references a vertex not in the vertex set
90  pub fn new(vertices: HashSet<V>, edges: HashSet<(V, V)>) -> Self {
91    let edges =
92      edges.into_iter().map(|(a, b)| if a <= b { (a, b) } else { (b, a) }).collect::<HashSet<_>>();
93
94    assert!(
95      edges.iter().all(|(a, b)| vertices.contains(a) && vertices.contains(b)),
96      "All edges must be between vertices",
97    );
98    Self { vertices, edges, d: PhantomData }
99  }
100}
101
102impl<V: PartialOrd + Eq + Hash> Graph<V, Directed> {
103  /// Creates a new graph with the given vertices and edges.
104  ///
105  /// For undirected graphs, edges are normalized so that the smaller vertex
106  /// (by `PartialOrd`) is always first in the pair.
107  ///
108  /// # Arguments
109  /// * `vertices` - The set of vertices in the graph
110  /// * `edges` - The set of edges in the graph
111  ///
112  /// # Panics
113  /// * If any edge references a vertex not in the vertex set
114  pub fn new(vertices: HashSet<V>, edges: HashSet<(V, V)>) -> Self {
115    assert!(
116      edges.iter().all(|(a, b)| vertices.contains(a) && vertices.contains(b)),
117      "All edges must be between vertices",
118    );
119    Self { vertices, edges, d: PhantomData }
120  }
121}
122
123impl<V: PartialOrd + Eq + Hash + Clone> Collection for Graph<V, Directed> {
124  type Item = VertexOrEdge<V>;
125
126  fn is_empty(&self) -> bool { self.vertices.is_empty() }
127
128  fn contains(&self, point: &Self::Item) -> bool {
129    match point {
130      VertexOrEdge::Vertex(v) => self.vertices.contains(v),
131      VertexOrEdge::Edge(u, v) => self.edges.contains(&(u.clone(), v.clone())),
132    }
133  }
134}
135
136impl<V: PartialOrd + Eq + Hash + Clone> Collection for Graph<V, Undirected> {
137  type Item = VertexOrEdge<V>;
138
139  fn is_empty(&self) -> bool { self.vertices.is_empty() }
140
141  fn contains(&self, point: &Self::Item) -> bool {
142    match point {
143      VertexOrEdge::Vertex(v) => self.vertices.contains(v),
144      VertexOrEdge::Edge(u, v) =>
145        self.edges.contains(&(u.clone(), v.clone())) | self.edges.contains(&(v.clone(), u.clone())),
146    }
147  }
148}
149
150#[cfg(test)]
151mod tests {
152  use super::*;
153
154  /// Helper function to create a test graph.
155  fn create_graph_undirected() -> Graph<usize, Undirected> {
156    let mut vertices = HashSet::new();
157    vertices.insert(1);
158    vertices.insert(2);
159    vertices.insert(3);
160    vertices.insert(4);
161    vertices.insert(5);
162
163    let mut edges = HashSet::new();
164    edges.insert((1, 2));
165    edges.insert((2, 3));
166    edges.insert((3, 4));
167
168    Graph::<usize, Undirected>::new(vertices, edges)
169  }
170
171  /// Helper function to create a test graph.
172  fn create_graph_directed() -> Graph<usize, Directed> {
173    let mut vertices = HashSet::new();
174    vertices.insert(1);
175    vertices.insert(2);
176    vertices.insert(3);
177    vertices.insert(4);
178    vertices.insert(5);
179
180    let mut edges = HashSet::new();
181    edges.insert((1, 2));
182    edges.insert((2, 3));
183    edges.insert((3, 4));
184    edges.insert((4, 5));
185
186    Graph::<usize, Directed>::new(vertices, edges)
187  }
188
189  #[test]
190  fn graph_builds_undirected() {
191    let graph = create_graph_undirected();
192    assert_eq!(graph.vertices.len(), 5);
193    assert_eq!(graph.edges.len(), 3);
194  }
195
196  #[test]
197  fn graph_builds_directed() {
198    let graph = create_graph_directed();
199    assert_eq!(graph.vertices.len(), 5);
200    assert_eq!(graph.edges.len(), 4);
201  }
202
203  #[test]
204  fn graph_contains_vertex() {
205    let graph = create_graph_undirected();
206    assert!(graph.contains(&VertexOrEdge::Vertex(1)));
207    assert!(!graph.contains(&VertexOrEdge::Vertex(6)));
208  }
209
210  #[test]
211  fn graph_contains_edge() {
212    let graph = create_graph_undirected();
213    assert!(graph.contains(&VertexOrEdge::Edge(1, 2)));
214  }
215
216  #[test]
217  fn graph_contains_edge_undirected() {
218    let graph = create_graph_undirected();
219    assert!(graph.contains(&VertexOrEdge::Edge(1, 2)));
220    assert!(graph.contains(&VertexOrEdge::Edge(2, 1)));
221  }
222
223  #[test]
224  fn graph_contains_edge_directed() {
225    let graph = create_graph_directed();
226    assert!(graph.contains(&VertexOrEdge::Edge(1, 2)));
227    assert!(!graph.contains(&VertexOrEdge::Edge(2, 1)));
228  }
229}
harness_space/graph.rs

harness_space/
graph.rs
