problemreductions/topology/
graph.rs

1//! Graph trait and SimpleGraph implementation.
2//!
3//! This module provides a `Graph` trait that abstracts over different graph
4//! representations, following Julia's Graphs.jl `AbstractGraph` pattern.
5//!
6//! Supported graph types:
7//! - [`SimpleGraph`]: Standard unweighted graph (wrapper around petgraph)
8//! - [`UnitDiskGraph`]: Vertices with 2D positions, edges based on distance
9//! - [`HyperGraph`]: Edges can connect any number of vertices (via adapter)
10
11use petgraph::graph::{NodeIndex, UnGraph};
12use petgraph::visit::EdgeRef;
13use serde::{Deserialize, Serialize};
14
15/// Trait for graph types, following Julia's Graphs.jl AbstractGraph pattern.
16///
17/// This trait abstracts over different graph representations, allowing
18/// problems to be generic over the underlying graph type.
19///
20/// # Example
21///
22/// ```rust,ignore
23/// use problemreductions::topology::{Graph, SimpleGraph};
24///
25/// fn count_triangles<G: Graph>(graph: &G) -> usize {
26///     let mut count = 0;
27///     for u in 0..graph.num_vertices() {
28///         for v in graph.neighbors(u) {
29///             if v > u {
30///                 for w in graph.neighbors(v) {
31///                     if w > v && graph.has_edge(u, w) {
32///                         count += 1;
33///                     }
34///                 }
35///             }
36///         }
37///     }
38///     count
39/// }
40/// ```
41pub trait Graph: Clone + Send + Sync + 'static {
42    /// The name of the graph type (e.g., "SimpleGraph", "KingsSubgraph").
43    const NAME: &'static str;
44
45    /// Returns the number of vertices in the graph.
46    fn num_vertices(&self) -> usize;
47
48    /// Returns the number of edges in the graph.
49    fn num_edges(&self) -> usize;
50
51    /// Returns all edges as a list of (u, v) pairs.
52    ///
53    /// For undirected graphs, each edge appears once with u < v.
54    fn edges(&self) -> Vec<(usize, usize)>;
55
56    /// Checks if an edge exists between vertices u and v.
57    fn has_edge(&self, u: usize, v: usize) -> bool;
58
59    /// Returns all neighbors of vertex v.
60    fn neighbors(&self, v: usize) -> Vec<usize>;
61
62    /// Returns the degree of vertex v (number of neighbors).
63    fn degree(&self, v: usize) -> usize {
64        self.neighbors(v).len()
65    }
66
67    /// Returns true if the graph has no vertices.
68    fn is_empty(&self) -> bool {
69        self.num_vertices() == 0
70    }
71
72    /// Iterates over all edges, calling a closure for each.
73    ///
74    /// This can be more efficient than `edges()` when you don't need to collect.
75    fn for_each_edge<F>(&self, mut f: F)
76    where
77        F: FnMut(usize, usize),
78    {
79        for (u, v) in self.edges() {
80            f(u, v);
81        }
82    }
83}
84
85/// A simple unweighted undirected graph.
86///
87/// This is the default graph type for most problems. It wraps petgraph's
88/// `UnGraph` and implements the `Graph` trait.
89///
90/// # Example
91///
92/// ```
93/// use problemreductions::topology::SimpleGraph;
94/// use problemreductions::topology::Graph;
95///
96/// let graph = SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]);
97/// assert_eq!(graph.num_vertices(), 4);
98/// assert_eq!(graph.num_edges(), 3);
99/// assert!(graph.has_edge(0, 1));
100/// assert!(!graph.has_edge(0, 2));
101/// ```
102#[derive(Debug, Clone)]
103pub struct SimpleGraph {
104    inner: UnGraph<(), ()>,
105}
106
107impl SimpleGraph {
108    /// Creates a new graph with the given vertices and edges.
109    ///
110    /// # Arguments
111    ///
112    /// * `num_vertices` - Number of vertices in the graph
113    /// * `edges` - List of edges as (u, v) pairs
114    ///
115    /// # Panics
116    ///
117    /// Panics if any edge references a vertex index >= num_vertices.
118    pub fn new(num_vertices: usize, edges: Vec<(usize, usize)>) -> Self {
119        Self::try_new(num_vertices, edges).unwrap_or_else(|error| panic!("{error}"))
120    }
121
122    fn try_new(
123        num_vertices: usize,
124        edges: Vec<(usize, usize)>,
125    ) -> Result<Self, crate::registry::ConstructionError> {
126        let mut inner = UnGraph::new_undirected();
127        for _ in 0..num_vertices {
128            inner.add_node(());
129        }
130        for (u, v) in edges {
131            if !(u < num_vertices && v < num_vertices) {
132                return Err(format!(
133                    "edge ({}, {}) references vertex >= num_vertices ({})",
134                    u, v, num_vertices
135                )
136                .into());
137            }
138            inner.add_edge(NodeIndex::new(u), NodeIndex::new(v), ());
139        }
140        Ok(Self { inner })
141    }
142
143    /// Creates an empty graph with the given number of vertices.
144    pub fn empty(num_vertices: usize) -> Self {
145        Self::new(num_vertices, vec![])
146    }
147
148    /// Creates a complete graph (all vertices connected).
149    pub fn complete(num_vertices: usize) -> Self {
150        let mut edges = Vec::new();
151        for i in 0..num_vertices {
152            for j in (i + 1)..num_vertices {
153                edges.push((i, j));
154            }
155        }
156        Self::new(num_vertices, edges)
157    }
158
159    /// Creates a path graph (0-1-2-...-n).
160    pub fn path(num_vertices: usize) -> Self {
161        let edges: Vec<_> = (0..num_vertices.saturating_sub(1))
162            .map(|i| (i, i + 1))
163            .collect();
164        Self::new(num_vertices, edges)
165    }
166
167    /// Creates a cycle graph (0-1-2-...-n-0).
168    pub fn cycle(num_vertices: usize) -> Self {
169        if num_vertices < 3 {
170            return Self::path(num_vertices);
171        }
172        let mut edges: Vec<_> = (0..num_vertices - 1).map(|i| (i, i + 1)).collect();
173        edges.push((num_vertices - 1, 0));
174        Self::new(num_vertices, edges)
175    }
176
177    /// Creates a star graph (vertex 0 connected to all others).
178    pub fn star(num_vertices: usize) -> Self {
179        let edges: Vec<_> = (1..num_vertices).map(|i| (0, i)).collect();
180        Self::new(num_vertices, edges)
181    }
182
183    /// Creates a grid graph with the given dimensions.
184    ///
185    /// Vertices are numbered row by row: vertex `r * cols + c` is at row `r`, column `c`.
186    pub fn grid(rows: usize, cols: usize) -> Self {
187        let num_vertices = rows * cols;
188        let mut edges = Vec::new();
189
190        for r in 0..rows {
191            for c in 0..cols {
192                let v = r * cols + c;
193                // Right neighbor
194                if c + 1 < cols {
195                    edges.push((v, v + 1));
196                }
197                // Down neighbor
198                if r + 1 < rows {
199                    edges.push((v, v + cols));
200                }
201            }
202        }
203
204        Self::new(num_vertices, edges)
205    }
206}
207
208impl Graph for SimpleGraph {
209    const NAME: &'static str = "SimpleGraph";
210
211    fn num_vertices(&self) -> usize {
212        self.inner.node_count()
213    }
214
215    fn num_edges(&self) -> usize {
216        self.inner.edge_count()
217    }
218
219    fn edges(&self) -> Vec<(usize, usize)> {
220        self.inner
221            .edge_references()
222            .map(|e| (e.source().index(), e.target().index()))
223            .collect()
224    }
225
226    fn has_edge(&self, u: usize, v: usize) -> bool {
227        self.inner
228            .find_edge(NodeIndex::new(u), NodeIndex::new(v))
229            .is_some()
230    }
231
232    fn neighbors(&self, v: usize) -> Vec<usize> {
233        self.inner
234            .neighbors(NodeIndex::new(v))
235            .map(|n| n.index())
236            .collect()
237    }
238}
239
240impl PartialEq for SimpleGraph {
241    fn eq(&self, other: &Self) -> bool {
242        if self.num_vertices() != other.num_vertices() {
243            return false;
244        }
245        if self.num_edges() != other.num_edges() {
246            return false;
247        }
248        // Check all edges exist in both
249        let mut self_edges: Vec<_> = self.edges();
250        let mut other_edges: Vec<_> = other.edges();
251        // Normalize edge order
252        for e in &mut self_edges {
253            if e.0 > e.1 {
254                *e = (e.1, e.0);
255            }
256        }
257        for e in &mut other_edges {
258            if e.0 > e.1 {
259                *e = (e.1, e.0);
260            }
261        }
262        self_edges.sort();
263        other_edges.sort();
264        self_edges == other_edges
265    }
266}
267
268impl Eq for SimpleGraph {}
269
270impl Serialize for SimpleGraph {
271    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
272        use serde::ser::SerializeStruct;
273        let mut state = serializer.serialize_struct("SimpleGraph", 2)?;
274        state.serialize_field("num_vertices", &self.num_vertices())?;
275        let edges: Vec<(usize, usize)> = self.edges();
276        state.serialize_field("edges", &edges)?;
277        state.end()
278    }
279}
280
281impl<'de> Deserialize<'de> for SimpleGraph {
282    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
283        #[derive(Deserialize)]
284        struct GraphData {
285            num_vertices: usize,
286            edges: Vec<(usize, usize)>,
287        }
288        let data = GraphData::deserialize(deserializer)?;
289        SimpleGraph::try_new(data.num_vertices, data.edges).map_err(serde::de::Error::custom)
290    }
291}
292
293use crate::impl_variant_param;
294impl_variant_param!(SimpleGraph, "graph");
295
296#[cfg(test)]
297#[path = "../unit_tests/topology/graph.rs"]
298mod tests;
problemreductions/topology/graph.rs

problemreductions/topology/
graph.rs
