graph_algo_ptas/embedding/maximal_planar/
index.rs

1//! Contains the implementation of the maximal planar embedding algorithm
2
3use super::phase1::Phase1;
4use super::phase2::Phase2;
5use super::phase3::Phase3;
6use crate::data_structure::link_graph::{LinkDart, LinkFace, LinkGraph, LinkGraphIter, LinkVertex};
7use crate::embedding::index::Embedding;
8use crate::utils::convert::UndirectedGraph;
9
10/// Contains the implementation of the maximal planar embedding algorithm
11pub struct MaximalPlanar {}
12
13impl
14    Embedding<
15        LinkVertex,
16        LinkDart,
17        LinkFace,
18        LinkGraphIter<LinkVertex>,
19        LinkGraphIter<LinkDart>,
20        LinkGraphIter<LinkFace>,
21        LinkGraph,
22    > for MaximalPlanar
23{
24    fn embed(mut graph: UndirectedGraph) -> LinkGraph {
25        let graph_copy = graph.clone();
26        let mut stack = Vec::new();
27        let mut dcel = LinkGraph::new();
28        let node_count = graph.node_count();
29
30        if node_count < 3 {
31            panic!("For embedding, a graph with at least 3 nodes is required")
32        }
33
34        if node_count == 3 {
35            Phase2::new(&mut dcel).triangle_embedding();
36            return dcel;
37        }
38
39        Phase1::new(&mut graph, &mut stack).execute();
40        Phase2::new(&mut dcel).execute();
41        Phase3::new(graph, graph_copy, &mut stack, &mut dcel).execute();
42
43        dcel
44    }
45}
46
47#[cfg(test)]
48mod tests {
49    use petgraph::stable_graph::StableGraph;
50
51    use crate::data_structure::graph_dcel::GraphDCEL;
52    use crate::{
53        embedding::{index::Embedding, maximal_planar::index::MaximalPlanar},
54        generation::planar::generate,
55        utils::convert::UndirectedGraph,
56    };
57
58    fn test_embed(graph: UndirectedGraph) {
59        let dcel = MaximalPlanar::embed(graph.clone());
60
61        dcel.validate();
62        assert_eq!(
63            dcel.vertex_count(),
64            graph.node_count(),
65            "Invalid Vertex count. Expected {} got {}",
66            graph.node_count(),
67            dcel.vertex_count()
68        );
69        assert_eq!(
70            dcel.edge_count(),
71            graph.edge_count(),
72            "Invalid Edge count. Expected {} got {}",
73            graph.edge_count(),
74            dcel.edge_count(),
75        );
76    }
77
78    #[test]
79    #[should_panic]
80    fn embedd_to_small() {
81        let graph: UndirectedGraph = StableGraph::from_edges(&[(0, 1)]);
82        MaximalPlanar::embed(graph);
83    }
84
85    #[test]
86    fn embedd_triangle_graph() {
87        let graph: UndirectedGraph = StableGraph::from_edges(&[(0, 1), (0, 2), (1, 2)]);
88        test_embed(graph);
89    }
90
91    #[test]
92    fn embed_k4_graph() {
93        let graph = generate(4, Some(0)).to_pet_graph();
94        test_embed(graph)
95    }
96
97    #[test]
98    fn embed_min_graph() {
99        let graph = generate(5, Some(0)).to_pet_graph();
100        test_embed(graph)
101    }
102
103    #[test]
104    fn embed_small_graph() {
105        let graph = generate(10, Some(0)).to_pet_graph();
106        test_embed(graph)
107    }
108
109    #[test]
110    fn embed_medium_graph() {
111        let graph = generate(50, Some(0)).to_pet_graph();
112        test_embed(graph)
113    }
114
115    #[test]
116    fn embed_large_graph() {
117        let graph = generate(100, Some(0)).to_pet_graph();
118        test_embed(graph)
119    }
120}
graph_algo_ptas/embedding/maximal_planar/index.rs

graph_algo_ptas/embedding/maximal_planar/
index.rs
