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, Deserialize)]
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        let inner = SimpleGraph::new(num_vertices, edges);
34        if num_vertices >= 3 {
35            let max_edges = 3 * num_vertices - 6;
36            assert!(
37                inner.num_edges() <= max_edges,
38                "graph has {} edges but a planar graph on {} vertices can have at most {} edges",
39                inner.num_edges(),
40                num_vertices,
41                max_edges
42            );
43        }
44        Self { inner }
45    }
46
47    /// Get a reference to the underlying SimpleGraph.
48    pub fn inner(&self) -> &SimpleGraph {
49        &self.inner
50    }
51}
52
53impl Graph for PlanarGraph {
54    const NAME: &'static str = "PlanarGraph";
55
56    fn num_vertices(&self) -> usize {
57        self.inner.num_vertices()
58    }
59
60    fn num_edges(&self) -> usize {
61        self.inner.num_edges()
62    }
63
64    fn edges(&self) -> Vec<(usize, usize)> {
65        self.inner.edges()
66    }
67
68    fn has_edge(&self, u: usize, v: usize) -> bool {
69        self.inner.has_edge(u, v)
70    }
71
72    fn neighbors(&self, v: usize) -> Vec<usize> {
73        self.inner.neighbors(v)
74    }
75}
76
77use crate::impl_variant_param;
78impl_variant_param!(PlanarGraph, "graph", parent: SimpleGraph,
79    cast: |g| g.inner.clone());
80
81#[cfg(test)]
82#[path = "../unit_tests/topology/planar_graph.rs"]
83mod tests;
problemreductions/topology/planar_graph.rs

problemreductions/topology/
planar_graph.rs
