graph_algo_ptas/embedding/maximal_planar/
phase1.rs

1//! Implements the first phase of the algorithm.
2//! Three different reductions are applied to the graph until it has only four nodes and therefore corresponds to the K4 graph.
3//! The reductions are stored on a stack.
4
5use super::stack_item::StackItem;
6use crate::utils::convert::UndirectedGraph;
7use petgraph::graph::NodeIndex;
8use petgraph::visit::EdgeRef;
9use std::collections::BTreeSet;
10
11pub struct Phase1<'a> {
12    graph: &'a mut UndirectedGraph,
13    stack: &'a mut Vec<StackItem>,
14    reducible: BTreeSet<NodeIndex>,
15}
16
17impl Phase1<'_> {
18    pub fn new<'a>(graph: &'a mut UndirectedGraph, stack: &'a mut Vec<StackItem>) -> Phase1<'a> {
19        let mut phase1 = Phase1 {
20            graph,
21            stack,
22            reducible: Default::default(),
23        };
24
25        phase1.reducible = phase1
26            .graph
27            // TODO: remove clone?
28            .clone()
29            .node_indices()
30            .filter(|n| phase1.is_reducible(*n))
31            .collect::<BTreeSet<_>>();
32
33        phase1
34    }
35
36    pub fn execute(&mut self) {
37        while self.graph.node_count() > 4 {
38            let v = match self.reducible.iter().next() {
39                Some(v) => *v,
40                None => panic!(), // TODO: improve
41            };
42            self.reducible.remove(&v);
43            let degree = self.graph.edges(v).count();
44            let h = self.graph.neighbors(v).collect::<BTreeSet<_>>();
45
46            self.graph.clone().edges(v).for_each(|e| {
47                self.stack
48                    .push(StackItem::Edge(self.graph.edge_endpoints(e.id()).unwrap()));
49                self.graph.remove_edge(e.id());
50            });
51
52            self.graph.remove_node(v);
53            self.stack.push(StackItem::Node(v));
54
55            let new_h = h.clone();
56            let w = if degree >= 4 {
57                new_h.iter().find(|n| self.find_neighbors(&h, **n))
58            } else {
59                None
60            };
61
62            if degree >= 4 {
63                let mut x = h.clone();
64                self.graph.neighbors(*w.unwrap()).for_each(|n| {
65                    x.remove(&n);
66                });
67                x.remove(w.unwrap());
68
69                let mut xi = x.iter();
70
71                self.add_edge(*w.unwrap(), *xi.next().unwrap());
72
73                if degree == 5 {
74                    self.add_edge(*w.unwrap(), *xi.next().unwrap());
75                }
76            }
77
78            self.update_local(&h);
79            self.stack.push(StackItem::Degree(degree))
80        }
81    }
82
83    fn is_reducible(&mut self, node_idx: NodeIndex) -> bool {
84        let count = self.graph.edges(node_idx).count();
85        let small_neighbor_count = self.get_small_neighbor_count(node_idx);
86
87        count <= 3
88            || count == 4 && small_neighbor_count >= 2
89            || count == 5 && small_neighbor_count >= 4
90    }
91
92    fn get_small_neighbor_count(&mut self, node_idx: NodeIndex) -> usize {
93        self.graph
94            .neighbors(node_idx)
95            .into_iter()
96            .filter(|n| self.graph.edges(*n).count() < 18)
97            .count()
98    }
99
100    fn find_neighbors(&mut self, h: &BTreeSet<NodeIndex>, node_idx: NodeIndex) -> bool {
101        let neighbors = self.graph.neighbors(node_idx);
102        let mut count = 0;
103
104        neighbors.for_each(|n| {
105            if h.contains(&n) {
106                count += 1;
107            }
108        });
109
110        count == 2
111    }
112
113    fn update_local(&mut self, h: &BTreeSet<NodeIndex>) {
114        h.iter().for_each(|x| {
115            if self.graph.edges(*x).count() < 18
116            /* TODO: check if x was small before reduction */
117            {
118                self.update_reducible(*x);
119            }
120
121            // TODO: remove clone?
122            self.graph.clone().neighbors(*x).for_each(|n| {
123                if self.graph.edges(n).into_iter().count() <= 5 {
124                    self.update_reducible(n);
125                }
126            })
127        })
128    }
129
130    fn update_reducible(&mut self, node_idx: NodeIndex) {
131        let is_reducible = self.is_reducible(node_idx);
132
133        if is_reducible {
134            self.reducible.insert(node_idx);
135        } else {
136            self.reducible.remove(&node_idx);
137        }
138    }
139
140    fn add_edge(&mut self, a: NodeIndex, b: NodeIndex) {
141        self.graph.add_edge(a, b, ());
142        self.stack.push(StackItem::Edge((a, b)));
143    }
144}
145
146#[cfg(test)]
147mod tests {
148    use petgraph::stable_graph::StableGraph;
149
150    use crate::{embedding::maximal_planar::phase1::Phase1, utils::convert::UndirectedGraph};
151
152    fn other_graph() -> UndirectedGraph {
153        StableGraph::from_edges([
154            (0, 1),
155            (1, 2),
156            (2, 0),
157            (1, 3),
158            (2, 3),
159            (0, 4),
160            (1, 4),
161            (2, 4),
162            (3, 4),
163        ])
164    }
165
166    #[test]
167    fn phase_1() {
168        let mut graph = other_graph();
169        let mut stack = Vec::new();
170
171        Phase1::new(&mut graph, &mut stack).execute();
172
173        // TODO: test
174    }
175}
graph_algo_ptas/embedding/maximal_planar/phase1.rs

graph_algo_ptas/embedding/maximal_planar/
phase1.rs
