graph_algo_ptas/data_structure/
ring_segment.rs

1//! Contains the ring_segment function
2
3use crate::data_structure::graph_dcel::{Dart, Face, GraphDCEL, Vertex};
4use std::cmp::Ordering;
5use std::collections::{HashMap, HashSet};
6use std::fmt::Debug;
7use std::hash::Hash;
8use std::marker::PhantomData;
9
10struct RingSegmentationState<
11    'g,
12    V: Vertex + Eq + Hash + Clone + Debug,
13    D: Dart + Eq + Hash + Clone + Debug,
14    F: Face + Eq + Hash + Clone + Debug,
15    VI: Iterator<Item = V>,
16    DI: Iterator<Item = D>,
17    FI: Iterator<Item = F>,
18    G: GraphDCEL<V, D, F, VI, DI, FI> + Default,
19> {
20    input_graph: &'g G,
21    output_graph: G,
22    start_vertex: V,
23    i: usize,
24    ring_map: HashMap<V, usize>,
25    ring: HashSet<V>,
26    vertexes: HashMap<V, V>,
27    darts: HashMap<D, D>,
28    faces: HashMap<F, F>,
29    stack: Vec<D>,
30    visited: HashSet<D>,
31    inner_vertex: Option<V>,
32    outer_face: Option<F>,
33    // PhantomData to make the compiler happy
34    _vi: PhantomData<VI>,
35    _di: PhantomData<DI>,
36    _fi: PhantomData<FI>,
37}
38
39impl<
40        'g,
41        V: Vertex + Eq + Hash + Clone + Debug,
42        D: Dart + Eq + Hash + Clone + Debug,
43        F: Face + Eq + Hash + Clone + Debug,
44        VI: Iterator<Item = V>,
45        DI: Iterator<Item = D>,
46        FI: Iterator<Item = F>,
47        G: GraphDCEL<V, D, F, VI, DI, FI> + Default,
48    > RingSegmentationState<'g, V, D, F, VI, DI, FI, G>
49{
50    fn init(
51        input_graph: &'g G,
52        start_vertex: V,
53        rings: Vec<HashSet<V>>,
54        i: usize,
55    ) -> RingSegmentationState<'g, V, D, F, VI, DI, FI, G> {
56        let mut output_graph = G::default();
57
58        let ring_map = rings
59            .iter()
60            .enumerate()
61            .flat_map(|(i, ring)| ring.iter().map(move |vertex| (vertex.clone(), i)))
62            .collect::<HashMap<_, _>>();
63        let ring = rings.get(i).cloned().unwrap_or_default();
64        let vertexes = HashMap::new();
65        let darts = HashMap::new();
66        let faces = HashMap::new();
67
68        let inner_rings_not_empty = rings
69            .iter()
70            .take(i)
71            .collect::<Vec<_>>()
72            .iter()
73            .any(|ring| !ring.is_empty());
74        let inner_vertex = if inner_rings_not_empty {
75            Some(output_graph.add_vertex())
76        } else {
77            None
78        };
79        let outer_face: Option<F> = None;
80
81        let stack: Vec<D> = Vec::new();
82        let visited = HashSet::new();
83
84        RingSegmentationState {
85            input_graph,
86            output_graph,
87            start_vertex,
88            i,
89            ring_map,
90            ring,
91            vertexes,
92            darts,
93            faces,
94            stack,
95            visited,
96            inner_vertex,
97            outer_face,
98            _vi: Default::default(),
99            _di: Default::default(),
100            _fi: Default::default(),
101        }
102    }
103
104    fn dfs(&mut self) {
105        let mut current_dart = self.input_graph.dart_vertex(&self.start_vertex);
106
107        loop {
108            self.visit(&current_dart);
109
110            self.visited.insert(current_dart.clone());
111            self.stack.push(current_dart.clone());
112
113            current_dart = self.input_graph.next(&current_dart);
114            while self.visited.contains(&current_dart) {
115                let mut potential_dart = current_dart.clone();
116                while {
117                    potential_dart = self
118                        .input_graph
119                        .next(&self.input_graph.twin(&potential_dart));
120                    self.visited.contains(&potential_dart) && potential_dart != current_dart
121                } {}
122
123                current_dart = if !self.visited.contains(&potential_dart) {
124                    potential_dart
125                } else {
126                    match self.stack.pop() {
127                        Some(dart) => dart,
128                        None => return,
129                    }
130                }
131            }
132        }
133    }
134
135    fn visit(&mut self, current_dart: &D) {
136        let input_twin = self.input_graph.twin(current_dart);
137        let input_current_vertex = self.input_graph.dart_target(&input_twin);
138
139        let current_vertex = self.get_vertex(input_current_vertex);
140        if let Some(current_vertex) = current_vertex {
141            let input_target_vertex = self.input_graph.dart_target(current_dart);
142            let target_vertex_option = self.get_vertex(input_target_vertex);
143
144            if let Some(target_vertex) = target_vertex_option {
145                if target_vertex == current_vertex {
146                    return;
147                }
148                let (input_prev, prev_skipped) =
149                    self.get_first_dart_in_ring(current_dart, Mode::Prev);
150                let (input_next, next_skipped) =
151                    self.get_first_dart_in_ring(current_dart, Mode::Next);
152                let skipped = prev_skipped || next_skipped;
153
154                let prev = self.darts.get(&input_prev).cloned();
155                let next = self.darts.get(&input_next).cloned();
156                let twin = self
157                    .darts
158                    .get(&self.input_graph.twin(current_dart))
159                    .cloned();
160                let face = if !skipped {
161                    self.faces
162                        .get(&self.input_graph.face(current_dart))
163                        .cloned()
164                } else {
165                    self.outer_face.clone()
166                };
167
168                let new_dart = self.output_graph.add_dart(
169                    current_vertex,
170                    target_vertex,
171                    prev,
172                    next,
173                    twin,
174                    face.clone(),
175                );
176
177                if face.is_none() {
178                    if !skipped {
179                        self.faces.insert(
180                            self.input_graph.face(current_dart),
181                            self.output_graph.add_face(new_dart.clone()),
182                        );
183                    } else {
184                        self.outer_face = Some(self.output_graph.add_face(new_dart.clone()));
185                    }
186                }
187
188                self.darts.insert(current_dart.clone(), new_dart);
189            }
190        }
191    }
192
193    fn get_vertex(&mut self, vertex: V) -> Option<V> {
194        let ring_of_vertex = *self.ring_map.get(&vertex).unwrap();
195        match ring_of_vertex.cmp(&self.i) {
196            Ordering::Equal => Some(
197                self.vertexes
198                    .entry(vertex)
199                    .or_insert_with(|| self.output_graph.add_vertex())
200                    .clone(),
201            ),
202            Ordering::Less => Some(
203                self.vertexes
204                    .entry(vertex)
205                    .or_insert_with(|| self.inner_vertex.clone().unwrap())
206                    .clone(),
207            ),
208            Ordering::Greater => None,
209        }
210    }
211
212    fn in_or_below_i_ring(&self, vertex: &V) -> bool {
213        self.ring_map.get(vertex).unwrap() <= &self.i
214    }
215
216    fn get_first_dart_in_ring(&self, dart: &D, mode: Mode) -> (D, bool) {
217        let mut dart_skipped = false;
218        let mut next_dart = dart.clone();
219
220        loop {
221            next_dart = match mode {
222                Mode::Next => GraphDCEL::next,
223                Mode::Prev => GraphDCEL::prev,
224            }(self.input_graph, &next_dart);
225            let vertex = match mode {
226                Mode::Next => GraphDCEL::dart_target,
227                Mode::Prev => |graph: &G, dart: &D| graph.dart_target(&graph.prev(dart)),
228            }(self.input_graph, &next_dart);
229            if self.in_or_below_i_ring(&vertex) {
230                return (next_dart, dart_skipped);
231            }
232            dart_skipped = true;
233            next_dart = self.input_graph.twin(&next_dart)
234        }
235    }
236
237    fn get_outer_face(&mut self, dart: &D) -> F {
238        match &self.outer_face {
239            Some(outer_face) => outer_face.clone(),
240            None => {
241                let new_face = self.output_graph.add_face(dart.clone());
242                self.outer_face = Some(new_face.clone());
243                new_face
244            }
245        }
246    }
247}
248
249#[derive(Debug)]
250enum Mode {
251    Next,
252    Prev,
253}
254
255/// Returns a tuple which contains new graph containing the nodes of ring `i` and the nodes less then `i` combined in a single node and the combined node.
256pub fn ring_segment<
257    V: Vertex + Eq + Hash + Clone + Debug,
258    D: Dart + Eq + Hash + Clone + Debug,
259    F: Face + Eq + Hash + Clone + Debug,
260    VI: Iterator<Item = V>,
261    DI: Iterator<Item = D>,
262    FI: Iterator<Item = F>,
263    G: GraphDCEL<V, D, F, VI, DI, FI> + Default,
264>(
265    input_graph: &G,
266    start_vertex: V,
267    rings: Vec<HashSet<V>>,
268    i: usize,
269) -> (G, Option<V>, Option<V>) {
270    let mut state = RingSegmentationState::init(input_graph, start_vertex, rings, i);
271    state.dfs();
272    let new_start_vertex = state.vertexes.get(&state.start_vertex).cloned();
273    (state.output_graph, new_start_vertex, state.inner_vertex)
274}
275
276#[cfg(test)]
277mod test {
278    use crate::data_structure::graph_dcel::GraphDCEL;
279    use crate::data_structure::link_graph::example::three_ring_graph;
280    use crate::data_structure::link_graph::{LinkDart, LinkGraph, LinkVertex};
281    use crate::data_structure::ring_segment::ring_segment;
282    use std::collections::HashSet;
283
284    fn get_ring_graph() -> (LinkGraph, LinkVertex, Vec<HashSet<LinkVertex>>) {
285        let (graph, vertexes, _darts) = three_ring_graph();
286        let ring_one: HashSet<_> = [vertexes[0].clone()].into_iter().collect();
287        let ring_two: HashSet<_> = [
288            vertexes[1].clone(),
289            vertexes[2].clone(),
290            vertexes[3].clone(),
291            vertexes[4].clone(),
292        ]
293        .into_iter()
294        .collect();
295        let ring_three: HashSet<_> = [
296            vertexes[5].clone(),
297            vertexes[6].clone(),
298            vertexes[7].clone(),
299            vertexes[8].clone(),
300            vertexes[9].clone(),
301            vertexes[10].clone(),
302            vertexes[11].clone(),
303            vertexes[12].clone(),
304        ]
305        .into_iter()
306        .collect();
307        let rings = vec![ring_one, ring_two, ring_three];
308        (graph, vertexes[0].clone(), rings)
309    }
310
311    fn ensure_is_ring_of_length(graph: &LinkGraph, dart: LinkDart, length: usize) {
312        let mut current_dart = dart.clone();
313        let start_face = graph.face(&current_dart);
314        for _ in 0..length {
315            let last_dart = current_dart;
316            current_dart = graph.next(&last_dart);
317            if current_dart == last_dart {
318                panic!("one loop detected");
319            }
320            let face = graph.face(&current_dart);
321            if face != start_face {
322                panic!("invalid faces");
323            }
324        }
325        assert_eq!(current_dart, dart);
326    }
327
328    #[test]
329    fn test_ring_one() {
330        let (graph, start_vertex, rings) = get_ring_graph();
331        let (segmented, start_vertex, inner_vertex) = ring_segment(&graph, start_vertex, rings, 0);
332        assert_ne!(start_vertex, inner_vertex);
333        assert_eq!(segmented.vertex_count(), 1);
334        assert_eq!(segmented.edge_count(), 0);
335        assert!(inner_vertex.is_none());
336    }
337
338    #[test]
339    fn test_ring_two() {
340        let (graph, start_vertex, rings) = get_ring_graph();
341        let (segmented, start_vertex, inner_vertex) = ring_segment(&graph, start_vertex, rings, 1);
342        assert_eq!(segmented.vertex_count(), 5);
343        assert_eq!(segmented.edge_count(), 8);
344        assert_eq!(start_vertex, inner_vertex);
345        assert!(inner_vertex.is_some());
346    }
347
348    #[test]
349    fn test_ring_two_inner_darts() {
350        let (graph, start_vertex, rings) = get_ring_graph();
351        let (segmented, start_vertex, _inner_vertex) = ring_segment(&graph, start_vertex, rings, 1);
352        let inner_dart = segmented.dart_vertex(&start_vertex.unwrap());
353        ensure_is_ring_of_length(&segmented, inner_dart, 3);
354    }
355
356    #[test]
357    fn test_ring_two_outer_darts() {
358        let (graph, start_vertex, rings) = get_ring_graph();
359        let (segmented, start_vertex, _inner_vertex) = ring_segment(&graph, start_vertex, rings, 1);
360        let dart_on_outer_face =
361            segmented.twin(&segmented.next(&segmented.dart_vertex(&start_vertex.unwrap())));
362        ensure_is_ring_of_length(&segmented, dart_on_outer_face, 4);
363    }
364
365    #[test]
366    fn test_ring_three() {
367        let (graph, start_vertex, rings) = get_ring_graph();
368        let (segmented, start_vertex, inner_vertex) = ring_segment(&graph, start_vertex, rings, 2);
369        assert_eq!(segmented.vertex_count(), 9);
370        assert_eq!(segmented.edge_count(), 20);
371        assert_eq!(start_vertex, inner_vertex);
372        assert!(inner_vertex.is_some());
373        let dart_on_outer_face =
374            segmented.twin(&segmented.next(&segmented.dart_vertex(&start_vertex.unwrap())));
375        ensure_is_ring_of_length(&segmented, dart_on_outer_face, 8);
376    }
377
378    #[test]
379    fn test_ring_three_inner_darts() {
380        let (graph, start_vertex, rings) = get_ring_graph();
381        let (segmented, start_vertex, _inner_vertex) = ring_segment(&graph, start_vertex, rings, 2);
382        let dart_on_inner_face = segmented.next(&segmented.dart_vertex(&start_vertex.unwrap()));
383        ensure_is_ring_of_length(&segmented, dart_on_inner_face, 3);
384    }
385
386    #[test]
387    fn test_ring_three_outer_darts() {
388        let (graph, start_vertex, rings) = get_ring_graph();
389        let (segmented, start_vertex, _inner_vertex) = ring_segment(&graph, start_vertex, rings, 2);
390        let dart_on_outer_face =
391            segmented.twin(&segmented.next(&segmented.dart_vertex(&start_vertex.unwrap())));
392        ensure_is_ring_of_length(&segmented, dart_on_outer_face, 8);
393    }
394
395    #[test]
396    fn test_ring_four() {
397        let (graph, start_vertex, rings) = get_ring_graph();
398        let (segmented, start_vertex, inner_vertex) = ring_segment(&graph, start_vertex, rings, 3);
399        assert_eq!(segmented.vertex_count(), 1);
400        assert_eq!(segmented.edge_count(), 0);
401        assert_eq!(start_vertex, inner_vertex);
402        assert!(inner_vertex.is_some());
403    }
404}
graph_algo_ptas/data_structure/ring_segment.rs

graph_algo_ptas/data_structure/
ring_segment.rs
