problemreductions/topology/
planar_graph.rs

1//! Planar graph — validated wrapper around SimpleGraph.
2
3use super::graph::{Graph, SimpleGraph};
4use serde::{Deserialize, Serialize};
5
6/// Planar graph — validated wrapper around SimpleGraph.
7///
8/// Construction validates the necessary planarity condition: |E| <= 3|V| - 6 for |V| >= 3.
9/// This is a necessary but not sufficient condition.
10///
11/// # Example
12///
13/// ```
14/// use problemreductions::topology::{PlanarGraph, Graph};
15///
16/// // K4 is planar: 4 vertices, 6 edges, 6 <= 3*4 - 6 = 6
17/// let edges = vec![(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)];
18/// let g = PlanarGraph::new(4, edges);
19/// assert_eq!(g.num_vertices(), 4);
20/// assert_eq!(g.num_edges(), 6);
21/// ```
22#[derive(Debug, Clone, Serialize)]
23pub struct PlanarGraph {
24    inner: SimpleGraph,
25}
26
27impl PlanarGraph {
28    /// Create a new planar graph.
29    ///
30    /// # Panics
31    /// Panics if the graph violates the necessary planarity condition |E| <= 3|V| - 6.
32    pub fn new(num_vertices: usize, edges: Vec<(usize, usize)>) -> Self {
33        Self::from_inner(SimpleGraph::new(num_vertices, edges))
34            .unwrap_or_else(|error| panic!("{error}"))
35    }
36
37    /// Get a reference to the underlying SimpleGraph.
38    pub fn inner(&self) -> &SimpleGraph {
39        &self.inner
40    }
41    fn from_inner(inner: SimpleGraph) -> Result<Self, crate::registry::ConstructionError> {
42        let num_vertices = inner.num_vertices();
43        if num_vertices >= 3 {
44            let max_edges = 3 * (num_vertices as u128) - 6;
45            if inner.num_edges() as u128 > max_edges {
46                return Err(format!("graph has {} edges but a planar graph on {num_vertices} vertices can have at most {max_edges} edges", inner.num_edges()).into());
47            }
48        }
49        Ok(Self { inner })
50    }
51}
52
53impl<'de> Deserialize<'de> for PlanarGraph {
54    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
55        #[derive(Deserialize)]
56        struct PlanarGraphData {
57            inner: SimpleGraph,
58        }
59        let data = PlanarGraphData::deserialize(deserializer)?;
60        Self::from_inner(data.inner).map_err(serde::de::Error::custom)
61    }
62}
63
64impl Graph for PlanarGraph {
65    const NAME: &'static str = "PlanarGraph";
66
67    fn num_vertices(&self) -> usize {
68        self.inner.num_vertices()
69    }
70
71    fn num_edges(&self) -> usize {
72        self.inner.num_edges()
73    }
74
75    fn edges(&self) -> Vec<(usize, usize)> {
76        self.inner.edges()
77    }
78
79    fn has_edge(&self, u: usize, v: usize) -> bool {
80        self.inner.has_edge(u, v)
81    }
82
83    fn neighbors(&self, v: usize) -> Vec<usize> {
84        self.inner.neighbors(v)
85    }
86}
87
88use crate::impl_variant_param;
89impl_variant_param!(PlanarGraph, "graph");
90
91#[cfg(test)]
92#[path = "../unit_tests/topology/planar_graph.rs"]
93mod tests;
problemreductions/topology/planar_graph.rs

problemreductions/topology/
planar_graph.rs
